[Math] Provide a bijection between power set of natural numbers and the Cantor set in $[0,1]$

cantor setreal-analysis

Question: I am trying to prove that Cantor Middle Third Set $C$ is uncountable, by establishing a bijection $f$ from $C$ onto the power set of $\mathbb{N}.$

My attempt: We know that every element of Cantor set $C$ has a ternary representation.

Let $\mathcal{P}(\mathbb{N})$ be the power set of $\mathbb{N}.$
Define $f:C\to\mathcal{P}(\mathbb{N})$ by
$$f((a_1,a_2,a_3,…,a_n,…)) = \{n\in\mathbb{N}:a_n\neq 0 \},$$
where $a_n\in\{0,2\}$ for all natural number $n.$

Clearly $f$ is well-defined and injective.

To prove that $f$ is surjective, given any subset $X\in \mathcal{P}(\mathbb{N}),$ we pick $x \in C$ such that non-zero entries of $x$ corresponds to numbers in $X.$
For example, if $X=\{1,4,6\},$ then we pick $x = (2,0,0,2,0,2,0,0,0,…).$

Is my proof correct?

Best Answer

There are, of course, things to nit-pick about your presentation, but the proof itself is entirely correct. Here are the three things that I saw and thought could've been better:

You should be clearer on what $(a_1,a_2,\ldots)$ is. It is the ternary expansion of a point in $C$ with the restriction that $a_i\neq 1$ for all $i$. It's implicitly understood, but I think it is better to state explicitly. The fewer things a reader has to guess (no matter how certain you are that you guessed right), the better.

Perhaps you should have a short justifying sentence for each of well-definedness and injectivity, just to be safe. Well-definedness hinges on the uniqueness of the ternary expansion (as long as we require no $1$'s), and injectivity on the fact that two real numbers with the same expansion are equal.

Your surjectivity proof is explained via an example. This is better to do generally. Say we have a $U\subseteq \Bbb N$, and we then define $x = \sum_{n = 1}^\infty a_n3^{-n}$ where $a_n =2$ iff $n\in U$ and $0$ otherwise. Then $x\in C$, and we get $f(x) = U$. (Whether you want to prove that $x\in C$ and $f(x) = U$ is completely up to you.) After that you are free to do an example to illustrate.