One has now shown that the natural numbers are totally ordered according to the canonical order. Believe it or not, one can go even further! The natural numbers are also well-ordered i.e. every non-empty subset of the naturals have a smallest/least element. Thus, one cannot have "bottomless chasms" in the natural numbers. At some point, as one descends down a non-empty natural subset according to canonical order, one must reach the bottom in a finite number of steps.

Definition LE

Least Element: Let $X\subseteq\mathbb{N}$. Then, an element $n \in X$ is called the least element of $X$ iff for any $x \in X$, it is the case that $n \leq x$.

Lemma ULE

Uniqueness of the Least Element: If $X\subseteq\mathbb{N}$ has a least element $n$, then it is unique.

Proof: Suppose $n'$ is some other least element of $X$. Then, as $n \in X$, $n' \leq n$. At the same time, since $n$ is also a least element and $n' \in X$, $n \leq n'$. So, $n=n'$ by antisymmetry.

Theorem Well-Ordering

Well Ordering of $\mathbb{N}$: If $X\subseteq\mathbb{N}$ and $X\neq\emptyset$, then $X$ has a least element.

Proof: Do induction with $\Sigma=\{n\in\mathbb{N}:\ \text{if}\ X\subseteq\mathbb{N}\ \text{and}\ n \in X\ \text{, then}\ X\ \text{ has a least element}\}$.

1. $0\in\Sigma$ because it is already the least natural number.
2. Now suppose that $n\in\Sigma$. One now has to show that $S(n)\in\Sigma$ also. To that end, consider any $X\subseteq\mathbb{N}$ such that $S(n) \in X$. Now, if $n \in X$, then one is done because by the initial hypothesis, any subset with $n$ must have a least element. Otherwise, consider $X'=X\cup\{n\}$. Clearly, $n \in X'$, so that $X'$ has some least element $l$. Now
   • If $l \neq n$, then $l \in X$. It is easy to see in this case that $l$ is the least element of $X$. For, fix any $s \in X$; then certainly $s \in X'$ also. But then as $l$ is the least element of $X'$, $l \leq s$.
   • Otherwise, $l=n$. In this case, one can show that $S(n)$ is the least element of $X$. Well, for starters, fix any $s \in X$. Since $s \in X'$ also and $l=n$ is the least element of $X'$, $n \leq s$ i.e. there is some $k\in\mathbb{N}$ such that $n+k=s$. Now, $k \neq 0$ as otherwise, $s=n+0=n \notin X$. Thus, there is a $k'\in\mathbb{N}$ such that $S(k')=k$. So, $s=n+k=n+S(k')=S(n)+k'$ (using Lemma SSwap). Hence, $S(n) \leq s$.

Because least elements are unique by the previous lemma, one can unambiguously denote the least element of $X$, as given by this theorem, as $\text{min}(X)$.

One can also flesh out well-ordering in terms of greatest elements in bounded subsets of $\mathbb{N}$.

Definition GE

Greatest Element: Let $X\subseteq\mathbb{N}$. Then, an element $n \in X$ is called the greatest element of $X$ iff for any $x \in X$, $x \leq n$.

Lemma UGE

Uniqueness of the Greatest Element: If $X\subseteq\mathbb{N}$ has a greatest element $n$, then it is unique.

The proof of this is entirely analogous to the proof that least elements are unique.

Definition Upper Bound

Upper Bound on a Subset of $\mathbb{N}$: Let $X\subseteq\mathbb{N}$. A natural number $n$ is called an upper bound on $X$ iff for any $x \in X$, $x \leq n$.

Thus, the greatest element of a subset of $\mathbb{N}$ is precisely an upper bound which is in the subset itself.

Definition Bounded Subset

Bounded Subsets of $\mathbb{N}$: Let $X\subseteq\mathbb{N}$. Then one says that $X$ is bounded above iff an upper bound on it exists.

Lemma SxLESGx

$S(x)$ is the Least Element Strictly Greater Than $x$: For any $x,y\in\mathbb{N}$, if $x<y$, then $S(x) \leq y$.

Proof Sketch: If $x<y$, then there is a natural $k'$ such that $x+S(k')=S(x)+k'=y$ i.e. $S(x) \leq y$.

The above lemma is sometimes used in its contrapositive form: For any $x,y\in\mathbb{N}$, if not $S(x) \leq y$, then not $x<y$. By alternative totality, this is equivalent to: For any $x,y\in\mathbb{N}$, if $y<S(x)$, then $y \leq x$.

Theorem Well-Ordering-Alt

Well-Ordering on $\mathbb{N}$ (Alternative Form): If $X\subseteq\mathbb{N}$ is non-empty and bounded above, then $X$ has a greatest element.

Proof: Form the set of all upper bounds on $X$, $\tilde{X}$. This is non-empty since $X$ is bounded above. Hence, by well-ordering, $\tilde{X}$ has a least element $l$. Now, clearly as $l$ is an upper bound on $X$, for any $x \in X$, $x \leq l$. The only thing that remains to be shown, to conclude that $l$ is the greatest element of $X$, is that $l \in X$.

If $l=0$, since $0$ is the least element period, for any $x \in X$, $l \leq x$. Hence, by antisymmetry, $x=l$. Now, as $X$ is non-empty, there is at least one natural $x \in X$ and by the previous sentence, $l=x \in X$.

Otherwise, $l \neq 0$. Hence, there is some $l' \in \mathbb{N}$ such that $S(l')=l$. Since $l'<S(l')$ ($l' \neq S(l')$ as $S$ has no fixed points and $l' \leq S(l')$ by an earlier lemma), it cannot be that $l=S(l') \leq l'$ by alternative totality. Hence, $l' \notin \tilde{X}$; otherwise, $l$ would no longer be the least element of $\tilde{X}$. Thus, $l'$ is not an upper bound on $X$. In other words, there is an $x \in X$ such that $x \leq l'$ is not true; hence, $l'<x$ by alternative totality. So, by the previous lemma, $l=S(l') \leq x$. But then, by antisymmetry, $l=x \in X$.

Because greatest elements are unique by the Lemma UGE, one can unambiguously denote the greatest element of $X$, as given by this theorem, as $\text{max}(X)$.