SUNY Geneseo Department of Mathematics
Monday, April 2
Math 239 01
Spring 2018
Prof. Doug Baldwin
Section 5.2.
Progress check 5.9: Prove that if A and B are subsets of universal set U, and A ⊆ B, then BC ⊆ AC.
Proof: Let x be an element of BC. By the definition of set complement, x is not in B. Since A ⊆ B, x cannot be in A either (if it were, it would also be in A’s superset B). Therefore x is an element of AC. This reasoning applies to every element of BC, i.e., every member of BC is also a member of AC. Thus BC is a subset of AC by the definition of subset. QED.
Progress check 5.12: Prove that if A and B are subsets of universal set U, then A - B = A ∩ BC.
Proof: We prove A - B = A ∩ BC by proving that A - B ⊆ A ∩ BC and that A ∩ BC ⊆ A - B.
Let x be in A - B, i.e., x is in A and not in B. Since x is not in B, x is in BC. So x is in A and in BC, or, by the definition of intersection, in A ∩ BC. Thus A - B ⊆ A ∩ BC.
Now let x be in A ∩ BC. By the definition of intersection, x is in A and x is in BC, so x is not in B. Since x is in A and not in B, x is in A - B. Thus A ∩ BC ⊆ A - B.
Having shown both that A - B ⊆ A ∩ BC and that A ∩ BC ⊆ A - B, we have shown that A - B = A ∩ BC. QED.
You could also phrase this proof as a chain of biconditionals to avoid having to do 2 very similar parts.
Prove that the set S = { x ∈ ℝ | x2 < 2 and x - 4 > 0 } is empty.
Maybe it helps to think of S as S = { x ∈ ℝ | x2 < 2} ∩ { x ∈ ℝ | x - 4 > 0 }?
The heart of the argument is contradiction: If x were in S, you would have to have that |x| < √2 and x > 4, which can’t happen.
The element chasing proof technique.
Prove that A = B by proving A ⊆ B and B ⊆ A.
Prove emptiness by contradiction. Imagining counterfactuals can help you discover proofs by contradiction (in general, not just for empty sets), i.e., imagining that some x has such-and-such properties and seeing what the consequences are.
The algebra of set operations.
Read section 5.3.