Let $R$ be an equivalence relation on set $A$. Prove that for any $x,y \in A$ either $[x] = [y]$ or $[x] \cap [y] = \varnothing$.

Question

For any $x$ and any $y$
$(x,x) \in R$ and $(y,y) \in R$ (since $R$ is reflexive)
So there exist $[x]$ and $[y]$ equivalence classes for $R$.

When $[x]$ and $[y]$ are equivalence classes of $R$ then, there are possible two status which is either $[x] = [y]$ or $[x] \neq [y]$,

Assume if $[x] \neq [y]$ then $[x] \cap [y] \neq \varnothing$.

Let $z$ be an arbitrary element for $[x] \cap [y]$.

then $z \in [x] \cap [y] \implies z \in [x]$ and $z \in [y]$ but $[x] \neq [y]$ Therefore, This is contradiction! Therefore, if $[x] \neq [y]$ then $[x] \cap [y] = \varnothing$.

if either $[x] = [y]$ or $[x] \neq [y]$, $\implies$ either $[x] = [y]$ or $[x] \cap [y] = \varnothing$. (since if $[x] \neq [y]$ then $[x] \cap [y] = \varnothing$)

Is this correct? Is there a fault? Is there another way to prove it?

Answer 1

There are only two possibilities: either $[x]\cap[y]=\emptyset$ or $[x]\cap[y]\neq\emptyset$. Now $[x]\cap[y]\neq\emptyset$ means that there exists an element $z\in[x]\cap[y]$.

If $z\in[x]\cap[y]$, then $xRz$ and $yRz$, which implies by transitivity and symmetry ($yRz\implies zRy$) that $xRy$. In that case you can show $[x]=[y]$. This is because for any $a\in A$ with $aRx$, $aRx$ and $xRy$ implies by transitivity that $aRy$, and hence $[x]\subseteq[y]$. The reverse inclusion $[y]\subseteq[x]$ follows similalry.

Answer 2

Suppose that $[x] \cap [y] \neq \emptyset$ and $[x] \neq [y]$.

Since the intersection is nonempty, we may pick $z \in [x] \cap [y]$. Since the classes are not equal, we may pick an element $w \in R$ which is in one class but not in the other. WLOG, assume that $w \in [x]\setminus[y]$.

Since $w, z \in [x],$ we have that $x \sim w$ and $x \sim z$. Using symmetry and transitivity, we get that $z \sim w$. However, we also have $y \sim z$. Transitivity gives $y \sim w$ which is a contradiction since $w \notin [y]$.

Answer 3

Let $x,y\in A$.

Either $x R y$ of $x \not R y$.

Case 1: $x R y$.

$[x]=\{z\in A| z R x\}$, $[y]=\{z\in A|z R y\}$.

If $m\in [x]$ then $m Rx$ and as $R$ is transitive and $xR y$ then $m Ry$ so $m \in [y]$ so $[x]\subset [y]$ but if $n \in[y]$ then $n Ry$ but as $R$ is symmetric and $xRy$ the $yR x$ and as $R$ is transitive $nRx$ so $n\in [x]$ and $[y]\subset [x]$ so $[x]=[y]$.

Case 2: $x \not R y$.

If $n \in [x]\cap [y]$ then $n Rx$ and $nR y$. As $R$ is symmetric than $xRn$ and $nRy$. As $R$ is transitive $x R y$ which is a contradiction. So $[x]\cap [y] = \emptyset$.

So $x Ry \implies [x]=[y]$

And $x \not R y \implies [x]\cap [y] = \emptyset$.

Those are the only two options.

Answer 4

It suffices to prove that, for all $x,y\in A$, if $[x]\cap[y]\neq \varnothing$, then $[x]=[y]$.

Suppose $x,y$ are arbitrary in $A$ and let $z\in [x]\cap[y]$. Then $zRx$ and $zRy$ by definition. The former implies $xRz$, which, together with the latter, gives $xRy$. So $[x]\subseteq [y]$. But by symmetry, $[y]\subseteq [x]$. Hence $[x]=[y]$.