Using proof by contradiction vs proof of 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: PQ
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?

Answer

To prove PQ, you can do the following:

  1. Prove directly, that is assume P and show Q;
  2. Prove by contradiction, that is assume P and ¬Q and derive a contradiction; or
  3. Prove the contrapositive, that is assume ¬Q and show ¬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 ¬Q; if we can then derive ¬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 ¬P, if one has assumed (P and ¬Q). Arriving at any contradiction counts in a proof by contradiction: say we assume P and ¬Q and derive, say, Q. Since Q¬Q is a contradiction (can never be true), we are forced then to conclude it cannot be that both (P¬Q).

But note that ¬(P¬Q)¬PQPQ.

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

  • P¬Q Premise
    • P
    • ¬Q
    • R
    • ¬R
    • ¬RR Contradiction


Attribution
Source : Link , Question Author : Kasper , Answer Author : amWhy

Leave a Comment