Next: Gödel's Incompleteness Theorem Up: Mathematical structure Previous: Infinity   Contents

# Cardinal numbers

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

George Cantor used a diagonalization argument to show there does not exist a function5.2that 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 by 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.

In giving Cantor's proof one can limit the reals to those between 0 and 1 since, if these cannot be mapped uniquely to the integers, it is impossible to do so for a more inclusive set such as 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 5.3.

Cantor showed how to construct a real, , whose th digit differed from the th digit of the the real that was mapped from by which is . The th digit of the real is written as . The th digit of the real is written as . The real Cantor defined satisfies the following:

differs in its th digit from for every integer . Thus it differs from every real in the range of . An example is shown in Table 5.3. The assumption that is a function that has the integers as its domain and all reals as its range is false.

Section 6.10 describes the counter point to Cantor's proof known as the Lowenheim Skolem Theorem. This shows that no matter how large the infinite sets a mathematical 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 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. We know today it cannot be proved or disproved from the standard axioms of mathematics[14]. I believe the Continuum Hypothesis is neither true nor false in an absolute sense. In a sense I think it is the modern version of the parallel postulate. It may be true false or undecidable in a particular formal system, just as the parallel postulate may be true or false in a particular geometry.

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. For example such axioms can solve instances of the Halting Problem. To see how this is possible we now turn our attention to Gödel's result. It was the starting point for developing the hierarchy of unsolvable problems. I think it is the key to revealing the fundamentally creative nature of mathematics.

Table 5.3: Trying to map the integers onto the reals
 tries to map integers to reals 0 .0000000000000000... 1 .1111111111111111... 2 .2222222222222222... 3 .3333333333333333... 4 .4444444444444444... 5 .5555555555555555... 6 .6666666666666666... 7 .7777777777777777... 8 .8888888888888888... 9 .9999999999999999... 10 .1010101010010101... 11 .1212121212112121... 12 .1313131313133131... 13 .1414141414141141... 14 .1515151515151551... ... ...

The above shows the start of a possible map from integers onto the reals. The digits along the diagonal have a line above them (). One 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 the constructed real has 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.