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

  • 1
    $\begingroup$ 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$. $\endgroup$ – Tobias Kildetoft Apr 24 '15 at 9:03
  • $\begingroup$ Thanks @TobiasKildetoft for the hint and the correction!! $\endgroup$ – Zuriel Apr 24 '15 at 9:04
  • 1
    $\begingroup$ If $ar′b$ means that $arb$ or $bra$, then $xr′y$ and $yr′x$ are "the same thing" ... $\endgroup$ – 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.$)

  • $\begingroup$ Many thanks for the detailed answer! It is now very clear to me. $\endgroup$ – Zuriel Apr 25 '15 at 0:46
  • $\begingroup$ @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., $\endgroup$ – coffeemath Apr 25 '15 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.