# The Unapologetic Mathematician

## Well-Ordering

A well-ordering on a set is a special kind of total order: one in which every non-empty subset contains a least element.

The two best examples of ordered sets we have handy are the natural numbers $\mathbb{N}$ and the integers $\mathbb{Z}$. For now, forget all the other algebraic structure we’ve talked about. The natural numbers are well-ordered, but the integers are not.

Seeing that the integers are not well-ordered is pretty easy: just take the subset of negative integers. There’s no negative number that’s less than all the others. Seeing that the natural numbers are well-ordered is a little more difficult. Given a set $X$, either ${}0$ is in $X$ or it isn’t. If it is, it’s the least element — nothing could be less than it. If it isn’t, then we move to $S(0)$. As we keep going, either we eventually hit an element of $X$ or we don’t. If we do, the first one is the least element of $X$. If not, then by induction the set of natural numbers not in $X$ is all of them, and $X$ must be empty!

It turns out that in the standard logical framework I’m using, any set can be equipped with a well-order. For instance, we could well-order the integers by saying $x\preceq y$ if either $|x|\leq|y|$ or $|x|=|y|$ and $x\leq y$. We can list the integers in this order: $0,-1,1,-2,2,...,-n,n,...$. The problem is that this doesn’t mesh with the algebraic structure very well.

Now as we’ll see when we get to them, the natural order on the real numbers is even further from being well-ordered, and there doesn’t seem to be any sensible way to well-order them. Still, we’ll see eventually that though the well-ordering principle is “plainly false” — very counterintuitive — it turns out to be logically equivalent to another tool that’s so incredibly useful we really should accept this unexpected fact.

April 2, 2007 - Posted by | Fundamentals, Orders

1. Is S(0) = “the integers except 0” ? Comment by isomorphismes | January 9, 2015 | Reply

2. The set {−1,1,−2} doesn’t have a least element under the well-ordering you said for the integers: it has two “least” elements of equal size.

Did you mean to define the well-ordering case-wise, with a −x<x as a tiebreaker in case |y|=|z| ? Comment by isomorphismes | January 9, 2015 | Reply

3. No, $S(0)$ is the successor of $0$, or $1$. Then if $1\notin X$ we move on to $S(1)=2$, and so on. And yes, I stated that tiebreaker. First try $|x|\leq|y|$ or if that’s not the case use $|x|=|y|$ and $x\leq y$. Comment by John Armstrong | January 9, 2015 | Reply