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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proof of contrapositive law

Loading...

Similar Threads - Proof contrapositive | Date |
---|---|

B Did President Garfield really come up with an alternate proof? | Mar 7, 2018 |

B Fermat's Last Theorem; unacceptable proof, why? | Feb 15, 2018 |

I Proof without words for Heron's formula | Jan 19, 2018 |

I Proof of an Inequality | Dec 19, 2017 |

I Can you make the induction step by contradiction? | Jun 19, 2016 |

**Physics Forums - The Fusion of Science and Community**