Home » forums » LtU Forum

Do you happen to hear about pre-equivalence?

Dear all,

I am wondering whether it is appropriate to ask a naive technique question here,

Let's define the pre-equivalence relation as a relation which has the propriety
1) symmetry 2) reflexivity.
(Attention, the transitivity is not guaranteed)

Do you happen to know some theory/paper that has a detailed study to this structure? It is for me interesting because I am working on an abstract interpretation of sequences of pre=equivalence relation over a finite set.

Thanks for all your ideas.

Zell

By zell08v at 2010-10-28 10:00 | LtU Forum | previous forum topic | next forum topic | other blogs | 5627 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

What you have is basically

What you have is basically an undirected graph. http://en.wikipedia.org/wiki/Graph_theory

By Jules Jacobs at Thu, 2010-10-28 13:59 | login or register to post comments

Reflexive

A graph isn't necessarily reflexive and if I remember right some kinds of graph are precluded from having self loops.

By James Iry at Thu, 2010-10-28 15:00 | login or register to post comments

Graphs where every node has

Graphs where every node has a self loop attached are the same as graphs without self loops, just like graphs that are drawn with a blue pen are the same as graphs drawn with a red pen. The properties of these two structures are essentially the same.

By Jules Jacobs at Thu, 2010-10-28 15:06 | login or register to post comments

Not graphical

A graph is a set of vertices and a collection of edges (which may be a set or a multi-set). Saying that the edge (multi)set always includes self loops is a different structure from saying that it never does or even sometimes does.

See Simple Graph for a kind of graph that explicitly precludes self loops.

"In a simple graph the edges of the graph form a set (rather than a multiset) and each edge is a pair of distinct vertices."

(Emphasis mine)

By James Iry at Thu, 2010-10-28 15:29 | login or register to post comments

Sure, they are not exactly

Sure, they are not exactly the same, but there is no interesting difference between them. I'm saying that if you want to know more about this structure, graph theory is exactly the place to look. A structure that *sometimes* has self loops *is* different, however.

Suppose that we take the natural numbers, and give each natural number a property whizzbang, which always has the value flitzpop. Do we now have a different thing than natural numbers? Sure. Is the difference interesing? No.

By Jules Jacobs at Thu, 2010-10-28 15:35 | login or register to post comments

Same to isomorphism

Okay, I see what you mean, there's an isomorphism between a totally non-reflexive graph and a totally reflexive graph.

By James Iry at Thu, 2010-10-28 15:38 | login or register to post comments

Yes, exactly. So the OP is

Yes, exactly. So the OP is lucky because everything there is hope to learn about his structure is very likely already known in the context of graph theory.

By Jules Jacobs at Thu, 2010-10-28 15:44 | login or register to post comments

Tolerance relation

The standard term for a relation that is reflexive and symmetric is ``tolerance''. The wikipedia page at

http://en.wikipedia.org/wiki/Tolerance_relation

provides some references.

By jack at Thu, 2010-10-28 14:54 | login or register to post comments

that's it! Thanks

Tolerance relation

By zell08v at Thu, 2010-10-28 22:51 | login or register to post comments