The law of excluded middle and the abstraction of "actual infinity".

Question

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?

Answer 1

See Brouwer’s Development of Intuitionism:

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$.

Answer 2

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.