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: ¹/₂ n if n is even, ¹/₂ (n - 1) if n is odd.
   
   
   
2. The set N × 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, ¹/₁ = ²/₂ 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.a₁a₂a₃a₄a₅...
0.b₁b₂b₃b₄b₅...
0.c₁c₂c₃c₄c₅...
0.d₁d₂d₃d₄d₅...
...
and now define a decimal x = x₁x₂x₃x₄... by x₁≠ a₁ (or 9), x₂≠ b₂ (or 9), x₃≠ c₃ (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 ⊆ A then count through the elements of A leaving out those which are not in B.
   More rigorously, let b₁ be the first element of B to be counted. Then either B - {b₁} is empty, in which case the set is finite, or one can repeat the process to get b₂ , b₃ , etc.
   
   
   

   Theorem
   

   A countable union of finite or countable sets is finite or countable.
   That is, if the sets A_i 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 × N is countable.
   Since I is countable we may as well take I = N. Then use N × {1} to count A₁ , N × {2} to count A₂ , etc.
   If the A_i overlap, leave out any elements counted already and one gets a one-one correspondence between a subset of N × N which is thus countable by the last result.
   
   
   

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 √n is a root of x² - n = 0 and so is algebraic.
   
2. The real number √2 + √3 satisfies the equation (x² - 5)² = 24 x² 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 × Q × ... × Q (n+ 1 times). This is countable by an extension of the above result about N × 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 π 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 ≠ 0, 1) and x is irrational then a^x is transcendental. This was proved by Gelfond in 1934.