The law of excluded middle is a logical principle that says that for any sentence $A$, the sentence $A\lor\,\neg A$ is true. This is a valid law of classical logic, but is rejected by intuitionistic logic. However, for some the proofs of mathematical theorems that use the law of excluded middle, there exists an alternative proof of the theorem that does not use the law of excluded middle. Is there any theorem of classical mathematics that cannot be proved without using the law of excluded middle?

  • $\begingroup$ @Arthur One may observe by a simple recurrence that its continued fraction is $[1;2,2,\dots]$ forever, and an infinite continued fraction can't be rational. This argument doesn't generalize to a lot of familiar situations, though. $\endgroup$ – Ian Jul 7 '16 at 0:58
  • 1
    $\begingroup$ math.stackexchange.com/questions/1209852/… $\endgroup$ – user301988 Jul 7 '16 at 1:03
  • $\begingroup$ See math.stackexchange.com/a/1852683/630 $\endgroup$ – Carl Mummert Jul 11 '16 at 3:20

Well what do you mean by "theorem of classical mathematics"? The answer is going to change depending on how you define it.

If for example you have first-order theory over a language with a predicate symbol $P$ that has no axioms at all. Then $\forall x\ ( P(x) \lor \neg P(x) )$ is a theorem, but is not provable in intuitionistic logic.

For a more crucial example, take any formal system $S$. Then "$S$ is consistent or $S$ is inconsistent." is a classically valid sentence but not provable intuitionistically. So not having classical logic makes one unable to state intuitively true facts.

  • $\begingroup$ By the way, $\sqrt{2}$ not being rational does not need excluded middle, since the conclusion is "There is no rational $r$ such that $r^2 = 2$." which is valid intuitionistically because we can from "There is a rational $r$ such that $r^2 = 2$." derive a contradiction. $\endgroup$ – user21820 Jul 7 '16 at 6:18

Just to clarify: the intuitionists' rejection of Excluded Middle does not mean embracing $\lnot (A \lor \lnot A)$ for all $A$! Some instances of Excluded Middle are acceptable, namely those for which we can prove either $A$ or $\lnot A$.

With this in mind, two standard examples of classical theorems that are not valid intuitionistically are

Trichotomy For each $x\in\mathbb{R}$ exactly one of the following holds: $x < 0$ or $x = 0$ or $x > 0$.

Or, a particular case: $x = 0 \lor x \neq 0$.

Intermediate Value Theorem If $f:[a, b]\to\mathbb{R}$ is continuous and $f(a) < m < f(b)$ for some $m \in\mathbb{R}$, then there exists a $c\in (a,b)$ such that $f(c) = m$.

(The proof of the Intermediate Value Theorem may not obviously rely on Excluded Middle, but it does rely on the Least Upper Bound property for $\mathbb{R}$ which is also rejected by intuitionists.)

Diagnosing what is "wrong" with them intuitionistically is a bit more subtle than pointing out where they use Excluded Middle. What is usually done is to show that these theorems imply an unacceptable instance of Excluded Middle, and must therefore be rejected.

For Trichotomy, one constructs a "weak counterexample". Let $G(n) \equiv \text{"}2n+4 \text{ is the sum of two primes"}$ for $n \in \mathbb{N}$ (including 0). We then define the following sequence:

$$ a_n = \begin{cases} 2^{-n} & \text{if }(\forall k\leq n)G(k);\\ 2^{-k} & \text{if } k \leq n \text{ is the first number such that } \lnot G(k);\end{cases}$$

The predicate $G(n)$ is decidable: for each $n$, a finite calculation will show whether $G(n)$ holds or $\lnot G(n)$. Hence $(a_n)_{n\in\mathbb{N}}$ is a well-defined sequence. Furthermore, we can prove that it is Cauchy: for each $N\in\mathbb{N}$, compute $G(N)$. If true, then $|a_n - a_m| < 2^{-N}$ for all $n,m > N$; if false, then there is a $k < N$ such that $a_n = 2^{-k}$ for all $n>k$, so $|a_n - a_m| = 0 < 2^{-N}$ for all $n,m > N$. Therefore, $(a_n)_n$ defines a bona fide real number, call it $a$.

Note that nowhere in the proof that $(a_n)_n$ is a Cuachy sequence (or even a sequence) did I use the fact that either $G(n)$ holds for all $n\in\mathbb{N}$ or it fails for some $n$. I only assumed that, for any particular $n$, $G(n)\lor\lnot G(n)$. This is intuitionistically acceptable since we could (in principle) check all prime numbers less than $n$ in order to find a pair whose sum is $n$ or prove by exhaustion that there isn't such a pair.

I claim that $a$ is a (weak) counter-example to Trichotomy's corollary: it is clear from the definition that $$a = 0 \iff (\forall n\in\mathbb{N})G(n),$$ so $$a = 0 \lor a \neq 0 \iff (\forall n\in\mathbb{N})G(n) \lor \lnot(\forall n\in\mathbb{N})G(n).$$ The Right Hand Side of the last equivalence is a "problematic" instance of Excluded Middle: it asserts (intuitionistically) that the Goldbach Conjecture is either proved or refuted. At the time of my writing this, the Goldbach Conjecture remains open, so it is not intuitionistically valid to assert: Goldbach Conjecture $\lor$ $\lnot$(Goldbach Conjecture). It follows that we cannot assert $a = 0 \lor a \neq 0$.

The Intermediate Value Theorem suffers a similar fate, although one can prove (intuitionistically)

Intuitionistic Intermediate Value Theorem. If $f:[a, b]\to\mathbb{R}$ is continuous and $f(a) < m < f(b)$ for some $m \in\mathbb{R}$, then for all $\varepsilon > 0$ there exists a $c\in (a,b)$ such that $|f(c) - m| < \varepsilon$.

Even if we cannot "rescue" all theorems proved using Excluded Middle (e.g. by finding proofs that circumvent Excluded Middle), we can often prove analogous theorems that are "close enough" and classically equivalent -- although not intuitionistically equivalent!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.