SUNY Geneseo Department of Mathematics
Wednesday, March 27
Math 239 01
Spring 2019
Prof. Doug Baldwin
Next Wednesday (April 3).
Covers proof techniques (e.g., contrapositive, biconditionals, contradiction, cases, induction — problem sets 4 through 6).
Rules and format will be similar to exam 1, particularly open-references rule. But there may be slightly fewer questions, because more of the questions will ask you to write proofs.
Next Tuesday, April 2, 2:30 - 3:30, Welles 138.
Chris Leary (Geneseo), on “Learnability Can Be Undecidable”
Extra credit for going and writing around 1 paragraph on connections you make or reactions you have.
Section 5.2.
Prove that for sets A and B, A - B ⊆ A ∩ BC.
See the complete formal proof here (Theorem 1), and its LaTeX source here.
Prove that A ∩ BC ⊆ A - B.
Proof sketch: Let x be an element of A ∩ BC. This means x ∈ A and x ∈ BC, i.e., x is not in B. x ∈ A and not in B means x ∈ A - B.
What can you conclude from the above 2 propositions?
That A - B = A ∩ BC.
Let A = { x ∈ ℤ | x ≡ 1 (mod 4) } and B = { y ∈ ℤ | y ≡ 2 (mod 10) }. Prove that A and B are disjoint.
Proof sketch: Use proof by contradiction. Assume A and B are not disjoint, i.e., there exists some value z in both sets. Thus z = 4p + 1 and z = 10q + 2. Then...
4p + 1 = 10q + 2
4p = 10q + 1
But this means an even integer equals an odd one, which is a contradiction.
See this proof written formally here (Theorem 2), with LaTeX code here.
How did this proof get from x ≡ 1 (mod 4) to x = 4p + 1?
Formally, x ≡ 1 (mod 4) means 1 - x = 4n for some integer n
Subtracting 1 from both sides, -x = 4n - 1
Negating both sides gives x = 1 - 4n
Which we can write as x = 4(-n) + 1 = 4p + 1 where p = -n.
The choose-an-element technique for proving subset or equality relations between sets.
To prove A ⊆ B, show that whenever x is in A, x is also in B.
To prove A = B, show A ⊆ B and B ⊆ A.
Disjointness proofs can often be done by contradiction.
See handout for details.
An algebra of sets (whose laws we can prove now that we have the choose-an-element method).
Read section 5.3.