Misc
Colloquium
Marcus Elia, “Fast Polynomial Multiplication for Cryptography”
Wednesday, March 13, 4:00 - 5:00 PM
Newton 201
Up to 2 problem set points of extra credit for going and writing a paragraph about connections you make to the talk.
Questions?
Inductive Sets
Part of section 4.1.
Definition
Definition: for a set to be inductive, it must...
- Be a subset of the integers, and
- Have the property that if n is in the set, then n+1 is also in the set.
Are the following inductive?
- { n ∈ ℕ | n > 1000 }. Yes, each member is an integer, and for any n > 1000, n+1 is also > 1000.
- { 2n | n ∈ ℕ }. No, elements of the set “step” by 2, so when n is in the set n+1 is not.
- { n ∈ ℕ | 2n > 1000 }. Yes, this is just a round-about way to describe the set of integers greater than 500.
- { 0.5, 1.5, 2.5, 3.5, ... }. No, the elements of this set aren’t integers, even though when n is in the set so is n+1.
- { n ∈ ℤ | n < 0 }. No, there is an n (namely -1) that is in the set but n+1 isn’t.
Proofs
Prove that { n ∈ ℤ | n > -30 } is inductive.
To prove that a set is inductive, you have to show that it is a subset of the integers, and that whenever n is in the set so is n+1. Here is the proof for this set (Theorem 1 in the document), and the LaTeX source the proof came from.
Prove that if the universal set is the natural numbers, then the truth set of the predicate P(n) = “4 divides (5n - 1)” is inductive.
This proof is similar to the first example. The proof is here (Theorem 2), and its LaTeX source is here.
Does this prove that 4 in fact divides 5n - 1 for any (or all) n? No, because it doesn’t prove that there actually is an n in the set at all.
Next
Proof by induction (i.e., adding on the “is there such an n at all” part of our proof that a truth set is inductive).
Read the rest of section 4.1.