# The equivalence relation generated by a relation

Let $X$ be a non-empty set and let $r\subseteq X\times X$ be a relation on $X$. Let $R$ be the intersection of all equivalence relations on $X$ that contain $r$.

Prove that if $xRy$, then one of the following is true:

• $x=y$;
• $xr'y$ or $yr'x$;
• There exist finitely many elements $z_0,\ldots,z_n$ such that $xr'z_0, z_0r'z_1,\ldots,z_nr'y$,

where $ar'b$ means that $arb$ or $bra$.

• The "or" in the second bullet is not needed due to the way you define $r'$. Anyway, assume that you have two elements not satisfying those but which are related by $R$. Show that there is a smaller equivalence relation containing $r$. – Tobias Kildetoft Apr 24 '15 at 9:03
• Thanks @TobiasKildetoft for the hint and the correction!! – Zuriel Apr 24 '15 at 9:04
• If $ar′b$ means that $arb$ or $bra$, then $xr′y$ and $yr′x$ are "the same thing" ... – Mauro ALLEGRANZA Apr 24 '15 at 9:04

Let $S$ be the set of pairs $(x,y)$ satisfying at least one of your bullet list. One can show that $S$ is an equivalence relation. Reflexivty and symmetry are almost immediate, and for transitivity assuming $(x,y),(y,z)$ lie in $S$ one can use the bulleted list to construct a chain from $x$ to $z$ using the assumed chains from $x$ to $y$ and from $y$ to $z.$
Now it's clear that since $R$ is the intersection of all equivalence classes containing r, and since $S$ is one of them, that $R \subseteq S.$ On the other hand $R$ must contain each pair $(x,y)$ in $S$ since $R$ contains $r$ and hence also your $r'.$ So $S \subseteq R$ and we get $R=S$ which shows what you wish to show.
Added note: Actually just from $R \subseteq S$ one can conclude what you want. (No need to use the full equality $R=S.$)
• @Zuriel I found the problem interesting. At first I thought it wouldn;t be true by looking at the relation $r$ on $\mathbb{Z}$ consisting of all pairs $(t,t+1).$ Here $R$ includes all pairs of integers, and I thought it might not be possible to have the third bullet. But for any specific pair $(x,y)$ one needs only a chain of finite length., – coffeemath Apr 25 '15 at 6:38