The cantor set is uncountable

Question

I am reading a proof that the cantor set is uncountable and I don't understand it. Hopefully someone can help me.

Let $C$ be the Cantor set and $x\in C$.

Then there exists unique $x_k\in \{0,2\}$ such that $x=\sum_{k\in \mathbb N}\frac{x_k}{3^k}$. Conversely every $x$ with this representation lies in C.

If $C$ would be countable then there would exists a injective map $f:C\rightarrow \mathbb N$.

Let $f^{-1}(i)=\sum_{k\in \mathbb N}\frac{x_{ik}}{3^k}$ or $f^{-1}(i)=\emptyset$.

Set $z_k=2-x_{i_k}$, then z=$\sum_{k\in \mathbb N}\frac{z_k}{3^k}$

Then $z$ is in the cantor set but z isn't in the pre-image of $f$.

Questions:

1. Shouldn't it be $z_k=2-x_k$?
2. I understand that z lies in C but why it is not in the pre image of f?

Thanks in advance

Answer 1

It shouldn't be $2-x_k$ but rather $2-x_{k,k}$. What you are trying to accomplish is a diagonalization. You are attempting to be different from every one of a countable set of objects and the way you do that is by making sure that from step $k$ onwards you differ from object $k$.

This is a very general approach and works even for uncountable amounts of objects except you have to be a bit more careful and obviously you need "larger" objects.

As for the second part that exactly follows from the fact that in step $k$ when you define $z_k$ you make sure you are not $f^{-1}(k)$ since you differ in the $k$'th digit.

Answer 2

How about a more direct proof?

All $x$ in the set have a unique representation as $$x=\sum_{k\in \mathbb N}\frac{x_k}{3^k}$$ Define a map to $[0,1]$ by $$ x \mapsto \sum_{k\in \mathbb N}\frac{(x_k/2)}{2^{k}}. $$ This is a bijection. Done.

To see that it's a bijection, observe that it is a binary representation where we have taken the 2s in the initial sum and replaced them by 1s.

Answer 3

Perhaps the easiest direct argument, assuming that you already know that $\wp(\Bbb Z^+)$ is uncountable, is to map $x\in C$ to $\{k\in\Bbb Z^+:x_k=2\}$; this is clearly a bijection from $C$ to $\wp(\Bbb Z^+)$.