So I am not really comfortable with equivalence relations, so this example from Wikipedia gives me trouble. Here is what it says:

Let the set $\{a,b,c\}$ have the equivalence relation $\{(a,a),(b,b),(c,c),(b,c),(c,b)\}$.

So it can also be $\lbrace(a,a), (b,b), (c,c) \rbrace$ if I so choose?

  • 1
    $\begingroup$ Yes, that is an equivalence relation, too. In fact, a little meditations shows that an equivalence relation on a set is essentially the same thing as a partition on the set. $\endgroup$ May 3 '15 at 4:23
  • $\begingroup$ @Travis So the equivalence classes depend on which equivalence relation I choose? $\endgroup$ May 3 '15 at 4:25
  • $\begingroup$ @SalmonKiller Yes, that is exactly right. $\endgroup$
    – apnorton
    May 3 '15 at 4:26

Your relation is indeed an equivalence relation:

Reflexivity clearly holds, as symmetry does. Transitivity does hold since

$$\forall x,y,z\in X: xRy \wedge yRz \implies xRz $$

is a true statement: $xRy \wedge yRz$ is true in this case if and only if $x=y=z$, in which case clearly (reflexivity) $xRz$.

EDIT: Simpler argument (without symbolic logic)

You want to prove that the relation $R=\lbrace(a,a), (b,b), (c,c) \rbrace$ defined on the set $X=\{a,b,c\}$ is an equivalence relation, so you must prove three properties:

  1. For every $x\in X$, $(x,x)\in R$. (Reflexivity)
  2. For every $x,y\in X$, if $(x,y)\in R$ then necessarily $(y,x)\in R$ (Symmetry)
  3. For every $x,y,z\in R$, if $(x,y)\in R$ and $(y,z)\in R$, then necessarily $(x,z)\in R$. (Transitivity).

We now prove those properties.

  1. Take any element $x$ of $X$, we have only three possibilities, namely $x$ equals $a$, $b$ or $c$, in any case, $(x,x)\in R$ so the relation is reflexive.
  2. Take any element $x$ and $y$ of $X$, we must prove that if $(x,y)\in R$, then $(y,x)\in R$. We only need to focus on the cases where $(x,y)\in R$ (if $(x,y)\notin R$ there's nothing to prove!), so the only cases are $x=y=a, b, c$ where the symmetry clearly holds.
  3. Here's the point, we must take any three elements $x,y,z$ of $X$ and prove that if $(x,y)\in R$ and $(y,z)\in R$, then $(x,z)\in R$. Again, we only focus on the case $(x,y)\in R$ and $(y,z)\in R$, but this happens only if $x=y=z$ and therefore, clearly, $(x,z)\in R$.

Please notice not every relation you define on $X$ becomes an equivalence relation. For example, if you choose to add (only) $(a,b)$ to $R$, then symmetry is lost.

  • $\begingroup$ Can you please explain that same idea without symbolic logic? I would really appreciate that. $\endgroup$ May 3 '15 at 4:30

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.