Cardinal numbers

The cardinal numbers originated from Cantor's proof that there are `more' real numbers than integers. This was the start of the modern concept of mathematical infinity.

Cantor used a diagonalization argument to show there does not exist a function^3.3that assigned a unique integer to every real number. He assumed such a function,

, exists and used it to construct a real,

, not in the range of the function

This technique is proof my contradiction. If an assumption leads to a contradiction then the assumption must be false.

If there is a function that maps a unique integer onto each element of a set then that set is said to be countable. Cantor proved the reals are not countable.

We can limit the reals we consider to those between 0 and 1 since if we cannot map the integers unto these reals we obviously cannot map them onto all reals. A real number in this range can be represented as an infinitely long decimal fraction with the first digit just to the right of the decimal point as shown in Table 3.3.

Cantor showed how to construct a real,

, whose

th digit differed from the

th digit of the the real that was a mapped from

(

). We will write

for the

th digit of real

. Thus the the

th digit of the real

we are constructing is written as

. The

th digit of the real

is written as

. The real

Cantor defined satisfies the following:

In Section 4.9 we describe the counter point to Cantor's proof known as the Lowenheim Skolem Theorem. This shows that no matter how large the infinite sets a formal system claims to define there is a countable model that satisfies the axioms of the system if there is any model that does so. A model is a collection of sets for which the axioms of the formal system hold.

The reals have cardinality greater than the integers by Cantor's argument. It is unknown if there are cardinals larger than the integers and smaller than the reals. The assertion that there are none is called the Continuum Hypothesis. Cantor went mad trying to prove this. We know today it cannot be proved or disproved from the standard axioms of mathematics[10]. We think the Continuum Hypothesis is neither true nor false in an absolute sense. It may be true false or undecidable in a particular formal system.

The hierarchy of cardinal numbers is of practical importance because axioms asserting the existence of such sets solve problems that almost everyone agrees are meaningful like instances of the Halting Problem. So we now turn our attention to Gödel's result that leads to the hierarchy of unsolvable problems and suggests the creative nature of mathematics.

Table 3.3: Trying to map the integers onto the reals

tries to map integers to reals

0	. $\overline{0}$ 0000000000000000...
1	.1 $\overline{1}$ 111111111111111...
2	.22 $\overline{2}$ 22222222222222...
3	.333 $\overline{3}$ 3333333333333...
4	.4444 $\overline{4}$ 444444444444...
5	.55555 $\overline{5}$ 55555555555...
6	.666666 $\overline{6}$ 6666666666...
7	.7777777 $\overline{7}$ 777777777...
8	.88888888 $\overline{8}$ 88888888...
9	.999999999 $\overline{9}$ 9999999...
10	.1010101010 $\overline{1}$ 010101...
11	.12121212121 $\overline{2}$ 12121...
12	.131313131313 $\overline{1}$ 3131...
13	.1414141414141 $\overline{4}$ 141...
14	.15151515151515 $\overline{1}$ 51...
...	...

The above shows the start of a possible map from integers onto the reals. The digits along the diagonal have a line above them ( $\overline{0}$ ). We can construct a real that is different from every real in the list by making its th digit different from the th digit of the th real in the list. The digits that we have to differ from are .012345678912141... Any real that differs in every decimal position from this number cannot be in the list. Thus the real .101111111101010... constructed by putting 1 in every position that was not 1 on the diagonal and 0 in the remaining positions. This real will differ in at least one digit from every number in the list.