6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @isomorphismes If you think the last sentence has nothing to do with the rest, please add a comment saying so (or an answer), but do not suggest to Edit the post. $\endgroup$ – Did Feb 6 '13 at 20:45
26
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Even stronger, $A$ cannot be $L$, since the set of statements over which $A$ ranges, as used in formulating $L$, cannot include the law $L$ itself. $\endgroup$ – Marc van Leeuwen Feb 6 '13 at 13:36
  • $\begingroup$ @Marc: Perhaps we're working in a system that has a rule of generalization for propositional variables, such that $(A\veebar\bar A) \vdash (A\veebar\bar A)\veebar\overline{(A\veebar \bar A)}$ by generalization. (Of course that wouldn't save the argument here, because such a rule of generalization would need to exclude variables that appear in a still-undischarged assumption). $\endgroup$ – Henning Makholm Feb 6 '13 at 14:01
  • $\begingroup$ @Marc I don't really see your point - I have seen axioms used on axioms in math logic course. The range is usually "any statement"... $\endgroup$ – Džuris Feb 6 '13 at 14:48
  • $\begingroup$ @Juris: Any statement in a given language - say any well formed propositional formula (or first-order). Self-referencing systems can easily lead to paradoxes such as Russel's or "This statement is false". $\endgroup$ – Maciej Piechotka Feb 6 '13 at 18:22
  • $\begingroup$ Even in intuitonistic logic, where the law of the excluded middle is generally invalid, there are some statements $P$ for which $P\lor \lnot P$ is true. $\endgroup$ – MJD Dec 14 '14 at 4:38
15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am aware that the law is also used in the way you pointed out, but I already told in the title that the law is being proved using itself here :) $\endgroup$ – Džuris Feb 6 '13 at 14:43
  • 5
    $\begingroup$ @Juris: Any law can by 'proven' from itself as (at least in most logics) $A \to A$ is valid. Let say I assume that all natural numbers are equal to 0. I know that $a = b \to ac = bc$. Any number can be written as multiplication of two numbers. Lets take arbitrary number $z = bc$. Let $0 = b$ (from assumption). Hence $0 = 0c = bc = 0$. Therefore all natural number are equal to 0. It is of course 'silly' axiom but $A \to A \not\vDash A$ (except possibly quite uninteresting case of 1-value logic). $\endgroup$ – Maciej Piechotka Feb 6 '13 at 18:31
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I know that this is an axiom, that's the reason why I started asking - it seemed strange that axiom appeared provable to me. $\endgroup$ – Džuris Feb 6 '13 at 14:44
0
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ How does Contradiction in case of A and in case of ~A lead to contradiction in ~(A v A) . $\endgroup$ – Shubham Ugare Aug 20 '15 at 14:33
0
$\begingroup$

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.

$\endgroup$

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.