|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``Re: Well-ordered set?''
by marijke on 2006-02-16 09:11:54 |
|
| Sorry, read your original msg too quickly. Your lovely set
M = { 0, 1/2, 2/3, 3/4, ... 1, 1+1/2, 1+2/3, ... 2, ... 3, ... }
(when ordered by the usual < from the rationals or reals) has the same ordering structure as
K = { 0, 1, 2, 3, ... w, w+1, w+2, ... 2w ... 3w ... }
Remember, it's not the names of the elements that matter, it's their position in the ordering. As far as ordering is concerned, they are isomorphic (they have the same ordering). The name for M or K ordered that way is w^2, by the way.
Names for well-orderings are called "ordinals". The ordinal 0 is the name for the ordering of the empty set. 1 is the name for the ordering of every single-element set. 2 is the name for every two-element set that is ordered * < *. And so on for all the natural number names, for instance 13 is the name for the ordering structure of a set of 13 elements *provided* it has the simple * < * < * < ... ordering (that is, for any two elements a and b, we have a < b or a = b or a > b (*note).
The name of the ordering of all natural numbers the usual
* < * < * < * < ...
way is w (omega). If it has an extra element at the end, it's w+1. And so on. Now here is the nice thing: the ordinals themselves are well ordered! And the set { ordinals less than ordinal k } is itself a set whose ordering type is k (where "less than" is defined the obvious way). Now
0 is the ordering of { }
1 is the ordering of { 0 }
2 is the ordering of { 0, 1 } ordered as 0 < 1
3 is the ordering of { 0, 1, 2 } ordered 0 < 1 < 2
...
w is the ordering of { 0,1,2,3... } ordered the way you expect
w+1 is that of { 0,1,2,... w } ordered ... < w
w+2 is that of { 0,1,2,... w,w+1} ordered ... < w < w+1
See where it is going? Any ordering k is the ordering of the set of ordinals "less than" k, ordered by "less than" each other, where for two ordinals i and j, i "less than" j means i is a left part of j. It gets nicer even. We can DEFINE
0 = {}
1 = {0} = {{}}
2 = {0,1} = {{},{{}}}
3 = {0,1,2} = {{},{{}},{{},{{}}}}
4 = {0,1,2,3} = ...
and now i "less than" j means BOTH i element of j and i subset j. All the ordinals, spun out of thin air with nothing inside :)
*note: Such an ordering is also called "total ordering". For finite sets, total ordering == well ordering. For infinite sets, total doesn't necessarily imply well. The integers (including the negative ones) with the usual ordering are totally ordered but not well ordered.
Here's an example of an ordering that's not total: "descendant" in the tree
d a < b < c < d
\ b < e
c e but
\ / no other < relations
b
|
a
This is a "partial order". Usually a partial order is expressed with <= rather than < and everything is also <= itself. A total order is a partial order where for every a and b at least one of a<=b and b<=a is true (elements are always comparable).
You may like to prove well ordering implies total ordering, but not vice versa (unless the set is finite).
The tree example also shows that < doesn't have to be about the usual smaller/bigger < of numbers. Any one set (such as the natural numbers for instance) has many different orderings.
Quick test: let's call a <| b (both natural numbers) iff b is divisible by a. Is <| defined this way a partial order? Is it total? Is it well?
Another one... define the order << as follows (natural numbers again). If a has fewer or more factors 2 than b, say that a << b or b << a respectively. If they have the same number of factors 2, look at factors 3. If they tie too, look at factors 5. And so on. Is << a partial order? Is it total? Is it well?
--have fun,
marijke
--regards, marijke
http://web.mat.bham.ac.uk/marijke/ |
| | [ reply | up | top ] | |
|
|
|
|
|
|
|
