Continuum equals Cardinality of Power Set of Naturals

From ProofWiki
Jump to: navigation, search

Theorem

$\mathfrak c = \left\vert{\mathcal P \left({\N}\right)}\right\vert$

where

$\mathcal P \left({\N}\right)$ denotes the power set of $\N$
$\left\vert{\mathcal P \left({\N}\right)}\right\vert$ denotes the cardinality of $\mathcal P \left({\N}\right)$
$\mathfrak c = \left\vert{\R}\right\vert$ denotes the continuum.


Proof

By Reals are Isomorphic to Dedekind Cuts there exists bijection:

$f: \R \to \mathscr D$

where:

$\mathscr D$ denotes the set of all Dedekind cuts of $\left({\Q, \leq}\right)$.

Dedekind's cuts are subsets of $\Q$ therefore by definition of power set:

$\mathscr D \subseteq \mathcal P \left({\Q}\right)$

By Subset implies Cardinal Inequality:

$\left\vert{\mathscr D}\right\vert \leq \left\vert{\mathcal P \left({\Q}\right)}\right\vert$

By Rational Numbers are Countably Infinite:

$\Q$ is countably infinite.

Then by definition of countably infinite there exists a bijection

$g: \Q \to \N$

By definition of set equivalence:

$\Q \sim \N$

Hence by definition of cardinality:

$\left\vert{\Q}\right\vert = \left\vert{\N}\right\vert$

Then by Cardinality of Power Set is Invariant:

$\left\vert{\mathcal P \left({\Q}\right)}\right\vert = \left\vert{\mathcal P \left({\N}\right)}\right\vert$

By definition of set equivalence:

$\R \sim \mathscr D$

Hence by definition of cardinality:

$\left\vert{\R}\right\vert = \left\vert{\mathscr D}\right\vert$

Thus:

$\mathfrak c \leq \left\vert{\mathcal P \left({\N}\right)}\right\vert$


Define a mapping $h:\operatorname{Fin} \left({\N}\right) \times \mathcal P \left({\N}\right) \to \R^+$:

$\forall F \in \operatorname{Fin} \left({\N}\right), A \in \mathcal P \left({\N}\right):h \left({F, A}\right) = \displaystyle \sum_{i \mathop \in F}2^i + \sum_{i \mathop \in A} \left({\frac{1}{2}}\right)^i$

where $\operatorname{Fin} \left({\N}\right)$ denotes the set of all finite subsets of $\N$.

A pair $\left({F, A}\right)$ corresponds to binary denotation of a real number $h \left({F, A}\right)$.

It means that $h$ is a surjection.

By Surjection iff Cardinal Inequality:

$\left\vert{\operatorname{Fin} \left({\N}\right) \times \mathcal P \left({\N}\right)}\right\vert \leq \left\vert{\R^+}\right\vert$

By definition of subset:

$\operatorname{Fin}\left({\N}\right) \subseteq \mathcal P \left({\N}\right)$

Then by Subset implies Cardinal Inequality:

$\left\vert{\operatorname{Fin}\left({\N}\right)}\right\vert \leq \left\vert{\mathcal P \left({\N}\right)}\right\vert$
\(\displaystyle \left\vert{\operatorname{Fin} \left({\N}\right) \times \mathcal P \left({\N}\right)}\right\vert\) \(=\) \(\displaystyle \max\left({\left\vert{\operatorname{Fin} \left({\N}\right)}\right\vert, \left\vert{\mathcal P \left({\N}\right)}\right\vert}\right)\) Cardinal Product Equal to Maximum
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{\mathcal P \left({\N}\right)}\right\vert\)

Because $\R^+ \subseteq \R$ therefore by Subset implies Cardinal Inequality:

$\left\vert{\R^+}\right\vert \leq \left\vert{\R}\right\vert$

Thus:

$\left\vert{\mathcal P \left({\N}\right)}\right\vert \leq \mathfrak c$

Hence the result:

$\mathfrak c = \left\vert{\mathcal P \left({\N}\right)}\right\vert$

$\blacksquare$


Sources