Does law of excluded middle prove itself?

You have a problem in that assuming $L$ to be false does not mean that $L\veebar\bar{L}$ is false. It just means that $A\veebar\bar{A}$ is false for some statement $A$, which may not be $L$.


In addition to what Matt pointed out, the proof step

We have shown that [such-and-such] is true regardless of our assumptions, so it is proven.

is dangerous when you don't already have the law of excluded middle. This proof step usually depends on an implicit use of the law of excluded middle to establish that at least one of the assumptions that were investigated must be true. And indeed you're doing that here when your two assumptions are $L$ and $\overline L$. Without the law of excluded middle, proof by contradiction is not valid! (A negated statement can still be proved by contradiction, though).

Additionally, you seem to be arguing not from any particular logical axioms, but simply from an inspection of the truth table for $\veebar$ to establish that $\overline{A\veebar B}$ implies $(A \land B) \lor (\overline A \land \overline B)$. However, if you allow reasoning from truth tables at all, you might as well prove the law of excluded middle directly by writing down the truth table for $V\mapsto V\veebar \overline V$.

In intuitionistic logic, which rejects the law of excluded middle, arguments by truth tables are not valid either.


You can prove the law of excluded middle if you start by assuming something else that is equivalent to it. For example, the law $A\Leftrightarrow \overline{\overline A}$ is equivalent to excluded middle, as is the rule of indirect proof $(\overline A\Rightarrow A)\Rightarrow A$ or Peirce's law $((A\Rightarrow B)\Rightarrow A)\Rightarrow A$.


I'm assuming the question is really "is the LEM provable from the other axioms," not "does it prove itself," because everything proves itself.

In addition to those problems mentioned in Matt's answer and Henning's answer, another problem with the proof is that one cannot use the lack of LEM to conclude that there is any proposition $P$ such that $\neg (P \vee \neg P)$ actually holds. In fact, it cannot hold—otherwise we could deduce $\neg P$, and we could also deduce $\neg\neg P$, getting a contradiction. Therefore $\neg\neg(P \vee \neg P)$ holds. (Note that proving a negative statement by contradiction does not require LEM—in fact the negation $\neg Q$ can be defined as "$Q \to \bot$" where $\bot$ denotes "contradiction" or "absurdity".)

The validity of $\neg\neg(P \vee \neg P)$ is a special case of the fact that whenever $Q$ is a theorem of classical logic, $\neg \neg Q$ is a theorem of intuitionistic logic (which is what you get by removing LEM from the usual formulation of classical logic.)

So it's not that $P \vee \neg P$ can be false, just that without LEM you have no way to derive it unless (1) you know that $P$ is true, or (2) you know that $\neg P$ is true (i.e. that $P$ is false.)

Tags:

Logic