In this edition of Occupy Math we are going to look at a famous mathematical concept, the Cantor diagonal argument. This argument logically demonstrates that there are at least two different sizes of infinity. It also uses a useful logical technique called proof by contradiction which sounds much more contentious than it actually is. The existence of multiple sizes of infinity was discovered by Georg Cantor in 1891, a period in which math was getting not so much real as surreal, where it has stayed ever since.
Proof by Contradiction
This technique of logical argument is a little bit inside-out, but easy to understand. You start by assuming the logical opposite of what you want to prove is true. You then argue, from that assumption, to something that is impossible or contradictory. This then demonstrates, logically, that your initial assumption was wrong and so demonstrates that its opposite, a.k.a. the thing you really wanted to prove, is true. The application of this technique in the Cantor diagonal argument shows how much power this technique can have in the right place.
The logic behind proof by contradiction shows up in the real world. Take the concept of an alibi. You want to prove someone was not anywhere near where a crime was committed. You take the assumption that your person of interest was near the crime scene, but then provide evidence he was somewhere far removed from the place of the crime at the time of the crime, which is impossible because people cannot be in two places at once. This sort of contradiction is so intuitive and obvious that it does not require the formal structure of proof by contradiction, but it does help illustrate the logic.
Types of Infinity
Lets start with a simple example of infinity. There are an infinite number of counting numbers: 1, 2, 3, 4, 5, … and on and on, forever. The counting numbers, as a set, are an example of the simplest form of infinity called a countable infinity. The formal definition of a countable infinity is an infinite set with the added property that it is possible to number the members of the set so that you will reach any one, particular member of the set in a finite number of steps. In other words, you can number the set so that each member of the set gets assigned a finite number. One danger here is that some care may be needed. If, for example, you are trying to number the counting numbers and start by numbering all the even numbers first, you will never get to the odd ones. Infinity leads to a lot of weirdness like this.
Now consider the set of numbers between zero and one. This is everything that starts with “Zero-decimal point” and then has digits. We will add zeros to the end whenever a number has a finite number of digits so that every one of these numbers has an infinite number of digits. The decimal form of 1/2 is 0.5 but we will use the very inefficient form 0.500000000000000 … please trust Occupy Math: there is a reason for doing this. Many of the numbers are already like this. The decimal form of 1/3 is 0.333333333333… and goes on forever without needing zeros. Anyhow we are now considering the numbers between zero and one as infinite strings of digits. Next up: the proof by contradiction.
Assume that the set of numbers between 0 and 1 is infinite and countable. Then we can number them first, second, third and so on, in such a fashion that every number appears in the list. To make things easy, we will given them the names: r1 for the first, r2 for the second, r3 for the third, and so on. This means that we have the numbers between zero and one all listed as
r1, r2, r3, r4, r5, …The “…” means “and so on”. Now that we have this list, what do we do with it?
Build a new number q that starts with “zero-decimal point” and then has digits as follows. The first digit of q after the decimal is nine minus the first digit of r1. The second digit of q is nine minus the second digit of r2. The third digit of q is nine minus the third digit of r3. Keep going like this for all the different numbers rwhatever in our list. The mechanic of taking nine minus a digit just insures that we will use a different digit than the one we got from the number in our list. The following deductions are now possible:
- The number q is between zero and one. This is because it starts “0.” and has at least some non-zero digits.
- Because of the way we constructed it, the number q is different from every number in the list we made (of all numbers between zero and one). Notice q must disagree with every number on the list at (at least) one of its digits.
- This means that the number q is not anywhere in the list.
- If the numbers between zero and one form an infinite set that is countable, then it is possible to construct the list so that all the numbers between zero and one are on the list (that’s the definition of “countable infinity”).
- This means our assumption that the numbers between zero and one form a countable infinite set is false.
To recap: we used the list we got by counting through the numbers between zero and one, together with the trick of taking nine minus a digit of each number on the list, to construct a new number q that was between zero and one but which could not be on the list.
Since an infinite set cannot be smaller than countable, it follows that the set of numbers between zero and one is larger than countable! In particular, this tells us that there is at least one type of infinity both different from and larger than a countable infinity. This fact was one of the things that made math seem, to both its practitioners and the parts of the general public that kept up, to be getting out of control. In fact, the getting out of control had just barely begun. If you generalize the diagonal argument, you can use it to construct a larger infinity from any infinity and a whole hierarchy of different sizes of infinity springs up. This, however, is a topic for another day.
There is a good chance that you were able to follow the steps of Cantor’s diagonal argument and, possibly, that the conclusions it yields makes sense to you. The argument is not that complex. If you didn’t follow it, try reading it again, or even writing out some of it with pencil and paper. Understanding this kind of math isn’t immediate and can take a couple tries.
The hard part of the argument is accepting its implications. You cannot just blithely say “infinity” any more; you may need to worry about which infinity you are talking about. The topic is not purely abstract, either. The set of distances is an uncountable infinity, for example, as is the set of directions. There is also the ever-vexing question, “How did Cantor think of that argument?”
Occupy Math hopes that this trip into the history of math to harvest one of our really odd facts has been broadening. The work of Georg Cantor contains many other weird discoveries, like the Cantor Set, and his work on logic and infinity were picked up by others like Kurt Gödel about whom Occupy Math has already written. Remember, Occupy Math likes getting topics from readers. Please comment or tweet!
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics