SUNY Geneseo Department of Mathematics
Monday, February 12
Math 239 01
Spring 2018
Prof. Doug Baldwin
I will be out of town at a conference next Wednesday through Sunday (Feb. 21 - 25).
“Classes” for the 21st and 23rd will happen, maybe as a series of Canvas-based discussions building on what we talk about in class next Monday, or maybe something else.
First hour exam is Friday, February 16.
Covers material from the beginning of the semester through sets, e.g., statements, proof writing, logic, sets. Also see problem sets 1 through 3, and lecture notes from Jan. 17 through Feb. 5.
You’ll have the full class period.
Expect 3 to 5 short-answer questions, similar (at least in my mind) to those on problem sets. But any questions that ask for formal proofs will not require them to be typeset.
Open book, open notes, open computer for reference, but closed person.
Problem 3 on problem set 3 (and, for that matter, the rest of the problem set too) does not require formal proofs.
Extra credit write-ups can be turned in any time until our final.
Section 3.1.
(Progress check 3.2)
Prove that for all integers a, b, and c with a ≠ 0, if a divides b and a divides c, then a divides b + c.
Theorem: For all integers a, b, and c with a ≠ 0, if a divides b and a divides c, then a divides b + c.
(Note that theorem statements aren’t quite the same as problem instructions. Theorem statements are direct statements of fact, without commands such as “prove that.”)
Proof: Assuming a, b, and c are integers and a ≠ 0, we will prove that if a divides b and a divides c, then a divides b + c. By the definition of divisibility and the fact that a divides b, b = xa for some integer x. Similarly, c = ya some some integer y. Therefore
b + c = xa + ya
= (x+y) a
Since the integers are closed under addition, (x+y) is an integer, and therefore a also divides (b+c). We have thus shown that for all integers a, b, and c with a ≠ 0, if a divides b and a divides c, then a divides b + c. QED.
(Progress check 3.6)
Prove that if a and b are integers and a ≡ 5 (mod 8) and b ≡ 5 (mod 8), then (a+b) ≡ 2 (mod 8).
Theorem: If a and b are integers and a ≡ 5 (mod 8) and b ≡ 5 (mod 8), then (a+b) ≡ 2 (mod 8).
Proof: We assume that a and b are integers such that a ≡ 5 (mod 8) and b ≡ 5 (mod 8), and will show that (a+b) ≡ 2 (mod 8). We rely on Sundstrom’s observation that a ≡ b (mod n) means that a = kn + b for some integer k. This observation and the fact that a ≡ 5 (mod 8) means that a = 8k + 5 for some integer k. Similarly, b = 8c + 5 for some integer c. We therefore see that
(a+b) = 8k + 8c + 10
= 8k + 8c + 8 + 2
= 8(c+k+1) + 2.
Since the integers are closed under addition, (c+k+1) is an integer. Thus (a+b) ≡ 2 (mod 8). We have therefore shown that if a and b are integers and a ≡ 5 (mod 8) and b ≡ 5 (mod 8), then (a+b) ≡ 2 (mod 8). QED.
Constructing a proof is a process of moving from intuitive ideas to their formal expression.
Proofs about conditional statements often flow directly (thus the name “direct proof”) from the hypotheses of the statement through a series of mathematical deductions to the conclusion.
A good guideline, although less of a “key” point: if you can, avoid explicit division in proofs about integers, since division is the one common arithmetic operation the integers are not closed under.
Proofs about conditionals and biconditionals.
Read section 3.2.