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.


Yes, that is essentially how it goes.

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.