nLab
weak excluded middle

Weak excluded middle

Weak excluded middle

Definition

In logic, the principle of weak excluded middle says that for any proposition PP we have ¬P¬¬P\neg P \vee \neg\neg P.

This follows from the full principle of excluded middle, which says that for any QQ we have Q¬QQ \vee \neg Q (take Q=¬PQ = \neg P). Thus, in classical mathematics weak excluded middle is just true. But in constructive mathematics (i.e. intuitionistic logic), it is a weaker assumption than full excluded middle.

Equivalent forms

De Morgan’s Law

In intuitionistic logic, de Morgan’s law often refers to the one of de Morgan's four laws that is not an intuitionistic tautology, namely ¬(PQ)(¬P¬Q)\neg (P \wedge Q) \to (\neg P \vee \neg Q) for any P,QP,Q.

Theorem

De Morgan’s law is equivalent to weak excluded middle.

Proof

If de Morgan’s law holds, then since ¬(P¬P)\neg (P \wedge \neg P), we have ¬P¬¬P\neg P \vee \neg\neg P, as desired. Conversely, if weak excluded middle holds and we have ¬(PQ)\neg (P\wedge Q), then from weak excluded middle we get ¬P¬¬P\neg P \vee \neg\neg P and ¬Q¬¬Q\neg Q \vee \neg\neg Q which give four cases. In three of those cases ¬P¬Q\neg P \vee \neg Q holds, while in the fourth we have ¬¬P\neg\neg P and ¬¬Q\neg\neg Q, which together imply ¬¬(PQ)\neg\neg(P\wedge Q) (see the first lemma here and its proof), contradicting the assumption of ¬(PQ)\neg (P\wedge Q); so the fourth case is impossible.

Last revised on May 30, 2019 at 17:48:46. See the history of this page for a list of all contributions to it.