I'm having troubles with the following exercise about equivalence classes on a defined set.
Let $R$ be an equivalence relation on a set $A$. Given $a,b \in A$ prove the following statements are equivalent (logic equivalence):

  • $[a] \cap [b] \neq \emptyset $
  • $a \in [b]$
  • $[a] \subseteq [b]$

Where the notation $[a]$ means the equivalence class on the set $A$ under the equivalence relation $R$. Edit: I started considering the definition of an equivalence class: $$[a] = \{b\in A:aRb\} $$ And then applying the definition of the intersection: $$[a] \cap [b] = \{a,b \in A:aRb \land bRa\}$$
However, I don't know if I applied the definition correctly and I don't know how to continue.
Can you help me out? Thanks in advance.


The way you've written $[a] \cap [b]$ is incorrect; you first treat $a$ and $b$ as bound variables (i.e. elements of $A$ that were already specified), and then later as free variables (i.e. variables into which you can substitute any element of $A$); I'm no expert on this but I'm quite sure that the way you've intercharged these two notions is syntactically incorrect (at any rate it confuses the reader). If this doesn't make any sense you could consider reading up on this a bit on wikipedia, or at least try to understand what the trouble is with your definition.

Anyway, the correct definition would be $[a] \cap [b] = \{c \in A : aRc \mbox{ } \land \mbox{ }bRc \}$. (can you see why?)

For (1) $\Rightarrow$ (2) use the above definition and the fact that $R$ is transitive; you can prove (2) $\Rightarrow$ (3) again by using the transitive property (and of course the definition of equivalence classes); and (3) $\Rightarrow$ (1) is trivial (or rather it's just very basic set theory).

Hope that helps, and if you have any questions remaining I'll try to answer them!


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.