Markowsky or Cohn?

I have already mentioned Markowsky’s Theorem [1]: every chain-complete poset is a dcpo.  This is a non-trivial theorem, and I’ve given you a proof of it based on Iwamura’s Lemma and ordinals in a previous post.

Maurice Pouzet recently pointed me to P. M. Cohn’s book Universal algebra [2], and you can find it already on page 33!  Let me quote:

Proposition 5.9.  Let A be an ordered set; then the following three conditions on A are equivalent:

(i) Every nonempty directed subset of A has a supremum.

(ii) Every nonempty chain of A has a supremum.

(iii) Every nonempty well-ordered chain of A has a supremum.

Hence his proof predated Markowsky’s proof by a good decade.  One might say, of course, that Iwamura’s paper was even older, but Iwamura never proved the above.  (And saying that it easily follows from Iwamura’s Lemma won’t change it!)

Cohn’s proof

Cohn’s proof uses ordinals, just like Markowsky’s proof, but the proof is very different.

We start with a poset X, with the property that every non-empty well-founded chain of elements of X has a supremum.  We fix a directed subset D of X, and our goal is to show that D has a supremum.  In other words, we look at a proof of (iii) ⇒ (i).  I hope you will agree that the implications (i) ⇒ (ii) ⇒ (iii) are trivial.

Instead of decomposing infinite directed families as smaller chains of smaller directed families, Cohn expands D into a larger one E that has the same upper bounds, and with an extra property:

(*) the supremum of every well-founded chain of elements of E lies in E.

In other words, the following key lemma holds.

Lemma. There is a directed family E containing D, with the same upper bounds as D, and satisfying (*).

Proof. We build E as follows.  Let A be the set of upper bounds of D.  Let F be the family of all directed sets containing D and whose set of upper bounds is A.  Order F by inclusion.  One can easily check that the union of any chain of elements of F is again in F.  By Zorn’s Lemma F must have a maximal element, and that is our E.

We have not yet checked that E satisfies (*), and that is the only thing we need to check.  Let us reason by contradiction.  Assume there is a non-empty well-founded chain C of elements of E whose supremum sup C (which always exists in X) is not in E. That chain is isomorphic to a unique non-zero ordinal λ, called the length of C.  Explicitly, we may write the elements of C as some chain (cμ)μ<λ (this notation for chains will be taken to imply that cμ is monotone in μ, too).

Since ordinals are themselves well-founded, we can assume that C has minimal length λ, among all those non-empty well-founded chains C included in E such that sup C is not in E.  In particular, for every chain (xμ)μ<β of elements of E, for any ordinal β<λ, supμ<β xμ is in E.

Now let E’ be the family of elements x of X that can be written as supμ<λ xμ for some chain (xμ)μ<λ of elements of E.  In other words, E’ is the family of elements of chains inside E that may be just a bit too long to have a supremum in E.  [Here I must thank Oscar North, an MMath student from Oxford, for having found a mistake in a previous version of this post (February 27th, 2018).]

Given two chains (xμ)μ<λ and (yμ)μ<λ of elements of E, with respective suprema x and y (in E’, as we have just seen), we can build a new chain (zμ)μ<λ of elements of E such that xμ, yμ < zμ for every μ<λ.  This is done by ordinal induction.  When μ=0, we just use the fact that E is directed and pick any element z0 of E above both x0 and y0.  For a successor ordinal μ+1, we pick zμ+1 in E above xμ+1, yμ+1 and zμ, again using the fact that E is directed.  For a limit ordinal β, we observe that supμ<β zμ is in E by assumption, and must be above every zμ with μ<β.  We now pick zβ in E above xβ, yβ and supμ<β zμ, using directedness for the final time.

By assumption on λ, the element z defined as supμ<λ zμ is in E’.

Hence we have obtained the following: E’ is directed.  (We have not checked that it is not empty, but that follows from the following statement.)

Also, E’ contains E, since every element x of E can be written as such a supremum of a chain, where xμ=x for every μ<λ (a constant chain).

Since E’ contains E, every upper bound of E‘ is an upper bound of E.  Conversely, for every upper bound a of E, a≥supμ<λ xμ for every chain (xμ)μ<λ of elements of E, so that a is also an upper bound of E’.

It follows that E’ is in F and, being larger than E, must be equal to it.  Look back at our chain C = (cμ)μ<λ.  By definition, its supremum c is in E’.  Hence c is in E.  That is impossible since we had taken C so that sup C is not in E.  ☐

We can now prove the hard implication (iii) ⇒ (i).

Theorem [1, 2].  If X has suprema of all non-empty well-founded chains, then X is a dcpo.

Proof. Let D be any directed family, and E be as in the previous lemma.  The family G of non-empty well-ordered chains included in E can be ordered by extension, namely (xμ)μ<β≺(yμ)μ<λ if and only if β≤λ and xμ=yμ for every μ<β.  (In other words, one obtains (yμ)μ<λ by adding extra element above those we already had in (xμ)μ<β.  We are forbidden to add some inbetween or below.)

Since the union of a non-empty chain of elements of G (themselves non-empty well-ordered chains) is again an element of G, and is easily seen to be an upper bound of that chain with respect to the extension ordering, we can apply Zorn’s Lemma: there is a maximally extended non-empty well-ordered chain (xμ)μ<λ included in E.

Let x be the supremum of that chain.  We claim that x=sup E, in fact that x is the largest element of E.

By (*), x is in E.  For every element y of E, by directedness there is an element z in E above both x and y.  Then adding z to (xμ)μ<λ would produce a strict extension of (xμ)μ<λ, which is impossible by maximality, unless z is already some xμ.  But xμxz=xμ now implies x=z=xμ, and therefore yz=x.  This shows that x is above every element y of E.

Since x is the largest element of E, it is an upper bound of D, hence belongs to the set A of upper bounds of DA is also the set of upper bounds of E.  Hence, for every a in A, a is above every element of E, in particular x.  This means that x is the least element of A.  Put differently: x is the least of the upper bounds of D.  That means that x is the supremum of D we were looking for all along.  ☐

Next time

The funny thing is that Maurice Pouzet pointed that proof to me, and at the same moment I was traveling to Birmingham to be an external examiner of Xiaodong Jia’s PhD thesis, and Xiaodong’s work has a lot to do with the above!

I have already mentioned some of Xiaodong’s results in the past, notably on coherence of dcpos.

One of the wonderful things he shows in his PhD thesis is that every Cartesian-closed categories of quasi-continuous domains must consist of continuous domains already.  That is a very non-trivial result, and one which definitely ruins any hope that my discovery of QRB-domains (in 2010) may have spurred.

I won’t tell the story for now, but one of the techniques Xiaodong uses goes through notions of core-compactness and meet-continuity, and in particular through characterizations of dcpos X whose function space is core-compact, resp. meet-continuous, by the fact that certain bad dcpos do not occur as retracts of X.

Without the Markowsky/Cohn result, those bad dcpos would be very complicated to describe: essentially, arbitrary directed families flipped upside-down, with some points on the side or at the bottom.

With the Markowsky/Cohn result, we know that the only bad dcpos we have to consider are inverted well-founded chains, with possibly one point on the side, or 2 or 3 points in a certain configuration at the bottom.

I am not promising anything, but I might talk about that next time.

  1. George Markowsky. Chain-complete posets and directed sets with applications. Algebra Universalis 6, 1976, pages 53-68.
  2. Paul Moritz Cohn.  Universal Algebra.  Harper and Row, 1965.

Jean Goubault-Larrecqjgl-2011

Leave a Reply