Cardinality of the continuum

The real numbers ${\displaystyle \mathbb{R}}$ are more numerous than the natural numbers ${\displaystyle \mathbb{N}}$. Moreover, ${\displaystyle \mathbb{R}}$ has the same number of elements as the power set of ${\displaystyle \mathbb{N}}$. Symbolically, if the cardinality of ${\displaystyle \mathbb{N}}$ is denoted as ${\displaystyle {\mathrm{\aleph }}_0}$, the cardinality of the continuum is

${\displaystyle \mathfrak{c}=2^{{\mathrm{\aleph }}_0}>{\mathrm{\aleph }}_0.}$

This was proven by Georg Cantor in his uncountability proof of 1874, part of his groundbreaking study of different infinities. The inequality was later stated more simply in his diagonal argument in 1891. Cantor defined cardinality in terms of bijective functions: two sets have the same cardinality if, and only if, there exists a bijective function between them.

Between any two real numbers a < b, no matter how close they are to each other, there are always infinitely many other real numbers, and Cantor showed that they are as many as those contained in the whole set of real numbers. In other words, the open interval (a,b) is equinumerous with ${\displaystyle \mathbb{R}}$, as well as with several other infinite sets, such as any n-dimensional Euclidean space ${\displaystyle {\mathbb{R}}^n}$ (see space filling curve). That is,

${\displaystyle |(a,b)|=|\mathbb{R}|=|{\mathbb{R}}^n|.}$

The smallest infinite cardinal number is ${\displaystyle {\mathrm{\aleph }}_0}$ (aleph-null). The second smallest is ${\displaystyle {\mathrm{\aleph }}_1}$ (aleph-one). The continuum hypothesis, which asserts that there are no sets whose cardinality is strictly between ${\displaystyle {\mathrm{\aleph }}_0}$ and ${\displaystyle \mathfrak{c}}$, means that ${\displaystyle \mathfrak{c}={\mathrm{\aleph }}_1}$. This hypothesis is independent of the widely used Zermelo–Fraenkel set theory with axiom of choice (ZFC); that is, ZFC can neither prove that it is true nor that it is false.

Properties

Uncountability

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 {\mathrm{\aleph }}_0}$:

${\displaystyle {\mathrm{\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.

Cardinal equalities

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 \mathrm{\wp }(\mathbb{N})}$ of the natural numbers ${\displaystyle \mathbb{N}}$ is uncountable). In fact, the cardinality of ${\displaystyle \mathrm{\wp }(\mathbb{N})}$, by definition ${\displaystyle 2^{{\mathrm{\aleph }}_0}}$, is equal to ${\displaystyle \mathfrak{c}}$. This can be shown by providing one-to-one mappings in both directions between subsets of a countably infinite set and real numbers, and applying the Cantor–Bernstein–Schroeder theorem according to which two sets with one-to-one mappings in both directions have the same cardinality. In one direction, reals can be equated with Dedekind cuts, sets of rational numbers, or with their binary expansions. In the other direction, the binary expansions of numbers in the half-open interval ${\displaystyle [0,1)}$, viewed as sets of positions where the expansion is one, almost give a one-to-one mapping from subsets of a countable set (the set of positions in the expansions) to real numbers, but it fails to be one-to-one for numbers with terminating binary expansions, which can also be represented by a non-terminating expansion that ends in a repeating sequence of 1s. This can be made into a one-to-one mapping by that adds one to the non-terminating repeating-1 expansions, mapping them into ${\displaystyle [1,2)}$. Thus, we conclude that

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

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

${\displaystyle {\mathfrak{c}}^2=(2^{{\mathrm{\aleph }}_0}{)}^2=2^{2\times {\mathrm{\aleph }}_0}=2^{{\mathrm{\aleph }}_0}=\mathfrak{c}.}$

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

${\displaystyle {\mathfrak{c}}^{{\mathrm{\aleph }}_0}={{\mathrm{\aleph }}_0}^{{\mathrm{\aleph }}_0}=n^{{\mathrm{\aleph }}_0}={\mathfrak{c}}^n={\mathrm{\aleph }}_0\mathfrak{c}=n\mathfrak{c}=\mathfrak{c}}$

where n is any finite cardinal ≥ 2 and

${\displaystyle {\mathfrak{c}}^{\mathfrak{c}}=(2^{{\mathrm{\aleph }}_0}{)}^{\mathfrak{c}}=2^{\mathfrak{c}\times {\mathrm{\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}}$.

Alternative explanation for 𝔠 = 2א‎0

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

1/2 = 0.50000... 1/3 = 0.33333... π = 3.14159....

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

In any given case, the number of decimal places 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 decimal place of π. Since the natural numbers have cardinality ${\displaystyle {\mathrm{\aleph }}_0,}$ each real number has ${\displaystyle {\mathrm{\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}\le {\mathrm{\aleph }}_0\cdot {10}^{{\mathrm{\aleph }}_0}\le 2^{{\mathrm{\aleph }}_0}\cdot {(2^4)}^{{\mathrm{\aleph }}_0}=2^{{\mathrm{\aleph }}_0+4\cdot {\mathrm{\aleph }}_0}=2^{{\mathrm{\aleph }}_0}}$

where we used the fact that

${\displaystyle {\mathrm{\aleph }}_0+4\cdot {\mathrm{\aleph }}_0={\mathrm{\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^{{\mathrm{\aleph }}_0}\le \mathfrak{c}}$

and thus

${\displaystyle \mathfrak{c}=2^{{\mathrm{\aleph }}_0}.}$