Discrete Mathematics – Using Proof by Contradiction vs Proof of the Contrapositive

discrete mathematicslogicpropositional-calculus

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?

Best Answer

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 (P \land \lnot Q) \equiv P \rightarrow Q$

Related Question