Does law of excluded middle prove itself?

Question

Law of excluded middle says that for any proposition ($A$) either it is true or it's negation ($\bar{A}$) is true: $A\veebar\bar{A}$.

When I was taught math logic, this was given as an axiom, but I thought of a proof of this law. My proof goes like this:

1) Let's assign letter $L$ to mean the law of excluded middle. If assume that it is correct, it instantly follows that $L$ is correct. Let's instead assume that it is wrong: $\bar{L}$.

2) If we use law of excluded middle, we would get that $L\veebar\bar{L}$. But we assumed that this is wrong. And the law could be wrong in two ways - either both $L$ and $\bar{L}$ could be wrong or both are correct.

3) We have assumed that $\bar{L}$ is true, so it can't be that they are wrong, thus both must be correct. We have shown that $L$ is true regardless of our assumptions, so it is proven.

Is this proof alright or it logically fails somewhere?

Does this interfere with Gödel's completeness stuff in any way?

Answer 1

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$.

Answer 2

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$.

Answer 3

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.)

Answer 4

This law is an axiom, and if you don't want that you can always look at intuitionistic logic, or even non bi-valued logics (e.g., fuzzy logic).

I see your points, but how can you say that $L$ is either true or false, if you exclude the third middle?

If you exclude the axiom, I don't see ho you can state that $L$ may have just two values.

Answer 5

This is a standard second year Sentential Logic derivation of a THEOREM. I can't show it here but in words:

1. Prove $p \wedge \neg p$.
2. Assume the negation $\neg(p\wedge \neg p)$
3. and you can derive it from there.

Answer 6

Yes it does. You can assume that A or not A is false and deduce a contradiction.

~(A v ~A) (assumption)
A (assumption)
A v ~ A (v introduction)
contraction
~ A
A v ~ A (v introduction)
contradiction
~~(A v ~A)
(A v ~A)

Answer 7

These proofs are wrong. Using a proof by contradiction presumes the law of excluded middle. The structure of the proof you have provided is such that you prove that -(A v -A) cannot be the case, and conclude that its negation (A v -A) must be the case.

First, that is itself a use of the law of the excluded middle. Your proof argues that since it cannot be the case that-(A v -A), it must be the case that (A v -A) is true. However, this argument makes sense only with the additional premise -(A v -A) v (A v -A), which is the law of the excluded middle.

Secondly, following the same argument i just used, you first showed that if A, then -(A v -A) cannot be the case, and then you showed if -A, then -(A v -A) cannot be the case. In logic, the reason this is acceptable is because you have exhausted all the possible scenarios of the state of the world, and concluded that no scenario gives us -(A v -A). However, this relies on the idea that choosing A, and then -A, gives us an exhaustive list of all scenarios, and therefore once again, this argument relies on the law of excluded middle i.e. A v -A. It is precisely because of A v -A - that either A is the case or -A is the case and those are all the possibilities - that you conclude that -(A v -A) cannot be the case.

Hope this helps.