{"id":563,"date":"2015-02-23T16:27:06","date_gmt":"2015-02-23T15:27:06","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=563"},"modified":"2022-11-19T15:31:02","modified_gmt":"2022-11-19T14:31:02","slug":"iwamuras-lemma-kowalskys-theorem-and-ordinals","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=563","title":{"rendered":"Iwamura’s Lemma, Markowsky’s Theorem and ordinals"},"content":{"rendered":"

On p.61 of the book<\/a>, there is a remark that the dcpos are exactly the chain-complete posets.\u00a0 This is a theorem by George Markowsky [1].\u00a0 It is time I explained seriously how this worked.\u00a0 The first step is Iwamura’s Lemma [2], which states that every directed subset decomposes as the union of a small chain of small directed subsets.<\/p>\n

The reason I did not put the proof of that result in the book<\/a> is because it rests on using ordinals, and I did not want to introduce ordinals, specially if they served for only one result.\u00a0 I’ll need them badly here, mostly to explain what “small” means in the informal statement of the lemma given above.<\/p>\n

Ordinals<\/strong><\/p>\n

Ordinals are a generalization of natural numbers “into the transfinite”.\u00a0 That is, ordinals contain 0, are closed under successors (adding 1), … and also under taking suprema of chains. And there is an induction principle that states that ordinals form the smallest collection that has these properties.<\/p>\n

Every natural number is an ordinal, but there are many more. For example, the set of natural numbers itself forms a chain, so their supremum is an ordinal. This ordinal is written \u03c9, and is the first infinite ordinal.\u00a0 Then you can form \u03c9+1, \u03c9+2, …, \u03c9+n<\/em> for every natural number n<\/em>.\u00a0 Their supremum is an even higher ordinal, written \u03c9+\u03c9, or \u03c9.2 (not 2.\u03c9! the latter would be the supremum of the family 0, 2, 4, …, 2n<\/em>, …, hence equal to \u03c9).\u00a0 Again, you can form \u03c9.2+1, \u03c9.2+2, …, \u03c9.2+\u03c9 = \u03c9.3.<\/p>\n

At each step, we build larger ordinals.\u00a0 And we can go even further.\u00a0 For example, the chain 0, \u03c9, \u03c9.2, \u03c9.3, …, \u03c9.n<\/em>, … again has a supremum, written \u03c9.\u03c9, or \u03c92<\/sup>.\u00a0 I’ll let you build \u03c93<\/sup>, \u03c94<\/sup>, …, \u03c9n<\/sup><\/em>, also their supremum \u03c9\u03c9<\/sup>, etc.\u00a0 We have barely scratched the surface.<\/p>\n

All that is good and dandy, but I really have not defined ordinals yet.\u00a0 For that, I need to say what a chain of ordinals is, and what their supremum is, so I need to define how they are ordered.\u00a0 Let us see how this can be defined formally.<\/p>\n

In set theory, 0 is an abbreviation for the empty set \u2205, and \u03b1+1 is an abbreviation for the funny \u03b1 \u222a {\u03b1}.\u00a0 So 1 is encoded as {\u2205}, 2 as {\u2205, {\u2205}}, 3 as {\u2205, {\u2205}, {\u2205, {\u2205}}}, and so on. The point of this weird convention is that every natural number n<\/em> is encoded as the set {0, 1, …,n-1} of its predecessors.\u00a0 We shall encode ordinals in a similar way, encoding every ordinal \u03b1 as the set of ordinals \u03b2 strictly less than \u03b1.<\/p>\n

Note that if we do so, then strict ordering < on ordinals is just set membership: \u03b2<\u03b1 if and only if \u03b2\u2208\u03b1.\u00a0 Also, the ordering \u2264 on ordinals will be set inclusion: \u03b2\u2264\u03b1 if and only if \u03b2\u2286\u03b1.<\/p>\n

Finally, note that, the way I explained ordinals, it should be clear that they are totally ordered.\u00a0 Given two ordinals \u03b1 and \u03b2, either \u03b1\u2264\u03b2, or \u03b2<\u03b1.\u00a0 Equivalently, there is trichotomy<\/em> between three exclusive cases: \u03b1\u2208\u03b2, \u03b1=\u03b2, or \u03b2\u2208\u03b1.<\/p>\n

This is one of the standard definitions of an ordinal:<\/p>\n

Definition<\/strong>. An ordinal is a transitive trichotomous set<\/em>, where:<\/p>\n