The Well-Ordering Principle of the Natural Numbers

We begin our look through abstract algebra with a rather simple theorem regarding the set of natural numbers known as The Well-Ordering Principle of the Natural Numbers.

Consider the following set which we define to be the set of natural numbers:

(1)

\begin{align} \quad \mathbb{N} = \{ 1, 2, 3, ... \} \end{align}

Now consider any subset $A$ of $\mathbb{N}$. For example, let us consider the subsets $A_1 = \{ 7, 29 \}$, $A_2 = \{1, 3, 5, ... \}$, and $A_3 = \{2, 4, 6, ... \}$. The subset $A_1$ describes a finite set containing two integers. The subset $A_2$ describes the infinite set of all odd natural numbers, and the subset $A_3$ describes the infinite set of all even natural numbers. Notice that in each of these cases we can identify a least element of the subset. For example, the least element in $A_1$ is $7$, the least element in $A_2$ is $1$, and the least element in $A_3$ is $2$.

In fact, it is impossible to construct a nonempty subset $A$ of $\mathbb{N}$ that does not contain a least element. We describe this very important result below in the following theorem.

Theorem 1 (The Well-Ordering Principle of the Natural Numbers): Let $A$ be a nonempty subset of the natural numbers $\mathbb{N} = \{1, 2, 3, ...\}$. Then there exists a least element $x \in A$, that is, $x \leq y$ for all $y \in A$.

We do not have the tools to prove Theorem 1 although it is a rather intuitively obvious result. Nevertheless, we should note that while Theorem 1 holds true for the set of natural numbers, it does not hold true for all sets of real numbers. For example, consider the set of rational numbers $\mathbb{Q}$:

(2)

\begin{align} \quad \mathbb{Q} = \left \{ \frac{a}{b} : a, b \in \mathbb{Z}, b \neq 0 \right \} \end{align}

Any subset of the rational numbers need not have a least element. For example, consider the following subset of rational numbers between $0$ and $1$ noninclusive, that is, $A = \{ x \in \mathbb{Q} : 0 < x < 1 \}$. We claim that $A$ has no least element. To prove this, assume that $A$ does have a least element, say $x \in A$ is such that $x \leq y$ for all $y \in A$. Since $x \in A$ we have that $x = \frac{a}{b}$ where $a, b \in \mathbb{Z}$ Since $x \in A$ we must have that $x > 0$ too since $0 < x < 1$ and so:

(3)

\begin{align} \quad 0 < \frac{a}{b} < 1 \end{align}

Consider the number $y$ in the middle of $0$ and $\frac{a}{b}$. This number is $y = \frac{a}{2b}$. Since $b \in \mathbb{Z}$ and $b \neq 0$ we have that $2b \in \mathbb{Z}$ and $2b \neq 0$, so indeed, $y = \frac{a}{2b} \in A$ and $0 < y < x < 1$ which is a contradiction to our assumption that a least element exists in $A$.

It's important to note that while not every subset of the rational numbers $\mathbb{Q}$ contains a least element, there are still subsets of $\mathbb{Q}$ that do contain a least element.