Misc
Colloquium
- “Derivative-Free Methods and Applications”
- Ahmad Almomani, faculty candidate from Clarkson University
- March 23 (tomorrow), 2:30, Newton 203
- Extra credit for writing a paragraph connecting the talk to your own interests
Give me your mid-semester course evaluation form today if you want to turn it in.
Questions?
Proofs of Set Relationships
Conjecture 1. If A and B are subsets of some universal set, then A - B ⊆ A.
Helpful ideas or questions from reading
- Use the choose-an-element method...
- ...which is pertinent when universal quantifiers appear in backward steps in know-show tables
- But what exactly does this mean?
- If your goal is to prove a statement of the general form “all x’s have property y,” then somewhere near the end of a know-show table there is likely to be the formal statement “for all x, y.” This is the “universal quantifier” in a “backward step.”
- Working forward towards this, you might have a step of the form “let a be an x...” early in the know-show table. This is where the “choose-an-element” part enters.
Strategy: to prove X ⊆ Y, use the definition of subset (all elements of X are also elements of Y) and so prove that if a is in X then a is in Y.
Proof. Let A and B be subsets of some universal set U. Let y be any element in A - B, i.e., y is any element in { x in U | x is in A and x is not in B }. From this definition of set difference, y is in A. Thus all members of A - B are members of A and so A - B is a subset of A. QED.
Conjecture 2. If A and B are subsets of some universal set, then (A-B) ∩ (B-A) = ∅
Helpful ideas or questions from the reading
- Proof by contradiction or via the contrapositive is likely to be helpful
Proof. The proof is by contradiction. Assume that (A-B) ∩ (B-A) is not empty, so that there is some element of (A-B) ∩ (B-A). Let x be such an element. Then x must be in both A-B and B-A, from the definition of intersection. To be in A-B, x must be in A and not in B, but to be in B-A x must be in B but not A. This is a contradiction because x cannot both be in A and not be in A (and similarly with respect to B). Therefore it must be the case that (A-B) ∩ (B-A) = ∅. QED.
Next
Algebraic properties of set operations
Read textbook section 5.3