Topology: Showing the Collection Is Uncountable

Question

Here's my attempt to this question

Answer 1

There is a bijection between $\mathcal{P}(\mathbb{N})$ and $2^\mathbb{N}$, namely, for any subset $A \subseteq \mathbb{N}$ consider the characteristic function $\chi_A$, i.e. $\chi_A(x) = 1$ if $x \in A$ and zero else. Thus if $\mathcal{P}(\mathbb{N})$ is uncountable so is $2^\mathbb{N}$. The problem with your solution is, that you already assume that $2^\mathbb{N}$ denotes the power set of $\mathbb{N}$, which is a priori not clear (if it is, you wouldn't have to prove anything). The prove you stated is usually known as Cantor's Theorem, and shows more generally that $$|X| < |\mathcal{P}(X)|.$$

Answer 2

Your proof attempt is about subsets of $\mathbb{N}$, not the set $2^{\mathbb{N}}$, (although there is a natural bijection between them, using the characteristic functions).

Suppose $F:\mathbb{N} \to 2^{\mathbb{N}}$ is a function.

Define $f: \mathbb{N} \to \{0,1\}$ by $f(n) = 1+F(n)(n)$ where we add modulo $2$, so $1+1 = 0, 0+1=1$ etc. This $f$ is a well-defined function in $2^{\mathbb{N}}$. Suppose there were some $, \in \mathbb{N}$ such that $F(m) = f$.

But then $f(m) = F(m)(m) + 1$ by definition of $f$, while $F(m) = f$ implies that $F(m)(m) = f(m)$. But these are different elements of $\{0,1\}$, so no such $m$ can exist: $F$ is not surjective.

As this holds for all such $F$, $2^{\mathbb{N}}$ is uncountable.