Proving that a pair of equivalence classes must be identical or disjoint

Question

Give an equivalence $R$ relation over a set $A$:

$$C_x=\{y\in{A}:xRy\}$$

I'm trying to prove that if $x,y\in{A}$, Either $C_x=C_y$ or $C_x\cap{C_y}=\{\}$. In other words, $C_x$ and $C_y$ must be either identical or disjoint. I can see intuitively that it is the case, however, I am looking for a way to rigorously prove it using predicate logic and elementary set theory.

I have two ideas on where to start, but don't know how to proceed from there:

1. Start with the statement $(x\in{A}\land{y}\in{A})\to{(C_x=C_y\lor{C_x}\cap{C_y}=\{\})}$ and take the contrapositive, which seems easier to prove (but I could be wrong): $$(C_x\ne{C_y}\land C_x\cap{C_y}\ne\{\})\to{\lnot(x\in{A}\land{y}\in{A})}$$
2. Start with the observation that logical statements $X\lor{Y}$ is logically equivalent to $\bar{X}\to{Y}$.

I'm not sure how to proceed from here. Can anyone give me a hint on how to proceed?

Answer 1

HINT: Show that if $C_x\cap C_y\ne\varnothing$, then $C_x=C_y$.

One way to do this:

If $C_x\cap C_y\ne\varnothing$, then there is some $z\in C_x\cap C_y$. Now use the definition of $C_x$ and $C_y$ and the properties of an equivalence relation to show that $x\in C_y$ and $y\in C_x$. Finally, use them again to show that if $x\in C_y$, then $C_x\subseteq C_y$.