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 
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 
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 
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.
3 Comments »
Leave a Reply
RSS Feeds
Is S(0) = “the integers except 0″ ?
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| ?
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 
.