Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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
1  
Yes. $\:\hspace{0 in}$ –  Ricky Demer Feb 6 '13 at 6:06
2  
Yes, there is, though that’s not the easiest way to show it. –  Brian M. Scott Feb 6 '13 at 6:06
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
1  
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$). –  Andres 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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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