Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

Your Answer


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.