Law of excluded middle

One of the traditional three laws of thought (along with the laws of identity and contradiction).

Every proposition is either true or not true.

This is weaker than the law of bivalence (every proposition is true or false), since if there is a third truth value excluded middle can still hold, though bivalence will fail. (However, bivalence is sometimes treated as a version of excluded middle).

For classical logic, excluded middle follows from the law of contradiction. Intuitionist logic accepts the latter but not excluded middle (also see: double negation), for reasons connected with the ‘Jones was brave’ example (see bivalence).

Also see: degrees of truth

Source:
P T Geach and W F Bednarowski, “The Law of Excluded Middle’ (symposium), Proceedings of the Aristotelian Society, supplementary volume (1956)

History

Aristotle

The earliest known formulation is in Aristotle’s discussion of the principle of non-contradiction, first proposed in On Interpretation,^[2] where he says that of two contradictory propositions (i.e. where one proposition is the negation of the other) one must be true, and the other false.^[3] He also states it as a principle in the Metaphysics book 3, saying that it is necessary in every case to affirm or deny,^[4] and that it is impossible that there should be anything between the two parts of a contradiction.^[5]

Aristotle wrote that ambiguity can arise from the use of ambiguous names, but cannot exist in the facts themselves:

It is impossible, then, that “being a man” should mean precisely “not being a man”, if “man” not only signifies something about one subject but also has one significance. … And it will not be possible to be and not to be the same thing, except in virtue of an ambiguity, just as if one whom we call “man”, and others were to call “not-man”; but the point in question is not this, whether the same thing can at the same time be and not be a man in name, but whether it can be in fact. (Metaphysics 4.4, W.D. Ross (trans.), GBWW 8, 525–526).

Aristotle’s assertion that “it will not be possible to be and not to be the same thing”, which would be written in propositional logic as ¬(P ∧ ¬P), is a statement modern logicians could call the law of excluded middle (P ∨ ¬P), as distribution of the negation of Aristotle’s assertion makes them equivalent, regardless that the former claims that no statement is both true and false, while the latter requires that any statement is either true or false.

But Aristotle also writes, “since it is impossible that contradictories should be at the same time true of the same thing, obviously contraries also cannot belong at the same time to the same thing” (Book IV, CH 6, p. 531). He then proposes that “there cannot be an intermediate between contradictories, but of one subject we must either affirm or deny any one predicate” (Book IV, CH 7, p. 531). In the context of Aristotle’s traditional logic, this is a remarkably precise statement of the law of excluded middle, P ∨ ¬P.

Also in On Interpretation, Aristotle seems to deny the law of excluded middle in the case of future contingents, in his discussion on the sea battle.

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)

Bertrand Russell and Principia Mathematica

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

{\displaystyle \mathbf {*2\cdot 11} .\ \ \vdash .\ p\ \vee \thicksim p}.^[6]

So just what is “truth” and “falsehood”? At the opening PM quickly announces some definitions:

Truth-values. The “truth-value” of a proposition is truth if it is true and falsehood if it is false* [*This phrase is due to Frege]…the truth-value of “p ∨ q” is truth if the truth-value of either p or q is truth, and is falsehood otherwise … that of “~ p” is the opposite of that of p…” (p. 7-8)

This is not much help. But later, in a much deeper discussion (“Definition and systematic ambiguity of Truth and Falsehood” Chapter II part III, p. 41 ff), PM defines truth and falsehood in terms of a relationship between the “a” and the “b” and the “percipient”. For example “This ‘a’ is ‘b'” (e.g. “This ‘object a’ is ‘red'”) really means “‘object a’ is a sense-datum” and “‘red’ is a sense-datum”, and they “stand in relation” to one another and in relation to “I”. Thus what we really mean is: “I perceive that ‘This object a is red'” and this is an undeniable-by-3rd-party “truth”.

PM further defines a distinction between a “sense-datum” and a “sensation”:

That is, when we judge (say) “this is red”, what occurs is a relation of three terms, the mind, and “this”, and “red”. On the other hand, when we perceive “the redness of this”, there is a relation of two terms, namely the mind and the complex object “the redness of this” (pp. 43–44).

Russell reiterated his distinction between “sense-datum” and “sensation” in his book The Problems of Philosophy (1912), published at the same time as PM (1910–1913):

Let us give the name of “sense-data” to the things that are immediately known in sensation: such things as colours, sounds, smells, hardnesses, roughnesses, and so on. We shall give the name “sensation” to the experience of being immediately aware of these things… The colour itself is a sense-datum, not a sensation. (p. 12)

Russell further described his reasoning behind his definitions of “truth” and “falsehood” in the same book (Chapter XII, Truth and Falsehood).

Consequences of the law of excluded middle in Principia Mathematica[edit]

From the law of excluded middle, formula ✸2.1 in Principia Mathematica, Whitehead and Russell derive some of the most powerful tools in the logician’s argumentation toolkit. (In Principia Mathematica, formulas and propositions are identified by a leading asterisk and two numbers, such as “✸2.1”.)

✸2.1 ~p ∨ p “This is the Law of excluded middle” (PM, p. 101).

The proof of ✸2.1 is roughly as follows: “primitive idea” 1.08 defines p → q = ~p ∨ q. Substituting p for q in this rule yields p → p = ~p ∨ p. Since p → p is true (this is Theorem 2.08, which is proved separately), then ~p ∨ p must be true.

✸2.11 p ∨ ~p (Permutation of the assertions is allowed by axiom 1.4)
✸2.12 p → ~(~p) (Principle of double negation, part 1: if “this rose is red” is true then it’s not true that “‘this rose is not-red’ is true”.)
✸2.13 p ∨ ~{~(~p)} (Lemma together with 2.12 used to derive 2.14)
✸2.14 ~(~p) → p (Principle of double negation, part 2)
✸2.15 (~p → q) → (~q → p) (One of the four “Principles of transposition”. Similar to 1.03, 1.16 and 1.17. A very long demonstration was required here.)
✸2.16 (p → q) → (~q → ~p) (If it’s true that “If this rose is red then this pig flies” then it’s true that “If this pig doesn’t fly then this rose isn’t red.”)
✸2.17 ( ~p → ~q ) → (q → p) (Another of the “Principles of transposition”.)
✸2.18 (~p → p) → p (Called “The complement of reductio ad absurdum. It states that a proposition which follows from the hypothesis of its own falsehood is true” (PM, pp. 103–104).)

Most of these theorems—in particular ✸2.1, ✸2.11, and ✸2.14—are rejected by intuitionism. These tools are recast into another form that Kolmogorov cites as “Hilbert’s four axioms of implication” and “Hilbert’s two axioms of negation” (Kolmogorov in van Heijenoort, p. 335).

Propositions ✸2.12 and ✸2.14, “double negation”: The intuitionist writings of L. E. J. Brouwer refer to what he calls “the principle of the reciprocity of the multiple species, that is, the principle that for every system the correctness of a property follows from the impossibility of the impossibility of this property” (Brouwer, ibid, p. 335).

This principle is commonly called “the principle of double negation” (PM, pp. 101–102). From the law of excluded middle (✸2.1 and ✸2.11), PM derives principle ✸2.12 immediately. We substitute ~p for p in 2.11 to yield ~p ∨ ~(~p), and by the definition of implication (i.e. 1.01 p → q = ~p ∨ q) then ~p ∨ ~(~p)= p → ~(~p). QED (The derivation of 2.14 is a bit more involved.)

Reichenbach

It is correct, at least for bivalent logic—i.e. it can be seen with a Karnaugh map—that this law removes “the middle” of the inclusive-or used in his law (3). And this is the point of Reichenbach’s demonstration that some believe the exclusive-or should take the place of the inclusive-or.

About this issue (in admittedly very technical terms) Reichenbach observes:

The tertium non datur

29. (x)[f(x) ∨ ~f(x)]

is not exhaustive in its major terms and is therefore an inflated formula. This fact may perhaps explain why some people consider it unreasonable to write (29) with the inclusive-‘or’, and want to have it written with the sign of the exclusive-‘or’

30. (x)[f(x) ⊕ ~f(x)], where the symbol “⊕” signifies exclusive-or^[7]

in which form it would be fully exhaustive and therefore nomological in the narrower sense. (Reichenbach, p. 376)

In line (30) the “(x)” means “for all” or “for every”, a form used by Russell and Reichenbach; today the symbolism is usually {\displaystyle \forall } x. Thus an example of the expression would look like this:

• (pig): (Flies(pig) ⊕ ~Flies(pig))
• (For all instances of “pig” seen and unseen): (“Pig does fly” or “Pig does not fly” but not both simultaneously)

Logicians versus Intuitionists

From the late 1800s through the 1930s, a bitter, persistent debate raged between Hilbert and his followers versus 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”, and was thereby invoking the law of excluded middle cast into 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), and that work gave a precise definition to 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 lecture in 1941 at Yale and the 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” (Dawson, p. 157))

Gödel’s approach to the law of excluded middle was to assert that objections against “the use of ‘impredicative definitions'” “carried more weight” than “the law of excluded middle and related theorems of the propositional calculus” (Dawson p. 156). 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.