Law of excluded middle

The law of the excluded middle is also known as the law/principle of the excluded third, in Latin principium tertii exclusi. Another Latin designation for the law is tertium non datur or "no third [possibility] is given".

In classical logic, the law of the excluded middle is taken as a tautology. Intuitionistic logic, by contrast, does not affirm the law. To prove $p \lor \neg p$ in intuitionist logic, it is necessary to prove either $p$ or $\neg p$ .

History

Aristotle

William Hamilton writes in a history of the so-called laws of thought:

The law of Excluded Middle between two contradictories remounts, as I have said, also to Plato, though the Second Alcibiades, the dialogue in which it is most clearly expressed, must be admitted to be spurious. It is also in the fragments of Pseudo-Archytas, to be found in Stobæus. [Hamilton LECT. V. LOGIC. 65]

Hamilton further observes that "It is explicitly and emphatically enounced by Aristotle in many passages both of his Metaphysics (l. iii. (iv.) c.7.) and of his Analytics, both Prior (l. i. c. 2) and Posterior (1. i. c. 4). In the first of these, he says: "It is impossible that there should exist any medium between contradictory opposites, but it is necessary either to affirm or to deny everything of everything." [Hamilton LECT. V. LOGIC. 65]

The Sea Battle

Yet in On Interpretation, Book 9, Aristotle seems to deny the law of excluded middle in the case of future contingents, in his discussion on the sea battle. It would seem to entail fatalism or logical determinism; and for this reason, the Stoics like Chrysippus affirmed it and embraced fatalism. Epicureans denied the law of excluded middle for this reason.

Some take Aristotle to be more strictly denying the principle of bivalence, which states that every proposition is either true or false. However, the principle of bivalence always implies the law of excluded middle.

Leibniz

Its usual form, "Every judgment is either true or false" [footnote 9] …"(from Kolmogorov in van Heijenoort, p. 421) footnote 9: "This is Leibniz's very simple formulation (see Nouveaux Essais, IV,2)" (ibid p 421)

Russell and Whitehead

The principle was stated as a theorem of propositional logic by Russell and Whitehead in Principia Mathematica as:

✸2.1 ~p ∨ p

Formalists versus Intuitionists

From the late 1800s through the 1930s, Hilbert and his followers had a bitter, persistent debate with Hermann Weyl and L. E. J. Brouwer. Brouwer's philosophy, called intuitionism, started in earnest with Leopold Kronecker in the late 1800s.

Hilbert intensely disliked Kronecker's ideas:

Kronecker insisted that there could be no existence without construction. For him, as for Paul Gordan [another elderly mathematician], Hilbert's proof of the finiteness of the basis of the invariant system was simply not mathematics. Hilbert, on the other hand, throughout his life was to insist that if one can prove that the attributes assigned to a concept will never lead to a contradiction, the mathematical existence of the concept is thereby established (Reid p. 34)

It was his [Kronecker's] contention that nothing could be said to have mathematical existence unless it could actually be constructed with a finite number of positive integers (Reid p. 26)

The debate had a profound effect on Hilbert. Reid indicates that Hilbert's second problem (one of Hilbert's problems from the Second International Conference in Paris in 1900) evolved from this debate (italics in the original):

In his second problem, [Hilbert] had asked for a mathematical proof of the consistency of the axioms of the arithmetic of real numbers.

To show the significance of this problem, he added the following observation:

"If contradictory attributes be assigned to a concept, I say that mathematically the concept does not exist" (Reid p. 71)

Thus, Hilbert was saying: "If p and ~p are both shown to be true, then p does not exist", invoking the law of excluded middle in the form of the law of contradiction.

And finally constructivists … restricted mathematics to the study of concrete operations on finite or potentially (but not actually) infinite structures; completed infinite totalities … were rejected, as were indirect proof based on the Law of Excluded Middle. Most radical among the constructivists were the intuitionists, led by the erstwhile topologist L. E. J. Brouwer (Dawson p. 49)

The rancorous debate continued through the early 1900s into the 1920s; in 1927 Brouwer complained about "polemicizing against it [intuitionism] in sneering tones" (Brouwer in van Heijenoort, p. 492). But the debate was fertile: it resulted in Principia Mathematica (1910–1913), which precisely defined the law of excluded middle, and all this provided an intellectual setting and the tools necessary for the mathematicians of the early 20th century:

Out of the rancor, and spawned in part by it, there arose several important logical developments; Zermelo's axiomatization of set theory (1908a), that was followed two years later by the first volume of Principia Mathematica, in which Russell and Whitehead showed how, via the theory of types: much of arithmetic could be developed by logicist means (Dawson p. 49)

Brouwer reduced the debate to the use of proofs designed from "negative" or "non-existence" versus "constructive" proof:

According to Brouwer, a statement that an object exists having a given property means that, and is only proved, when a method is known which in principle at least will enable such an object to be found or constructed …

Hilbert naturally disagreed.

"pure existence proofs have been the most important landmarks in the historical development of our science," he maintained. (Reid p. 155)

Brouwer refused to accept the logical principle of the excluded middle, His argument was the following:

"Suppose that A is the statement "There exists a member of the set S having the property P." If the set is finite, it is possible—in principle—to examine each member of S and determine whether there is a member of S with the property P or that every member of S lacks the property P." For finite sets, therefore, Brouwer accepted the principle of the excluded middle as valid. He refused to accept it for infinite sets because if the set S is infinite, we cannot—even in principle—examine each member of the set. If, during the course of our examination, we find a member of the set with the property P, the first alternative is substantiated; but if we never find such a member, the second alternative is still not substantiated.

Since mathematical theorems are often proved by establishing that the negation would involve us in a contradiction, this third possibility which Brouwer suggested would throw into question many of the mathematical statements currently accepted.

"Taking the Principle of the Excluded Middle from the mathematician," Hilbert said, "is the same as … prohibiting the boxer the use of his fists."

"The possible loss did not seem to bother Weyl … Brouwer's program was the coming thing, he insisted to his friends in Zürich." (Reid, p. 149)

In his 1941 lecture at Yale and subsequent paper, Gödel proposed a solution: "that the negation of a universal proposition was to be understood as asserting the existence … of a counterexample". His approach to the law of excluded middle was to assert that objections against "the use of 'impredicative definitions'" had "carried more weight" than "the law of excluded middle and related theorems of the propositional calculus". He proposed his "system Σ … and he concluded by mentioning several applications of his interpretation. Among them were a proof of the consistency with intuitionistic logic of the principle ~ (∀A: (A ∨ ~A)) (despite the inconsistency of the assumption ∃ A: ~ (A ∨ ~A))" (Dawson, p. 157)

The debate seemed to weaken: mathematicians, logicians, and engineers continue to use the law of excluded middle (and double negation) in their daily work.

Intuitionist definitions of the law (principle) of excluded middle

The following highlights the deep mathematical and philosophic problem behind what it means to "know", and also helps elucidate what the "law" implies (i.e. what the law really means). Their difficulties with the law emerge: that they do not want to accept as true implications drawn from that which is unverifiable (untestable, unknowable) or from the impossible or the false. (All quotes are from van Heijenoort, italics added).

Brouwer offers his definition of "principle of excluded middle"; we see here also the issue of "testability":

On the basis of the testability just mentioned, there hold, for properties conceived within a specific finite main system, the "principle of excluded middle", that is, the principle that for every system every property is either correct [richtig] or impossible, and in particular the principle of the reciprocity of the complementary species, that is, the principle that for every system the correctness of a property follows from the impossibility of the impossibility of this property. (335)

Kolmogorov's definition cites Hilbert's two axioms of negation

A → (~A → B)
(A → B) → { (~A → B) → B}

Hilbert's first axiom of negation, "anything follows from the false", made its appearance only with the rise of symbolic logic, as did the first axiom of implication … while … the axiom under consideration [axiom 5] asserts something about the consequences of something impossible: we have to accept B if the true judgment A is regarded as false …

Hilbert's second axiom of negation expresses the principle of excluded middle. The principle is expressed here in the form in which is it used for derivations: if B follows from A as well as from ~A, then B is true. Its usual form, "every judgment is either true or false" is equivalent to that given above".

From the first interpretation of negation, that is, the interdiction from regarding the judgment as true, it is impossible to obtain the certitude that the principle of excluded middle is true … Brouwer showed that in the case of such transfinite judgments the principle of excluded middle cannot be considered obvious

footnote 9: "This is Leibniz's very simple formulation (see Nouveaux Essais, IV,2). The formulation "A is either B or not-B" has nothing to do with the logic of judgments.

footnote 10: "Symbolically the second form is expressed thus

A ∨ ~A

where ∨ means "or". The equivalence of the two forms is easily proved (p. 421)

3 more chapters are free with a Lably account.

Examples

For example, if P is the proposition:

Socrates is mortal.

then the law of excluded middle holds that the logical disjunction:

Either Socrates is mortal, or it is not the case that Socrates is mortal.

is true by virtue of its form alone. That is, the "middle" position, that Socrates is neither mortal nor not-mortal, is excluded by logic, and therefore either the first possibility (Socrates is mortal) or its negation (it is not the case that Socrates is mortal) must be true.

An example of an argument that depends on the law of excluded middle is a proof by cases such as follows. We seek to prove that

there exist two irrational numbers

a

and

b

such that

a^{b}

is rational.

It is known that $\sqrt{2}$ is irrational (see proof). Consider the number

{\sqrt{2}}^{\sqrt{2}}

Clearly (excluded middle) this number is either rational or irrational. If it is rational, the proof is complete, and

a = \sqrt{2}

and

b = \sqrt{2}

But if ${\sqrt{2}}^{\sqrt{2}}$ is irrational, then let

a = {\sqrt{2}}^{\sqrt{2}}

and

b = \sqrt{2}

Then

a^{b} = {({\sqrt{2}}^{\sqrt{2}})}^{\sqrt{2}} = {\sqrt{2}}^{(\sqrt{2} \cdot \sqrt{2})} = {\sqrt{2}}^{2} = 2

and 2 is certainly rational. This concludes the proof.

In the above argument, the assertion "this number is either rational or irrational" invokes the law of excluded middle. An intuitionist, for example, would not accept this argument without further support for that statement. This might come in the form of a proof that the number in question is in fact irrational (or rational, as the case may be); or a finite algorithm that could determine whether the number is rational.

Non-constructive proofs over the infinite

The above proof is an example of a non-constructive proof disallowed by intuitionists:

The proof is non-constructive because it doesn't give specific numbers $a$ and $b$ that satisfy the theorem but only two separate possibilities, one of which must work. (Actually $a = {\sqrt{2}}^{\sqrt{2}}$ is irrational but there is no known easy proof of that fact.) (Davis 2000:220)

(Constructive proofs of the specific example above are not hard to produce; for example $a = \sqrt{2}$ and $b = \log_{2} 9$ are both easily shown to be irrational, and $a^{b} = 3$ ; a proof allowed by intuitionists).

By non-constructive Davis means that "a proof that there actually are mathematic entities satisfying certain conditions would not have to provide a method to exhibit explicitly the entities in question." (p. 85). Such proofs presume the existence of a totality that is complete, a notion disallowed by intuitionists when extended to the infinite—for them the infinite can never be completed:

In classical mathematics there occur non-constructive or indirect existence proofs, which intuitionists do not accept. For example, to prove there exists an n such that P(n), the classical mathematician may deduce a contradiction from the assumption for all n, not P(n). Under both the classical and the intuitionistic logic, by reductio ad absurdum this gives not for all n, not P(n). The classical logic allows this result to be transformed into there exists an n such that P(n), but not in general the intuitionistic … the classical meaning, that somewhere in the completed infinite totality of the natural numbers there occurs an n such that P(n), is not available to him, since he does not conceive the natural numbers as a completed totality. (Kleene 1952:49–50)

Hilbert and Brouwer both give examples of the law of excluded middle extended to the infinite. Hilbert's example: "the assertion that either there are only finitely many prime numbers or there are infinitely many" (quoted in Davis 2000:97); and Brouwer's: "Every mathematical species is either finite or infinite." (Brouwer 1923 in van Heijenoort 1967:336). In general, intuitionists allow the use of the law of excluded middle when it is confined to discourse over finite collections (sets), but not when it is used in discourse over infinite sets (e.g. the natural numbers). Thus intuitionists absolutely disallow the blanket assertion: "For all propositions P concerning infinite sets D: P or ~P" (Kleene 1952:48).

Putative counterexamples to the law of excluded middle include the liar paradox or Quine's paradox. Certain resolutions of these paradoxes, particularly Graham Priest's dialetheism as formalised in LP, have the law of excluded middle as a theorem, but resolve out the Liar as both true and false. In this way, the law of excluded middle is true, but because truth itself, and therefore disjunction, is not exclusive, it says next to nothing if one of the disjuncts is paradoxical, or both true and false.

Criticisms

The Catuṣkoṭi (tetralemma) is an ancient alternative to the law of excluded middle, which examines all four possible assignments of truth values to a proposition and its negation. It has been important in Indian logic and Buddhist logic as well as the ancient Greek philosophical school known as Pyrrhonism.

Many modern logic systems replace the law of excluded middle with the concept of negation as failure. Instead of a proposition's being either true or false, a proposition is either true or not able to be proved true. These two dichotomies only differ in logical systems that are not complete. The principle of negation as failure is used as a foundation for autoepistemic logic, and is widely used in logic programming. In these systems, the programmer is free to assert the law of excluded middle as a true fact, but it is not built-in a priori into these systems.

Mathematicians such as Brouwer and Arend Heyting have also contested the usefulness of the law of excluded middle in the context of modern mathematics.

In mathematical logic

In modern mathematical logic, the excluded middle has been argued to result in possible self-contradiction. It is possible in logic to make well-constructed propositions that can be neither true nor false; a common example of this is the "Liar's paradox", the statement "this statement is false", which is argued to itself be neither true nor false. Arthur Prior has argued that the Paradox is not an example of a statement that cannot be true or false. The law of excluded middle still holds here as the negation of this statement "This statement is not false", can be assigned true. In set theory, such a self-referential paradox can be constructed by examining the set "the set of all sets that do not contain themselves". This set is unambiguously defined, but leads to Russell's paradox: does the set contain, as one of its elements, itself? In the modern Zermelo–Fraenkel set theory, this type of contradiction is no longer admitted. Furthermore, paradoxes of self-reference can be constructed without invoking negation, as in Curry's paradox.

Analogous laws

Some systems of logic have different but analogous laws. For some finite n-valued logics, there is an analogous law called the law of excluded n+1th. If negation is cyclic and "∨" is a "max operator", then the law can be expressed in the object language by (P ∨ ~P ∨ ~~P ∨ ... ∨ ~...~P), where "~...~" represents n−1 negation signs and "∨ ... ∨" n−1 disjunction signs. It is easy to check that the sentence must receive at least one of the n truth values (and not a value that is not one of the n).

Other systems reject the law entirely.

Law of the weak excluded middle

A particularly well-studied intermediate logic is given by De Morgan logic, which adds the axiom $\neg P \lor \neg \neg P$ to intuitionistic logic, which is sometimes called the law of the weak excluded middle.

This is equivalent to a few other statements:

Satisfying all of De Morgan's laws including $\neg (P \land Q) \leftrightarrow \neg P \lor \neg Q$
$(P \to Q) \lor (\neg P \to \neg Q)$
$(P \to (Q \lor \neg R)) \to ((P \to Q) \lor (P \to \neg R))$