Cardinal numbers

As well as the idea of countability, Georg Cantor introduced the concept of a cardinal number. Two sets have the same cardinal number if there is a one-one correspondence between them. So finite cardinals look the same as ordinary integers. It's when we get to infinite sets that things get interesting.

Cantor defined the cardinal of the natural numbers N to be ℵ₀. The symbol ℵ is called aleph and is the first letter of the Hebrew alphabet.

So all countable sets have cardinal ℵ₀.

You can do arithmetic with cardinals as follows.

If disjoint sets A and B have cardinals m and n, then we define m + n to be the cardinal of the union A ∪ B. It should be clear that for finite cardinals this agrees with the usual definition.

We define m × n to be the cardinal of the Cartesian product A × B. Again this agrees with the usual definition for finite sets.

For the infinite cardinal ℵ₀ you can use the results on countability to show that ℵ₀ + m = ℵ₀ for any finite cardinal m, and indeed, ℵ₀ + ℵ₀ = ℵ₀.

Also, ℵ₀ × m = ℵ₀ for any finite cardinal m, and ℵ₀ × ℵ₀ = ℵ₀.

If sets A and B are finite then we can count the number of maps from A to B by observing that we have a choice of |B| elements of B to which we can map every element of A.
Hence if the sets A and B have cardinals m and n, then we define n^m to be the cardinal of the set of maps from A to B. Then we get the usual results for finite cardinals and can verify that, for example, ℵ₀ × ℵ₀ = ℵ₀².

Now things get a little tricky. A subset T of a set S can be represented by a map from S to the two element set {0, 1}, by mapping s to 1 if s ∈ T and mapping it to 0 otherwise. So the set of subsets of N is in one-one correspondence with the set of maps from N to this two element set. So this set has cardinal 2^ℵ₀ . Cantor's diagonalisation argument shows that this is strictly greater than ℵ₀.

Note that a map from N to N can be considered as a certain subset of N × N and so the set of all maps from N to N is contained in the set of subsets of the countable set N × N. Hence we may show that ℵ₀^ℵ₀ = 2^ℵ₀.

You can identify the decimal expansion of a real number in the interval [0, 1] with a map from N to the ten-element set of decimal digits. So the cardinality of the set R of real numbers is the same as 10^ℵ₀ which is the same as 2^ℵ₀. This is often called C : the cardinality of the continuum.

With a bit of effort one may verify that cardinality of the set of all functions from R to R is 2^C and is strictly greater than C.

One question which mathematicians puzzled over for a long time was whether there was a cardinal between ℵ₀ and 2^ℵ₀ = C. The conjecture that there was no set with such a cardinal is called the Continuum Hypothesis.

This was the first of the famous set of questions that David Hilbert posed in 1900. In 1940 the Austrian mathematician Kurt Gödel showed that this could not be disproved using the other axioms of Set Theory. Then in 1963, the American mathematician Paul Cohen proved that it could not be proved either. So one may either accept it or deny it.

Cantor also devised a theory of ordinal numbers (associated with ordered rather than unordered sets). As with the cardinal numbers, these coincide with N for finite sets, but for infinite sets, you get some really wild stuff!