Georg Cantor: Diagonal Method
This chapter discusses the famous diagonal method of Georg Cantor to prove that the real numbers are uncountable. Two variants on the classic proof are presented, one involving probability.
- PDF / 241,885 Bytes
- 4 Pages / 441 x 666 pts Page_size
- 0 Downloads / 237 Views
15
Georg Cantor discovered his famous diagonal proof method, which he used to give his second proof that the real numbers are uncountable. It is a curious fact that Cantor’s first proof of this theorem did not use diagonalization. Instead it used concrete properties of the real number line, including the idea of nesting intervals so as to avoid overlapping a given countable sequence. This brings us to discuss the famous second proof: the diagonal method of Cantor. In my teaching experience, students find it hard to believe Cantor’s diagonal method. Perhaps it is my fault, but I have talked to others who teach the same result, and I hear the same comments. The diagonal method is elegant, simple, and deep. Students usually follow the method line by line, but I am sure that many really fail to get it. Perhaps that it is a proof by contradiction makes it hard to follow? But, they seem to get other proofs by contradiction. Or is the key problem that it is about infinities? Here is an interesting quote by the logician Wilfrid Hodges: I dedicate this essay to the two-dozen-odd people whose refutations of Cantor’s diagonal argument have come to me either as referee or as editor in the last twenty years or so. Sadly these submissions were all quite unpublishable; I sent them back with what I hope were helpful comments. A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument—what had it done to make them angry with it? So I started to keep notes of these papers, in the hope that some pattern would emerge. These pages report the results.
You might enjoy his essay—it is a careful treatment of some of the issues that people have in following Cantor’s famous argument. Let’s turn to prove the famous result.
15.1
Proofs
I will give two different proofs that the reals are not countable. Actually, I will prove the statement that no countable list of infinite sequences of 0–1’s can include all such sequences. R.J. Lipton, K.W. Regan, People, Problems, and Proofs, DOI 10.1007/978-3-642-41422-0_15, © Springer-Verlag Berlin Heidelberg 2013
83
84
15
Georg Cantor: Diagonal Method
This is enough because of two observations. First, it is enough to show that the interval [0, 1] is uncountable. Second, the reals in the interval have the same cardinality as the set of all of the infinite 0–1 sequences. The first proof is essentially the famous diagonal proof, with a slight—very slight—twist. The second is a proof based on probability theory.
15.2
A Variant of the Classic Proof
Consider the following triangular array of bits that has an infinite number of rows: s 1 (1) s 2 (1) s 3 (1) .. .
s 2 (2) s 3 (2)
s 3 (3)
The ith row is s i (1) s i (2) . . . s i (i) where each s i (j ) is a 0 or a 1. Our plan is to construct an infinite sequence t (n) that is different from each row. Let’s construct t. We need that t is different from s 1 (1) so there is no choice: set t (1) equal to ¬s 1 (1). Note, there was no choice here: often the lack of choice is a good thing.
Data Loading...
