3
$\begingroup$

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?

$\endgroup$
1
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Replace \not Q by \lnot Q in the first sentence. :-) $\endgroup$ – Asaf Karagila Sep 12 '13 at 12:28
  • $\begingroup$ @Asaf: Fixed, thanks. Strangely MathJax didn't produce an overcrossed Q from \not Q for me. It just ignored the \not... $\endgroup$ – hmakholm left over Monica Sep 12 '13 at 12:38
  • $\begingroup$ For me it did. Strange... $\not Q$. $\endgroup$ – Asaf Karagila Sep 12 '13 at 12:39

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.