# Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$

Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$ and show where it was used the axiom of choice.

This is a question of my homework. I could already prove that the cardinality of all finite subsets of $\mathbb{R}$ is $2^{\aleph_0}$ and I know that every real finite set is countable. I don't know how to use this (if I need this) and how to use de axiom of choice.

## 1 Answer

Here is a general road map:

1. Show that $\Bbb{R^N}$, all the sequences of real numbers has cardinality $2^{\aleph_0}$.

2. Find a surjection from $\Bbb{R^N}$ onto the set of all countable subsets of $\Bbb R$.

3. Conclude (using what you already know) that the cardinals are equal.

Let me give you an additional hint that the axiom of choice is used in the third step. And let me also add that you cannot prove this equality of cardinals without using some of the axiom of choice.

• I prove the first and the second steps but, in the third I use the Cantor Bernstein Theorem to conclude that the cardinals are equal... But Cantor Bernstein don't use the axiom of choice. :( – Felipe Nov 21 '14 at 21:25
• Yes, but what is the exact formulation of the Cantor-Bernstein theorem which doesn't use the axiom of choice? – Asaf Karagila Nov 21 '14 at 21:26
• The Cantor-Bernstein theorem tell to us that if $X,Y$ are sets and $|X|\leq|Y|$ and $|Y|\leq|X|$ so $|X|=|Y|$. In the proof we consider a one-to-one function in each case. I don't see here the axiom of choice. – Felipe Nov 21 '14 at 21:31
• Yes, that is correct. But now look at the second step I wrote in my answer again, and see where the axiom of choice was used. – Asaf Karagila Nov 21 '14 at 21:32
• I suppose that the axiom of choice was used in the surjection from $\mathbb{R}^\mathbb{N}$ on to the set of all countable subsets of $\mathbb{R}$, because I need choose a surjection such that all works, but I don't understand if this is really true... – Felipe Nov 21 '14 at 21:38