# Proof of contrapositive law

1. Jul 18, 2011

### Dr. Seafood

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. Jul 19, 2011

### Dr. Seafood

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
3. Jul 20, 2011

### nickalh

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.