canonical ordering on pairs of ordinals
The lexicographic ordering on OnOn, the class of all pairs of ordinals, is a well-order in the broad sense, in that every subclass of OnOn has a least element, as proposition 2 of the parent entry readily shows. However, with this type of ordering, we get initial segments which are not sets. For example, the initial segment of consists of all ordinal pairs of the form , where On, and is easily seen to be a proper class. So the questions is: is there a way to order OnOn such that every initial segment of OnOn is a set? The answer is yes. The construction of such a well-ordering in the following discussion is what is known as the canonical well-ordering of OnOn.
For example, consider the usual ordering on . Given . Suppose . Then the set of all such that is the union of the three pairwise disjoint sets .
. is a strict linear ordering on .
It is irreflexive because is never comparable with itself. It is linear because, first of all, given , exactly one of the three conditions is true, and hence either , or . It remains to show that is transitive, suppose and .
The two cases
produce . Now, assume , which result in three more cases
, and and ,
the first two produce , and the last and . In all cases, we get . ∎
If is a well-order on , then so is on .
Let be non-empty. Let
Then , and therefore has a least element , since is a well-order on . Next, let
Then , and has a least element . Finally, let
Again, , so has a least element . So . We want to show that is the least element of .
Pick any distinct from . Then is at least . If , then . Otherwise, , so that is at least . If , then again we have . But if , then , so that . Since , and , . Therefore , and as a result. ∎
The ordering relation above can be generalized to arbitrary classes. Since On is well-ordered by , the canonical ordering on OnOn is a well-ordering by proposition 2. Moreover,
Given the canonical ordering on OnOn, every initial segment is a set.
Given ordinals On, suppose . The initial segment of is the union of the following collections
, which is a subcollection of ,
, which again is a subcollection , and
, which is a subcollection of .
Since and are both sets, so is the initial segment of . ∎
Remark. The canonical well-ordering on OnOn can be used to prove a well-known property of alephs: , for any ordinal .
|Title||canonical ordering on pairs of ordinals|
|Date of creation||2013-03-22 18:50:02|
|Last modified on||2013-03-22 18:50:02|
|Last modified by||CWoo (3771)|