Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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\}$
share|improve this question
1  
Well, R has to be transitive and $\,bRc\,\,,\,cRe\,$, so... –  DonAntonio Aug 1 '12 at 13:20
    
You only know that ${(a,d),(b,c),(e,a),(c,e)}\subset R$. The problmm does not state that this is the entire relationship. You need to apply the rules for equivalence relationships to extrapolate enough relationships. –  Thomas Andrews Aug 1 '12 at 13:23
1  
You are TOLD that it is an equivalence relation, so you can assume the transitive, symmetric, and reflexive property all hold, and therefore any consequence of these properties and the given ordered pairs being in the relation. –  Geoff Robinson Aug 1 '12 at 13:25
    
You need to work on the transitivity to get the answer right. –  Mark Bennet Aug 1 '12 at 13:44
    
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$. –  Gerry Myerson Aug 1 '12 at 23:29
add comment

6 Answers

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…

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
We never learned to make diagrams of equivalence classes, sadly. Thanks for your explanation though. –  laser295 Aug 1 '12 at 13:47
3  
Now you've learned it. –  Henning Makholm Aug 1 '12 at 13:48
    
+1 really good answer. @laser295 check out the Wikipedia page on # of connected components in a graph. –  user2468 Aug 1 '12 at 23:43
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.