# Proof by contradiction vs Prove the contrapositive

What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by contradiction, and the other proves the contrapositive, the proofs look almost exactly the same.

For example, say I want to prove: $P \implies Q$ When I want to prove by contradiction, I would say assume this is not true. Assume $Q$ is not true, and $P$ is true. Blabla, but this implies $P$ is not true, which is a contradiction.

When I want to prove the contrapositive, I say. Assume $Q$ is not true. Blabla, this implies $P$ is not true.

The only difference in the proof is that I assume $P$ is true in the beginning, when I want to prove by contradiction. But this feels almost redundant, as in the end I always get that this is not true. The only other way that I could get a contradiction is by proving that $Q$ is true. But this would be the exact same things as a direct proof.

Can somebody enlighten me a little bit here ? For example: Are there proofs that can be proven by contradiction but not proven by proving the contrapositve?

-
Also related: math.stackexchange.com/questions/71245/… and more importantly, math.stackexchange.com/questions/227109/… –  Asaf Karagila Dec 20 '12 at 19:06
Excellent question, +1. –  Matt N. Dec 20 '12 at 19:16
Andrej Bauer had a recent blog post about this. "I am discovering that mathematicians cannot tell the difference between “proof by contradiction” and “proof of negation”. " –  MJD Dec 20 '12 at 22:39
@MJD: Nearly three years is not very recent in terms of the internet. Just to get some perspective, Google+ was not yet conceived when Andrej posted this. –  Asaf Karagila Dec 21 '12 at 1:10
@asaf: I thought it was recent because I hadn't seen it when it was new, or perhaps because I saw it when it was new, forgot it, and saw it again last week. –  MJD Dec 21 '12 at 1:24

To prove $P \rightarrow Q$, you can do the following:

1. Prove directly, that is assume $P$ and show $Q$;
2. Prove by contradiction, that is assume $P$ and $\lnot Q$ and derive a contradiction; or
3. Prove the contrapositive, that is assume $\lnot Q$ and show $\lnot P$.

Sometimes the contradiction one arrives at in $(2)$ is merely contradicting the assumed premise $P$, and hence, as you note, is essentially a proof by contrapositive $(3)$. However, note that $(3)$ allows us to assume only $\lnot Q$; if we can then derive $\lnot P$, we have a clean proof by contrapositive.

However, in $(2)$, the aim is to derive a contradiction: the contradiction might not be arriving at $\lnot P$, if one has assumed ($P$ and $\lnot Q$). Arriving at any contradiction counts in a proof by contradiction: say we assume $P$ and $\lnot Q$ and derive, say, $Q$. Since $Q \land \lnot Q$ is a contradiction (can never be true), we are forced then to conclude it cannot be that both $(P \land \lnot Q)$.

But note that $\lnot (P \land \lnot Q) \equiv \lnot P \lor Q\equiv P\rightarrow Q.$

So a proof by contradiction usually looks something like this ($R$ is often $Q$, or $\lnot P$ or any other contradiction):

• $P \land \lnot Q$ Premise
• $P$
• $\lnot Q$
• $\vdots$
• $R$
• $\vdots$
• $\lnot R$
• $\lnot R \land R$ Contradiction

$\therefore \lnot (\lnot P \land Q) \equiv P \rightarrow Q$

-
"We are forced then to conclude $¬P$, since $Q∧¬Q$ is a contradiction." But this is essentially proving directly $(1)$, right ? –  Kasper Dec 20 '12 at 19:11
No, this is not the same as proving directly: To prove P, one uses step by step implications to arrive directly at $Q$, without assuming $\lnot Q$. (2) Note that the contradiction obtained may may be that assuming P and $\lnot Q$ leads to both $R \land \lnot R$ (R may happen to be Q)$. – amWhy Dec 20 '12 at 19:18 Yes, Kasper, usually. It's just that in longer proofs, we may find a point were some other statement AND its negation follow from assuming both$P\land \lnot Q$. (e.g., P may imply R, and$\lnot Q$may imply$\lnot R$, in which we have to conclude that we cannot have both$P$and$\lnot Q$, which is equivalent to proving$P\rightarrow Q$). – amWhy Dec 20 '12 at 19:44 Okay, I understand. I've one other question if you don't mind :). Does a problem like the following exist? You're assuming:$P∧¬Q$(to prove a contradiction). And in this problem it's impossible to prove$Q∧¬Q$or$P∧¬P$from this assumption. But it's possible to prove another contradiction$R∧¬R$. – Kasper Dec 20 '12 at 20:02 Yes, I'll try to find an example. There are many...usually longer proofs, where we assume$P \land \lnot Q$...then show$\lnot Q \rightarrow q_i ....\rightarrow...q_j....\rightarrow R$and$P \rightarrow ...p_i....\rightarrow...p_j \rightarrow \lnot R$, giving$R \land \lnot R$. When I have a little time to look through some texts, for a shortish proof using this, I'll post here, or we can go through it in chat...either way, I'll let you know. – amWhy Dec 20 '12 at 20:09 show 7 more comments It's not the same. If$P$and$Q$are statements about instances that (a priori independently) are true for some instances and false for others then proving$P\Rightarrow Q$is the same as proving the contrapositive$\neg Q\ \Rightarrow \neg P$. Both mean the same thing: The set of instances for which$P$is true is contained in the set of instances where$Q$is true. Proving a statement$A$by contradiction is something else: You add$\neg A$to your list of axioms, and using the rules of logic arrive at a contradiction, e.g., at$1=0$. Then you say: My axiom system was fine before adding$\neg A$. Since this addition has spoiled it, in reality$A$has to be true. An example: You want to prove the statement $$A:\quad {\rm "The\ number}\ \sqrt{2}\ {\rm is\ irrational."}$$ Then you add$\sqrt{2}={p\over q}\$ to your list of axioms about rational numbers and arrive at a contradiction.

-