2
$\begingroup$

I'm trying to understand the logic behind "proof by contradiction" and hoping that I can clear up a few things in this post.

First of all, suppose I have a proposition $P$ and from this I can imply some statement $Q$, i.e. $P\Rightarrow Q$, then to prove this by contradiction I assume the negation of this, $\neg \left(P\Rightarrow Q \right)$, which is equivalent to assuming $P\wedge \neg Q$, i.e. $\neg \left(P\Rightarrow Q \right)=P\wedge \neg Q$. Is there any way to prove this algebraically (apologies, I'm fairly new to logic)? I have shown this is true via a truth table, but not sure whether this counts as a proof or not?!

Next, having assumed $P\wedge \neg Q$, following logically from this if we find some statement $R$ such that a contradiction arises, $R\wedge \neg R$ then it follows that $\neg \left(P\Rightarrow Q \right)\Rightarrow R\wedge \neg R$. Now, my understanding of this is that, as $R\wedge \neg R$ is always false, then the only way this implication can be true is if $\neg \left(P\Rightarrow Q \right)$ is false, which implies that $P\Rightarrow Q $ is true, hence proving think intial claim. Is this the correct reasoning?

Thanks for your time.

$\endgroup$
  • $\begingroup$ For the equivalence between $¬(P⇒Q)$ and $P∧¬Q$ we can prove it with a proof system, like Natural Deduction. Do you know it ? $\endgroup$ – Mauro ALLEGRANZA Sep 21 '14 at 10:29
  • 1
    $\begingroup$ Basically YES. See also this post. In general, a proof by contradiction of $A$ exploit the following rule : $(¬A→B)→((¬A→¬B)→A)$. We assume the falsity of $A$, i.e. $\lnot A$ as true and derive both $B$ and $\lnot B$, i.e. a contradiction. Thus, by modus ponens, having proved $(¬A→B)$ and $(¬A→¬B)$ we can conclude with $A$. In your example, $A$ is $P⇒Q$. $\endgroup$ – Mauro ALLEGRANZA Sep 21 '14 at 10:32
  • $\begingroup$ @MauroALLEGRANZA Ah, thanks for the information! I'm fairly new to the subject, so unfortunately haven't heard of 'Natural deduction'. If you know of any useful introductory notes on logic (and/or propositional logic) that you can suggest, that'd be great. In any case, really appreciate the help! $\endgroup$ – Will Sep 21 '14 at 10:53
  • $\begingroup$ There are many good textbook. See e.g. Peter Smith, An Introduction to Formal Logic (2003) and (available on-line) : Stephen Simpson, Mathematical Logic $\endgroup$ – Mauro ALLEGRANZA Sep 21 '14 at 11:17
  • $\begingroup$ Great! Thanks for the recommendations. $\endgroup$ – Will Sep 21 '14 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.