canonical ordering on pairs of ordinals

The lexicographic ordering on On×On, the class of all pairs of ordinalsMathworldPlanetmathPlanetmath, is a well-order in the broad sense, in that every subclass of On×On has a least element, as propositionPlanetmathPlanetmath 2 of the parent entry readily shows. However, with this type of orderingMathworldPlanetmath, we get initial segments which are not sets. For example, the initial segment of (1,0) consists of all ordinal pairs of the form (0,α), where α On, and is easily seen to be a proper class. So the questions is: is there a way to order On×On such that every initial segment of On×On 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 On×On.

To begin, let us consider a strictly linearly ordered set (A,<). We construct a binary relationMathworldPlanetmath on A×A as follows:

(a1,a2)(b1,b2)iff{max{a1,a2}<max{b1,b2}, or max{a1,a2}=max{b1,b2}, and a1<b1, or max{a1,a2}=max{b1,b2}, and a1=b1, and a2<b2.

For example, consider the usual ordering on . Given (p,q)×. Suppose pq. Then the set of all (m,n)× such that (m,n)(p,q) is the union of the three pairwise disjoint sets {(m,n)max{m,n}<q}{(m,q)m<p}{(p,n)n<q}.

Proposition 1.

. is a strict linear ordering on A×A.


It is irreflexiveMathworldPlanetmath because (a1,a2) is never comparablePlanetmathPlanetmath with itself. It is linear because, first of all, given (a1,a2)(b1,b2), exactly one of the three conditions is true, and hence either (a1,a2)(b1,b2), or (b1,b2)(a1,a2). It remains to show that is transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath, suppose (a1,a2)(b1,b2) and (b1,b2)(c1,c2).

The two cases

  1. 1.

    max{a1,a2}<max{b1,b2} and max{b1,b2}max{c1,c2},

  2. 2.

    max{a1,a2}max{b1,b2} and max{b1,b2}<max{c1,c2},

produce max{a1,a2}<max{c1,c2}. Now, assume max{a1,a2}=max{b1,b2}=max{c1,c2}, which result in three more cases

  1. 1.

    a1<b1 and b1c1,

  2. 2.

    a1b1 and b1<c1,

  3. 3.

    a1=b1=c1, and a2<b2 and b2<c2,

the first two produce a1<c1, and the last a1=c1 and a2<c2. In all cases, we get (a1,a2)(c1,c2). ∎

Proposition 2.

If < is a well-order on A, then so is on A×A.


Let RA×A be non-empty. Let


Then BA, and therefore has a least element b, since < is a well-order on A. Next, let

C:={c1max{c1,c2}=b, where (c1,c2)R}.

Then C, and has a least element c. Finally, let

D:={d2max{c,d2}=b, where (c,d2)R}.

Again, D, so has a least element d. So (c,d)R. We want to show that (c,d) is the least element of R.

Pick any (x,y)R distinct from (c,d). Then max{x,y}B is at least b=max{c,d}. If b<max{x,y}, then (c,d)(x,y). Otherwise, b=max{x,y}, so that xC is at least c. If c<x, then again we have (c,d)(x,y). But if c=x, then yD, so that dy. Since (x,y)(c,d), and x=c, yd. Therefore d<y, and (c,d)(x,y) as a result. ∎

The ordering relation above can be generalized to arbitrary classes. Since On is well-ordered by , the canonical ordering on On×On is a well-ordering by proposition 2. Moreover,

Proposition 3.

Given the canonical ordering on On×On, every initial segment is a set.


Given ordinals α,βOn, suppose λ=max{α,β}. The initial segment of (α,β) is the union of the following collectionsMathworldPlanetmath

  1. 1.

    {(γ,δ)max{γ,δ}<λ}, which is a subcollection of λ×λ,

  2. 2.

    {(γ,δ)max{γ,δ}=λ, and γ<α}, which again is a subcollection λ×λ, and

  3. 3.

    {(α,δ)max{α,δ}=λ, and δ<β}, which is a subcollection of {α}×β.

Since λ×λ and {α}×β are both sets, so is the initial segment of (α,β). ∎

Remark. The canonical well-ordering on On×On can be used to prove a well-known property of alephs: αα=α, for any ordinal α.

Title canonical ordering on pairs of ordinals
Canonical name CanonicalOrderingOnPairsOfOrdinals
Date of creation 2013-03-22 18:50:02
Last modified on 2013-03-22 18:50:02
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 03E10
Classification msc 06A05
Synonym canonical well-ordering
Related topic IdempotencyOfInfiniteCardinals
Defines canonical ordering