Here’s Mathematician KP Hart’s Math Question and Answer for Monday, December 21st!

### Counting, Part 4

We will look at the proof that Cantor gave of the theorem that R, the set of real numbers is uncountable. We must show that there is no way to couple natural numbers to real numbers in such a way that every natural number goes with exactly one real number and every real number goes with exactly one natural number.

Cantor formulated it thus: assume we are given a sequence x0, x1, …, xn, … of real numbers. Then we can find in every interval (α,β) a real number η that does not occur in the sequence. This shows that any attempt at coupling natural and real numbers will leave many real numbers disappointed (or not, if they like to be alone).

The proof goes as follows. Look at the terms of the sequence; if possible we take natural numbers m and n with xm and xn in (α,β) and xm≠xn: we let m be the first natural number with xm∈(α,β) and then we let n be the first natural number, larger than m, such that xn∈(α,β) and xm≠xn. If this is not possible then there is at most one term of the sequence of the sequence in (α,β) and then we have very many candidates for η. We do not know whether xm<xn or the other way around; but in the first case we write α0=xm and β0=xn, and in the opposite case α0=xn and β0=xm: so α0 is the minimum of the two and β0 is the maximum. Before we continue we note that because of the choice of m and n we know that xi∉(α00) for all i≤n: if i≠m,n then xi is not even in (α,β). In addition we have 0≤m<n, so l≥1 and we are sure that x0 and x1 are not in (α00).

We repeat this: take the first k such that xk∈(α00) and then the first l for which xl∈(α00) and xl≠xk. The smallest of the two we call α1 and the largest we call β1. Nu we know, as above, that xi∉(α11) when i≤l; also l≥3 so x2 and x3 are certainly not in (α11)

We keep doing this: is when we have found (αii) we make (αi+1i+1) by taking the first two different terms of the sequence that are in αii) and calling the smallest αi+1 and the largest βi+1. Now note that these terms are at least numbers 2i+2 and 2i+3 in the sequence so that x2i+2 and x2i+3 are not in (αi+1i+1).

If the above can not be done at some i then this is because there are not enough terms of the sequence in (αii); in that case the proof is finished because there are many candidates for η. If we can execute the process for every natural number i the we obtain a decreasing sequence of intervals (α00) … (αii) … There is then a real number η with the property that αi<η<βi for all i. But because x2i, x2i+1∉(αii) for all i it follows that η does not occur in the sequence.

This result was and is groundbreaking; it shows that “infinitely many” is an ambiguous expression: there are infinite sets that do not have the same size. About fifteen years later Cantor showed that the infinite is much richer: for every set you can make an other one that has strictly more elements. We will see how that goes next time.

*********************************

Read all of KP Harts math questions here!

About Dutch Mathematician KP Hart: In the beginning of this year the Dutch government opened a website, The Dutch Science Agenda, where everyone could post questions that they thought were of scientific interest. This was an attempt to involve the whole country in determining what the Dutch science agenda should be in the coming years.

I looked through the questions and searched for terms like `mathematics’, `infinity’ … to see what mathematical questions there were and I noticed various questions that already have answers (and have had for a long time). On a whim I decided to post answers to those questions, in Dutch. For your edification I will translate these posts into English.