Understanding the Well-Ordering Theorem: A Simplified Explanation

[mlsbbe]

Can somebody please explain to me what is the well-ordering theorem in layman's terms. After looking at the explanation on wikipedia, I'm still not too sure...

 

[CRGreathouse]

Take a set. The set can be well-ordered.

A set S is well-ordered exactly when it has a relation ≺ such that:
* For any a and b in S, exactly one of a ≺ b, b ≺ a, a = b holds;
* For any a, b, and c in S, if a ≺ b and b ≺ c, a ≺ c;
* For any subset A of S, there is an a in A with a ≺ b for all other b in A.

The first two mean that ≺ is a total order: you can 'line up all the elements in order' if you have enough space. The last means that ≺ is well-founded.

 

[JSuarez]

(Nitpicking:any nonempty set or subset )

But CRGreathouse is correct: the well-ordering theorem (which is sometimes taken as an axiom of Set Theory), states that any nonempty set admits a well-order, that is, a total order such that any nonempty subset has a minimum element; in other words, every nonempty set, may be made to look, in terms of ordering, like the natural numbers.

The downside is that this well-order is impossible to find explicitly for most sets; we only know that ir exists.

 

[dodo]

If I understood correctly, this means the integers are well-ordered, but the rationals are not: they fail the last, "well-founded" axiom. (Unless you rewrite the axiom to allow for the bordering element "a" to be outside the subset.) Is that correct?

 

[JSuarez]

If I understood correctly, this means the integers are well-ordered, but the rationals are not: they fail the last, "well-founded" axiom. (Unless you rewrite the axiom to allow for the bordering element "a" to be outside the subset.) Is that correct?

No, that's not correct at all. First, the usual order <, well-orders the naturals, not the integers (the integers $\mathbb Z$ also have negative numbers, and many subsets don't have a minimum element). Second, the well-ordering theorem does not fail, theorems don't fail if their premises obtain: what it states is that, from all possible total orders that we impose on a set (there are an infinite number of them, if the set is infinite), there will be at least one that is also a well-order.
This means that, for $\mathbb Z$, $\mathbb Q$, $\mathbb R$, etc., there will be a total order (completely different from the usual order) that is also a well-order; we simply don't know how to find it, but we do know it exists.

 

[CRGreathouse]

If I understood correctly, this means the integers are well-ordered, but the rationals are not: they fail the last, "well-founded" axiom. (Unless you rewrite the axiom to allow for the bordering element "a" to be outside the subset.) Is that correct?

The rational numbers are not well-ordered by "<", the usual order on the rationals. But they can be well-ordered lexicographically.

Harder are the real numbers. It can be proved that no well-order of the real numbers can be demonstrated (unlike the rationals), but if you believe the Axiom of Choice or the Well Ordering Theorem then there is one (just not one we can write down explicitly).

 

[dodo]

Ok, thanks to both of you. It's a bit more clear now, though I still lack foundations on axiomatic theory to grasp the abstract definition fully. I only heard it in the context of number theory, in a form "like" this one (sorry, I quote from memory, I don't have the exact definition at hand): "any non-empty subset of integers bounded below has a minimum element", and same for above and maximum.

The rational numbers are not well-ordered by "<", the usual order on the rationals. But they can be well-ordered lexicographically.

I take you mean Cantor's argument of ordering pairs of naturals, in order to show Q is countable, don't you? Or similar.

Edit:
On second thought, you might have just meant "lexicographically". :) The strings "1/1", "1/2", ..., "111/211", etc, all have a finite length and can be ordered as plain text.

 

[mlsbbe]

Take a set. The set can be well-ordered.

A set S is well-ordered exactly when it has a relation ≺ such that:
* For any a and b in S, exactly one of a ≺ b, b ≺ a, a = b holds;
* For any a, b, and c in S, if a ≺ b and b ≺ c, a ≺ c;
* For any subset A of S, there is an a in A with a ≺ b for all other b in A.

The first two mean that ≺ is a total order: you can 'line up all the elements in order' if you have enough space. The last means that ≺ is well-founded.

Excuse my stupidity here, but is ≺ an inequality sign? If so, from condition (1),
how can a<b and b<a at the same time? I still don't understand this...sigh...

I get the impression that ≺ means something else entirely...

 

[dodo]

from condition (1), how can a<b and b<a at the same time?

No, condition (1) just said that there are three cases: either a<b, or a>b, or a=b; and that any pair a,b you can think of will fall in one (and only one) of the three cases. It cannot fall in two cases, nor in none and be undefined; exactly one case will be true.

As for < being "inequality", I presume it is intended here as an abstract operation, with no previous context at all: it only does what the definition above allows it to do. But a power cat can provide a more complete answer next.

 

[CRGreathouse]

As for < being "inequality", I presume it is intended here as an abstract operation, with no previous context at all: it only does what the definition above allows it to do. But a power cat can provide a more complete answer next.

Exactly. For the natural numbers we can use the usual "<" for ≺; for the rationals, the lexicographic (sort by length then 'alphabetically') for ≺; for the reals, we can't write one but under ZFC one exists.

The symbols < (U+003C) and ≺ (U+227A) should be distinct. On this computer the ≺ doesn't look quite right, but you can at least tell it apart from <. ≺ should look curved while < has only two straight line segments.

I suppose I could have used a more exaggerated character like ⊰ (U+22B0) but I don't like that one.

 

[kazordoon]

(Nitpicking:any nonempty set or subset )

But CRGreathouse is correct: the well-ordering theorem (which is sometimes taken as an axiom of Set Theory), states that any nonempty set admits a well-order, that is, a total order such that any nonempty subset has a minimum element; in other words, every nonempty set, may be made to look, in terms of ordering, like the natural numbers.

The downside is that this well-order is impossible to find explicitly for most sets; we only know that ir exists.

yes, but not totally correct. Most of the well orders are different from the one in the natural numbers. Take any ordinal greater than N. For example w+1 defined as:

{0,1,2,3,4, ...} U {w} where the order is the usual < for the natural numbers and n<w for all n in N.

ie, we are adding a extra element to the naturals larger than each one of them.

You can easily prove that this is a well order but there is no 1 to 1 function that preserves order between N and w+1.

 

[JSuarez]

I'm sorry, but I can't see where is the "error".

yes, but not totally correct. Most of the well orders are different from the one in the natural numbers.

This was repeatedly stated by myself, CRgreathouse and others in this thread.

You can easily prove that this is a well order

That's not such a big deal: all ordinals, either sucessor (as the ones you mention) or limit ones are naturally well-ordered.

The imprecise term "like" was not meant mathematically, but merely as an analogy; therefore, going beyond the finite ordinals doesn't really add anything.

 

[kazordoon]

I'm sorry, but I can't see where is the "error".



This was repeatedly stated by myself, CRgreathouse and others in this thread.



That's not such a big deal: all ordinals, either sucessor (as the ones you mention) or limit ones are naturally well-ordered.

The imprecise term "like" was not meant mathematically, but merely as an analogy; therefore, going beyond the finite ordinals doesn't really add anything.

my apologies then for misunderstanding your use of the word "like". Things of the natural language! :D

 

[doomCookie]

Hi,

So if under ZFC a well ordering exists for the reals, why isn't this in contradiction to their uncountability?

Is it enough that we cannot demonstrate this well-ordering by a mapping of reals to natural numbers to say they are not countable?

I ask because it seems for a set to be well ordered it would necessarily be countable (even if we are unable to do so), with every least element being assigned a natural number and then the least element of the remaining elements and so on to infinity according to the well order...

So why is it that reals are uncountable despite their well order?

Someone please enlighten me?

 

[micromass]

A set can both be uncountable and well-ordered. In fact, I don't quite see how you would construct that bijection. You said to map all least numbers to a natural number, but that doesn't quite work, take

$$\mathbb{N}\cup\{\infty\}$$

where infinity is larger than all natural numbers. Then you can't map all least elements to a natural number. Indeed, your map would send n to n. But then, where do you send infinity to?
And still, this set is well-ordered. (It is also countable, but I hope this example shows you the flaw in the reasoning)

 

[doomCookie]

Thank you for the reply. I am still not sure why a set can be both uncountable and well ordered. I will clarify my confusion.

So the reals are uncountable by the Cantor diagonalization proof, so they cannot be put in one-to-one correspondence with the natural numbers. But the reals are well ordered by the Well Ordering theorem, so for any subset A of the real numbers R, there is an a in A with a ≺ b for all other b in R.

How can that 'a' exist for R if by the diagonalization I can always construct a new member of R, one that could be ≺ a?

I would think that to make a claim about 'a' over all 'b's in R the set R itself would need to be countable in order that any kind of order be discovered at all.

Unless the main point is that (as someone said above) such an order exists but we cannot demonstrate it and thus by definition the set is not countable, if for it to be countable means basically that we demonstrate such a well order by means of the bijection.

 

[micromass]

Thank you for the reply. I am still not sure why a set can be both uncountable and well ordered. I will clarify my confusion.

So the reals are uncountable by the Cantor diagonalization proof, so they cannot be put in one-to-one correspondence with the natural numbers. But the reals are well ordered by the Well Ordering theorem, so for any subset A of the real numbers R, there is an a in A with a ≺ b for all other b in R.

That's not really what well ordering is. It's probably a typo from your side, but I'll clarify it anyway. Well ordering is such that for any non-empty subset A of R, there is an a in A such that $$a\leq b$$ for all other b in A.

Also note that well-ordering doesn't say that R is well-ordered, but merely that a well-ordering exists!

How can that 'a' exist for R if by the diagonalization I can always construct a new member of R, one that could be ≺ a?

So, how would that work then? How would you construct that new member. I can easily define my well-order such that 0 is the smallest member of R. How can you then construct a new member that is smaller than 0?

I would think that to make a claim about 'a' over all 'b's in R the set R itself would need to be countable in order that any kind of order be discovered at all.

I understand that this is your intuition about the subject. But you need to formalize your intuition. Then you will see what the problems are.

 

[doomCookie]

Thank you for the reply. I must have misunderstood the well ordering theorem, I will try and increase my knowledge on the subject before I post again.

 

[spamiam]

Hi doomCookie, and welcome to the forum!

I think part of your confusion may stem from the fact that, for ordered sets, cardinality doesn't tell the whole story. The classic example that my professor used in illustrating this was with the natural numbers. One ordering we can use is just the normal <, which gives us:

0, 1, 2, 3, 4, ...

But we could also list all the even numbers first, from low to high, followed by the odd numbers:

0, 2, 4, 6, 8, ..., 1, 3, 5, 7, 9, ...

It seems that the second ordering is somehow "longer" than the first, and I'm pretty sure (correct me if I'm wrong) these two orders have different order types (http://en.wikipedia.org/wiki/Order_type), even though they're defined on the same set. In general, sets with the same cardinality may still have different order type--an example from the article:

"But the set of integers and the set of rational numbers (with the standard ordering) are not order isomorphic, because, even though the sets are of the same size (they are both countably infinite), there is no order-preserving bijective mapping between them."

 

[SteveL27]

Hi,

So if under ZFC a well ordering exists for the reals, why isn't this in contradiction to their uncountability?

I think that the fact you're missing is this: There are uncountable ordinals.

Rather than attempt to summarize the theory, I'll just link the Wikipedia page.

http://en.wikipedia.org/wiki/Ordinal_number

Now, there is no mystery. The Axiom of Choice (the 'C' in ZFC) is equivalent to the proposition that every set can be well-ordered. So, given the set of reals, there exists some well-order on it. Since the reals are uncountable, the ordinal of their well-order would be some uncountable ordinal. There's no contradiction, provided that one can get one's mind around uncountable ordinals!

Here is an informal proof that the reals can be well-ordered. The reals are nonempty, so just pick any element, call it r1. The set of reals minus {r1} is nonempty, so pick r2. The reals minus {r1, r2} is nonempty, so pick r3. Dot Dot Dot! To formalize this proof, you need the Axiom of Choice to keep picking an element from each of the nonempty sets you get after each step.