Proof by contradiction vs Prove the contrapositive

Question

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 proofs by contradiction, and the other proofs the contrapositive, the proofs look almost exactly the same.

For example, say I want to proof: $P \implies Q$ When I want to proof 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 proof 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 proof 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?

Answer 1

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$

---

Answer 2

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.