Power Set of Natural Numbers is Cardinality of Continuum

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\N$ denote the set of natural numbers.

Let $\powerset \N$ denote the power set of $\N$.

Let $\card {\powerset \N}$ denote the cardinality of $\powerset \N$.


Then $\card {\powerset \N}$ is the cardinality of the continuum.


Proof

Outine

$\powerset \N$ is demonstrated to have the same cardinality as the set of real numbers.

This is done by identifying a real number with its basis expansion in binary notation.

Such a basis expansion is a sequence of $0$s and $1$s.

Each $1$ of a real number $x$ expressed in such a way can be identified with the integer which identifies the power of $2$ representing the $1$ in that place.

Hence $x$ corresponds to the subset of $\N$ whose elements are the positions in $x$ which hold a $1$.

Thus $\R$ and $\powerset \N$ are equivalent.

From the Cantor-Dedekind Hypothesis, the real numbers are in one-to-one correspondence with the points on a line segment.

The points on a line segment form a continuum.



Sources