# Countability and uncountability of a set $A$ and the set of equivalence classes $A / R$

Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove:

1. If $A$ is countable then all the equivalence classes of $R$ are countable.
2. If $A$ isn't countable then the quotient group $A/R$ isn't countable.
3. If $A$ isn't countable and $A/R$ is countable, then there is an equivalence class in $R$ that isn't countable.
1. Well, I thought of going from the definitions and say that two equivalence class is either identical or foreign, also, the equivalence relation (that is transitivity, reflexivity and symmetry) can add only a finite number of elements so at most it will be countable. So it's true.

2. False: $A=\Bbb R , \ R=mod (2)$ so there are only two equivalence class and the quotient group consists of only $1$ and $0$.

3. I'm pretty sure it's true, $A/R$ at most has the cardinality $\aleph_0$ and it's possible to have an equivalence class that is in one to one correspondence with $A$. But I don't really have an idea on how to prove it.

Please share your thoughts on how to solve this.

Thanks.

Note: This is from set theory intro course so I probably won't understand solutions that utilize knowledge from abstract algebra, rings or group theory.

• @Ragnar, but integers are countable, I chose the reals because they aren't countable. – GinKin Dec 20 '13 at 18:36
• Oh, sorry, you're right, but then, your '$\mod 2$' wasn't right either. You could say $xRy$ if and only if $\lfloor x\rfloor=\lfloor y\rfloor$ – Ragnar Dec 20 '13 at 18:41
• @Ragnar That is in $A=\mathbb R$ ? – GinKin Dec 20 '13 at 18:47
• Yes, $A=\mathbb R$. – Ragnar Dec 20 '13 at 18:49
• that's right...(at least 12 characters....) – Ragnar Dec 20 '13 at 19:00

## 2 Answers

First note that equivalence classes $R$ are subsets of $A$. Because the size of any subset of a countable set is countable, all equivalence classes are countable.

For part $3$, suppose all equivalence classes are countable. The order of a union countable sets is also countable, so the order of $A$ (which is the order of the union of all equivalence classes) is countable. This is a contradiction, so there is at least one non-countable equivalence class.

• I don't understand how an order come into play here, why does ordering the sets even matter in this case ? isn't a union enough ? – GinKin Dec 20 '13 at 19:05
• The 'order' of a set is just the number of elements it contains, i.e. it's size. – Ragnar Dec 20 '13 at 19:42
• Or it's cardinality, I see. Thanks again. – GinKin Dec 20 '13 at 19:48

I have prove for 3. If A isn't countable and A/R is countable then there is an equivalence class that isn't countable. We have example for it is- If A= the set of real numbers Relation between a and b is either both are rational or irrational Then Q/R is countable having two equivalence classes one of rationals and second is of irrationals. So here equivalence class of irrationals is uncountable.