Iwamura’s Lemma, Markowsky’s Theorem and ordinals

On p.61 of the book, there is a remark that the dcpos are exactly the chain-complete posets.  This is a theorem by George Markowsky [1].  It is time I explained seriously how this worked.  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.

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

Ordinals

Ordinals are a generalization of natural numbers “into the transfinite”.  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.

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 ω, and is the first infinite ordinal.  Then you can form ω+1, ω+2, …, ω+n for every natural number n.  Their supremum is an even higher ordinal, written ω+ω, or ω.2 (not 2.ω! the latter would be the supremum of the family 0, 2, 4, …, 2n, …, hence equal to ω).  Again, you can form ω.2+1, ω.2+2, …, ω.2+ω = ω.3.

At each step, we build larger ordinals.  And we can go even further.  For example, the chain 0, ω, ω.2, ω.3, …, ω.n, … again has a supremum, written ω.ω, or ω².  I’ll let you build ω³, ω⁴, …, ωⁿ, also their supremum ω^ω, etc.  We have barely scratched the surface.

All that is good and dandy, but I really have not defined ordinals yet.  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.  Let us see how this can be defined formally.

In set theory, 0 is an abbreviation for the empty set ∅, and α+1 is an abbreviation for the funny α ∪ {α}.  So 1 is encoded as {∅}, 2 as {∅, {∅}}, 3 as {∅, {∅}, {∅, {∅}}}, and so on. The point of this weird convention is that every natural number n is encoded as the set {0, 1, …,n-1} of its predecessors.  We shall encode ordinals in a similar way, encoding every ordinal α as the set of ordinals β strictly less than α.

Note that if we do so, then strict ordering < on ordinals is just set membership: β<α if and only if β∈α.  Also, the ordering ≤ on ordinals will be set inclusion: β≤α if and only if β⊆α.

Finally, note that, the way I explained ordinals, it should be clear that they are totally ordered.  Given two ordinals α and β, either α≤β, or β<α.  Equivalently, there is trichotomy between three exclusive cases: α∈β, α=β, or β∈α.

This is one of the standard definitions of an ordinal:

Definition. An ordinal is a transitive trichotomous set, where:

• A set is transitive if and only if, for element α of this set, all the elements of α are in the set.
• A set is trichotomous if and only if, for any two elements α and β of this set, α∈β, α=β, or β∈α.

Sometimes you’ll find in the literature that it is required to be well-founded as well.  However we have assumed every set to be well-founded in the Von Neumann-Bernays-Gödel axiomatization given at the beginning of the book.

I’ll let you check that 0 is an ordinal in this sense, and that for every ordinal α, α+1 is again an ordinal.  We can now make sense of chains and suprema: a chain is one for the inclusion ordering, and suprema of chains are just unions.  I’ll let you check that any union of a chain of ordinals is an ordinal.

By the way, the ordinals that one cannot write down as 0 or of the form α+1 are called limit ordinals.  The only way we can construct a limit ordinal is as a supremum of strictly smaller ordinals.  For example, the first limit ordinal is ω.  The next ones are ω.2, ω.3, …, ω.n, etc.

There is much one can say about ordinals, and the Wikipedia page on ordinals is a good start.

The most important properties of ordinals are probably the following:

• Every ordinal is a well-founded chain (of ordinals), ordered by ≤ (inclusion)
• Every well-founded, totally ordered set is order-isomorphic to a unique ordinal.

The first property is because set membership is well-founded.  The second property is shown by well-founded induction on the given set.

The first property allows one to prove properties by (well-founded) induction on ordinals: to show that a property P holds of all ordinals, prove it on 0, show that it holds of α+1 as soon as it holds of α, and show that for every limit ordinal α, if P holds of all ordinals smaller than α, then P also holds of α.

Cardinals

Recall that a set I has cardinality smaller than or equal to that of a set J if and only if there is an injective map from I into J, or equivalently if and only if there is a surjective map from J onto I.

Zermelo’s Theorem asserts that every set I can be equipped with a well-founded, total ordering.  I’ll give a sketch of a proof shortly.

It follows that every set I can be put in bijection with some ordinal.  Since ordinals are well-founded, there is a smallest ordinal in bijection with I (for the usual ordering on ordinals).  This is called the cardinality of I.

Such smallest ordinals are called cardinals.  By definition, these are ordinals that are in bijection with none of their elements.  For example, 0, 1, 2, …, n, … are cardinals.  The first infinite ordinal ω is also a cardinal, because it is infinite, but all smaller ordinals are natural numbers n, hence are finite sets {0, 1, …, n-1}.  As a cardinal, ω is also written aleph 0.  The next infinite cardinal, aleph 1, is pretty mysterious.  As an ordinal, it is much higher than all the ordinals we have enumerated at the beginning (ω, ω.2, ω.3, ω², ω^ω, etc.)  It is smaller than or equal to the cardinality of the powerset of ω, simply because the latter is strictly larger than the cardinal of ω, by Cantor’s Theorem 2.2.1.  Whether it is equal to it or not is in fact unprovable from VBG set theory alone, as shown by Paul Cohen in the early 1960s.

In any case, what all this boils down to is:

• Every set I is in bijection with a smallest ordinal; this ordinal is called the cardinality |I| of I;
• I has smaller cardinality than J (in the sense that there is an injection from I into J, equivalently a surjection from J onto I) if and only if |I| < |J| (the smaller than relation for ordinals);
• In particular, the “smaller cardinality than” relation is well-founded (!).  We shall need this below.

Before we continue, let me state and prove Zermelo’s Theorem:

Theorem (Zermelo). Every set I can be equipped with a well-founded, total ordering.

Consider pairs (E, ≤) of a subset E of I and a well-founded, total ordering ≤ on E.  These pairs are ordered by extension: (E, ≤) is below (E‘, ≤’) if and only if E is a downward closed subset of E’ with respect to ≤’, and ≤ is the restriction of ≤’ to E.  Under extension, the set of those pairs is inductive.  Zorn’s Lemma gives us a maximal pair (E, ≤).  If E was not the whole of I, say there is a point i in I that is not in E, then we could find a larger pair (E ∪ {i}, ≤’) where ≤’ is defined so that i is the new top element.  So E=I.

A curious theorem

We have everything we need to prove Iwamura’s Lemma, but let’s not go too fast.  Achim Jung suggested that I presented the following, curious result first.  Its proof has the same canvas as for Iwamura’s Lemma, which we shall see next.

We let |D| denote the cardinality of D, represented as an ordinal.

Proposition.  Every infinite set can D be written as a union of a chain of subsets D_α of strictly smaller cardinality, indexed by ordinals α<|D|.

So we have a small set of subsets D_α, in the sense that there are at most |D| of them, and each of these sets is small, in the sense that they have strictly smaller cardinality than D.

The result is curious.  For example, if you were to write {0, 1, 2, 3, 4} as a union of a chain of subsets, then one of them would have to be the whole of {0, 1, 2, 3, 4}, whose cardinality is certainly not strictly smaller than that of the whole set.  The proposition holds because D is infinite.

For the proof, we index the elements of D as x_α, α<|D|.  This is the definition of |D|, which, as we have noted, exists by Zermelo’s Theorem.  We let D₀ = ∅, D_α+1 = D_α ∪ {x_α}, and, for every limit ordinal α, D_α = ∪_β<αD_β.  We check that for each of the involved ordinals α, |D_α| = α < |D|, and we are done.

Iwamura’s Lemma

In 1944, Iwamura proved the following [2].

Lemma (Iwamura). Let X be a poset, and D be an infinite directed subset of X.  Then one can write D as the union of a chain of directed subsets D_α, indexed by ordinals α<|D|, such that:

• |D_α| < |D|
• if α<β then D_α is included in D_β

In other words, every directed subset D can be decomposed as the union of a small chain of small directed subsets, where “small” means of cardinality strictly smaller than that of D.

• The proof rests on the following construction.  For every finite subset E of D, fix an upper bound Ê of E in D.  This exists because D is directed, and we can fix the map from E to Ê once and for all by using the Axiom of Choice.
  • Given an infinite directed subset D‘ of D, and a point x in D, we can form the smallest subset of D‘ that contains D’ and x, and such that for every finite subset E of D’, Ê is again in D’.  Call that subset D’+x.  Note that D’+x is directed.
    One can show that D’+x has exactly the same cardinality as D’.  Here is how. D’+x is the least fixed point of a Scott-continuous operator T on the collection of infinite subsets of D that contain D’ and x, defined by T(A) = A ∪ {Ê | E finite included in A}.  So D’+x is a countable union of sets of the form Tⁿ(∅), n∈ N.  Because A is infinite, one can show that T(A) has exactly the same cardinality as A.  Also, a countable union of sets of infinite cardinality c again has cardinality c.  We conclude that D’+x has exactly the same cardinality as D’.
  • If D’ is a finite directed subset of D, that construction would be too large for our purposes.  Instead, we define D’+x in this case as the union of E = D’ ∪ {x}, and {Ê}.  This is again directed, but now D’+x is guaranteed to be finite.
• We now construct D_α by induction on α<|D|.  By the definition of |D|, we can index the elements of D as x_α, α<|D|.  We let D₀ = {x₀}, D_α+1 =D_α + x_α, and, for every limit ordinal α, D_α = ∪_β<αD_β. Note that, by the considerations above, if α is a finite ordinal, then D_α is finite, hence |D_α| < |D| since D is infinite; while in the other cases, |D_α| ≤ α < |D|.

Markowsky’s Theorem

We can now show Markowsky’s Theorem [1].

Theorem (Markowsky).  Every chain-complete poset is a dcpo.

Let X be a chain-complete poset, and D be a directed subset of X.  We show by well-founded induction on |D| that D has a supremum.

• If D is finite, then in fact D has a maximal element since D is directed, and this must be its supremum.
• Otherwise, apply Iwamura’s Lemma.  Using the notations we have used there, let y_α be the supremum of D_α in X.  This exists, by induction hypothesis, since |D_α| < |D|.  If α<β then D_α is included in D_β, hence y_α≤y_β, so the elements y_α, α<|D|, form a (well-founded) chain. By assumption, this has a supremum in X, and it is easy to check that this is the desired supremum of D.

That’s it.  As a bonus, we have shown that every “well-founded-chain-complete” poset is also a dcpo, where a “well-founded-chain-complete” poset is a poset in which only the well-founded chains are required to have a supremum.

On Exercise 4.2.26

Exercise 4.2.26 asks you to show that the chain-open topology on a poset X is just the same as the Scott-open topology.  A subset U is chain-open if and only if it is upward-closed and for every chain C such that sup C is in U, some element of C is in U already.

The proof that I was trying to make you find was as follows.  Let F be the complement of U in X.  This is a chain-complete poset by assumption, hence a dcpo by Markowsky’s Theorem.  Since F is closed under directed sups, and downward-closed, its complement U is Scott-open.

As it stands, this proof has a flaw.  There is no reason that directed suprema, or suprema of chains would be computed in F as in X, and this has to be shown.  Formally, let D be a directed family of elements of F.  What we know is that D has a supremum y in F.  It may have another supremum in X, or none at all, for what we know.  Oops, it must have a supremum in X, because we have assumed that X was a dcpo.  Call it z.  Certainly, y is an upper bound of D, even inside X, so y≥z.  Since F is closed, it is downward-closed, so z is in F.  However, since z is an upper bound of D in X, hence also in F, z is above the supremum y of D taken in F.  We conclude that y and z are equal.  That was hard!

Knowing how Markowsky’s Theorem is proved, we can prove the result of the Exercise in a more transparent fashion.  Let D be any directed family whose supremum (in X) is in U.  We show by induction on |D| that D must meet U.  Using Iwamura’s Lemma, as in the proof of Markowsky’s Theorem, let y_α be the supremum of D_α in X.  By induction hypothesis, each y_α is in F.  They form a chain, whose supremum z taken in X is in F.  However, z is the supremum of D, taken in X.  It follows that F is Scott-closed, hence U is Scott-open.

— Jean Goubault-Larrecq(February 23rd, 2015)

1. George Markowsky.  Chain-complete posets and directed sets with applications.  Algebra Universalis 6, 1976, pages 53-68.

2. Tsurane Iwamura.  A lemma on directed sets.  Zenkoku Shijo Sugaku Danwakai 262, 1944, pages 107-111.  In Japanese.  (Let me thank Hideki Tsuiki for checking the name and the reference.  If there is still any mistake here, it will be my fault.)