The principle of induction is a technique used to prove the relationship between a smaller subset The following three statements are equivalent. standard induction Suppose S \subset \mathbb{N}, which is non-empty. If S is a non-empty subset such that 0 \in S, and for all n \in \mathbb{N}, n \in S \implies n+1 \in S. Then, S = \mathbb{N}. strong induction Suppose S \subset \mathbb{N}, which is non-empty. If S is a non-empty subset such that 0 \in S, and for all n \in \mathbb{N}, \{0, \dots, n\} \in S \implies n+1 \in S. Then, S = \mathbb{N}. well-ordering principle If S \subset \mathbb{N} is non empty, then it has a smallest element PROOF: assume well-ordering principle, prove standard induction Given S \in \mathbb{N}, such that 0 \in S, whenever n \in S, then n+1 is also in S. We desire that that S is the natural numbers. Assume for the sake of contradiction S \neq \mathbb{N}. Define T = \mathbb{N} \setminus S. Assume T is non-empty. The WOP tells us that T has a smallest element t \in T. We know that t \neq 0, because 0 \in S. Therefore, t-1 \in \mathbb{N}. But, t-1 < t, which means that t-1 \in S. But by the statement of the givens, (t-1) \in S \implies (t-1)+1 = t \in S. Reaching contradiction. \blacksquare assuming strong induction, proof well-ordering principle Assume S has no smallest element. Create some T = \mathbb{N} \setminus S. Now, 0 \in T because otherwise 0 \in S would be the smallest element. Now, consider 0, 1, … n \in T, we notice that n+1 must be in T as well. By strong induction, we have that T = \mathbb{N} and S is empty.