MT2002 Analysis

 Previous page (Farey sequences) Contents Next page (Continued fractions)

## 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 ℵ0. The symbol ℵ is called aleph and is the first letter of the Hebrew alphabet.

So all countable sets have cardinal ℵ0.

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 AB. 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 ℵ0 you can use the results on countability to show that ℵ0 + m = ℵ0 for any finite cardinal m, and indeed, ℵ0 + ℵ0 = ℵ0.

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

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 nm 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, ℵ0 × ℵ0 = ℵ02.

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 sT 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 20 . Cantor's diagonalisation argument shows that this is strictly greater than ℵ0.

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 ℵ00 = 20.

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 100 which is the same as 20. 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 2C and is strictly greater than C.

One question which mathematicians puzzled over for a long time was whether there was a cardinal between ℵ0 and 20 = 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!

 Previous page (Farey sequences) Contents Next page (Continued fractions)

JOC September 2001