Naturals Powerset Uncountable

show that the powerset of the natural numbers is not denumerable

To show that the powerset of the natural numbers $\mathcal{P}(\mathbb{N})$ is not denumerable, we aim to prove that it is uncountable—that is, it cannot be placed into a one-to-one correspondence with $\mathbb{N}$ (the set of natural numbers).

---

Step-by-step Proof (Using Cantor’s Diagonal Argument)

1. Assume for contradiction:

Suppose $\mathcal{P}(\mathbb{N})$ is countable. Then there exists a bijection $$f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$$ So we can list all subsets of $\mathbb{N}$ as: $$f(0),f(1),f(2),\dots$$ where each $f(n)\subseteq \mathbb{N}$.

---

2. Construct a special subset:

Define a subset $D\subseteq \mathbb{N}$ by: $$D=\{n\in \mathbb{N}\mid n\notin f(n)\}$$ This is called the diagonal subset, because its construction resembles Cantor’s diagonalization.

---

3. Check whether $D$ appears in the list:

Since we assumed all subsets are listed, $D$ must be $f(k)$ for some $k\in \mathbb{N}$. So consider whether $k\in D$:

• If $k\in D$, then by definition of $D$, $k\notin f(k)=D$ ⇒ contradiction.
• If $k\notin D$, then $k\in f(k)=D$ ⇒ contradiction.

In either case, we get a contradiction.

---

Conclusion:

This contradiction shows our assumption was false. Therefore:

$$\boxed{{\displaystyle \mathcal{P}(\mathbb{N})\text{ is not countable, i.e., not denumerable.}}}$$

It is, in fact, uncountably infinite.