Thread: Well-ordering Theorem

I find this weird, anyone any thoughts?. Let's start by defining a well-order.

A set S is said to be well-ordered if each of its subsets has a least element. A moments thought tells you this implies that each element of S has an immediate predecessor. No problems here, I trust.

For example, the "counting" (aka natural) numbers are well ordered; 0 is the least element in N and 2 < 3. Allow me a little abstraction. I will say that, given the binary operation ≤, the follow relations must apply:

x ≤ x;
if x ≤ y and y ≤ x, then x = y;
if x ≤y and y ≤ z, then x ≤ z.
No difficulties here either, I imagine.

Let's now consider the set R of real numbers, with, say (0, 1) a subset in its standard topology. Is R well-ordered? What is the least element in this subset? Obviously it's not 0, what is it? Think of a real number ever so slightly more that 0, then half it, half it again and so on. You'll never find a least element, right? Moreover, what's the immediate predecessor to 1? (No, don't open that can of worms!)

So, the well-ordering theorem states that it is always possible to place a well-order on any set, which will, of course, include R. What gives? Here's my take, anybody any better ideas?

Well, we know this: as 0 ∉ (0, 1), 0 cannot be the least element of this subset. But we also may assume 0 < 1, so there must be some element x of R with 0 < x < 1 that is the least element in (0, 1). Can we say what it is? No. Does it exist? We must assume so.

Likewise, for y < z in (0, 1), we must assume there is some r ≠ y, r ≠ z such that r immediately precedes z. Can we say what it is? No. Does it exist? It must!

Have you seen a proof of the well-ordering theorem guitarist? Its kind of cute and introduces quite a few important nuts and bolts topics.

Evidently, by the above, not. But you're about to show me, right?

lol yeah, was just making sure you wanted to see it as it may take a few posts. Firstly, do you know about ordinal numbers and transfinite induction?

Well of course (I think) I know about ordinal numbers. Transfinite induction, sadly not. Anyway, fire away, I really love non-intuitive math

ah ok, lets start at the very beginning (as it apparently is a very good place to start)

An ordinal number is defined to be the union of all ordinal numbers smaller then it. It's easy to see that every natural number is an ordinal number (for example 2 = {0, 1}) which allows us to talk about our first infinite ordinal number omega = {0, 1, 2, ...}.

Now the ordinal numbers are well ordered under set containment (let S be a nonempty subset of ordinal numbers, then define s = intersection of S which is the minimal element of S).

That all sound familiar?

Sure.

Well there are two types of ordinal numbers. The first type are like the naturals numbers in that they are successor ordinals i.e. alpha is a succesor ordinal iff there exists an ordinal beta such that alpha is the first ordinal larger then beta. Given any ordinal number beta, it is easy to see that beta union {beta} is a succesor ordinal.

All ordinals which are not succesor ordinals are limit ordinals and they behave like omega in a sense.

Now transfinite induction is the extension of induction to all ordinal numbers.

Suppose P(alpha) holds for alpha = 0, and if the truth of P(alpha) for all alpha < beta => the truth of P(beta) then P(alpha) is true for all ordinals alpha.

The proof of this is exactly the same as in the natural number case.

Next stop, order isomorphisms and the axiom of choice.

Yeah, yeah, now are you going to bowl, or stand all day polishing the ball?

lol, ok here is the proof without all the side fluff.

Axiom of choice : Every set admits a choice function i.e. a function f : 2^X -> X such that f(A) is an element of A for all non-empty A in 2^x.

Let X be an infinite set and let f be a choice function on X, define a alpha-sequence as follows.

define x₀ = f(X). Suppose x_alpha has been defined for all alpha < beta. Consider the set X \ U{x_alpha}. If it is empty we have our alpha-sequence so let k = beta (|k| = |X| btw), else define x_beta = f(X \ U{x_alpha}). By the principle of transfinite induction this alpha-sequence is well-defined.

define a function g : {alpha : alpha < k} -> X by g(alpha) = x_alpha. Now g is a bijection as the alpha-sequence constructed above is well-defined and covers X. Define a partial order on X by :

a < b iff g^-1(a) < g^-1(b).

Now let A be a subset of X, then g^-1(A) is a subset of {alpha : alpha < k} which is well-ordered so has a least element beta. But then g(beta) is the least element of A by the construction of g.

So X can be well-ordered assuming the axiom of choice. In fact the two statements are equivalent, given the well-ordering theorem you can derive the axiom of choice (let f : 2^X -> X be defined by the min(A) for all non-empty A)

Gosh, I'm so stupid (and so vain). I just spent the last half hour working up a version of Zermelo's proof to show you all how clever I am, only to realize it is formally equivalent to river_rat's. Doh.

Anyway, the axiom of choice is an interesting topic, but not one I want get into too deeply. Suffice it to say that I have just completed, with many false starts, a proof that, assuming that the statement "every vector space has a basis" is true and is, moreover, a restatement of the axiom of choice, then, if dimV is countably infinite, then dimV* is uncountably so.

In other words, by the axiom of choice, we may assume that V* has a basis, but we can never know what it is. Likewise here; there is a least element for any subset A of X, but we may not be able to write it down. That's weird.

I am told there is a fringe of mathmen that rejects the axiom of choice, because of this weirdness. I don't doubt they encounter their own sorts of weirdness, e.g. not all vector spaces have a basis! but I value my sanity too much to go down this path.

Mark C. Chu-Carroll has written a few good posts on this topic on his blog. This post and this one are two of the most relevant, although there are others.

Out of curiosity, can you use the surreal numbers to provide a well-ordering of the reals (sorting by birthday then by the normal order)? Or rather, why wouldn't that work?

Hi MagiMaster

I'm not too familiar with the surreal numbers, can you explain what you mean?

Hey guitarist, post your proof never the less as then we can finish off the usual equivalence loop that AC <=> Well-ordering thm <=> Zorn's lemma.

Talking about weird, i find the notion of a basis for the reals over the rationals quite weird all by itself!

Well, in trying to be brief (and with my bad memory) I'll probably get something wrong, but here goes.

Every number is defined by a left and right set consisting of previously defined numbers less than and greater than the new number. This starts with { | } (two empty sets) which is defined as 0. Then you get { | 0} = -1 and {0 | } = 1. ({0 | 0} can be defined, but it's not a number.) Next you get { | -1, 0, 1} = { | -1} = -2, {-1 | 0, 1} = {-1 | 0} = -1/2, etc.

The step at which a number appears is called its birthday. 0 has the birthday 0, -1 and 1 have 1, etc. In a finite number of steps, you get all the numbers of the form x / 2^y (I forgot what those are called), and at omega steps you get all the reals. After that, new numbers continue to appear, including various infinities and infinitesimals.

The point is, taking this sequence of numbers 0, -1, 1, -2, -1/2, 1/2, 2, etc., would that be a well ordering?

Originally Posted by river_rat

Hey guitarist, post your proof never the less as then we can finish off
the usual equivalence loop that AC <=> Well-ordering thm
<=> Zorn's lemma.

Well, no, first because I didn't complete it, second because you gave a complete proof, and third because it would probably bore other members. But I will give a sketch of how I thought it might go.

Suppose X is an infinite set. Choice allows me to select an element, any element, of X to be the first element in some subset A of X. Call it x₁. I may then, in a similarly arbitrary fashion, select another element from X\{x₁} and call it x₂, select x₃ from X\{x₁, x₂} and so on.

Carry on, as far as I like, and call this my "initial segment" A, where the following applies: for the nth element of A, the (n -1)th element is also is in A. I will call this a strict total order on A.

I further insist on the following rules: no element of X can simultaneously be the mth and nth element of A (m ≠ n), and neither can x, y each be be the nth element in A unless x = y. Iterate the above, in an attempt to build a nested set of such subsets of X.

But surely there is no guarantee that for some subsest B of X ordered as above, that the orders on A and B will agree? But in fact, of the uncountably many total orders that Choice allows me to place on A and separately on B, I can always find some A and some B such that the following is true:

A ⊆ B;
if x < y in B and y is in A, then x is in A;
the orderings in A and B agree on A up to ≤.

This last implies the union of {A, <} and {B, <} is {B, ≤}.

Then the union of all strictly ordered sets where the above is true is X, which is now well ordered, essentially by construction.

Originally Posted by MagiMaster

Well, in trying to be brief (and with my bad memory) I'll probably get something wrong, but here goes.

Every number is defined by a left and right set consisting of previously defined numbers less than and greater than the new number. This starts with { | } (two empty sets) which is defined as 0. Then you get { | 0} = -1 and {0 | } = 1. ({0 | 0} can be defined, but it's not a number.) Next you get { | -1, 0, 1} = { | -1} = -2, {-1 | 0, 1} = {-1 | 0} = -1/2, etc.

The step at which a number appears is called its birthday. 0 has the birthday 0, -1 and 1 have 1, etc. In a finite number of steps, you get all the numbers of the form x / 2^y (I forgot what those are called), and at omega steps you get all the reals. After that, new numbers continue to appear, including various infinities and infinitesimals.

The point is, taking this sequence of numbers 0, -1, 1, -2, -1/2, 1/2, 2, etc., would that be a well ordering?

Ah i kind of see what you mean (those rationals are called dyadic btw). The problem with your construction is this:

At each step alpha you construct a new subset of reals A_alpha which is pairwise disjoint from all the previous subsets A_beta you have constructed so far. You only ever create a countable number of these subsets though (as omega is countable) so one of those subsets must be uncountable and you have no way of well ordering that subset given your construction.

Make sense?

Sorry for the late reply.

Anyway, that makes some sense. The construction of the surreals carries on after omega, but I'm reasonably sure all the reals (other than the dyadics) have omega as their birthday.

So, since the reals are uncountable, but omega isn't, the set of all numbers with the birthday omega is uncountable, and my method can't well-order that set since it can't specify a least element?

Yep that's pretty much the issue - you can create a well ordering on a finite union of countable disjoint sets (just use a lexicographic ordering) but you get stuck trying to do the same construction on an uncountable set without using the axiom of choice.

Actually, thinking about it a bit more, I think there are more surreals created at omega than just the reals. (I think +/- omega and +/- 1/omega are there too.)

So the basic requirement for it to be a well ordering is that given any position you can get the number and given any number you can get the position? So in the previous attempt, you couldn't give the position of any real other than the dyadics even though you could give the number at any position?

A well-ordering is any ordering for which every subset has a least element. So i'm not sure about the position thing you are talking about - care to expand?

Well, I could just be wrong.

Using that definition though, the set as a whole has a least element, so it's in position 0. The set minus that element has a least element, so it's in position 1. Etc. Hmm... It seems like you could make a case for going the other way too, but I can't see exactly how at the moment. (Of course, for both directions, you'd need numbers past omega to count with.)

Would it be called anything if you could say that every open interval has a least element? (Assuming that question made sense. :P)

Ok, i see what you were on about. Yeah in general with out the axiom of choice you can't construct that list.

mmm, I guess you would have some strange weaker version of the axiom of choice really. Would have to think about it more.