Earliest diagonal proof of the uncountability of the reals. - MathOverflow

Earliest diagonal proof of the uncountability of the reals.

2010-05-08T19:38:50Z

I cited the diagonal proof of the uncountability of the reals as an example of a `common false belief' in mathematics, not because there is anything wrong with the proof but because it is commonly believed to be Cantor's second proof. The stated purpose of the paper where Cantor published the diagonal argument is to prove the existence of uncountable infinities, avoiding the theory of irrational numbers. I have no problem believing that Cantor himself realized that a diagonal proof of the uncountability of R was possible but I have not even found an allusion to this in his collected works. The earliest appearance in print that I know is on page 43 of The theory of sets of points by W. H. Young and Grace Chisholm Young (1906). I would be very grateful for any reference to some scrap of paper where Cantor himself mentions the possibility of using the diagonal method to prove the set of reals uncountable.

Answer by Jason Dyer for Earliest diagonal proof of the uncountability of the reals.

2010-05-08T21:07:05Z

From Labyrinth of thought: a history of set theory and its role in modern mathematics by José Ferreirós and José Ferreirós Domínguez:

page 184 (quoting a margin note of Cantor's)

Besides, the theorem of paragraph 2 presents itself as the reason why the collections of real numerical magnitudes that constitute what is called a continuum (say all real numbers that are greater or equal to 0 and less than or equal to 1) cannot be univocally correlated with the collection (v) [of all natural numbers]; thus I find the clear distinction between a continuum and a collection of the kind of the totality of all real algebraic numbers.

The book also discusses why this was a margin note and not Cantor's main concern: His goal was a new proof of Liouville's theorem that within any given interval there are infinitely many transcendent numbers.

Answer by Harald Hanche-Olsen for Earliest diagonal proof of the uncountability of the reals.

2010-05-08T21:15:54Z

Edit: A closer look reveals that the proof in the reference below is not the diagonal proof. I am leaving the answer up since the reference might be of interest anyhow.

Cantor had a paper in Crelle's Journal 77 (1874) 258–262. In Christopher P. Grant's translation, the title of the paper is On a Property of the Class of all Real Algebraic Numbers. In §2, we can read

If an inﬁnite sequence of distinct real numerical quantities $$\omega_1, \omega_2,\ldots,\omega_\nu,\ldots\qquad(4)$$ (obtained according to whatever rule) is given, then in each prespeciﬁed interval $(\alpha\ldots\beta)$ a number $\eta$ (and consequently inﬁnitely many such numbers) can be speciﬁed, which does not occur in the sequence (4); this will now be proven.

I am not sure where I found the translation. Sloppy of me.

2nd Edit: here is a very brief outline of Cantor's non-diagonal proof. By induction on $k$, find $\alpha_k$ , $\beta_k$ as early as possible from the given sequence with $$\alpha<\alpha_1<\alpha_2<\cdots<\beta_2<\beta_1<\beta$$ and note that any number the the closed interval $[\alpha_\infty,\beta_\infty]$ is not in the given sequence. If the induction fails after step $k$, the interval $(\alpha_k,\beta_k)$ contains at most one point from the given sequence.

Answer by John Stillwell for Earliest diagonal proof of the uncountability of the reals.

2010-05-08T23:25:00Z

Cantor's diagonal argument first appears in his 1891 paper "Über eine elementare Frage der Mannigfaltigkeitslehre", Jahresbericht der Deutschen Mathematiker-Vereinigung 1: 75–78, in which he generalizes the argument to prove that any set has more subsets than elements. The 1891 paper has the diagonal argument as we know it today, but even his 1874 proof begins to look like a diagonal argument if you look at it closely. The proof uses the least upper bound $x$ of an increasing sequence $x_1,x_2,x_3,\ldots$ and $x$ "diagonalizes" the sequence in the sense that $x$ differs from each $x_i$ in some decimal place. The position of the place of difference increases with $i$, so the places of difference lie on a "jagged diagonal".

A more clearcut use of diagonalization before Cantor's 1891 proof, in my opinion, is in this 1875 paper by Paul du Bois-Reymond. Given a sequence of positive integer valued functions $f_1,f_2,f_3,\ldots$, du Bois-Reymond constructs a function $f$ that grows faster than each $f_i$. In particular, $f$ differs from $f_i$ on the value $i$.

Answer by Rhett Butler for Earliest diagonal proof of the uncountability of the reals.

2013-03-17T13:22:16Z

The evidence that you look for can already be found in the second paragraph of Cantor's original paper. There he states "Es läßt sich aber von jenem Satze ein viel einfacherer Beweis liefern, der unabhängig von der Betrachtung der Irrationalzahlen ist.", meaning that his diagonal argument supplies a much simpler proof of the theorem proved in his first paper on the uncountability of the real numbers. This does not only mention but declare that his method can be applied to real numbers.

Probably in order to emphasize its independence of numbers, Cantor did not use numerals 0 and 1, but m and w which (and this answers your last remark) in German are abbreviations of male and female. So he had a good substitution for 0 and 1 or up and down or yes and no - and he deliberately or unconsciously circumvented the problem that this proof without reservations, as stated in his original text, would fail on binary sequences.