# Earliest diagonal proof of the uncountability of the reals.

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.

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.

• Thanks for the reference - that is not a marginal note but the last sentence of the introduction to the 1874 paper that contains the nested-intervals proof sketched below by Harald Hanche-Olsen. I hesitate to ascribe motives to people but from the correspondence between Cantor and Dedekind it appears that the (im)possibility of a bijection between N and R was foremost in Cantor's mind. Dauben, in his biography, makes the case that Cantor hid this new type of result behind the set of algebraic numbers to avoid controversy. – KP Hart May 10 '10 at 9:06
• re: hiding the result, that's a good theory, is there a paper forthcoming on this? – Jason Dyer May 10 '10 at 12:44
• The material in the book (page 183 and on) also suggests that Cantor used the algebraic numbers to make the other result more palatable to the people in Berlin. Yes I'm working on a short note on misconceptions about the diagonal proof'. The other misconception is that Cantor proved his results by contradiction; neither uncountability paper supposes we have a bijection'' but simply proves that every map from the smaller to the larger set omits at least one value. – KP Hart May 11 '10 at 8:36
• @KPHart Did you write your paper? I'd love to read it. – Billy Rubina Jun 16 '18 at 2:00
• @BillyRubina Here it is, in Dutch: nieuwarchief.nl/serie5/pdf/naw5-2015-16-1-040.pdf – KP Hart Sep 3 '18 at 14:21

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$.

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.

• The nested-interval proof shows more: every complete and densely ordered chain is uncountable. Also, Cantor's diagonal argument establishes that the set of sequences of m's and w's (not zeroes and ones!) is uncountable; he noted that the method is very general and showed that there are more zero-one-valued functions on the interval [0,1] than there are points in that interval. Of course generalizing this to a set has more subsets than points'' is straightforward. I still wonder why he chose the letters m and w, maybe because one is the other but upside-down. – KP Hart May 10 '10 at 9:29
• @KPHart "männlich" and "weiblich" I've read somewhere (the biography perhaps?) – Henno Brandsma Feb 2 '20 at 11:04
• @HennoBrandsma I make that joke during lectures. Another explanation is that $m$ is $w$ upside-down. – KP Hart Feb 2 '20 at 14:27

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.

• No, read the first sentence of the paper, which refers to: "Mannigfaltigkeiten die sich nicht gegenseitig eindeutig aller endlichen ganzen Zahlen 1,2, ..., $\nu$, ... beziehen lassen" and refers back to he earlier paper for the example of an interval $(\alpha,\beta)$. It is the existence of uncountable infinities that he wants to reprove, <i>not</i> the uncountability of the reals. – KP Hart Sep 3 '18 at 14:28
• Supposing that "m and w" is a binary representation... Is the Wikipedia illustration of diagonal argument a modern view, or a kind of binary representation of Naturals was really used by Cantor in 1891? – Peter Krauss Mar 2 '20 at 1:40