Misc
Exam 1
Monday (Feb. 13)
Covers material from the start of the semester through problem set 4 (set basics).
Note that problem set 4 will be completed before the exam, but grading can be after — it’s up to you whether you want to schedule your grading appointment before or after the exam.
Expect 3 to 5 short-answer (e.g., around a paragraph of prose, 4 to 5 lines of derivation, etc.) questions. Some may be formal proofs. I think the questions will be comparable in difficulty to problem set questions, but your sense of “difficulty” may be different from mine.
I give partial credit, so showing scratch work can be good for you.
You’ll have the whole class period.
The test will be open book, open notes, open computer in so far as the computer is used as a reference. But you can’t communicate with other people during the test.
Consider using problems from the book for studying.
Questions?
Quantifiers
Negation
How do the rules for negating quantifiers relate to de Morgan’s Laws?
Think of “for all” as a generalization of “and,” in that all arguments to an “and” must be true for the whole conjunction to be true; for a universally quantified statement to be true its predicate must be true for the first member of the universal set and for the second and the third and so forth. Similarly think of “there exists” as a generalization of “or,” in that a disjunction is true as long as there exists one (or more) of its arguments that is true; an existentially quantified statement is true if its predicate is true of the first member of the universal set or of the second or the third, etc.
In this perspective, the rules for negating quantifiers are just generalizations of de Morgan’s Laws (or de Morgan’s Laws are just quantifier negation applied to particularly limited quantifications).
Quantifiers over the Empty Set
Is it true that every pink dragon in this room is dancing on the tables?
- Yes!
- Vacuous truth: any universally quantified statement about the empty set is true.
Is it true that some pink dragon in this room is writing down everything we say?
- No
- For an existentially quantified statement to be true there must actually be at least one member of its universal set.
Proving Quantified Statements
Universal quantifier: prove that for all integers x, x + (x-1) is odd
Theorem: (∀ x in ℤ)(x + (x-1) is odd )
- Or (stylistically better) for all integers x, x + (x-1) is odd
- Or if x is an integer then x + (x-1) is odd
Proof. We assume x is an integer and will show that x + (x-1) is odd. By algebra we see that x + (x-1) = 2x - 1 = 2x - 2 + 1 = 2(x-1) + 1. Since the integers are closed under subtraction, x-1 is an integer, and so x + (x-1) is of the form 2n + 1 for some integer n. This matches the definition of an odd integer, so x + (x-1) is odd. QED
Tactic: Rephrase the quantifier as a conditional, i.e., rephrase (∀ x in S)(...) as “if x is in S, then ...”
Existential quantifier: prove that some real number is a cube root of -1.
Tactic: find an example.
So you can prove the above by simply noting the -13 = -1 and that -1 is a real number.
Non-constructive proof: prove that there is some value of x such that cosx = x.
Intuition: the graphs of cosx and x cross. But this isn’t a proof because there could always be some problem at some minute level of detail too small to see on the graph:
Rigorous proof: cosx and x are both continuous functions. Therefore cosx - x is continuous. cos(0) - 0 = 1, while cos(π/2) - π/2 = -π/2. Since 1 > 0 > -π/2, the Intermediate Value theorem assures us that at some x between 0 and π/2, cosx - x = 0, i.e., cosx = x.
Non-constructive proofs show that something exists but without finding its actual value. The proof that cosx = x for some x is an example, because it shows that there must be such an x, but provides no hint as to what it is (other than that it is somewhere between 0 and π/2).
Next
(After test)
Proofs involving variations on conditional statements
Read section 3.2