Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@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. –  Did Feb 6 '13 at 20:45
add comment

6 Answers

up vote 23 down vote accepted

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

share|improve this answer
1  
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. –  Marc van Leeuwen Feb 6 '13 at 13:36
    
@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). –  Henning Makholm Feb 6 '13 at 14:01
    
@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"... –  Juris Feb 6 '13 at 14:48
    
@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". –  Maciej Piechotka Feb 6 '13 at 18:22
add comment

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

share|improve this answer
    
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 :) –  Juris Feb 6 '13 at 14:43
5  
@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). –  Maciej Piechotka Feb 6 '13 at 18:31
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Juris Feb 6 '13 at 14:44
add comment

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.
share|improve this answer
add comment

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)
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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