FOM Book: 5.1 (Induction)

This section is all about defining induction through set notation, exploring the relationship between natural numbers and inductive sets, and finally looking at cardinality of power sets.

Definition 5.1 : a set of numbers is called inductive if (∀t)(t∈S⇒t+1∈S) AKA closed under adding one.


Two inductive sets:



Two non-inductive sets:



Are there any finite inductive sets? Thinking about it, the only possible way that could happen is if the last number in the set looped to some other number in the set. There’s no way this is possible because there will always be a biggest number in a finite set, and the biggest number + 1 will not be included in the set.

What about the empty set? The empty set contains no element, so the first part of the inductive definition (∀t)(t∈S) cannot be true, because once there is an element in set S, it is no longer the empty set. So since the hypothesis is false, does that make the empty set vacuously inductive?

Natural Numbers

ℕ is the smallest inductive set containing 1.

Axiom 5.1(Principle of Induction): Any set which contains 1 and which is inductive must contain all natural numbers. Therefore, for any set S, if 1∈S and S is inductive, ℕ⊆S. For any open statement p(n), if “p(1)“ and “(∀t∈ℕ)(p(t)⇒p(t+1)“ are both true, then “(∀n∈ℕ)(p(n))“ is true.

Theorem 5.2: If n is a natural number, then n<2n. This can be rephrased in quantifier notation as (∀n∈ℕ)(n<2n). To prove this for all natural numbers, we need to also prove (∀t)(t∈P⇒t+1∈P), where P is the truth set of n<2n.

Proof: Let p(n) be the open statement n<2n (for the universe = ℕ).
We will have to show that: 1∈P, and that P is inductive.
First we need to prove the base case; we’ll use one.
p(1) < 21. This statement is true, so 1∈P.
Next we need to show that P is inductive. To do that, we assume p(t) is true. We need to prove p(t+1) < 2t+1 is true.
Since t∈ℕ, 1≤t.
t∈P, so t<2t. 
If we multiple both sides by two, we get 2t < 2 × 2t.
2×2t = 2(t+1)
Theorem 5.3: For any n∈ℕ,

13+ 23+ 33+…+ n3 = ((n(n+1))/2)²
Theorem 5.5: Generalized theorem of induction for any set S and any k∈ℤ, if k∈S and S is inductive, then ℕ[k,∞] ⊆ S.

[1,∞] = ℕ
[0,∞] = Whole numbers.
Theorem 5.6: For n∈ℕ, n≥6, (n+1)²≤2n.

Proof: Let p(n) = (n+1)²≤2n for universe ℕ[6,∞], and let P be it’s truth set.
P = {n∈ℕ[6,∞]: (n+1)²≤2n}
We need to prove that 6∈P, and that P is inductive.
 (6+1)²≤2which is true.
Assume (t+1)²≤ 2t ,we need to prove that ((t+1)+1)² ≤ 2× 21, which simplifies to (t+2)² ≤ 2× 21. Using Lemma 5.7, for t∈ℤ, if t≥6, then (t+2)² < 2(t+1)². From this, we then get (t+2)² ≤ 2(t+1)² < 2× 21 = 2(t+1), which, simplified is what we are trying to prove.

(t+2)² ≤ 2(t+1).
Theorem 5.9′: for any n∈W. If |A| = n, then |P(A)| = 2n. 

This weekend I’m going to try and figure out a way to prove Theorem 5.9′ this weekend that isn’t as confusing as the book does it.
Happy Easter  (or regular) weekend ya’ll!




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s