9
$\begingroup$

Im looking for a reference that characterizes when an equivalence relation can be generated from a relation and gives a clear explanation of it.

2 Answers 2

8

Recall that the equivalence relation generated by a relation is the smallest equivalence relation containing it. Equivalently, the equivalence relation $S$ generated by a relation $R$ is such that $(x,y)$ is in $S$ if and only if there exist $n\geqslant0$ and $(x_k)_{0\leqslant k\leqslant n}$ such that $x= x_0$, $y = x_n$, and for every $1\leqslant k\leqslant n$, either $(x_{k-1},x_{k})$ or $(x_{k},x_{k-1})$ belongs to $R$.

Since every equivalence relation is generated by itself, for every equivalence relation there exists a relation generating it.

To get $R\subseteq S$ generating $S$, one can erase from $S$ some or all of the following: (1) every $(x,x)$, (2) either $(x,y)$ or $(y,x)$ for every $x\ne y$ such that $(x,y)$ is in $S$, (3) every $(x,y)$ such that $(x,z)$ and $(z,y)$ are in $S$ for some $z\ne x,y$.

  • 0
    Thanks for the answer, I would still prefer a reference though as I don't want to go through all the "rigorous" details by myself and just cite a reference (preferably not wikipedia). One thing is missing is the following: Why is S generated by the relation explained in the second sentence of your first paragraph the smallest such equivalence relation? How did the characterization came to be? Im sure those are easy to prove but I don't want to go through it myself if they can be found somewhere else.2011-11-20
  • 0
    Any equivalence relation containing R is stable by reflexivity, symmetry and transitivity hence it must contain every such (x,y). On the other hand, the relation S thus defined is an equivalence relation hence S is the smallest equivalence relation containing R. No other reference (sorry).2011-11-20
  • 0
    Perhaps I'm missing something obvious, but I can't see why the relation $S$ (which is supposed to be the equivalence relation generated by $R$) is reflexive. What if $x$ is an element of the set such that for all $(y,z)\in R$, $y,z\neq x$, i.e., $x$ does not appear as a coordinate in any element of $R$? Then it seems that $(x,x)\notin S$.2011-12-09
  • 0
    @KeenanKidwell, yes $S$ is always reflexive. Here is a hint: one can choose paths $(x_k)_{0\leqslant k\leqslant n}$ of length $n=0$.2011-12-10
  • 0
    So by allowing $x=x_0$ to be a path, the condition for $x_0Sx_0$ is vacuously satisfied?2011-12-10
0

You can also see easily without an explicit construction that the intersection of all equivalence relations containing $R$ is an equivalence relation.

  • 0
    But looking at your question, I suppose you wanted something more explicit.2014-12-18