principle of finite induction proven from the well-ordering principle for natural numbers

We give a proof for the “strong” formulation.

Let $S$ be a set of natural numbers such that $n$ belongs to $S$ whenever all numbers less than $n$ belong to $S$ (i.e., assume $\forall n(\forall m<n\ m\in S)\Rightarrow n\in S$ , where the quantifiers range over all natural numbers). For indirect proof, suppose that $S$ is not the set of natural numbers $\mathbb{N}$ . That is, the complement $\mathbb{N}\setminus S$ is nonempty. The well-ordering principle for natural numbers says that $\mathbb{N}\setminus S$ has a smallest element; call it $a$ . By assumption, the statement $(\forall m<a\ m\in S)\Rightarrow a\in S$ holds. Equivalently, the contrapositive statement $a\in\mathbb{N}\setminus S\Rightarrow\exists m<a\ m\in\mathbb{N}\setminus S$ holds. This gives a contradition since the element $a$ is an element of $\mathbb{N}\setminus S$ and is, moreover, the smallest element of $\mathbb{N}\setminus S$ .

Title	principle of finite induction proven from the well-ordering principle for natural numbers
Canonical name	PrincipleOfFiniteInductionProvenFromTheWellorderingPrincipleForNaturalNumbers
Date of creation	2013-03-22 11:48:04
Last modified on	2013-03-22 11:48:04
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	16
Author	CWoo (3771)
Entry type	Proof
Classification	msc 03E25
Classification	msc 37H10