Is proof by contradiction always a sufficient proof technique?

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?

-

1 Answer

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

-
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