PrincipleOfFiniteInductionProvenFromWellOrderingPrinciple 2001-10-18 15:38:43 2007-06-21 21:09:43 Proof principle of finite induction 0 number theory \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{xypic} \PMlinkescapeword{range} 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 \emph{smallest} element of $\mathbb{N}\setminus S$.