Axiom:Law of Excluded Middle

Context

The law of (the) excluded middle is one of the axioms of natural deduction.

The rule

All statements have a truth value of either true or false:

$\vdash p \lor \neg p$

Otherwise known as:

• (Principium) tertium non datur, Latin for third not given, that is, a third possibility is not possible;
• Principium tertii exclusi, the Principle of the Excluded Third (PET).

It can be written:

$\displaystyle {{} \over p \lor \neg p} \textrm{LEM} \qquad \text { or } \qquad {\top \over p \lor \neg p} \textrm{LEM}$

where the symbol $\top$ (called top) signifies tautology.

• Abbreviation: $\textrm{LEM}$
• Deduced from: Nothing.
• Depends on: Nothing.

Explanation

This is one of the Aristotelian principles upon which the whole of classical logic, and the majority of mainstream mathematics rests.

This rule is denied by the intuitionist school.

Truth Table Demonstration

We apply the Method of Truth Tables to the proposition $\vdash p \lor \neg p$.

As can be seen by inspection, the truth value of the main connective, that is $\lor$, is $T$ for each model of $p$.

$\begin{array}{|cccc|} \hline p & \lor & \neg & p \\ \hline F & T & T & F \\ T & T & F & T \\ \hline \end{array}$

$\blacksquare$

Also see

It is possible to derive the Law of Excluded Middle from the Rule of Double Negation Elimination, and treat the latter as axiomatic instead.

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorem $\text{T59}$
• Alan G. Hamilton: Logic for Mathematicians (1978): $\S 1.2$: Example $1.6 \ \text{(a)}$
• Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.2$