1
$\begingroup$

I have a few short proofs that I wish to be checked regarding equivalent classes.

Suppose that R is an equivalence relation on set X. If $a, b \in X$, then

  1. $a\in [a]$
  2. $[a] = [b] \iff (a, b) \in R$
  3. $[a]\cap[b]=\emptyset\iff(a, b)\notin R$

For number 1 I understand that I have to make the claim "every element in X must be in one equivalence class." But how may I write out a rigid proof?

For number 2/3 I have minimal idea on how to begin. Would you shed some light to these short proofs please? Thank you.

Edit: Thanks Author. Equivalent relation is defined here as a relation that is reflexive, symmetric and transitive.

$\endgroup$
  • 5
    $\begingroup$ I believe it would be a very good start to familiarize yourself with how your book defines an equivalence class (exactly what words it uses). If you edit your question to include the definition, we would be better equipped to help you as well. $\endgroup$ – Arthur Apr 2 '14 at 22:24
1
$\begingroup$

For $(1)$, since $a\in X$, $R$ is an equivalence relation, we have that $aRa$. Therefore, $a\in [a]$. Because $[a] = \{x: xRa\}$.

Now for $(2)$, Assume $[a] = [b]$. You have deduced that $a\in [a]$. Since $[a]=[b]$ you can deduce that $a\in [b]$ because sets are equal if and only if they have the same elements. Since $a\in [b]$, $aRb \longrightarrow (a,b) \in R$. Now assume $(a,b)\in R$. Let $x\in [a]$. We desire to show that $x\in [b]$, (so that $[a]\subseteq [b]$). Since $x\in [a]$, we have $xRa$. Since $R$ is an equivalence relation, $R$ is transitive. By hypothesis, $aRb$. Therefore $xRa \land aRb \longrightarrow xRb$ so that $x\in [b]$. Now let $y\in [b]$. We desire to show that $y\in [a]$. By hypothesis, $aRb$. Since $aRb$ and $R$ is an equivalence relation, $R$ is symmetric and therefore $bRa$. Applying transitivity, we have $yRb \land bRa \longrightarrow yRa$, so $y\in [a]$. Thus we have $[a] \subseteq [b] \land [b] \subseteq [a] \longrightarrow [a] = [b]$.

Now for $(3)$, assume $[a] \cap [b] = \emptyset$. Later assume for sake of contradiction $(a,b) \in R$. $(a,b) \in R \longrightarrow a\in [b]$. We already have deduced that $a\in [a]$. So $\{a\} \subseteq [a]\cap [b] = \emptyset$, a contradiction. Now assume that $(a,b) \notin R$. We desire to show that $[a]\cap [b] = \emptyset$. Assume for sake of contradiction that $[a]\cap [b] \ne \emptyset$. Then there is some $x$ such that $xRa$ and $xRb$. Since $xRa$, and $R$ is symmetric, $aRx$. Now since $aRx \land xRb$, by transitivity of $R$, we have that $aRb$. Therefore, $(a,b) \in R$, a contradiction.


Remark: Most of these proofs are about unraveling definitions, applying them when needed, and following your nose. Hope this helps.

$\endgroup$
1
$\begingroup$

I guess $[a] := \{b\in X : (a,b)\in R\}$, is that right?

  1. You know $(a,a)\in R$ for any $a$, so ...

  2. $a\in [a] = [b]$ tells you that $(a,b)\in R$. That's one direction. For the other, say $(a,b)\in R$. Then which of the following is true: $a\in [b]$ or $a\notin [b]$?

  3. Say you can choose some $x\in [a]\cap [b]$. Then $(a,x)\in R$ and $(b,x)\in R$. Now transitivity of $R$ gives ...

Hope that helps!

$\endgroup$

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.