Philosophy
Intuitionistic Logic and the Rejection of Excluded Middle
Quick fact
Intuitionistic logic rejects the law of excluded middle because it asserts that a statement like 'P or not P' is true only if we can prove P or prove not P, and for many mathematical statements (such as the famous Goldbach conjecture) we currently have neither proof.
Why this is interesting
In classical logic, every statement is either true or false—there's no middle ground. But what if some mathematical truths are only true when we can actually construct a proof?
Read the full explanation
Understanding Intuitionistic Logic and the Rejection of Excluded Middle
Think of classical logic as a courtroom where every proposition is either guilty or innocent—there's no undecided verdict. In classical logic, the law of excluded middle says 'either P is true or P is false', so every statement has a definite truth value, even if we don't know it. \n\nIntuitionistic logic, proposed by mathematician L.E.J. Brouwer, takes a different approach: a statement is true only if we can prove it, and false only if we can prove its negation. There's no notion of truth independent of proof. This is like a detective who only accepts a case as solved when there is concrete evidence—not just because the detective knows the suspect must be either guilty or innocent. \n\nIn this framework, the law of excluded middle (LEM) fails. The statement 'P or not P' would require either a proof of P or a proof of not P. If we have neither, we cannot assert the disjunction as true. For example, Goldbach's conjecture (every even number greater than 2 is the sum of two primes) has not been proved nor disproved, so in intuitionistic logic we cannot claim 'Goldbach's conjecture is true or false.' Classical logic, by contrast, says it must be one or the other, even though we don't know which.
A deeper explanation
Intuitionistic logic is a formal system that captures the constructive notion of proof. In this logic, the meaning of logical connectives is given by the BHK (Brouwer-Heyting-Kolmogorov) interpretation: \n- A proof of 'A and B' is a pair of proofs (one for A, one for B). \n- A proof of 'A or B' is either a proof of A or a proof of B. \n- A proof of 'if A then B' is a construction that transforms a proof of A into a proof of B. \n- A proof of 'not A' is a construction that takes any proof of A and produces a contradiction. \n\nWith this interpretation, the law of excluded middle 'A or not A' would require that for every proposition A, we have either a proof of A or a proof of not A. This is not generally true for undecided mathematical statements. Furthermore, in intuitionistic logic, double negation elimination fails: from a proof of 'not not A' (i.e., a proof that assuming not A leads to contradiction) we cannot construct a proof of A. This is because 'not not A' only tells us that A is not false, but it does not give us a constructive proof of A. \n\nThe rejection of LEM has significant consequences. Many classical proofs rely on non-constructive arguments, such as proof by contradiction that establishes existence by showing that non-existence is impossible. In intuitionistic logic, such proofs are invalid because they do not provide a witness. This has led to constructivist mathematics, where only objects that can be explicitly constructed are considered to exist. Moreover, intuitionistic logic is the foundation of the Curry-Howard correspondence, which relates proofs to programs, making it central to type theory and functional programming. Philosophically, it challenges the view that mathematical truth is independent of human knowledge, suggesting instead that truth is tied to provability.