## 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 and the integers . 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 , either is in 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 . As we keep going, either we eventually hit an element of or we don’t. If we do, the first one is the least element of . If not, then by induction the set of natural numbers *not* in is all of them, and 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 if either or and . We can list the integers in this order: . 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.

Is S(0) = “the integers except 0” ?

Comment by isomorphismes | January 9, 2015 |

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 |

No, is the successor of , or . Then if we move on to , and so on. And yes, I stated that tiebreaker. First try or if that’s not the case use and .

Comment by John Armstrong | January 9, 2015 |