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.