SUNY Geneseo Department of Mathematics
Friday, March 24
Math 239 01
Spring 2017
Prof. Doug Baldwin
Random names are stressful.
Is there an alternative that encourages engaged reading with less stress?
Reading summaries.
Can I provide mine?
In some way(s), but after yours and example problem(s), to give you chances to engage with and think about the relevance of reading ideas.
Problem set solutions.
I’ll try to provide these more consistently.
Question 2 from problem set 9 (prove that all sufficiently big natural numbers can be expressed as a positive multiple of 4 plus a positive multiple of 5)?
The proof can be by strong induction.
The base cases are 12, 13, 14, and 15.
Induction step: strong induction, so assume for all m between 12 and k (i.e., 12 ≤ m ≤ k), where k ≥ 15, m = 4x + 5y; then show that k+1 = 4a + 5b for some non-negative integers a and b. Notice that k+1 = (k-3) + 4 and 12 ≤ k-3 < k so the induction hypothesis applies to k-3, i.e., k-3 = 4x + 5y for some non-negative integers x and y. Now substitute 4x + 5y into (k-3) + 4 and....
Prove one of Monday’s conjectures about differences: if A and B are subsets of universal set U, then (A - B) ∪ (B - A) = A ∪ B - (A∩B)
Relevant ideas or questions from the reading
Proof. Using set algebra, we see that
(A - B) ∪ (B - A) = (A ∩ BC) ∪ (B ∩ AC)
Now using the distributive law P ∪ (Q∩R) = (P ∪ Q) ∩ ( P ∪ R ) twice we have
(A ∩ BC) ∪ (B ∩ AC) = ((A ∩ BC ) ∪ B) ∩ ((A ∩ BC ) ∪ AC)
= ((A ∪ B) ∩ (BC ∪ B)) ∩ ((A ∪ AC) ∩ (BC ∪ AC))
Using the intuitively plausible idea, which we will prove as a lemma later, that P ∪ PC = U, we have
((A ∪ B) ∩ (BC ∪ B)) ∩ ((A ∪ AC) ∩ (BC ∪ AC)) = ((A ∪ B) ∩ U) ∩ (U ∩ (BC ∪ AC))
= (A ∪ B) ∩ (BC ∪ AC)
= (A ∪ B) ∩ (B ∩ A)C
= (A ∪ B) - (B ∩ A)
We have thus shown that if A and B are subsets of universal set U, then (A - B) ∪ (B - A) = A ∪ B - (A∩B). QED.
See handout
More set algebra, in particular