1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of contrapositive law

  1. Jul 18, 2011 #1
    I ran into some difficulties trying to show "prove" the contrapositive law (CPL). I remember in first year my professor showed that P ⇒ Q is logically equivalent to ¬Q ⇒ ¬P by showing that the truth tables for both statements were the same for all possible truth values of P and Q.

    Statement. Let A, B ⊆ S, where S is a set of an arbitrary nature, and let A ⊆ B. Then (S / B) ⊆ (S / A).

    Proof. Let A' = S / A and B' = S / B. If x ∈ B', then x ∉ B and so x ∉ A since A is a subset of B; thus x ∈ A'.
    Since x ∈ B' ⇒ x ∈ A', we have by definition B' ⊆ A'. □

    This shows the usefulness of CPL in the following sense: If P and Q are statements involving items in S, then let A = {x ∈ S : P(x)} and B = {x ∈ S : Q(x)}. Since A ⊆ B, all x satisfying P also satisfy Q, i.e. P ⇒ Q. Obviously A' = {x ∈ S : ¬P(x)} and B' = {x ∈ S : ¬Q(x)}. By the CPL above and the same idea, since B' ⊆ A' we get ¬Q ⇒ ¬P.

    There is a problem with the proof: I used the claim that since A ⊆ B, x ∉ B ⇒ x ∉ A (1). I can think of how to intuit this geometrically, since we can draw A as a circle inside the larger circle B and see clearly that elements not in circle B are certainly not in circle A. Still, this is an implicit use of the CPL: we know "x ∈ A ⇒ x ∈ B", by definition of subset. The contrapositive of this is (1). Obviously I can't make use of the CPL within its own proof. I attempted to show (1) independently before realizing that simply saying "obviously, since A is a subset of B" might be the best way to say it, though not the most formal/rigorous.

    I feel like I've sidestepped the CPL by using it here without explicitly stating it. Or maybe this is how a lot of proofs of fundamental/obvious statements are done: they are explained in an intuitive way using whichever convenient notation we have. I guess I'm just looking for a proof of (1), is there a better way to show it?
    Last edited: Jul 19, 2011
  2. jcsd
  3. Jul 19, 2011 #2
    Bump. I'm srs. Halp D:

    Essentially trying to prove that if A ⊆ B, then x ∉ B ⇒ x ∉ A, without using the contrapositive law.

    edit: Okay, it escaped me before, but there is a very obvious way to show this. Suppose A ⊆ B and x ∉ B. If x ∈ A, then x ∈ B by definition of subset, a contradiction; thus x ∉ A.
    Last edited: Jul 19, 2011
  4. Jul 20, 2011 #3
    Your method is essentially sound but could a little cleaning up.
    Suppose A is a subset of B and x ∉ B.
    Goal: Prove x is not in A.

    Assume for contradiction, x is in A.
    But the definition of subset tells us, if x is in A, then x is in B.
    (Modus ponens) So x is in B.
    This contradicts the given statement.
    a contradiction; thus x ∉ A.

    This could be cleaned up further, to more exactly match your original “statement”, but I leave that to you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook