7
$\begingroup$

Let $A=\{a,b,c,d,e\}$. Suppose $R$ is an equivalence relation on $A$. Suppose also that $aRd$ and $bRc$, $eRa$ and $cRe$. How many equivalence classes does $R$ have?

My thoughts: (Not sure if I have the right idea...)

UPDATED/EDITED

Since $R$ is an equivalence relation on $A$ and $aRd$, $bRc$, $eRa$, and $cRe$, then

$R=\{(a,d),(d,a),(a,a),(d,d),(b,c),(c,b),(c,c),\\ (b,b),(e,a),(a,e),(e,e),(c,e),(e,c)\}$ (Did I miss any?)

So $R$ has $1$ equivalence class:

  • $[a]=[b]=[c]=[d]=[e]=\{a,b,c,d,e\}$
  • 0
    Your conclusion about the number of equivalence classes is correct. Your list of the elements of $R$ is incomplete; $R$ is, in fact, *all* of $A\times A$.2012-08-01

6 Answers 6

8

Instead of trying to write down all the pairs in $R$ in a list, it is better to draw a diagram:

A----D | E--.     \ B----C 

Each line connects two elements that you explicitly know are related. Since you're told that $R$ is an equivalence relation, two elements must be related if there is any path between them.

However, the graph is easily seen to be connected, so everything is related to everything else, and there is one equivalence class $\{a,b,c,d,e\}$.

  • 0
    +1 really good answer. @laser295 [check out the Wikipedia page on # of connected components in a graph](http://en.wikipedia.org/wiki/Connected_component_(graph_theory)#An_equivalence_relation).2012-08-01
4

Hint: You are told that $R$ is an equivalence relation. So in particular, since it contains $(a, d)$, it must also contain $(d, a)$, since it is symmetric. So it is larger than you thought it was. Similarly, it must also be transitive…

4

It doesn't make sense to say "none of the elements in R are reflexive", as the reflexive property applies to the relation and not to elements.

What you need to do is make deductions like this:

If we know that $aRd$, then we must have $dRa$ since we are told that $R$ is an equivalence relation, and hence is symmetric.

3

The answer to (Right? Wrong?) is Wrong. Those members are elements of $R$ but not every element. You are given that R is an equivalence relation, so for example you know that (a,a) will also be in R.

Use the axioms of an equivalence relation to see more equivalences. For example eRa and cRe, you can conclude aRc. If you keep doing things like that, you'll soon see the answer.

2

You're told $R$ contains those 4 pairs; you're not meant to conclude that $R$ contains only those 4 pairs. Indeed, you're told $R$ is an equivalence relation, so it must be reflexive, so it must have, for example, $(a,a)$; it must be symmetric, so, for example, since it has $(a,d)$, it must have $(d,a)$; it must be transitive, so, for example, since it has $(b,c)$ and $(c,e)$, it must have $(b,e)$. Figure out what else it has to have, and then we can talk.

0

Some people find that it's easiest to cast this problem in more familiar terms. You're told that $R$ is an equivalence relation. So is $=$ on a set of numbers, so it will have all the properties of $R$ and so we can dispense with $R$ entirely for the moment and think in terms of numbers represented by the variables $a, b,c, d, e$. You're told that

(1) $a=d$

(2) $b=c$

(3) $e=a$

(4) $c=e$

The equivalence class of, say, $a$ will be all the elements equal to $a$ so we can argue

$a=a$, since anything is equal to itself (i.e., by reflexivity).

$a=d$ by (1)

$a=e$ by (3) and symmetry

$a=c$ since $c=e$ by (4), $e=a$ by (3), and transitivity

$a=b$ since $a=c$, and $c=b$ by (2) and transitivity again

So the set of elements equal to (related to) $a$, namely the equivalence class of $a$ is $\{a,b,c,d,e\}$. In other words, in this case there is just one equivalence class, everything.