1
$\begingroup$

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$

$\endgroup$
6
  • $\begingroup$ If $\mathcal{P}$ is a partition on $A$ then countability of $A$ implies countability of $\mathcal{P}$. Is that clear for you? $\endgroup$ – drhab May 21 '14 at 14:31
  • $\begingroup$ @drhab, please explain. $\endgroup$ – shinzou May 21 '14 at 14:36
  • $\begingroup$ 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. $\endgroup$ – drhab May 21 '14 at 14:42
  • 1
    $\begingroup$ $A/R=\left\{ \left[a\right]_{R}\mid a\in A\right\} $ where $\left[a\right]_{R}$ denotes the equivalenceclass represented by $a$. $\endgroup$ – drhab May 21 '14 at 15:32
  • 1
    $\begingroup$ 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. $\endgroup$ – drhab May 21 '14 at 15:38
2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ $\aleph_0$ at most. Why there's a surjection ? $\endgroup$ – shinzou May 21 '14 at 14:25
  • 3
    $\begingroup$ Think about it more than five minutes. $\endgroup$ – Asaf Karagila May 21 '14 at 14:27
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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