# The law of excluded middle and the abstraction of “actual infinity”.

The encyclopedia of mathematics states:

"Logically, acceptance of the abstraction of actual infinity leads to the acceptance of the law of the excluded middle as a logical principle."

This is mentioned in justifying constructive approaches.

What is the intuition for (and presumably proof of?) this "logical" connection?

• @Mauro. My apologies: the current link is correct now. – JRC Jan 20 at 9:24
• Who wrote that text? – Asaf Karagila Jan 20 at 9:30

on Brouwer’s view, there is no determinant of mathematical truth outside the activity of thinking, a proposition only becomes true when the subject has experienced its truth (by having carried out an appropriate mental construction); similarly, a proposition only becomes false when the subject has experienced its falsehood (by realizing that an appropriate mental construction is not possible). Hence Brouwer can claim that “there are no non-experienced truths”.

in his dissertation On the Foundations of Mathematics, defended in 1907, [...] Brouwer sets out to reconstruct Cantorian set theory. When an attempt at making constructive sense out of Cantor’s second number class (the class of all denumerably infinite ordinals) and higher classes of even greater ordinals fails, he realises that this cannot be done and rejects the higher number classes, leaving only all finite ordinals and an unfinished or open-ended collection of denumerably infinite ordinals [emphasis added]. Thus, as a consequence of his philosophical views, he consciously puts aside part of generally accepted mathematics. Soon he would do the same with a principle of logic, the principle of the excluded middle (PEM), but in the dissertation he still thinks of it as correct but useless, interpreting $$p \lor \lnot p$$ as $$\lnot p \to \lnot p$$.

In “The Unreliability of the Logical Principles” of 1908, Brouwer formulates, in general terms, his criticism of PEM: although in the simple form of $$p \lor \lnot p$$, the principle will never lead to a contradiction, there are instances of it for which one has, constructively speaking, no positive grounds. Brouwer names some. Because they do not in the strict sense refute PEM, they are known as “weak counterexamples”.

Later Brouwer [showed] a refutation of PEM in the form $$\forall x \in \mathbb R (Px \lor \lnot Px)$$, by showing that it is false that every real number is either rational or irrational (the first of "strong counterexamples").

The interplay between PEM (or LEM) and actual infinity is one of the basic ground for Intuitionistic Logic:

the constructive validity [of PEM: $$A ∨ ¬A$$] would mean that we have a method that, for any $$A$$, either gives us a construction for $$A$$, or shows that such a construction is impossible. But we do not have such a general decision method, and there are many open problems in mathematics. Brouwer states “Every number is finite or infinite” as an example of a general proposition for which so far no constructive proof has been found. As a consequence, he says, it is at present uncertain whether problems such as the following are solvable:

Is there in the decimal expansion of π a digit which occurs more often than any other one?

Do there occur in the decimal expansion of π infinitely many pairs of equal consecutive digits?

In effect, Brouwer is saying that we can assert the weak negations of the propositions expressed in these questions; hence, these propositions are so-called “Brouwerian counterexamples” or “weak counterexamples” to PEM. On the constructive reading of PEM, of course any as yet unsolved problem is a weak counterexample to PEM.

In a nutshell, the basic Brouwerian "rejections" are: LEM applied to infinite collections (for finite sets, there is no issue with it) and the indirect proof of existence, i.e. deriving $$\exists x Px$$ from a derivation of a contradiction from assumption $$\forall x \lnot Px$$.

• Thanks! Very instructive, although I still don't see why "logically, acceptance of the abstraction of actual infinity leads to the acceptance of the law of the excluded middle as a logical principle." Perhaps it is because the ONLY obstacle to LEM being accepted otherwise is infinity? If you then accept it's application to infinity, then you accept it generally. Not sure why this quote emphasizes logic though. – JRC Jan 20 at 12:39
• @JRC - ask to the author :-) Joke apart, I do not think that you have to take at at face value: it is a sort of short summary of Intuitionism; as you can see from my post and the related link, the matter is very complex. IMO, it would be better to say that LEM and the acceptance of actual infinity are strictly related to modern "classical math" grounded in set theory. The rejection of LEM is based on a different use of "not" in mathematics: a proof of a "negative" mathematical fact $\lnot P$ is a proof that the supposition of that fact leads to a contradiction: it is impossible that $P$. – Mauro ALLEGRANZA Jan 20 at 13:07
• But there is also a different sort of "factual" negation: we do not know that $P$, i.e. we have no ground for asserting it. The two are the same for finite set: it is enough to check all cases and we can get from "we do not know" to "we know that not". Not so for infinity: if infinity makes sense also "potentially", we cannot survey it in a finite amount of steps and the assertion that something holds for the actual infinity but it is hided somewhere is not acceptable... for Intuitionism. – Mauro ALLEGRANZA Jan 20 at 13:10

Edit: Looks like you updated the link to a new page (was abstraction of potential realizability, is now the abstraction of actual infinity). I will take a look and see how that changes my answer below.

Edit 2: I don't think the link update really changes the general ideas in my response below. The first link was about disregarding that reaching infinity is not doable in practice when assessing the validity of conclusions, whereas the second is saying, pretend it is actually reachable and treat it as if it has been reached. The ideas are similar. I'm not planning to modify my response further.

In the same encyclopedia website, searching for the law of the excluded middle, there is a section that says:

Since there is no general method for establishing in a finite number of steps the truth of an arbitrary statement, or of that of its negation, the law of the excluded middle was subjected to criticism by representatives of the intuitionistic and constructive directions in the foundations of mathematics (cf. Intuitionism; Constructive mathematics).

I think the connection is this finite steps idea. By embracing the abstraction of potential realizability, one accepts unbounded constructions as valid, even if it would be impossible to physically carry out an infinite number of logical steps or calculations. Applied to the law of the excluded middle, a given proposition may require an infinite number of steps to establish it's truth or that of its negation. The abstraction of potential realizability essentially says that you can treat things that require an infinite number of steps as valid.

This reminds me of something I read in the book Gödel, Escher, Bach, which I highly recommend. It explains how Gödel's incompleteness theorem involves the construction of statements that essentially say "This statement is not provable within this logical system". It is analogous to the "this statement is a lie" paradox. At the end of the book, there is discussion about adding an axiom to state a proof to the paradoxical statement does exist. By doing so, one finds that such a proof is essentially infinitely long (contains an infinite number of deduction steps). Incidentally this then implies the existence of a whole new class of numbers called surreal numbers, which is pretty interesting. The relevance here is: there was a paradoxical proposition that seemed neither true nor false, apparently falling within the excluded middle zone. By asserting there is an answer, one can resolve the paradox (placing the proposition squarely in either the true or false realm), but doing so requires acceptance of logical arguments which are infinitely long, embracing the abstraction of potential realizability.

• Thanks! I began to have an inkling when you said "applied to the law of the excluded middle, a given proposition may require an infinite number of steps to establish it's truth or that of its negation." But I'm afraid I still don't see clearly the logical entailment mentioned in my original quote. – JRC Jan 20 at 12:47
• @JRC Fair enough, perhaps someone else will post a more definitive answer. My take I suppose is the opposite direction wrt implication: Excluded Middle implies accepting infinitely long constructions. Whereas your original quote goes the other way: Accepting infinitely long constructions implies the excluded middle. I am not sure I actually agree with the quote. For example in calculus, you can take the limit of an expression as a variable approaches infinity, however that does not imply that a limit exists in every situation. – Matt Miguel Jan 20 at 16:04