# is equipotence between Cantor set and $[0,1]$ due to AC?

I only known a surjection from Cantor to $[0,1]$, but this thing only means that Cantor is equipotent whit [0,1] when AC is true.

What if ¬AC?

-
The Cantor is equipotent with $[0,1]$ with or without AC. – Brian M. Scott Feb 6 '13 at 5:57
Then, there is an injection from $[0,1]$ to cantor? – Gastón Burrull Feb 6 '13 at 6:03
Yes. $\:\hspace{0 in}$ – Ricky Demer Feb 6 '13 at 6:06
Yes, there is, though that’s not the easiest way to show it. – Brian M. Scott Feb 6 '13 at 6:06

Using continued fractions one can easily construct a bijection between the irrationals in $(0,1)$ and $\left(\Bbb Z^+\right)^{\Bbb Z^+}$, and there is an obvious bijection between that and $\omega^\omega$. Thus, there is a bijection between $[0,1]$ and $\omega^\omega\cup([0,1]\cap\Bbb Q)$. $[0,1]\cap\Bbb Q$ is countably infinite, so there is a bijection between $[0,1]$ and $\omega^\omega\cup\omega$. It’s a very easy application of the Schröder-Bernstein theorem to show that there is a bijection between $\omega^\omega\cup\omega$ and $\omega^\omega$, so we now have a bijection between $[0,1]$ and $\omega^\omega$.

It’s almost trivial that there is a bijection between the Cantor set and $\{0,1\}^\omega$, so to finish we need only show that there is a bijection between $\{0,1\}^\omega$ and $\omega^\omega$. This is another easy application of the Schröder-Bernstein theorem. Clearly there’s an injection from $\{0,1\}^\omega$ to $\omega^\omega$. For the other direction, there’s a bijection between $\{0,1\}^\omega$ and $\left(\{0,1\}^\omega\right)^\omega$, and there’s an injection of $\omega$ into $\{0,1\}^\omega$, so there’s an injection of $\omega^\omega$ into $\left(\{0,1\}^\omega\right)^\omega$ and hence into $\{0,1\}^\omega$.

(This is simply the first argument that occurred to me that was easy to write down; there may well be a shorter one, depending on what you already know.)

-
One could use Berenstein-Schroeder, using the Cantor function (en.wikipedia.org/wiki/Cantor_function) to check that $[0,1]$ injects into the Cantor set $C$ (map $x$ to the first $y$ in $C$ whose image is $x$). – Andrés Caicedo Feb 6 '13 at 6:37
Ty! so clear Brian!!! – Gastón Burrull Feb 6 '13 at 6:46
@Gastón: You’re welcome $-$ and thank you! – Brian M. Scott Feb 6 '13 at 6:47

Indeed proving that is a surjection from $A$ onto $B$ does not imply that $|B|\leq|A|$ without the axiom of choice, even if we assume $A\subseteq B$.

Let us denote the Cantor set as $\newcommand{\Cn}{\mathcal C}\Cn$. We know that $\Cn\subseteq[0,1]\subseteq\Bbb R$, therefore $|\Cn|\leq|\Bbb R|$.

Recall that $x\in\Cn$ then there exists a unique binary $\omega$-sequence $\langle x_n\mid n\in\omega\rangle$ such that $$x=2\sum_{n=0}^\infty\frac{x_n}{3^{n+1}}.$$ Therefore the map $x\mapsto\langle x_n\mid n\in\omega\rangle$ is a bijection from $\Cn$ to $2^\omega$, and therefore $|\Cn|=2^{\aleph_0}$.

Lastly, fix an enumeration of the rationals $\{q_n\mid n\in\omega\}$ and by using Dedekind cuts we know that $r\mapsto\{n\in\omega\mid q_n<r\}$ is an injection from $\mathbb R$ into $\mathcal P(\omega)$ and therefore we have:

$$|2^\omega|=|\Cn|\leq|\mathbb R|\leq|\mathcal P(\omega)|=|2^\omega|=2^{\aleph_0}$$

Using the Cantor-Bernstein theorem whose proof requires no choice whatsoever, we conclude the wanted equality.

-