Cardinality of the continuum

Georg Cantor introduced the concept of cardinality to compare the sizes of infinite sets. He famously showed that the set of real numbers is uncountably infinite. That is, ${\displaystyle {\mathfrak {c}}}$ is strictly greater than the cardinality of the natural numbers, ${\displaystyle \aleph _{0}}$:

${\displaystyle \aleph _{0}<{\mathfrak {c}}.}$

In practice, this means that there are strictly more real numbers than there are integers. Cantor proved this statement in several different ways. For more information on this topic, see Cantor's first uncountability proof and Cantor's diagonal argument.

A variation of Cantor's diagonal argument can be used to prove Cantor's theorem, which states that the cardinality of any set is strictly less than that of its power set. That is, ${\displaystyle |A|<2^{|A|}}$ (and so that the power set ${\displaystyle \wp (\mathbb {N} )}$ of the natural numbers ${\displaystyle \mathbb {N} }$ is uncountable). In fact, one can show that the cardinality of ${\displaystyle \wp (\mathbb {N} )}$ is equal to ${\displaystyle {\mathfrak {c}}}$ as follows:

1. Define a map ${\displaystyle f:\mathbb {R} \to \wp (\mathbb {Q} )}$ from the reals to the power set of the rationals, ${\displaystyle \mathbb {Q} }$, by sending each real number ${\displaystyle x}$ to the set ${\displaystyle \{q\in \mathbb {Q} :q\leq x\}}$ of all rationals less than or equal to ${\displaystyle x}$ (with the reals viewed as Dedekind cuts, this is nothing other than the inclusion map in the set of sets of rationals). Because the rationals are dense in ${\displaystyle \mathbb {R} }$, this map is injective, and because the rationals are countable, we have that ${\displaystyle {\mathfrak {c}}\leq 2^{\aleph _{0}}}$.
2. Let ${\displaystyle \{0,2\}^{\mathbb {N} }}$ be the set of infinite sequences with values in set ${\displaystyle \{0,2\}}$. This set has cardinality ${\displaystyle 2^{\aleph _{0}}}$ (the natural bijection between the set of binary sequences and ${\displaystyle \wp (\mathbb {N} )}$ is given by the indicator function). Now, associate to each such sequence ${\displaystyle (a_{i})_{i\in \mathbb {N} }}$ the unique real number in the interval ${\displaystyle [0,1]}$ with the ternary-expansion given by the digits ${\displaystyle a_{1},a_{2},\dotsc }$, i.e., ${\displaystyle \sum _{i=1}^{\infty }a_{i}3^{-i}}$, the ${\displaystyle i}$-th digit after the fractional point is ${\displaystyle a_{i}}$ with respect to base ${\displaystyle 3}$. The image of this map is called the Cantor set. It is not hard to see that this map is injective, for by avoiding points with the digit 1 in their ternary expansion, we avoid conflicts created by the fact that the ternary-expansion of a real number is not unique. We then have that ${\displaystyle 2^{\aleph _{0}}\leq {\mathfrak {c}}}$.

By the Cantor–Bernstein–Schroeder theorem we conclude that

${\displaystyle {\mathfrak {c}}=|\wp (\mathbb {N} )|=2^{\aleph _{0}}.}$

The cardinal equality ${\displaystyle {\mathfrak {c}}^{2}={\mathfrak {c}}}$ can be demonstrated using cardinal arithmetic:

${\displaystyle {\mathfrak {c}}^{2}=(2^{\aleph _{0}})^{2}=2^{2\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}}.}$

By using the rules of cardinal arithmetic, one can also show that

${\displaystyle {\mathfrak {c}}^{\aleph _{0}}={\aleph _{0}}^{\aleph _{0}}=n^{\aleph _{0}}={\mathfrak {c}}^{n}=\aleph _{0}{\mathfrak {c}}=n{\mathfrak {c}}={\mathfrak {c}},}$

where n is any finite cardinal ≥ 2, and

${\displaystyle {\mathfrak {c}}^{\mathfrak {c}}=(2^{\aleph _{0}})^{\mathfrak {c}}=2^{{\mathfrak {c}}\times \aleph _{0}}=2^{\mathfrak {c}},}$

where ${\displaystyle 2^{\mathfrak {c}}}$ is the cardinality of the power set of R, and ${\displaystyle 2^{\mathfrak {c}}>{\mathfrak {c}}}$.

Every real number has at least one infinite decimal expansion. For example,

(This is true even in the case the expansion repeats, as in the first two examples.)

In any given case, the number of digits is countable since they can be put into a one-to-one correspondence with the set of natural numbers ${\displaystyle \mathbb {N} }$. This makes it sensible to talk about, say, the first, the one-hundredth, or the millionth digit of π. Since the natural numbers have cardinality ${\displaystyle \aleph _{0},}$ each real number has ${\displaystyle \aleph _{0}}$ digits in its expansion.

Since each real number can be broken into an integer part and a decimal fraction, we get:

${\displaystyle {\mathfrak {c}}\leq \aleph _{0}\cdot 10^{\aleph _{0}}\leq 2^{\aleph _{0}}\cdot {(2^{4})}^{\aleph _{0}}=2^{\aleph _{0}+4\cdot \aleph _{0}}=2^{\aleph _{0}}}$

where we used the fact that

${\displaystyle \aleph _{0}+4\cdot \aleph _{0}=\aleph _{0}\,.}$

On the other hand, if we map ${\displaystyle 2=\{0,1\}}$ to ${\displaystyle \{3,7\}}$ and consider that decimal fractions containing only 3 or 7 are only a part of the real numbers, then we get

${\displaystyle 2^{\aleph _{0}}\leq {\mathfrak {c}}\,.}$

and thus

${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}}\,.}$