# Proof of well ordering principle for the set of positive integers with directly using the principle of induction and not strong induction

Can we prove well ordering principle for the set of natural numbers (positive integers ) with directly using the principle of induction i.e. $( S \subseteq \mathbb N ,1 \in S \space \&\ n \in S \implies n+1 \in S) \implies S=\mathbb N$ and not using principle of strong induction ? The proof I know first prove principle of induction implies principle of strong induction and then uses strong induction to prove well ordering principle , but I want a direct proof using only induction . Thanks in advance

• Why do you want that? You can just fold the two sub-proofs together -- that is, is you have a proof of $\varphi(n)$ by long induction, you can trivially word the same argument as a proof of $\forall k(k\le n\to\varphi(k))$ by mathematical induction instead. – Henning Makholm Jan 20 '15 at 15:35

You might consider this to be a bit cheating, but here is a proof using only induction and one additional inference.

Lemma. If $A\subseteq\Bbb N$ has a maximal element, then $A$ has a minimal element.

Proof. First note that $A$ has a maximal element, so it is non-empty. Now we prove by induction on $n$: If $\max A=n$ then $A$ has a minimal element.

• If $\max A=0$ then $A=\{0\}$ and $0$ is also $\min A$.
• Assume that for $n$ the claim holds. If $\max A=n+1$ then either $A'=A\setminus\{n+1\}$ is empty, in which case $A=\{n+1\}$, so it is also the minimal element; else $\max A'=n$ and by the induction hypothesis it has a minimal element, $k$ and $k\leq n<n+1$, so $k=\min A$.

Therefore if $A$ has a maximal element, it has a minimal element. $\square$

Theorem. The principle of induction implies that every non-empty set of natural numbers has a minimal element.

Proof. If $A$ is a non-empty set, pick some $n\in A$, then $A'=\{a\in A\mid a\leq n\}$ has a maximal element $n$. We proved by induction that $A'$ has a minimum element $k$. If $m\in A$ then either $m\leq n$ in which case $m\in A'$ so $k\leq m$ or $m>n$ and in which case $k<m$. In either case $k=\min A$. $\square$

Let $S \subseteq N$ be non-empty, and define:
$R = \{x \in N : x \le y, \forall y \in S\}.$

Then $0 \in R$ since $0 \le y$ $\forall y \in N$, in particular $\forall y \in S$.

Since S is non-empty, there is a $y \in S$; this implies $y + 1 \notin R$: otherwise we would have $y + 1 \le y$, [Perhaps you can disprove this with PEANO'S AXIOMS]

Thus $R$ contains $0$ but $R \neq N$; the induction axiom then implies that there must exist an $x \in R$ such that $x + 1 = s(x) \notin R$ [$S : N \rightarrow N$ is a successor function].

We claim that $x$ is a smallest element of $S$.

First, $x \in R$ implies $x \le y$, $\forall y \in S$> So, we only need to show that $x \in S$.
Assume $x \notin S$; then $x \le y$ ,$\forall y \in S$ implies $x < y$ (because we can’t have equality), hence $x + 1 = s(x) \le y$, $\forall y \in S$, which by definition of R shows that $x + 1 \in R$ in contradiction to the construction of $x$.