Thursday, May 1, 2025

Naturals Powerset Uncountable

show that the powerset of the natural numbers is not denumerable

To show that the powerset of the natural numbers P(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 N (the set of natural numbers).


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

1. Assume for contradiction:

Suppose P(N) is countable. Then there exists a bijection f:NP(N) So we can list all subsets of N as: f(0),f(1),f(2), where each f(n)N.


2. Construct a special subset:

Define a subset DN by: D={nNnf(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 kN. So consider whether kD:

  • If kD, then by definition of D, kf(k)=D ⇒ contradiction.
  • If kD, then kf(k)=D ⇒ contradiction.

In either case, we get a contradiction.


Conclusion:

This contradiction shows our assumption was false. Therefore:

P(N) is not countable, i.e., not denumerable.

It is, in fact, uncountably infinite.

No comments:

Post a Comment