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

Question

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

Answer 1

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$

Answer 2

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$.

Answer 3

I claim that for all $n$, for all $A \subseteq \mathbb{N}$, if $n \in A$ then $A$ has a least element.

The base case is $n = 0$. Clearly, if $0 \in A$, then $0$ is the least element of $A$.

Now suppose the claim holds for $k$, and suppose we have $k + 1 \in A$. We consider two cases. The first is that $k + 1$ is the smallest element of $A$. In that case, we’re done.

The other case is that there is some $j < k + 1$ such that $j \in A$. Note that $j \leq k$. Let $A’ = A \cup \{k\}$. Then $k \in A’$, so by the inductive hypothesis, $A’$ has a least element $w$. Since $w \in A \cup \{k\}$, we see that either $w \in A$ or $w = k$. If $w = k$, then we have $k \leq j \leq k$ and therefore $w = k = j \in A$, so either way, we know that $w \in A$. Since $w \in A \subseteq A’$ and $w$ is the smallest element of $A’$, it is also the smallest element of $A$.