How does one prove that there are more real numbers than integers? There are an infinite number of each, but the infinity of the real numbers is, in a strict sense, larger than the infinity of the integers. In math terminology, the set of reals has a larger cardinality. Roughly speaking, it’s equivalent to saying that it’s impossible to set up a correspondence that maps every real number to a different integer.
The standard proof of this fact is Cantor’s diagonalization method. I won’t go over it — you can read about it at Wikipedia, or any number of other places.
It’s a good proof. A classic. But something about it leaves some people unconvinced of its correctness. And there are many other proofs and plausibility arguments for the same thing, so it kind of bugs me that diagonalization seems to drown out everything else.
Here’s a method that I got from Gregory Chaitin’s book Meta Math, in which he used a variant of it. He credits the 1941 book What Is Mathematics?, by Courant and Robbins, for the idea. I assume it’s well known, for some value of “well known”.
Consider the real numbers from 0 to 1. Assume we have a list of all of them, indexed by the integers. It could look something like this:
| 0 | 0.31499447089717136482… |
| 1 | 0.94819431148498445799… |
| 2 | 0.74356562181529469704… |
| 3 | 0.12025639774223291162.. |
| 4 | 0.20109671714936909916… |
| 5 | 0.52817956338115809601… |
| 6 | 0.90446784130099615146… |
| 7 | 0.55419547424273376312… |
| … | … |
Consider the points on a number line that correspond to those numbers. I’ll only show a few points, but there would be an infinite number of them.
“Cover up” the first of those points with a cover of width 1/4, centered on the point. Cover the second with a cover of width 1/8, the third with a cover of width 1/16, and so on, with each cover being half the width of the previous one.
Continue that to infinity, and you’ll have covered up every number on the list. But the total width of all of the covers is just 1/4 + 1/8 + 1/16… = 1/2, so at least half of the line segment must remain uncovered. The real numbers corresponding to those non-covered points must not be on our list, contradicting our assumption that it contains all the real numbers in that interval. So, our assumption must be wrong, and no such list can exist.
(And of course, we can make the total width of the covers as small as we want, by making the starting width smaller.)
The way I presented this is not a formal proof, and it’s less “constructive” than diagonalization. But even so, I find it easier to grasp than the diagonalization method.
Entropymine 