# Questions on logic behind “proof by contradiction”

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?

• For the equivalence between $¬(P⇒Q)$ and $P∧¬Q$ we can prove it with a proof system, like Natural Deduction. Do you know it ? – Mauro ALLEGRANZA Sep 21 '14 at 10:29
• 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$. – Mauro ALLEGRANZA Sep 21 '14 at 10:32