# How many equivalence classes does $R$ have?

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

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

## 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…

-

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.

-

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.

-

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

-
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
– user2468 Aug 1 '12 at 23:43

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.

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 65, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9574995040893555, "perplexity_flag": "head"}