Tuesday, November 15, 2022

Proving Uncountability Without Diagonalization

Cantor is famous for his diagonal proof of the uncountability of the real numbers. I just learned that his first proof was different. Here it is.

First some facts about the completeness of the reals. A bounded monotone sequence of real numbers must converge. That is, if a0 < a1 < a2 < ... < C are real numbers, then the sequence must converge to some point b ≤ C. Likewise, if the sequence is monotone decreasing.

Consequently, if we have a sequence of nested intervals, ie where each interval properly contains the next one, then the intersection must be nonempty. That is because the left endpoints form a bounded monotone sequence, and must converge to some point in all the intervals.

(I am being a little sloppy about whether the intervals are open or closed, ie whether they include the endpoints. It does not matter, as long as each interval is contained in the interior of the previous one. They cannot share an endpoint.)

Theorem If a0, a1, a2, ... is a sequence of real numbers, then there must be a real point not in the sequence.

Proof Removing duplicates if necessary, assume the numbers are all distinct. Let I0 be the interval determined by a0 and a1. Find the next two points in the sequence that are also in the interval, and let them define the interval I1. If that is not possible, then all the points inside I0 must be absent from the sequence.

Continuing, we get an infinite sequence of nested intervals, and so there must be a point in all of them. By the construction, that point cannot be in he original sequence of reals.

This proves that the real numbers are uncountable.

No comments: