It seems the history of the interesting fact that there is no bijection between $\mathbb{N}$ and $\mathbb{R}$, Cantor's diagonalization trick in the mid 1800s, is common knowledge. Meanwhile, there are dozen(s) of clever proofs of the equally interesting fact that there is a bijection between $\mathbb{N}$ and $\mathbb{Q}$, but which proof was first and what was the story behind it?
$\begingroup$
$\endgroup$
14
asked Jan 26, 2017 at 23:14
-
8$\begingroup$ Certainly Cantor knew (and proved/wrote down) that the set of all algebraic numbers is countable; this was in 1874, see: en.m.wikipedia.org/wiki/…. It's hard to imagine any earlier proof because people didn't really think about countability before Cantor. $\endgroup$– Sam HopkinsJan 27, 2017 at 0:07
-
5$\begingroup$ "Common knowledge" of history among mathematicans is often false. Cantor's diagonalization trick did not appear until some time after his first proof of uncountability of the reals. $\endgroup$– Michael HardyJan 27, 2017 at 1:34
-
10$\begingroup$ @MichaelHardy You have mentioned your theory on that matter in several posts, but I don't really agree with your position. Cantor's first proof was indeed essentially a diagonalizaton, and essentially the same proof as the common proof given in his name now. He shrunk intervals so as successively to avoid the next point in a countable set, and thereby found a point different from all of them. But insisting on a certain digit in the decimal representation of a number is essentially the same as shrinking an interval so as to avoid the endpoint of an interval. It is the same argument each time. $\endgroup$– Joel David HamkinsJan 27, 2017 at 1:53
-
3$\begingroup$ @JoelDavidHamkins : Although I agree that the basic idea of the proof is the same, the word "diagonalization" invokes, in most non-experts' minds, a literal geometric diagonal. So there is a psychological difference, and I'm not even sure that the word "diagonalization" would have been coined without an explicit visual picture of a diagonal (and that explicit visual picture is not present in the original proof). $\endgroup$– Timothy ChowJan 27, 2017 at 16:28
-
3$\begingroup$ I don't believe that one ever needs to use the word "diagonal" in either the original proof or the one involving digits. The main point is that you exclude the $n^{th}$ point at the $n^{th}$ stage of the construction. Since the points $(n,n)$ form a diagonal in the plane, we now describe all such arguments as diagonal arguments. $\endgroup$– Joel David HamkinsJan 27, 2017 at 16:54
|
Show 9 more comments
1 Answer
$\begingroup$
$\endgroup$
From the Wikipedia article Cantor's first set theory article cited by Michael Hardy:
On November 29, 1873, Cantor asked Dedekind whether the collection of positive integers and the collection of positive real numbers "can be corresponded so that each individual of one collection corresponds to one and only one individual of the other?" Cantor added that collections having such a correspondence include the collection of positive rational numbers, and collections of the form $(a_{n_1, n_2, \ldots , n_ν})$ where $n_1, n_2, \ldots , n_ν$, and $ν$ are positive integers.
That tells you when, and given the juxtaposition with the last assertion together with his published proof that the algebraic numbers are countable, I think you can infer how the proof he had in mind probably went. (Define the height of a positive fraction $\frac{p}{q}$ written in lowest terms to be the number $p + q$, observe that there are only finitely many fractions of a given height, and enumerate by height.)
answered Jan 27, 2017 at 5:05