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{\mathcal{P}(\mathbb{N}) \text{ is not countable, i.e., not denumerable.}} \]

It is, in fact, uncountably infinite.