10
$\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

11

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
    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