2
$\begingroup$

Let A = {a, b, c, d, e}

Suppose R is an equivalence relation on A. Suppose R has three equivalence classes. Also aRd and bRc. Write out R as a set.

From my understanding an equivalence relation is reflexive, symmetric & transitive. I understand that but what is it saying when aRd and bRc? How can I form equivalence classes from this information?

$\endgroup$
  • $\begingroup$ $xRy$ means $x$ is related to $y$ in the given relation. In other words, suppose $R(x)$ is the definition of the relation. Then, $aRb\implies R(a)=b$ $\endgroup$ – Prasun Biswas Mar 24 '15 at 18:00
2
$\begingroup$

It means that $a$ and $d$ belong to the same equivalence class, and that $b$ and $c$ belong to the same equivalence class.

Now, use transivity, and the fact that there are three equivalence classes to sort things out; for instance, can $a$ and $b$ be in the same equivalence class? (i.e. would you still have three classes if this were true?)

$\endgroup$
  • $\begingroup$ Thanks so for the reflexive part of the set: {(a,a), (b,b), (c,c), (d,d), (e,e)} For the symetric part of the set because aRd and bRc: {(a,d), (d,a), (b,c), (c,b)} The union of these two subsets meet the definitions of transitivity, reflexivity, and symetry $\endgroup$ – Hare Krishan Mar 24 '15 at 18:10
  • $\begingroup$ The three equivalence classes would be defined as {a,b,c,d,e}, {a,d}, {c,b}? $\endgroup$ – Hare Krishan Mar 24 '15 at 18:13
  • 1
    $\begingroup$ Notice that you cannot have a particular element belonging to more than one distinct equivalence class: if $aRb$ and $aRd$ as you write, then $bRd$ by transitivity, and so there cannot be any equivalence class that includes $b$ but not $d$. $\endgroup$ – BaronVT Mar 24 '15 at 18:17
  • 1
    $\begingroup$ Ah okay so the three equivalence classes would be: {a,d}, {b,c}, {e} $\endgroup$ – Hare Krishan Mar 24 '15 at 18:22
  • 1
    $\begingroup$ Yes, that is correct. Good work. $\endgroup$ – BaronVT Mar 24 '15 at 18:28
2
$\begingroup$

Remember that $R$ is a collection of ordered pairs of members of $A$. So, $aRd$ means that $(a,d)\in R$. Similarly $(b,c)$. Now use the properties of an equivalence relation to find all the ordered pairs that are in $R$.

For example, by reflexivity, $aRa$, or $(a,a)\in R$, $(b,b)\in R$ etc. By symmetry, $(a,d)\in R$ implies $(d,a)\in R$.

$\endgroup$
  • 1
    $\begingroup$ Yes, that is a better term. $\endgroup$ – Tim Raczkowski Mar 24 '15 at 18:16
0
$\begingroup$

Hint:

If the equivalence classes are found then you can find $R$ by: $$R:=\{\langle x,y\rangle\mid x\text{ and }y\text{ belong to the same equivalence class}\}$$

$\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.