Who Cares About Well-Ordering?

Freshmen learning about the well-ordering principle ask the golden question: who cares? What’s its use, even in pure mathematics?

The goal of this post will be slightly different. We’ll take the following sequence:

State the well-ordering principle.
Apply it to prove the division algorithm.
Prove the well-ordering principle.
Prove that the well-ordering principle is equivalent to mathematical induction.

Let’s implement this big picture to gain a much-needed appreciation for the well-ordering principle, at least to math people. For this post, we will assume $\mathbb N = \mathbb N_0$ , i.e. that $0 \in \mathbb N$ .

Well-Ordering Principle. For any $K \subseteq \mathbb N$ , if $K \neq \emptyset$ , then there exists $n \in K$ such that for any $m \in K$ , $n \leq m$ . Concisely, $n$ is a minimum element of $K$ .

The well-ordering principle helps us establish the existence of positive integers that satisfy nice properties. In the context of discrete math, and more specifically, introductory number theory, we can prove the division algorithm.

Division Algorithm. Let $a,b$ be positive integers with $a < b$ . Then there exist unique integers $q, r$ such that $b = aq + r$ and $0 \leq r < a$ .

Proof of Division Algorithm. Let’s first prove existence. Consider the set $K := \{b - ak : k \in \mathbb Z\} \cap \mathbb N^+$ . (We will eventually define the set $\mathbb Z$ of integers rigorously, and independently, to avoid circular reasoning.)

Observe that $b - a \cdot 1 \in K$ , so that $K \neq \emptyset$ . By the well-ordering principle, it has a minimum element $r := \min(K)$ . Hence, there exists some integer $q$ such that $r=b-aq$ , yielding $b = aq + r$ by algebruh.

Next, we’ll prove uniqueness for the sake of completeness, not because it’s relevant to the well-ordering principle. Suppose there are integers $q,q',r,r'$ with $0 \leq r,r' < a$ such that

$b = aq + r = aq' + r'.$

Then $r-r' = a(q'-q)$ implies that $r-r'$ is a multiple of $a$ . Manipulating the constraints $0 \leq r,r' < a$ yields

$0 \leq r < a \quad \text{and}\quad {-a} < -r' \leq 0.$

Adding the constraints yields $-a < r-r' < a$ . Since $r-r'$ is a multiple of $a$ , $q'-q \neq 0$ yields a contradiction, thus $q'-q = 0$ , which yields $q=q'$ and $r=r'$ , thereby establishing uniqueness.

The well-ordering principle helps us prove the existence of $r$ . But how do we even know that the well-ordering principle is a logically valid theorem? It turns out to be a consequence of strong induction.

Proof of the Well-Ordering Principle. Let $K \subseteq \mathbb N$ . We will prove the contrapositive: if $K$ has no minimum element, then $K = \emptyset$ . This second result is equivalent to the claim that for any $n \in \mathbb N$ , $n \notin K$ . This result is where we can take advantage of the power of strong induction.

Firstly, for the base case, if $0 \in K$ , then by definition of the natural numbers, for any $m \in K \subseteq \mathbb N$ , $0 \leq m$ . Thus, $0$ is a minimum of $K$ , a contradiction. Thus, $0 \notin K$ .

For the (strong) induction step, fix any $k \in \mathbb N$ such that $0,1,\dots, k \notin K$ . We need to show that $k+1 \notin K$ . Suppose, for a contradiction, that $k +1 \in K$ . Fix $m \in K \subseteq \mathbb N$ . If $m < k+1$ , then $m$ is one of $0,1,\dots,k$ . This means that $m \notin K$ , a contradiction. Therefore, $k+1 \leq m$ . This means that $k+1$ is a minimum element for $K$ , a contradiction.

Therefore, by the principle of strong induction, for any $n \in \mathbb N$ , $n \notin K$ .

Remarkably, the well-ordering principle is equivalent to the fundamental principle of mathematical induction. That is, if instead we started with assuming that the well-ordering principle is true, then we can prove the principle of mathematical induction as a theorem.

Theorem 1. Suppose the well-ordering principle is true. Let $\phi(n)$ be a predicate on $\mathbb N$ . Suppose $\phi(0)$ and for any $k \in \mathbb N$ , $\phi(k) \Rightarrow \phi(k+1)$ . Then for any $n \in \mathbb N$ , $\phi(n)$ .

Proof of Theorem 1. Define $K := \{n \in \mathbb N : \neg \phi(n)\}$ . We claim that $K = \emptyset$ . Suppose $K \neq \emptyset$ . Then $K$ contains a least element $n \in \mathbb N$ . Thus, $\neg \phi(n)$ . By the first condition, $\phi(0)$ . Therefore, $n > 0 \Rightarrow n-1 \geq 0$ .

Since $n = \min(K)$ , $n-1 \in \mathbb N \backslash K$ . If $\neg \phi(n-1)$ , then $n-1 \in K$ , a contradiction. Thus, $\phi(n-1)$ . Instantiating the second condition, since $n-1 \in \mathbb N$ , $\phi(n-1) \Rightarrow \phi(n)$ . Since $\phi(n-1)$ , by modus ponens, $\phi(n)$ . But $n \in K$ implies $\neg \phi(n)$ . Thus, $\phi(n) \wedge \neg \phi(n)$ , a contradiction.

Therefore, $K = \emptyset$ , as required. Thus, for any $n \in \mathbb N$ , $\phi(n)$ , as required.

What is a negative number? We discuss this idea rigorously next time.

—Joel Kindiak, 12 Nov 24, 2302H

Responses

When Integers Converge – KindiakMath

April 9, 2025 at 6:47 pm

[…] . By the well-ordering principle, contains a minimum element so that for any […]

LikeLike

Generalised Eigenstuff – KindiakMath

July 14, 2025 at 4:54 pm

[…] By the Cayley-Hamilton theorem, there exists a monic polynomial such that . By the well-ordering principle, the […]

LikeLike

The Union Bound – KindiakMath

October 8, 2025 at 10:01 pm

[…] we first note that is obvious. For the direction , fix for some . Take to be the smallest by the well-ordering principle, so that . Therefore, , as required. […]

LikeLiked by 1 person

A Classic Numbers Challenge – KindiakMath

December 28, 2025 at 12:49 am

[…] is rather interesting. Bézout’s lemma is a fascinating result that invokes two uses of the division algorithm. But first, we need the notion of a greatest common divisor, abbreviated by […]

LikeLike

The Preconditions of Infinity – KindiakMath

December 28, 2025 at 1:04 am

[…] Firstly, if , then . Next, suppose . Define . By the well-ordering principle, for each , whenever , iteratively […]

LikeLike

A Fascinating Multiples Problem – KindiakMath

January 5, 2026 at 6:17 pm

[…] the well-ordering principle, there exists some unique such […]

LikeLike

Prime Factorisation – KindiakMath

January 5, 2026 at 6:20 pm

[…] Since , by the division algorithm, find unique integers such […]

LikeLike

What Makes Strong Induction Strong? – KindiakMath

January 5, 2026 at 6:52 pm

[…] Strong induction even helps us reason about the well-ordering principle, and we need that principle to establish long division. We do that next time. […]

LikeLike

Who Cares About Well-Ordering?

Share this:

Responses

Leave a reply to A Fascinating Multiples Problem – KindiakMath Cancel reply