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

  • 3
    $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy