Proof That Not All Infinities Are The Same Size

The proof is as follows: we count by matching the natural numbers to some set. For example, the set:

has three elements in it; we match each bullet with a natural number: and the last number is 3.

In infinite sets, we do the same thing. For example, the number of squares and the number of natural numbers is the same. To show this rather odd result, consider the following matching: 

	1	4	9	16	25	36	...

	^	^	^	^	^	^	
	|	|	|	|	|	|	
	v	v	v	v	v	v	

	1	2	3	4	5	6	...
You can continue this matching; as you can see, every natural number gets a unique square, so the number of squares and the number of natural numbers is the same. (Another way of putting this is that every natural number has a square, and every square is associated with a natural number).

How about the rational numbers? It might seem that the set of all rationals, like 3/8 and 5/9 and 12321/98732 would be much larger than the set of natural numbers. However, you can match them up. The proof is fairly simple, but difficult to format in html. But here's a variant, which introduces an important idea: matching each number with a natural number is equivalent to writing an itemized list. Let's write our list of rationals as follows:

  1. 0/1
  2. 0/2
  3. 1/1
  4. 0/3
  5. 1/2
  6. 2/1
  7. 0/4
  8. 1/3
  9. 2/2
  10. 3/1
and so on. Notice that first we list all the fractions whose numerator and denominator add to 1, then those that add to 2, then those that add to three, etc. Every fraction is somewhere on this list (and a little elementary arithmetic sequence calculation can tell you exactly where on the list a fraction like 12321/98732 would appear...an exercise I'll leave to the alert reader).

Now for the real numbers. Cantor's first proof is complicated, but his second is much nicer and is the standard proof today. Again, suppose we could list every one of the real numbers. A list might look like this:

  1. 0.3249187....
  2. 1.3289713....
  3. 3.1415926....
  4. 2.7182813....
  5. 0.2349873....
  6. 0.3987423....
and so on. If we suppose this list is complete, we can write a real number that is not on the list. We'll make the real number this way: here's our list again, with certain numbers highlighted:
  1. 0.3249187....
  2. 1.3289713....
  3. 3.1415926....
  4. 2.7182813....
  5. 0.2349873....
  6. 0.3987423....
Now, our new number will be constructed in the following manner: take each highlighted number, and add 1 to it. That will be the corresponding decimal digit in our new number. (If the result is 10, use 0). Thus, the new number is:
0.432393...
which is different from every number on the list: it's different from the first number in the first decimal place; from the second in the second decimal place, and so on. So it's not on our supposedly complete list of numbers. Thus our list is not complete, and no list of real numbers would be complete.

How about the points in the plane? You can describe any point in the plane with two coordinates. Suppose we're talking about the point (0.2132... , 0.9879...). This can get matched to the real number 0.29183727... Thus, every point in the plane is "counted" by a real number. An obvious extension says that the number of points in n-dimensional space is the same as the number of points on the line segment (0,1).

For a nice proof (with pictures) of these ideas, I can think of no more accessible source than George Gamow's One, Two, Three...Infinity. The science in the book is hopeless dated, but the mathematics (which make up the first and last sections) are still superb.

Return to Jeff's home page