Proof of contrapositive law

In summary, the conversation discusses the usefulness of the contrapositive law in proving statements involving sets. The proof provided uses the claim that if A is a subset of B, then x ∉ B ⇒ x ∉ A. The speaker also expresses their concern about implicitly using the contrapositive law in their proof and asks for a better way to show it. The summary then provides a cleaned-up version of their suggested proof, showing that if A is a subset of B and x ∉ B, then x ∉ A.
  • #1
Dr. Seafood
121
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?
 
Last edited:
Mathematics news on Phys.org
  • #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:
  • #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.
 

What is the proof of contrapositive law?

The contrapositive law is a logical rule that states if a conditional statement is true, then its contrapositive statement is also true. The proof of this law involves using the truth tables for conditional statements and their contrapositives.

Why is the contrapositive law important?

The contrapositive law is important because it allows us to prove the validity of an argument by showing that the contrapositive statement is true. This can be useful in mathematics, logic, and computer programming.

How is the contrapositive law used in mathematics?

In mathematics, the contrapositive law is often used in proofs by contradiction. This involves assuming the negation of a statement and showing that it leads to a contradiction, which then proves the original statement to be true.

Can you give an example of the contrapositive law?

Sure, one example of the contrapositive law is the statement "If it is raining, then the ground is wet." The contrapositive of this statement is "If the ground is not wet, then it is not raining." Both statements are logically equivalent and can be used interchangeably in a proof.

Is the contrapositive law always true?

Yes, the contrapositive law is always true by definition. It is a fundamental rule of logic and can be applied to any conditional statement.

Similar threads

Replies
9
Views
323
Replies
1
Views
708
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
107
  • General Math
2
Replies
66
Views
4K
Replies
8
Views
1K
Replies
3
Views
1K
  • General Math
Replies
2
Views
948
Replies
1
Views
453
Replies
6
Views
914
Back
Top