# Well-Ordering Principle "proof"

Theorem. Well-Ordering Principle.

Every non-empty subset of natural numbers has a least element.

I have seen some proofs for the theorem, but is very "complex"proof really needed here?

My attempt of proof:

Let $$D \subset \mathbb{N}= \left\{ 1, \ 2, \ 3, \ \dots \right\}$$ be an arbitrary non-empty subset of natural numbers. Therefore it has at least one element $$n \in D.$$

Consider the finite set $$\left\{1, \ \dots, \ n \right\}.$$ We check which of those natural numbers are elements of D. Then we choose the smallest one of those. There we have the least element.

• The principle is so obvious that you accidentally used it while trying to prove it: "we choose the smallest one of those" assumes this constructed set of natural numbers ... has a smallest element. Feb 27, 2021 at 13:41
• In mathematics what do you mean by "we check"? That sounds like a practical algorithm but even obtaining one element or checking membership is really not trivial for some sets. Feb 27, 2021 at 13:52

aschepler's comment points out the problem exactly. First you construct the set $$D\cap \{ 1,2,\ldots n\}$$ and then you consider the smallest element of this set...

Except that without the well-ordering principle, you cant be sure that it has a smallest element!

It might be instructive to consider what happens in your argument if you try to apply it to prove that $$\Bbb Z$$ is well-ordered.

• This I don't understand. In {1, ..., n} I have finitely many numbers. 1 < 2 < ... < n (by some axiom of real numbers). When I take the intersection, I again have finitely many numbers. So how would it not be quarantined that there is a smallest element? @MJD Feb 27, 2021 at 14:51
• and OK, I have been going through this precise proof as well. The one part that I don't understand is that when I have shown that the intersection of D and {1, 2, ..., n} has a smallest element, how does it (exactly) follow, that it is the smallest element of D as well? Could you explain this? Feb 27, 2021 at 14:54

This is a proof by induction. The theorem states that every non-empty subset of $$\mathbb{N}$$ has a least element.

Let $$A\subseteq \mathbb{N}$$ be a set with no least element. We want to prove that $$A=\varnothing$$, that is $$\forall n$$ $$\in \mathbb{N}$$, $$n\notin A$$. For induction on $$n$$ we have that:

$$0\notin A$$, in fact if $$0 \in A$$ we would have that: $$0=$$min$$\mathbb{N}=$$min$$A$$, but $$A$$ has no least element.

Suppose now that $$\begin{Bmatrix} 0,1,...,n \end{Bmatrix}\cap A=\varnothing$$. What we want to prove is that: $$n+1\notin A$$. If $$n+1\in A$$, infact, $$n+1\neq$$ min$$A$$ , since $$A$$ has no minimum for hypotesis. So $$\exists m\in A$$, $$m, which is a contradiction with the inductive hypothesis. So $$n+1 \notin A$$.

Hence $$A=\varnothing$$, as we wanted.