The Law of the Excluded Middle
Page last updated 11 Dec 2022
The law of the excluded middle is generally taken to be the assertion that a proposition must either be ‘true’ or ‘false’. However, what this is intended to signify depends on the interpretation of the terms ‘true’ and ‘false’.
Before proceeding further, we note that in the following we follow the convention that we assume that whatever mathematical system we use to prove mathematical statements is consistent, that is, that it is not contradictory, i.e., there is always an assumed axiom of non-contradiction that:
¬ (P ∧ ¬ P)
where ¬ indicates the negation of P, and ∧ signifies AND, i.e., it is always assumed that a proposition and its negation cannot both be proved in the system (regardless of whether or not that assumption is explicitly written as an axiom).
Intuitionistic logic asserts that we cannot assert in general the law of the excluded middle. In particular, intuitionistic logic asserts we can only assert the law of the excluded middle where no quantification over infinite quantities is involved, and rejects the notion that there is a Platonist pre-existing ‘true’ or ‘false’ value for propositions. The justification for this is that, at any given time, we may not know whether there must be a proof for a given proposition about infinitely many things or properties, or if there must be a proof of its negation.
A naive statement of the notion of the excluded middle might be something like:
True(P) XOR False(P)
where XOR is the exclusive OR which means that either True(P) or False(P) applies and that both cannot apply.
But, in fact, this leaves out the fact that the assertion itself is being asserted to be true, that is, what actually is being asserted is:
True [ True(P) XOR True(¬ P) ]
However, this does not address the question of what it means for a proposition to be ‘true’. And if ‘true’ is not equivalent to provable, then it is not clear what is being asserted, nor is it clear as to whether the claim is being made within the system or outside of the system.
But, in fact, there is no difficulty in stating, as an axiom for a system:
P ∨ ¬ P
This is not asserting that there must be a proof of P, nor is it asserting that there must be a proof of the negation of P, which is ¬ P. All it is asserting is that the entire expression P ∨ ¬ P is provable in the system (since it is an axiom of the system), and this applies for any proposition P. (Footnote: In a system where there is no notion of an independent ‘existence’ of the ‘truth’ or ‘falsity’ of a proposition (unlike Platonism), P ∨ ¬ P states nothing regarding ‘truth’ or ‘falsity’ of P; nor does it assert anything regarding the provability of the proposition P or its negation. )
Note that in a proof by contradiction, P ∨ ¬ P is taken to be an axiom of the system (whether implied or explicit), since in a proof by contradiction, the proposition P which is to be proved incorrect is assumed to apply, and along with the axiom of non-contradiction ¬ (P ∧ ¬ P), this implies the exclusive OR, i.e., the two axioms together imply P XOR ¬ P. This, in fact, is creating a new system which is the same as the original system except that there is an additional axiom which is this proposition P. When a contradiction is reached, that means that at least one of the axioms of the system makes the new system inconsistent. By the assumption that all the other axioms of the original system are consistent, the possibility that proposition P can be a valid proposition of that system, or that it can be proved within the original system is rejected. Nothing in such a method assumes any pre-existing Platonist mathematical entities.
A further insight may be given by the following. Suppose we have a propositional function B(n) with one free variable, and which does not involve any other infinite quantification, i.e: there are no quantifiers in the propositional function B(n). Then for a given system, for any specific value of n, say the value a, if the system is powerful enough, then either B(a) can be proven, or else the negation of B(a) can be proven. But we are not assuming anything about whether there is a proof of the generalization of B(n) or its negation. That is, there is no assumption that there must be a proof of:
For all n, B(n)
nor any assumption that there is a proof of:
¬ For all n, B(n)
All we are saying is that if P ∨ ¬ P is an axiom, then the proposition For all n, B(n) ∨ ¬ For all n, B(n) is provable. This does not imply that one of For all n, B(n) or ¬ For all n, B(n) must be provable, that is, there is no presumption that the system is complete.
Intuitionistic logic and double negation
The intuitionistic viewpoint contends that ¬ ¬ P is not necessarily the same as P (i.e: that the negation of the negation of P is not necessarily the same as P). But if one is asking:
Is Provable [¬ ¬ P] is the same as Provable [P]?
that is not the same question as asking:
Is ¬ Provable[¬ P] is the same as Provable[P]?
In the latter case, if the system is not complete, then if ¬ P is not provable in the system, then there is no implication that P must be provable in that system.
But there is no difficulty in having an axiom within a system that asserts the equivalence of P and ¬ ¬ P as:
P ≡ ¬ ¬ P
and which does not assert anything regarding the provability of P within the system.