Well Ordering Axiom (Principle or Theorem?)

by Dave
(DAVE)—

In this video, I’m going to talk about the Well-Ordering Axiom. First, I’ll discuss the ordering and why it’s reflexive, antisymmetric, and transitive. Then I explain the Well-Ordering Axiom followed by some basic examples. After that, I’ll discuss whether it should be an axiom or a theorem.

To state the Well-Ordering Axiom, we need to know what the underlying ordering is. How does the standard ordering arise on the natural numbers? Let’s begin with the definition of the familiar less than relation on the natural numbers.

What is the ordering in the Well Ordering Axiom?

The relation less than or equals is defined on the natural numbers as $m$ is less than or equal to $n$ means there exists a natural number $p$ such that $m+p=n$. The way I think about this is, $m$ is smaller than (or equal to) $n$, so $m$ needs a little bump (maybe none) $p$ so that $m+p$ is the same as $n$.

Definition (Ordering on the Natural Numbers) The relation $\leq$ defined on $\mathbb{N}$ by $$\forall m,n\in \mathbb{N} \ : \ m \leq n \Longleftrightarrow \exists \, p\in \mathbb{N} \ : \ m+p = n.$$

Notice that we can easily check that it is reflexive, antisymmetric, and transitive. Hence $\leq$ is a ordering on $\mathbb{N}.$

Reflexive

Here I discuss the reflexive property of $\leq$:

ordering on the natural numbers is reflexive
Ordering on the natural numbers is reflexive

Antisymmetric

Here I discuss the antisymmetric property of $\leq$:

ordering on the natural numbers is antisymmetric
Ordering on the natural numbers is antisymmetric

Transitive

Here I discuss the transitive property of $\leq$:

Ordering on the natural numbers is transitive
Ordering on the natural numbers is transitive

The Well Ordering Axiom

The Well Ordering Axiom is the simple claim that:

Every nonempty set of positive integers has a least element.

Example. Does each of the following sets have a smallest element in each subset.

$A=\{n\in \mathbb{N}\mid n \text{ is prime}\}$

$B=\{n\in \mathbb{N} \mid n \text{ is a multiple of 7} \}$

$C=\{n\in \mathbb{N} \mid n=110-7m \text{ for some } m\in \mathbb{Z} \} $

$D=\{n\in \mathbb{N} \mid n=12s+18t \text{ for some } s,t\in \mathbb{Z} \} $

Notice that for each set $A, B, C,$ and $D$ they are all subsets of the natural numbers. Also notice that each one of them is nonempty because $2\in A$, $7\in B$, $110\in C$, and $0\in D$. So in fact, by the Well Ordering Axiom each of these sets has a least element.

Conclusion

I talked about Mathematical Induction in a previous video. But there is a very close relationship between the Well-Ordering Axiom and Mathematical Induction. If you wish, you can choose to have the Well-Ordering Axiom as an axiom and then prove Mathematical Induction as a theorem. Or, if you prefer, you can use Mathematical Induction as an axiom and then prove the Well-Ordering Axiom as a theorem. For these reasons, we often call them the Principle of Mathematical Induction and the Well-Ordering Principle.

To learn a great deal more on this topic, consider taking the online course The Natural Numbers.