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

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

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.