- #1
Dr. Seafood
- 120
- 0
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?
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: