[Math] Status of proof by contradiction and excluded middle throughout the history of mathematics

ho.history-overviewlo.logicproof-theory

Occasionally I see the claim, that mathematics was constructive before the rise of formal logic and set theory. I'd like to understand the history better.

  1. When did proofs by contradiction or by excluded middle become accepted/standard? Can one find them for instance in classical works (Archimedes, Euclid, Euler, Gauss, etc.)?
  2. Was there ever a debate about their validity before Brouwer?

My interest was sparked after reading the following "proof" from Newton's Principia that seems to use contradiction:

LEMMA I.

Quantities, and the ratios of quantities, which in any finite
time converge continually to equality, and before the end of that time
approach nearer the one to the other than by any given difference,
become ultimately equal.

If you deny it, suppose them to be ultimately unequal, and let $D$ be
their ultimate difference. Therefore they cannot approach nearer to
equality than by that given difference $D$; which is against the
supposition.

Best Answer

I want to echo the other answer, that Brouwer presents the first robust challenge to the Law of Excluded Middle (LEM), but I do want to add some history and background, and maybe recommend a related paper.

The main paper by Brouwer is De onbetrouwbaarheid der logische principes or in English The unreliability of the logical principles published in 1908. In some sense, this is a continuation of his dissertation in 1907, but I think it's better to just speak of 1908 as the starting point for Brouwer's views on LEM.

In a paper [1] offering a new translation of Brouwer's paper, the authors have a section devoted to "precursors" (this is only four pages long, too long to quote in full, but worth reading). At first glance, the references given do not mention LEM, and the relationship to Brouwer seems slightly strained, but I think the authors adequately defend the relevance of the section. It starts with a quote from Kronecker in 1882 about constructability issues. It seems this was extended by Kronecker's student Molk, who said in 1885

The definitions should be algebraic and not only logical. It does not suffice to say: ‘A thing exists or it does not exist’. One has to show what being and not being mean, in the particular domain in which we are moving. Only thus do we make a step forward.

The authors then devote an entire page of quotes from Molk (in 1904), noting the similarities "even down to some of the finer detail" to Brouwer's line of thought, though Molk doesn't continue as far as Brouwer. For instance, here's one sentence from the page of quotes:

In order to give a mathematical demonstration of a proposition, it does not suffice, for example, to establish that the contrary proposition implies a contradiction.

I think it should be pointed out that the authors tried but failed to establish any record that Brouwer was aware of Molk's writings. A footnote points out that Brouwer himself seems to have become aware of the similarities some years later.

Following the discussion on Molk, the authors give a correspondence by Lebesgue in 1905 which contains an afterthought very similar to LEM:

Although I strongly doubt that one will ever name a set that is neither finite nor infinite, the impossibility of such a set seems to me not to have been demonstrated.

but this seems to be more a curious coincidence than serious mathematical reasoning.

I think the final sentence summarizes the section well:

However, in spite of the early efforts by Kronecker, only with Brouwer do we get a comprehensive development of mathematics excluding any ‘unreliable’ use of the principle of excluded middle.

Edit: Adding a little bit more history, just some more sources that say the same as above.

In [4], Kleene devotes the very first sentence to a brief background on intuitionism (he goes on to talk about Brouwer in the next paragraph, not included here):

The constructive tendency in mathematics has been represented, prior to or apart from intuitionism, in the criticism of "classical" analysis by Kronecker around 1880-1890, and in the work of Poincaré 1902, 1905-6, Borel 1898, 1922 and Lusin 1927, 1930 (cf. Heyting 1934 or 1935).

Above, Kleene references his Introduction to Meta-Mathematics [5], which says the following at the opening of section 13

In the 1880's, when the methods of Weierstrass, Dedekind and Cantor were flourishing, Kronecker argued vigorously that their fundamental definitions were only words, since they do not enable one in general to decide whether a given object satisfies the definition. Poincaré, when he defends mathematical induction as an irreducible tool of intuitive mathematical reasoning (1902, 1905-6), is also a fore-runner of the modern intuitionistic school. In 1908 Brouwer, in a paper entitled "The untrustworthiness of the principles of logic", challenged the belief that the rules of the classical logic, which have come down to us essentially from Aristotle (384-322 B.C.), have an absolute validity, independent of the subject matter to which they are applied. ...

I extracted the references for Poincaré and Borel, they are listed at the end of the references section below.

I could not find a copy of Brouwer’s Intuitionism. Studies in the History and Philosophy of Science, vol. 2 by W. van Stigt (1990) to read, so that may or may not have other useful information. However, I did find the following paragraph in a book review [2], I wanted to include this just to give some context for LEM and when it gained prominence.

From his philosophy of mathematics Brouwer draws the remarkable conclusion that the Principle of the Excluded Middle of logic is not reliable. His paper The Unreliability of the Logical Principles of 1908, written in Dutch, did not attract the attention it deserved. Van Stigt notes that even Brouwer himself originally did not appreciate its revolutionary character. Even in 1912 his attack on the Law of Excluded Middle is only an added footnote to the English translation of his inaugural address. Only in 1923 does Brouwer return to logic, criticizing the principle of double negation elimination $ \lnot \lnot \phi \rightarrow \phi $. By November he discovers $\lnot \lnot \lnot \phi \leftrightarrow \lnot \phi $. The attacks on the Principle of the Excluded Middle became a propagandistic rallying point. The development of intuitionistic logic, however, is left to Kolmogorov, Glivenko, and, finally, Heyting in 1928, just when Brouwer retires into silence.

Finally, there is a related paper [3] that might be relevant to the original question (though I think the "crisis" talk is a bit sensationalized from a modern perspective, and could have been moderated a bit more in the paper). It looks into the history of science and math about Intuitionism in particular, discusses Kuhnian paradigm shifts, and some difficulties in why Intuitionism never "caught on."

There's a lot of background, probably the only section of interest is section 4 which begins

In the early years of the twentieth century, classical mathematics entered a period of crisis. Paradoxes had sprung up in and around Cantor’s set theory, and ultimately these ‘crisis-provoking anomalies’ (to transplant a Kuhnian phrase) led concerned classical mathematicians to investigate the foundations of their subject, searching for a way to bring certainty back to mathematics. At the height of this crisis, in his 1907 dissertation and subsequent papers, the Dutch mathematician L. E. J. Brouwer offered a new paradigm for mathematics. Intuitionism promised to secure the foundations of mathematics and explain away the anomalies. Yet it failed to convert the mathematical community.

[1] Mark van Atten, Göran Sundholm. "L.E.J. Brouwer's `Unreliability of the logical principles'. A new translation, with an introduction" https://arxiv.org/abs/1511.01113

[2] Wim Ruitenburg. "Review of W. P. van Stigt, Brouwer's Intuitionism". Modern Logic 2 (1992), no. 4, 424--430. https://projecteuclid.org/euclid.rml/1204834908

[3] Bruce Pourciau. "Intuitionism as a (failed) Kuhnian revolution in mathematics" Studies in History and Philosophy of Science Part A. Volume 31, Issue 2, June 2000, Pages 297-329. https://doi.org/10.1016/S0039-3681(00)00010-8

[4] S. C. Kleene, R. E. Vesley. "The Foundations of Intuitionistic Mathematics" North-Holland, 1965, page 1.

[5] S. C. Kleene. "Introduction to Meta-Mathematics" Ishi Press, New York 2009. Page 46.

Kleene's references (apologies for bad French)

Borel 1898 Leçons sur la théorie des fonctions. Paris (Gauthier-Villars), 8+136 pp. 4th ed. (Leçons sur la théorie des fonctions; principes de la théorie des ensembles en vue des applications à la théorie des fonctions). Paris (Gauthier-Villars), 1950, xii+295 pp. Available on archive.org, e.g. https://archive.org/details/leconstheoriefon00borerich

Poincaré 1902. La Science et l'hypothèse. Paris, 284 pp. Translated by G. Bruce Halstead as pp. 27-197 of The foundations of science by H. Poincaré, New York (The Science Press) 1913; reprinted 1929.

Poincaré 1905-6 Les mathématiques et la logique. Revue de métaphysique et de morale, vol. 13 (1905), pp 815-835, vol. 14 (1906), pp. 17-34, 294-317. Reprinted in 1908 with substantial alterations and additions.

Related Question