# Status of proof by contradiction and excluded middle throughout the history of mathematics?

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.

• Yes, proof by contradiction can be found in Euclid. – Monroe Eskew May 20 '19 at 9:30
• mathcs.clarku.edu/~djoyce/java/elements/bookXII/propXII2.html – Monroe Eskew May 20 '19 at 9:34
• As with any old text, it matters what its contermporary reading is. The lemma you refer seems to rely on the fact that $\lnot \exists D . |x - y| > D$ implies $x = y$. This is not a proof by contradiction, and it is valid constructively. – Andrej Bauer May 20 '19 at 11:23
• @AndrejBauer Yes he does, in the course of that very proof. Look at the beginning. Anyway, I don't think it is that germane to this question to ask what is constructively valid by modern standards, because the ancients didn't know about that. But "reductio ad absurdum" comes from those ancient Mediterranean mathematicians and philosophers. – Monroe Eskew May 20 '19 at 12:10
• Just because an inference is constructively valid does not mean that the person was thinking constructively when making the inference. If LEM were generally regarded as invalid, then one would expect people either to avoid any appearance of its use, or to give a clear, explicit discussion of the matter and explain exactly when LEM is really being used and when it is not. In the absence of any such explicit discussion in antiquity, it is reasonable to interpret Eskew's example (transitioning from "not unequal" to "equal" without comment) as a tacit acceptance of double negation elimination. – Timothy Chow May 21 '19 at 15:17

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.

• This is interesting; I had never heard of Molk. I am always shocked by Brouwer’s obscurantism, eg in the first paragraph of the paper. Fortunately I like Brouwer’s examples at the end: Is $\pi$ normal? And are there infinitely many equal consecutive digits in its decimal expansion? – Matt F. May 20 '19 at 16:56

So far as I can tell, there was no debate about the validity of these methods before Brouwer. I rely on Colin McLarty's review of the key example in his 2007 paper "Theology and its discontents: David Hilbert's foundation myth for modern mathematics."

The famous examples from before Hilbert, e.g. Archimedes's method of exhaustion, Euclid's proof that "prime numbers are more than any assigned multitude", and Cantor-style diagonal proofs of the existence of transcendental numbers, all are or can easily be made constructive.

By contrast, Hilbert's 1888 proof of the existence of a finite system of invariants was not constructive. But apparently no one objected to it for that reason before Brouwer; Paul Gordan called the proof theological but even he did not reject it.

The starting point for the use of that word is Hilbert's reminiscence of 1923, as quoted and translated by McLarty (p. 13):

Gordan had a certain unclear feeling of the transfinite methods in my first invariant proof, which he expresed by calling the proof "theological".

This was about an unclarity in exposition, bad enough that the editors of the Mathematische Annalen noted that the theorem was not true as stated there. The quote "this is not Mathematics; it is Theology!" appears apocryphal; it's first attribution to Gordan was in an article by Felix Klein in 1928.

The actual attitudes of mathematicians to this proof were, as McLarty says, "practical", e.g. John Grace and Alfred Young in 1903: the method "gives practially no information as to the actual determination of the finite system whose existence it establishes". Turning that from an observation to an objection seems to have started with Brouwer.