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

- It was not until the 19th Century that mathematicians discovered that infinity comes in different sizes. Georg Cantor (1845 to 1918) defined the following.
- 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***The set***Z***of*(*positive, zero and negative*)*integers is countable.***Proof**

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

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

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

*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.*a*_{1}*a*_{2}*a*_{3}*a*_{4}*a*_{5}...

0.*b*_{1}*b*_{2}*b*_{3}*b*_{4}*b*_{5}...

0.*c*_{1}*c*_{2}*c*_{3}*c*_{4}*c*_{5}...

0.*d*_{1}*d*_{2}*d*_{3}*d*_{4}*d*_{5}...

...

and now define a decimal*x*=*x*_{1}*x*_{2}*x*_{3}*x*_{4}... by*x*_{1}≠*a*_{1}(or 9),*x*_{2}≠*b*_{2}(or 9),*x*_{3}≠*c*_{3}(or 9), etc.

Then the decimal expansion of*x*does not end in recurring 9's and it differs from the*n*th element of the list in the*n*th 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**

**Definition**

**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*_{1}be the first element of*B*to be counted. Then either*B*- {*b*_{1}} is empty, in which case the set is finite, or one can repeat the process to get*b*_{2},*b*_{3}, 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*_{1},**N**× {2} to count*A*_{2}, 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.

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**- If
*n*is a positive integer then √*n*is a root of*x*^{2}-*n*= 0 and so is algebraic.

- The real number √2 + √3 satisfies the equation (
*x*^{2}- 5)^{2}= 24*x*^{2}and so is also algebraic.

- If
**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.

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