Well-ordering theorem

1. Feb 2, 2010

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....

2. Feb 2, 2010

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.

3. Feb 2, 2010

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.

4. Feb 2, 2010

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?

5. Feb 2, 2010

JSuarez

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.

6. Feb 2, 2010

CRGreathouse

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).

7. Feb 3, 2010

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.

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.

Last edited: Feb 3, 2010
8. Feb 3, 2010

mlsbbe

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 dont understand this......sigh.....

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

Last edited: Feb 3, 2010
9. Feb 3, 2010

dodo

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.

10. Feb 3, 2010

CRGreathouse

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.

11. Apr 11, 2010

kazordoon

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.

12. Apr 11, 2010

JSuarez

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.

13. Apr 11, 2010

kazordoon

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

14. May 13, 2011

Hi,

So if under ZFC a well ordering exists for the reals, why isnt 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?

15. May 13, 2011

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)

16. May 13, 2011

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.

17. May 14, 2011

micromass

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!

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 understand that this is your intuition about the subject. But you need to formalize your intuition. Then you will see what the problems are.

18. May 14, 2011

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.

19. May 15, 2011

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."

20. Jun 2, 2011

SteveL27

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