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