SUNY Geneseo Department of Mathematics
Wednesday, February 14
Math 239 01
Spring 2018
Prof. Doug Baldwin
Friday, February 16, 2:30. Newton 203.
“From Differential Equations to Difference Equations and Everything Else in Between.”
Differential equations define a continuous function in terms of its derivative(s); difference equations define a discrete function in terms of its difference(s).
Billy Jackson, SUNY Geneseo.
Extra credit for going and writing a short reaction.
I will be out of town at a conference next Wednesday through Sunday (Feb. 21 - 25).
“Classes” for the 21st and 23rd will be a series of Canvas-based discussions building on what we talk about in class next Monday.
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.
An alphabet is a set of symbols, e.g., { A, B, C, ..., Z }, { ^, * , ∂, ˚ }
A string is a sequence of symbols from an alphabet. Repetitions are OK, and the string needn’t use all the symbols from the alphabet.
For this course, we’ll follow the textbook and define the natural numbers to be the positive integers: { 1, 2, 3, ... }. (Despite the fact that some people include 0 in the natural numbers.)
ℤ+ = positive integers = ℕ
Part of section 3.2.
What is a contrapositive? Given a conditional statement “if P then Q,” its contrapositive is “if not Q then not P.” That a conditional and its contrapositive are equivalent was proved in the readings on logic. Because they are equivalent, you can prove either by proving the other, which is sometimes easier.
Prove that for all integers a and b, if ab is a multiple of 4 then a is even or b is even.
Theorem 1: for all integers a and b, if ab is a multiple of 4 then a is even or b is even.
Proof: We prove that for all integers a and b, if ab is a multiple of 4 then a is even or b is even by proving the contrapositive. Specifically, we prove that if a is odd and b is odd then ab is not a multiple of 4. Let a and b be odd integers, so that a = 2k+1 for some integer k, and b = 2p+1 for some integer p. Then
ab = (2k+1)(2p+1)
= 4pk + 2k + 2p + 1
= 2(2pk + k + p) + 1
Since the integers are closed under addition and multiplication, (2pk + k + p) is an integer, showing that ab is odd. Since every multiple of 4 is also a multiple of 2, all multiples of 4 are even. An odd integer therefore cannot be a multiple of 4. We have thus proven that for all integers a and b, if ab is a multiple of 4 then a is even or b is even. QED.
Notice that I added a new feature of formal proofs: explicitly identifying the proof technique (e.g., proving the contrapositive) in the first few sentences of a proof.
Corollary: for all integers a, if a2 is a multiple of 4 then a is even.
Proof: We assume a is an integer, and prove that if a2 is a multiple of 4 then a is even. a2 = a × a so by Theorem 1, a is even or a is even. But this simply means a is even. We have thus shown that for all integers a, if a2 is a multiple of 4 then a is even. QED.
Also in section 3.2.
Prove that for all integers a, a2 is a multiple of 4 if and only if a is even.
Theorem: for all integers a, a2 is a multiple of 4 if and only if a is even.
Proof: Since the theorem is a biconditional, we prove each direction separately.
For the first direction, assume a is even, i.e., a = 2k for some integer k. Then a2 = 4k2 which is a multiple of 4.
For the second direction, assume a2 is a multiple of 4. Then by the corollary to Theorem 1, a is even.
We have now shown both directions of the biconditional, and so have proven that for all integers a, a2 is a multiple of 4 if and only if a is even. QED.
Notice that the second direction in this proof could also recapitulate the proof-by-contrapositive of Theorem 1, for the special case of a2. But using the corollary is shorter and simpler, and even the proof of the corollary doesn’t need to recapitulate the whole argument via the contrapositive.
Sometimes you can prove a biconditional by following a series of deductions that are themselves biconditionals. In this case you don’t need to explicitly prove each direction as a separate proof.
For example prove that 2x - 3 > 0 if and only if x > 3/2 by observing that 2x - 3 > 0 if and only if 2x > 3, which in turn holds if and only if x > 3/2.
The strategy of proving a conditional by proving its contrapositive.
Prove biconditionals by proving each conditional separately (although occasionally you can take advantage of other approaches).
(Monday, after Friday’s exam.)
Proof by contradiction.
Read section 3.3.