# Prove that the set of natural numbers is well-ordered

Before we go to the actual proof itself, note that the natural numbers are well-ordered under “

\leq“.

## Proof of that the set of natural numbers is well-ordered

We define the set

M, which is an arbitrarily non-empty subset of

\mathbb{N}. Further, we define the set

\begin{align*}
L := \{l \in \mathbb{N} \ | \ l \leq m, \ \forall m \in \mathbb{N}\}.
\end{align*}

We do know that

0 \in L, so that is the minimal element of

L. Now take

l \in L such that

l + 1 \not \in L, otherwise we will get the case that

L = \mathbb{N} (note the induction). Then there exists an

m \in M such that

m <

l + 1. This implies that

\begin{align*}
m \geq l \quad \text{and} \quad m < l + 1 \iff l \leq m < l + 1.
\end{align*}

It means that

m can't be

l + 1, but greater or equal to

l. Since we work with positive integers, there is no integer between

l and

l + 1, so

m = l.
This implies that

m must be the minimal element of

M.

## Conclusion

So the set of natural numbers is well-ordered.