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.


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.


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

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.

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)

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.

Same to isomorphism

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

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.

Tolerance relation

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

provides some references.

that's it! Thanks

Tolerance relation