MT2002 Analysis

Previous page
(Functions)
Contents Next page
(Axioms for the Real numbers)

Infinity and infinities

It was not until the 19th Century that mathematicians discovered that infinity comes in different sizes. Georg Cantor (1845 to 1918) defined the following.

Definition

Any set which can be put into one-one correspondence with N is called countable.

Remarks

Given such a set, one can count off its elements: 1st, 2nd, 3rd, .. and will eventually reach any element of the set.
We will see later that many infinite sets are countable but that some are not.
Some versions of the above definition include finite sets among the countable ones, but we will (mostly) not do so.

Examples of some countable sets

  1. The set Z of (positive, zero and negative) integers is countable.

    Proof
    Here is a counting. That is, we list the elements

    N  1  2  3  4  5  6  7 ...
    Z  0  1 -1  2 -2  3 -3 ...
    You can (if you wish) write down a formula: 1/2 n if n is even, 1/2 (n - 1) if n is odd.


  2. The set N cross N is countable.

    Proof
    Count the points with integer coefficients in the positive quadrant as shown. (The formula is now rather tricky to write down.)



  3. The set Q of all rationals is countable.

    Proof
    Write down a positive rational x/y at the point (x, y) in the plane and count as in the last example, except that you can leave out a point if you have already counted the rational. You have to do this because, for example, 1/1 = 2/2 etc.

    This will count all the positive rationals. Then use the same trick as in example 1 to count all the rationals.



The amazing insight achieved by Cantor is the following result.

Theorem (Cantor 1874)
The set of real numbers R is not countable.

Proof
We will show that the set of reals in the interval (0, 1) is not countable.
This proof is called the Cantor diagonalisation argument.

Suppose we could write down all the decimal expansions of the reals in (0, 1) in a list:
0.a1a2a3a4a5...
0.b1b2b3b4b5...
0.c1c2c3c4c5...
0.d1d2d3d4d5...
...
and now define a decimal x = x1x2x3x4... by x1noteq a1 (or 9), x2noteq b2 (or 9), x3noteq c3 (or 9), etc.
Then the decimal expansion of x does not end in recurring 9's and it differs from the nth element of the list in the nth decimal place. Hence it represents an element of the interval (0, 1) which is not in our counting and so we do not have a counting of the reals in (0, 1).


Some properties of countability

  1. Theorem
    A subset of a countable set is either finite or countable.

    Proof
    If A is countable and B subset A then count through the elements of A leaving out those which are not in B.
    More rigorously, let b1 be the first element of B to be counted. Then either B - {b1} is empty, in which case the set is finite, or one can repeat the process to get b2 , b3 , etc.


  2. Theorem
    A countable union of finite or countable sets is finite or countable.
    That is, if the sets Ai are finite or countable for each i in the finite or countable set I then is finite or countable.

    Proof
    This is based on the fact that N cross N is countable.
    Since I is countable we may as well take I = N. Then use N cross {1} to count A1 , N cross {2} to count A2 , etc.
    If the Ai overlap, leave out any elements counted already and one gets a one-one correspondence between a subset of N cross N which is thus countable by the last result.



One of the amazing consequences of Cantor's work is that it proves the existence of a class of real numbers which previously had been very difficult to investigate.

Definition

A real number is called algebraic if it is a root of a polynomial with rational (or integer) coefficients.
Other real numbers are called transcendental.

Examples

  1. If n is a positive integer then sqrtn is a root of x2 - n = 0 and so is algebraic.
  2. The real number sqrt2 + sqrt3 satisfies the equation (x2 - 5)2 = 24 x2 and so is also algebraic.

Theorem (Cantor)
The set of algebraic numbers is countable. Hence there are uncountably many transcendental numbers.

Proof
Since a polynomial of degree n with rational coeficients has (n+ 1) coefficients, such polynomials can be put into one-one correspondence with Q cross Q cross ... cross Q (n+ 1 times). This is countable by an extension of the above result about N cross N and so there are only countably many such polynomials. Such a polynomial can have at most n roots and so there are only countably many such roots.
Finally, the set of all such roots is the union over n of the roots of polynomials of degree n and so there are countably many of these.


Remarks

Many mathematicians found this proof of the existence of transcendentals rather unsatisfactory.
In 1851, Liouville was the first to prove the existence of a transcendental. He prove that the number 0.110001000... (with a 1 in the n! place and 0 elsewhere is transcendental.
In 1873, Hermite proved that e is transcendental.
In 1882, Lindemann proved that p is transcendental.
In 1900, Hilbert published a famous set of problems to challenge mathematicians in the new century. The 23rd problem was to prove that if a is algebraic (a noteq 0, 1) and x is irrational then ax is transcendental. This was proved by Gelfond in 1934.


Previous page
(Functions)
Contents Next page
(Axioms for the Real numbers)

JOC September 2002