Excluded middle, explained
How thinking about evidence instead of truth forces logicians to give up on a fundamental law of logic.
The law of excluded middle is the assertion that every statement of the form ‘P or not-P’ is true. In symbolic notation: ‘φ ∨ ¬φ.’ Is this law logically valid and a good reasoning principle?
If you understand logic as talking about truth and falsity, then the law of excluded middle turns out to be valid: Consider any statement φ. Is is true? If so, then ‘φ or not-φ’ must be true because its first conjunct, φ, is true. Is φ false? Well, then ‘not-φ’ must be true. But then, ‘φ or not-φ’ must be true because the second conjunct, ‘not-φ,’ is true.
The assumption that every statement φ is either true or false is called bivalence. It states that there are only two truth values: truth and falsity. The logic arising from the principle of bivalence is classical logic — the logic we use in everyday mathematical reasoning.
The argument above therefore shows that the law of excluded middle is valid in classical logic. For classical logicians, it’s a logical law.
Not everyone is convinced that logic is bivalent. Intuitionistic logicians do not believe that every statement has one of two truth values. They do not consider the law of excluded middle a logical truth. How so?
Intuitionistic logicians give up on the idea that every statement must be either true or false. Instead, they think about a statement in terms of evidence. To assert a statement φ means to have a proof for φ.
- To have a proof for ‘φ and ψ’ (‘φ ∧ ψ’) means to have a proof for φ and a proof for ψ.
- To have a proof for ‘φ or ψ’ (‘φ ∨ ψ’) means to have a proof for φ or to have a proof for ψ.
- To have a proof for ‘φ implies ψ’ (‘φ → ψ’) means to have a procedure that converts a proof of φ into a proof of ψ.
- To have a proof for ‘not-φ’ (‘¬φ’) means to have a procedure to convert a proof of φ into an absurdity.
With this understanding of the logical symbols, we can see why intuitionistic logicians think that the law of excluded middle is incorrect: If ‘φ ∨ ¬φ’ was true for every statement φ, then this would mean that we either have a proof for φ or a proof for ‘¬φ’.
But there are statements for which this is not the case. Probably the most famous example is Cantor’s Continuum Hypothesis (explained here): Neither the continuum hypothesis nor its negation have a proof in ZF-set theory. Therefore, ‘CH or not-CH’ does not hold in intuitionistic ZF-set theory but it does in classical ZF-set theory.
So the law of excluded middle is not valid in intuitionistic logic. Does that mean that it’s false? No. Because that would mean that ‘¬(φ ∨ ¬φ)’ holds for some statement φ. But that‘s impossible, even in intuitionistic logic.
Intuitionistic logic is sometimes called revisionary because if mathematicians adopted it for mathematical proofs, they would need to revise mathematics. A lot of proofs wouldn’t be valid anymore.
This is because the law of excluded middle is equivalent to the law of double negation elimination: the statement that ‘not-not-φ implies φ’ (‘¬¬φ → φ’). Double negation elimination allows to make use of the following proof principle:
Proof by Contradiction. To show φ, assume that ¬φ and derive a contradiction.
Imagine you have shown that a certain, very complicated set of equations has a solution in the real numbers. Now you want to show that the solution for these equation is rational. You could do it like this: Assume that the solution is irrational, and derive a contradiction.
A classical logician would be happy with such a proof. But the intuitionist would not. For them, all that this proof shows is that the solution is not-not-rational. That doesn’t mean it’s rational.
However, the following is perfectly acceptable by intuitionistic standards:
Proof of Negation. To show ¬φ, assume that φ and derive a contradiction.
For example, if you want to show that the square root of 2 is irrational and you do so by assuming it is rational and deriving a contradiction, then that’s a proof of negation. And that’s acceptable by intuitionistic standards! After all, a number is irrational if it’s not-rational, and that’s exactly what the proof shows.
If you derive a contradiction from assuming φ, then you proved that not-φ. That’s a proof by negation and intuitionistically valid. But if you derive a contradiction from assuming not-φ, then you only proved that not-not-φ. To conclude that φ, you need the power of classical logic (or a different intuitionistic proof).
Rejecting the law of excluded middle has deep consequences: Proofs by contradiction don’t work anymore. But don’t confuse proofs by contradiction with proofs of negation.
