Cardinality and Infinities

Cardinality is about measuring how many elements there are in a set. For finite sets it is simple: the cardinality is just the number of elements. For infinite sets it becomes more interesting, because not all infinities are the same size.

Finite sets

If $ \large A = \{1,2,3,4\}$, the cardinality is:

$$ \large |A| = 4 $$

Here it is simply a matter of counting the elements.

Countably infinite sets

A set is countably infinite if its elements can be listed so that each element gets a number: $1,2,3,\ldots$. That is, there exists a one-to-one correspondence between the set and the natural numbers $ \large \mathbb{N}$.

Examples:

The natural numbers: $ \large \mathbb{N} = \{1,2,3,\ldots\}$.
The integers: $ \large \mathbb{Z} = \{\ldots,-2,-1,0,1,2,\ldots\}$.
The rational numbers: $ \large \mathbb{Q} = \left\{\frac{p}{q} \,\middle|\, p,q \in \mathbb{Z}, q \neq 0\right\}$.

All these sets are infinite, but they can still be arranged in a list, which makes them countable.

Uncountable sets

Some sets are so large that they cannot be listed. They are called uncountable. The classic example is the set of real numbers $ \large \mathbb{R}$.

One can show that even between 0 and 1 there are infinitely many real numbers, and they cannot be numbered. This was proven by Georg Cantor with the famous diagonalization trick.

Cantor's diagonalization

Suppose we could list all real numbers between 0 and 1:

0.12345...

0.45012...

0.99999...

0.30147...

0.77777...

...

We now take the diagonal sequence of digits: $1, 5, 9, 4, 7, \ldots$. For each of these digits we make a change, e.g. by adding 1 (and replacing 9 with 0).

Thus a new number is constructed:

$$ \large 0.26058\ldots $$

This number is different from all on the list, because it differs in at least one digit from each number (the diagonal digit). Therefore no complete list of the real numbers in the interval $[0,1]$ can exist. The set of real numbers is therefore uncountable.

Sizes of infinity

The cardinality of the natural numbers is denoted $ \large \aleph_0$ (aleph-null). All countably infinite sets have this cardinality.

The cardinality of the real numbers is larger and is called the cardinality of the continuum, often written as $ \large \mathfrak{c}$.

Thus there are several “sizes” of infinity: one infinite set can be “smaller” than another infinite set, measured by cardinality.

The continuum hypothesis

We have seen that the natural numbers $ \large \mathbb{N}$ have cardinality $ \large \aleph_0$, and that the real numbers $ \large \mathbb{R}$ have a larger cardinality, called the continuum $ \large \mathfrak{c}$.

The continuum hypothesis (CH) asks the question: does there exist a set whose cardinality lies between the two?

$$ \large \aleph_0 < |X| < \mathfrak{c} \;? $$

If such a set exists, it would be “larger” than the countable infinities, but still “smaller” than the real numbers. Cantor believed the answer was no, i.e. that there is no set with a cardinality between $ \aleph_0$ and $ \mathfrak{c}$. This is called the original continuum hypothesis.

The problem is famous because it cannot be decided within the usual rules of set theory. These rules are called ZFC (Zermelo–Fraenkel set theory with the Axiom of Choice) and are used as the foundation of modern mathematics. Gödel showed in 1940 that the continuum hypothesis cannot be disproved in ZFC, and Cohen showed in 1963 that it also cannot be proved. This means the hypothesis is undecidable in ZFC.

In other words: the continuum hypothesis is a question that cannot be answered with the axioms we normally build mathematics on. One can choose to extend the system and assume the hypothesis is true, or that it is false – both are mathematically consistent.

Therefore it is one of the most fascinating examples of questions lying at the very boundary of what we can prove.