The Wiki article on Cantor's diagonal argument mentions that the first use of a diagonal argument was in the work of Paul du Bois-Reymond in 1875. This would be one year after Cantor's first proof of the uncountability of the reals and 16 years before Cantor's own diagonal argument.

I was quite surprised to learn this. A Google search turned up this MathOverflow question. John Stillwell's answer says:

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,\dots$, 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$.

The link in this response goes to a paper in German that comes up only intermittently in my browser; and in any event my German's not sufficient to understand it.

Does anyone know more about du Bois-Reymond's proof and how it relates to Cantor's work? Was Cantor already aware of the idea of a diagonal proof? Does Cantor incorrectly get credit for this idea? And was uncountability perhaps "in the air" among at least one of Cantor's contemporaries?

(ps) Also found this. Turns out du Bois-Reymond is also responsible for recognizing the importance of lim inf and lim sup, among many other contributions. This article vagely refers (without detail) to du Bois-Reymond initiating a priority dispute with Cantor regarding the discovery of dense sets.

  • 3
    Yes, he did invent this argument before Cantor. – Alexandre Eremenko May 21 '16 at 3:57
up vote 10 down vote accepted

This paper is one in a series of papers in which du Bois Reymond studied functions on the positive real line ordered by the "order of infinity" (order of growth at infinity), what he later called infinitary pantachy. This was motivated by attempts to find "ideal boundary" between converging and diverging series in terms of the growth of their terms by analogy to filling in Dedekind cuts to get real numbers. Du Bois Reymond more or less established that such completion would not work. Later Hausdorff developed modern theory in Cantorian terms which explains why, the "gaps" in the orders of growth are more severe, beyond what countable limits can fill in. These are now called Hausdorff gaps, but du Bois Reymond did not work in cardinality terms.

Fisher gives a detailed account in Infinite and Infinitesimal Quantities of du Bois-Reymond and their Reception, here is the reference with direct link:

Ueber asymptotische Werthe, infinitäre Approximationen und infinitäre Auflösung yon Gleichungen, Mathematische Annalen 8 (1875) 363-414 (Nachtrage zur Abhandlung: Ueber asymptotische Werthe etc., 574-576).

Du Bois-Reymond defines one order of infinity to be larger than another if the limit of the quotient of their representing functions is infinite. He is not very specific about the class of functions considered, and apparently overlooks the possibility of incomparable orders, an issue later investigated by Borel and Hausdorff. He then analogizes, and contrasts, this continuum of orders to the linear continuum of real numbers:

"Between the two domains there are many analogies... Instead of numbers as fixed signs in the domain of numbers, one has in the infinitary domain of quantities an unlimited number of simple functions: the exponential functions, the powers, the logarithmic functions, that likewise form fixed points of comparisons, and between whose arbitrarily close infinities a limitless number of infinities different from each other can still be inserted.

These functions serving as numbers stretch, in accordance with the present state of analysis, from exponential functions stacked arbitrarily high... down to logarithms repeated arbitrarily, often to infinity... The question which arises here, whether one actually includes in this interval of infinity the entire domain of infinity, in such a way that one can enclose any given infinity between two infinities of functions of that interval, as is possible for any number in the number series: This question I have already answered in substance and in fact negatively..."

He refers to 1873 paper where only a particular case was considered. This time he gives a more general version, which Borel highly praised and termed du Bois-Reymond's theorem. A consequence of it, and the motivation, is the non-existence of the "ideal boundary" that can be specified by a sequence of converging/diverging series, as Bertrand earlier proposed (he was thinking of reciprocals to products of powers and powers of iterated logarithms as terms). The du Bois-Reymond's theorem would be the "diagonal argument":

"...if an unlimited family of more and more slowly increasing functions $\lambda_1(x), \lambda_2(x), \lambda_3(x)...$ is given which for each $r$ satisfies the condition $\lim\lambda_r(X)/\lambda_{r+1}(X) = \infty$, one can always specify a function $\psi(x)$ which becomes infinite with $x$, but more slowly than any function of that family".

The construction of $\psi(x)$ is in a footnote on p. 365, and does show some "diagonality" if one looks hard. There is however no cardinality involved in du Bois-Reymond's setting (Hausdorff will relate gaps to cardinalities only later), so making it into the diagonal argument takes some reading in. In his 1882 book Die allgemeine Functionentheorie (The General Theory of Functions) du Bois-Reymond touches base with Cantorian set theory, and mentions that Cantor showed "continuum of the idealists" to be uncountable. He does not however point out any affinity between the diagonal argument by which it was shown and his earlier construction, let alone lay any claim to it. So whatever the relation between the two it was not apparent to du Bois-Reymond.

  • 1
    Or else he wanted to me more generous than most of his coprofessionals. – Mikhail Katz May 22 '16 at 16:15
  • Fantastic response, thank you. I'm enjoying the Fisher paper. – user4894 May 23 '16 at 2:48
  • @Mikhail Or perhaps he wouldn't want the credit as "proto-intuitionist". There is an interesting related issue. Hausdorff redefined pantachies as maximal chains in orders of growth and switched from functions to sequences. In 1909 he used field extensions and the maximality principle to construct a pantachy which is a non-Archemidean real-closed field with no ω or ω* limits, ωω gaps, neither coinitial to ω nor cofinal to ω. Assuming the continuum hypothesis there is a unique such field up to isomorphism. Should we say that Hausdorff constructed hyperreals decades ahead of Robinson? – Conifold May 23 '16 at 20:08
  • @Conifold a non-Archimedean field can be easily constructed by elementary means, for example by using a lexicographic ordering on rational functions. A test of whether a proper ordered extension is useful in analysis is whether the sine function naturally extends to it. Could you give more details on your surely interesting question? – Mikhail Katz May 24 '16 at 6:50
  • I should mention that Robinson's work was indeed anticipated by earlier authors, as I emphasize in my paper more than anybody else. Thus, between E. Hewitt's 1948 paper that introduced hyper-real ideals, and J. Los's 1955 paper on "Los's theorem", the basic framework was already in place. @Conifold – Mikhail Katz May 24 '16 at 7:11

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.