Material from beginning of semester through quantifiers (e.g., statements and non-statements, conditional
and biconditional statements, propositional logic, quantifiers, etc.)
2 - 5 short-answer questions, probably a longer question where I ask you to write a formal proof
Whole class period
Open book, notes, computer; closed person
ΦBK Lecture
Prof. Philip Kitcher, Columbia University
“Progress in the Sciences and in the Arts”
Thursday, Sept. 29, 4:00 PM
Doty Recital Hall
Extra credit for going and writing me a paragraph or 2 summarizing the talk in terms of how it connects
to your interests, plans, etc.
Questions?
Direct Proofs
Section 3.1
Examples
Which of the following are true?
Divisibility (|): a (≠ 0) divides b (integer) if there is integer q such that b = aq
3 | 6 true, q = 2
6 | 3 false, q = 1/2 , not integer
17 | 0 true: q = 0
Proofs
If a divides b and a divides c, then a divides b + c (Progress check 3.2)
Idea:
If a divides b, then b = as for some integer s
Similarly c = at for some integer t
So b + c = as + at = a(s+t)
Since integers are closed under addition, s+t is an integer
So there is an integer q (= s+t) such that b+c = aq, and thus a divides b+c
If a ≡ 4 (mod 8) and b ≡ 4 (mod 8) then (a+b) ≡ 0 (mod 8) (variation on progress
check 3.6)
a is congruent to b mod n (a ≡ b (mod n)) means that n | (a-b)
Theorem. If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
Proof idea
By definition of congruence, n | (a-b) and n | (b-c)
Thus a - b = nq and b - c = nt
Observe that a-c = a-b + b-c = (a-b) + (b-c) = nq + nt = n(q+t)
Thus n | (a-c), i.e., a ≡ c (mod n)
Next
(After exam)
Proof via the contrapositive
Read section 3.2 through “Other Logical Equivalencies”