# 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$:

### Antisymmetric

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

### Transitive

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

## 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.