2

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?

Hare Krishan
  • 221
  • $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$ – Prasun Biswas Mar 24 '15 at 18:00

3 Answers3

2

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?)

BaronVT
  • 13,613
  • 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

     – Hare Krishan Mar 24 '15 at 18:10
  • The three equivalence classes would be defined as {a,b,c,d,e}, {a,d}, {c,b}? – Hare Krishan Mar 24 '15 at 18:13
  • 1
    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$. – BaronVT Mar 24 '15 at 18:17
  • 1
    Ah okay so the three equivalence classes would be: {a,d}, {b,c}, {e} – Hare Krishan Mar 24 '15 at 18:22
  • 1
    Yes, that is correct. Good work. – BaronVT Mar 24 '15 at 18:28
2

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

Tim Raczkowski
  • 20,046
0

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

drhab
  • 151,093