# Proving if $A$ is a countable set then the quitent group $A/R$ is countable

Prove/disprove: if $A$ is a countable set then the quotient group $A/R$ is countable. $R$ is an equivalence relation.

I think it's not true, since every equvilance class is a subset of $A$, then the quotient group is like the set of all subsets of $A$. So a counter example could be: $|\mathbb N |=\aleph_0\le \mathcal P(\mathbb N)=\mathcal C$

• If $\mathcal{P}$ is a partition on $A$ then countability of $A$ implies countability of $\mathcal{P}$. Is that clear for you? – drhab May 21 '14 at 14:31
• @drhab, please explain. – shinzou May 21 '14 at 14:36
• Every equivalence relation on $A$ corresponds with a partition of $A$. The sets in this partition are the equivalenceclasses. Countability of $A/R$ is exactly the same thing as countability of this partition. In fact the partition can be identified with $A/R$. So if you can prove what I said in my first comment then you are ready. Visualizing set $A$ and partitioning it can help you in understanding why this is true. – drhab May 21 '14 at 14:42
• $A/R=\left\{ \left[a\right]_{R}\mid a\in A\right\}$ where $\left[a\right]_{R}$ denotes the equivalenceclass represented by $a$. – drhab May 21 '14 at 15:32
• Here $a\mapsto\left[a\right]_{R}$ is a surjection $A\rightarrow A/R$ and choosing for each element of $A/R$ some representative results in an injection $A/R\rightarrow A$. See the answers of Asaf and Rasmus. – drhab May 21 '14 at 15:38

HINT: There is a surjection from $A$ onto $A/R$. What can be the cardinality of the image of a function with a countable domain?
• $\aleph_0$ at most. Why there's a surjection ? – shinzou May 21 '14 at 14:25
You have a surjective map $A\to A/R$. Alternatively, you can choose an injective map $A/R\to A$. These should help you show that the statement you are trying to prove or disprove is, in fact, true.