# Proving the contrapositive

1. May 11, 2009

### tgt

It can be proved by proof by contradiction. hence it is just a variant of it?

2. May 14, 2009

### Focus

Not really. Say you have a statement p, a proof by contradiction would be not p implies false. Contrapositive is a direct proof. Say you have the statement p imples q. To prove this via contradiction you assume p is true and q is false then derive a contradiction, to prove this via contrapositive you assume not q is true (i.e. q is false) and prove that this imples p is false.

3. May 14, 2009

### CRGreathouse

Statement: p ⇒ q
Proof by contradiction: Assume p and ¬q; prove ⊥.
Proof by contraposition: Assume ¬q; prove ¬p.

A proof by contraposition can be turned into a proof by contradiction by adding the step "p ∧ ¬p ⇒ ⊥". But proofs by contradiction don't need to prove ¬p as an intermediate step; they can prove contradiction in other ways. So proof by contradiction is stronger.

On the other hand, the more constrained proof by contraposition is considered a constructive technique, while proof by contradiction is always considered nonconstructive. So if you have a choice use contraposition.

4. May 14, 2009

### HallsofIvy

Staff Emeritus
If a statement is "P implies Q" then the contrapositive is "if not Q then not P" and is equivalent. Proving the contrapositive is a kind of proof by contradiction in which we assume the conclusion is false and arrive at a contradiction: "if not Q" is certainly assuming the conclusion is false and proving "not P" would give a contradiction with "if P".

However, "proof by contradiction" more general. You start with "if not Q" but only need to arrive at two statements that contradict one another. I have seen proofs in which the two contraditory statements have no apparent connection with the hypothesis, P.