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

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

We define ** m** ×

For the infinite cardinal ℵ_{0} you can use the results on countability to show that ℵ_{0} + ** m** = ℵ

Also, ℵ_{0} × ** m** = ℵ

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

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**^{ℵ0 } . 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 ℵ_{0}^{ℵ0} = **2**^{ℵ0}.

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**^{ℵ0} which is the same as **2**^{ℵ0}. This is often called ** C** : the cardinality of the

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

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

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) |