Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving the contrapositive

  1. May 11, 2009 #1

    tgt

    User Avatar

    It can be proved by proof by contradiction. hence it is just a variant of it?
     
  2. jcsd
  3. May 14, 2009 #2
    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.
     
  4. May 14, 2009 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. May 14, 2009 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook