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.

Is proof by contradiction always a sufficient proof technique ?

A proof by contradiction has the form:

Let $P$ and $Q$ be statements. If $ P \rightarrow Q \land \lnot Q $ then you can conclude $\lnot P$.

However just because $P$ lead to a contradiction, how can one be sure that $\lnot P$ is true ? What if the axiomatic system allows both $P$ and $\lnot P$ to be false in different context? I mean you could prove $P$ is true by showing $\lnot P$ leads to a contradiction, but what if a different context you can show $\lnot P$ is true by showing $P$ leads to a contradiction?

Is the theory of mathematics always constructed so $P$ and $\lnot P$ cannot both be false in different context?

share|improve this question
add comment

1 Answer 1

What $P\to Q\land \neg Q$ means is that in every context where $P$ is true, $Q$ and $\neg Q$ will both be true. Since there is no situation in which $Q$ and $\neg Q$ are both true, there cannot be any situation where $P$ is true either. So instead $\neg P$ must be true always.

Sure, one can imagine a $Q$ that is sometimes true and sometimes false. But then $Q\land \neg Q$ will still always be false, because there's no case in which $Q$ and $\neg Q$ is true simultaneously. And for such a $Q$ you shouldn't be able to prove $P\to Q\land \neg Q$, unless $P$ itself is never true ...

share|improve this answer
    
Replace \not Q by \lnot Q in the first sentence. :-) –  Asaf Karagila Sep 12 '13 at 12:28
    
@Asaf: Fixed, thanks. Strangely MathJax didn't produce an overcrossed Q from \not Q for me. It just ignored the \not... –  Henning Makholm Sep 12 '13 at 12:38
    
For me it did. Strange... $\not Q$. –  Asaf Karagila Sep 12 '13 at 12:39
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.