# Proving the well ordering principle with induction

I am wondering if the following proof of the well ordering principle is correct by induction.

Well-ordering principle: Every non-empty subset of $$\mathbb{N}$$ has a least or smallest element.

To prove this, we will prove the following lemma:

Let $$n\in\mathbb{N}$$ and let S be a nonempty subset of $$\mathbb{N}$$ such that $$n\in S$$. Then S has a least element.

Proof by strong induction:

Base: When $$n=1$$, we have that $$1\in S$$. Then 1 is the least element of S.

Assume that when $$1,2,3,...,k \in S$$ then S contains a least element.

Inductive step: Let $$n+1\in S$$. This can be broken down into two cases.

Case 1: If any of the numbers $$1,2,3,...,n\in S$$ then S contains a least element by the induction hypothesis.

Case 2: If S doesn't contain any of the numbers $$1,2,3,...n$$ but $$n+1\in S$$ then $$n+1$$ is the least element in S.

We have concluded the lemma.

Now using the lemma to prove the well-ordering principle:

Let $$S$$ be a nonempty subset of $$\mathbb{N}$$. This implies $$\exists n \in \mathbb{N}$$ such that $$n\in S$$. By the previous lemma, S has a least element.

Note that what you're doing is really long induction, so strictly speaking your induction step should not go from $$n$$ to $$n+1$$, but from "all numbers smaller than $$n$$" to $$n$$. Or alternatively the claim you prove by induction should be "if $$S$$ contains some element that is $$\le n$$, then $$S$$ has a smallest element".
If you're working in a very formal setting where you have an actual definition of $$<$$ on the natural numbers, and axioms for the concepts that go into that definition, then it would be reasonable for you to go into more detail in case 2 to connect your reasoning rigorously to that definition. But if you don't have such a definition, there's not much else you can say but what you're saying already.