Introduction to Induction

Return to Course Outline

Previous Lecture

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...

1. Be a subset of the integers, and
2. 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 (5ⁿ - 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 5ⁿ - 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.

Next Lecture