Continuum equals Cardinality of Power Set of Naturals

From ProofWiki
Jump to navigation Jump to search

Theorem

$\mathfrak c = \card {\powerset \N}$

where

$\powerset \N$ denotes the power set of $\N$
$\card {\powerset \N}$ denotes the cardinality of $\powerset \N$
$\mathfrak c = \card \R$ 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 $\struct {\Q, \le}$.

Dedekind's cuts are subsets of $\Q$.

Therefore by definition of power set:

$\mathscr D \subseteq \powerset \Q$

By Subset implies Cardinal Inequality:

$\card {\mathscr D} \le \card {\powerset \Q}$

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:

$\card \Q = \card \N$

Then by Cardinality of Power Set is Invariant:

$\card {\powerset \Q} = \card {\powerset \N}$

By definition of set equivalence:

$\R \sim \mathscr D$

Hence by definition of cardinality:

$\card \R = \card {\mathscr D}$

Thus:

$\mathfrak c \le \card {\powerset \N}$


Define a mapping $h: \map {\operatorname {Fin} } \N \times \powerset \N \to \R^+$:

$\forall F \in \map {\operatorname {Fin} } \N, A \in \powerset \N: \map h {F, A} = \displaystyle \sum_{i \mathop \in F} 2^i + \sum_{i \mathop \in A} \paren {\frac 1 2}^i$

where $\map {\operatorname {Fin} } \N$ denotes the set of all finite subsets of $\N$.

A pair $\tuple {F, A}$ corresponds to binary denotation of a real number $\map h {F, A}$.

It means that $h$ is a surjection.

By Surjection iff Cardinal Inequality:

$\card {\map {\operatorname {Fin} } \N \times \powerset \N} \le \card {\R^+}$

By definition of subset:

$\map {\operatorname {Fin} } \N \subseteq \powerset \N$

Then by Subset implies Cardinal Inequality:

$\card {\map {\operatorname {Fin} } \N} \le \card {\powerset \N}$
\(\displaystyle \card {\map {\operatorname {Fin} } \N \times \powerset \N}\) \(=\) \(\displaystyle \max \set {\card {\map {\operatorname {Fin} } \N}, \card {\powerset \N} }\) Cardinal Product Equal to Maximum
\(\displaystyle \) \(=\) \(\displaystyle \card {\powerset \N}\)

Because $\R^+ \subseteq \R$, we have by Subset implies Cardinal Inequality:

$\card {\R^+} \le \card \R$

Thus:

$\card {\powerset \N} \le \mathfrak c$

Hence the result:

$\mathfrak c = \card {\powerset \N}$

$\blacksquare$


Sources