The Mathematical Induction Equivalence

by Dave
(DAVE)—

Why is mathematical induction an axiom to some and to others its a theorem? Should the well-ordering of the natural numbers be an axiom or theorem? Why does any of this matter?

In this video, I prove the Mathematical Induction Equivalence. This equivalence means that the Well-Ordering, Mathematical Induction, and Strong Induction are all equivalent. First, I prove that the Well-Ordering implies Mathematical Induction, and then I prove that Mathematical Induction implies Strong Induction. Finally, I prove that Strong Induction implies the Well-Ordering. These three proofs indicate that all three are logical equivalent.

The Well-Ordering Axiom Implies Mathematical Induction

Theorem. The following statements are equivalent.

(1) Every nonempty set of natural numbers has a least element.

(2) If $P$ is a subset of the positive integers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $k \in P$ implies $k+1 \in P$, then $P$ is the set of positive integers.

Proof. Let $P$ be a subset of natural numbers with $0\in P$ and the property that for all natural numbers $k$, $k\in P$ implies $k+1\in P.$ Assume, for a contradiction, there exists a nonempty set $S$ containing the natural numbers not in $P.$ By the Well-Ordering Axiom, $S$ has a least natural number, $s.$ Since $0\in P$, $s\neq 0.$ Thus there exists a natural number $t$ such that $t+1=s.$ Notice $t\not\in S$ since $t < s.$ Thus $t\in P$ and so $s=t+1\in P.$ This contradiction shows $S$ cannot exist, meaning $P=\mathbb{N}$ as desired.

Mathematical Induction Implies Strong Induction

Theorem. The following statements are equivalent.

(1) If $P$ is a subset of the natural numbers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $k \in P$ implies $k+1 \in P$, then $P$ is the set of natural numbers.

(2) If $Q$ is a subset of the natural numbers with the following properties: $0 \in Q$, and for all $k\in \mathbb{N}$, $0,1,\ldots , k \in Q$ implies $k+1 \in Q$, then $Q$ is the set of natural numbers.

Proof. Let $Q$ be a set of natural numbers with $0\in Q$ and the property, for all natural numbers $k$, $0,1,2,\ldots,k\in Q$ implies $k+1\in Q.$ Let $P$ be the set of natural numbers for which $0,1, \ldots, n\in Q$ is true. Notice $0\in P$ since $0\in Q.$ Assume $k\in P.$ Then $0,1, \ldots, k\in Q.$ Thus $0,1,\ldots , k , k+1\in Q$ meaning $k+1\in P.$ Hence, $P=\mathbb{N}.$ By definition of $P$, $Q=\mathbb{N}$ as desired.

Strong Induction Implies the Well-Ordering Axiom

Theorem. The following statements are equivalent.

(1) If $Q$ is a subset of the natural numbers with the following properties: $0 \in Q$, and for all $k\in \mathbb{N}$, $0,1,\ldots , k \in Q$ implies $k+1 \in Q$, then $Q$ is the set of natural numbers.

(2) Every nonempty set of natural numbers has a least element.

Proof. Assume, for a contradiction, there exists a nonempty set of natural numbers $S$ with no least element. Let $Q$ be the set of natural numbers for which $n\notin S$ is true. Because $0$ is the least element of all natural numbers, $0\notin S$ and so $0\in Q.$ Assume $0,1,\ldots ,k\in Q.$ If $k+1\in S$ then $k+1$ is the least element of $S.$ However, $S$ has no least element and thus $k+1\notin S.$ Thus, $k+1\in Q$ and so by Strong Induction we have $Q=\mathbb{N}.$ This contradiction shows $S$ can not exist.

Conclusion

To learn a great deal more on this topic, consider taking the online course The Natural Numbers.