Skip to main content

Subsection 5.1.5 Law of the Excluded Middle

We’ve just said that we will import all of the identities of Boolean logic into our system of predicate logic. There is one special case that we should say a bit more about.

The Law of the Excluded Middle:

For any statement P: P ∨ ¬P

The Law of the Excluded Middle (LEM) is a useful theorem proving tool.

Video cover image

Watch the video for a good example. In it, we prove that there exist irrational numbers x and y such that:

\(x^y\) is rational.

Classical logic, following Aristotle, assumes both LEM and the Principle of Noncontradiction:

For any statement P: ¬(P ∧ ¬P)

In Boolean logic, both of these rules are tautologies:

Table 5.1.1. Noncontradiction
LEM Noncontradiction
P ¬P P ∨ ¬P P ∧ ¬P ¬(P ∧ ¬P)
T F T F T
F T T F T

In predicate logic, they are not. They (or some variant) must be asserted as premises. The Principle of Noncontradiction is not controversial, since it’s not possible to build a useful logical system without it.

LEM, however, is slightly controversial. There are philosophers and mathematicians (such as constructivists) who don’t assume it.

But consider the following derivation:

[1] ¬(P ∧ ¬P) Principle of Noncontradiction

[2] ¬P ∨ ¬ ¬ P De Morgan

[3] ¬PP Double Negation

[4] P ∨ ¬P Commutativity

Line [4] is exactly LEM. We have derived it from the (noncontroversial) Principle of Noncontradiction. Why then, must LEM be assumed as a separate premise if we want to use it? The answer is that, in predicate logic, Double Negation is not a tautology. It too is rejected by the constructivists.

Arguments for rejecting LEM (and Double Negation) fall into at least two categories:

  • Philosophical and mathematical ones. For example, mathematicians from the constructivist school do not want to accept, as a proof of the existence of some object x with property P, anything short of the exhibition of a specific such x or a concrete procedure for finding it.

    Video cover image

  • Essentially linguistic ones. There are English sentences that, on first analysis, seem to contradict LEM in the sense that they do not appear to be either true or false. Further analysis often shows that the issue is the mapping from English into logic, rather than a logical problem with the LEM.

We will follow Aristotle and assume the Law of the Excluded Middle. Then we can prove Double Negation by running the derivation we just did, but backwards. (Alternatively, we could assume Double Negation and then prove LEM.)

Exercises Exercises

Exercise Group.

Assume standard definitions of the words used here. Mark each argument as sound (correct) or not.
1.

(Part I)

[1] x is an integer Premise

[2] x is not negative Premise

[3] x is a positive integer LEM [1], [2]

  1. Sound

  2. Not sound

Answer.
Correct answer is B.
Solution.
Explanation: This is an example of a false dichotomy. An integer can be positive, negative, or 0. So we can’t use LEM with [1] and [2] to conclude that x is positive. It might be 0.
2.

(Part II)

[1] x is an integer Premise

[2] x is not even Premise

[3] x is an odd integer LEM [1], [2]

  1. Sound

  2. Not sound

Answer.
Correct answer is A.
Solution.
Explanation: By the definitions of odd and even, every integer must be one or the other. So if x isn’t even, it must be odd.