{"id":799,"date":"2018-01-26T17:49:28","date_gmt":"2018-01-26T16:49:28","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=799"},"modified":"2022-05-17T09:46:41","modified_gmt":"2022-05-17T07:46:41","slug":"markowsky-or-cohn","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=799","title":{"rendered":"Markowsky or Cohn?"},"content":{"rendered":"

I have already mentioned Markowsky’s Theorem [1]: every chain-complete poset is a dcpo. \u00a0This 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<\/a>.<\/p>\n

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

Proposition 5.9.<\/strong>\u00a0 Let A be an ordered set; then the following three conditions on A are equivalent:<\/p>\n

(i) Every nonempty directed subset of A has a supremum.<\/p>\n

(ii) Every nonempty chain of A has a supremum.<\/p>\n

(iii) Every nonempty well-ordered chain of A has a supremum.<\/p><\/blockquote>\n

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

Cohn’s proof<\/h2>\n

Cohn’s proof uses ordinals, just like Markowsky’s proof<\/a>, but the proof is very different.<\/p>\n

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

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

(*) the supremum of every well-founded chain of elements of E<\/em> lies in E<\/em>.<\/p><\/blockquote>\n

In other words, the following key lemma holds.<\/p>\n

Lemma.<\/strong> There is a directed family E<\/em> containing D<\/em>, with the same upper bounds as D<\/em>, and satisfying (*).<\/p>\n

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

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

Since ordinals are themselves well-founded, we can assume that C<\/em> has minimal length\u00a0\u03bb, among all those non-empty well-founded chains C<\/em> included in E<\/em> such that sup C<\/em> is not in E<\/em>.\u00a0 In particular, for every chain (x<\/em>\u03bc<\/sub>)\u03bc<\u03b2<\/sub> of elements of E<\/em>, for any ordinal \u03b2<\u03bb, sup\u03bc<\u03b2<\/sub> x<\/em>\u03bc<\/sub> is in E<\/em>.<\/p>\n

Now let\u00a0E’<\/em> be the family of elements x<\/em> of X<\/em> that can be written as sup\u03bc<\u03bb<\/sub> x<\/em>\u03bc<\/sub> for some chain (x<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> of elements of E<\/em>. \u00a0In other words,\u00a0E’<\/em> is the family of elements of chains inside\u00a0E<\/em> that may be just a bit too long to have a supremum in\u00a0E<\/em>. \u00a0[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).]<\/p>\n

Given two chains (x<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> and\u00a0(y<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> of elements of E<\/em>, with respective suprema x<\/em> and y<\/em> (in E’<\/em>, as we have just seen), we can build a new chain (z<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> of elements of E<\/em> such that x<\/em>\u03bc<\/sub>, y<\/em>\u03bc <\/sub>< z<\/em>\u03bc<\/sub> for every \u03bc<\u03bb.\u00a0 This is done by ordinal induction.\u00a0 When \u03bc=0, we just use the fact that E<\/em> is directed and pick any element\u00a0z<\/em>0<\/sub> of E<\/em> above both x<\/em>0<\/sub> and y<\/em>0<\/sub>.\u00a0 For a successor ordinal \u03bc+1, we pick z<\/em>\u03bc+1<\/sub> in E<\/em> above\u00a0x<\/em>\u03bc+1<\/sub>, y<\/em>\u03bc+1 <\/sub> and z<\/em>\u03bc<\/sub>, again using the fact that E<\/em> is directed.\u00a0 For a limit ordinal \u03b2, we observe that sup\u03bc<\u03b2<\/sub> z<\/em>\u03bc<\/sub> is in E<\/em> by assumption, and must be above every\u00a0z<\/em>\u03bc<\/sub> with \u03bc<\u03b2.\u00a0 We now pick z<\/em>\u03b2<\/sub> in E<\/em> above x<\/em>\u03b2<\/sub>, y<\/em>\u03b2 <\/sub> and sup\u03bc<\u03b2<\/sub> z<\/em>\u03bc<\/sub>, using directedness for the final time.<\/p>\n

By assumption on \u03bb, the element z<\/em> defined as sup\u03bc<\u03bb<\/sub> z<\/em>\u03bc<\/sub> is in E’<\/em>.<\/p>\n

Hence we have obtained the following:\u00a0E’<\/em> is directed.\u00a0 (We have not checked that it is not empty, but that follows from the following statement.)<\/p>\n

Also, E’<\/em> contains E<\/em>, since every element x<\/em> of E<\/em> can be written as such a supremum of a chain, where x<\/em>\u03bc<\/sub>=x<\/em> for every \u03bc<\u03bb (a constant chain).<\/p>\n

Since E’<\/em> contains E<\/em>, every upper bound of E<\/em>‘ is an upper bound of E<\/em>.\u00a0 Conversely, for every upper bound a<\/em> of E<\/em>, a<\/em>\u2265sup\u03bc<\u03bb<\/sub> x<\/em>\u03bc<\/sub> for every chain (x<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> of elements of E<\/em>, so that a<\/em> is also an upper bound of E’<\/em>.<\/p>\n

It follows that E’<\/em> is in F<\/strong><\/em> and, being larger than E<\/em>, must be equal to it.\u00a0 Look back at our chain C<\/em> = (c<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub>.\u00a0 By definition, its supremum c<\/em> is in E’<\/em>.\u00a0 Hence c<\/em> is in E<\/em>.\u00a0 That is impossible since we had taken C<\/em> so that sup C<\/em> is not in E<\/em>.\u00a0 \u2610<\/p>\n

We can now prove the hard implication (iii) \u21d2 (i).<\/p>\n

Theorem [1, 2].<\/strong>\u00a0 If X<\/em> has suprema of all non-empty well-founded chains, then X<\/em> is a dcpo.<\/p>\n

Proof.<\/em> Let D<\/em> be any directed family, and E<\/em> be as in the previous lemma.\u00a0 The family G<\/strong><\/em> of non-empty well-ordered chains included in E<\/em> can be ordered by extension, namely (x<\/em>\u03bc<\/sub>)\u03bc<\u03b2<\/sub>\u227a(y<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> if and only if \u03b2\u2264\u03bb and x<\/em>\u03bc<\/sub>=y<\/em>\u03bc<\/sub> for every \u03bc<\u03b2.\u00a0 (In other words, one obtains (y<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> by adding extra element above those we already had in (x<\/em>\u03bc<\/sub>)\u03bc<\u03b2<\/sub>.\u00a0 We are forbidden to add some inbetween or below.)<\/p>\n

Since the union of a non-empty chain of elements of G<\/strong><\/em> (themselves non-empty well-ordered chains) is again an element of G<\/em><\/strong>, 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<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub> included in E<\/em>.<\/p>\n

Let x<\/em> be the supremum of that chain.\u00a0 We claim that x<\/em>=sup E<\/em>, in fact that x<\/em> is the largest element of E<\/em>.<\/p>\n

By (*), x<\/em> is in E<\/em>.\u00a0 For every element y<\/em> of E<\/em>, by directedness there is an element z<\/em> in E<\/em> above both x<\/em> and y<\/em>.\u00a0 Then adding z<\/em> to (x<\/em>\u03bc<\/sub>)\u03bc<\u03bb <\/sub>would produce a strict extension of (x<\/em>\u03bc<\/sub>)\u03bc<\u03bb<\/sub>, which is impossible by maximality, unless z<\/em> is already some x<\/em>\u03bc<\/sub>.\u00a0 But x<\/em>\u03bc<\/sub>\u2264x<\/em>\u2264z<\/em>=x<\/em>\u03bc<\/sub> now implies x<\/em>=z<\/em>=x<\/em>\u03bc<\/sub>, and therefore y<\/em>\u2264z<\/em>=x<\/em>.\u00a0 This shows that x<\/em> is above every element y<\/em> of E<\/em>.<\/p>\n

Since x<\/em> is the largest element of E<\/em>, it is an upper bound of D<\/em>, hence belongs to the set A<\/em> of upper bounds of D<\/em>.\u00a0 A<\/em> is also the set of upper bounds of E<\/em>.\u00a0 Hence, for every a<\/em> in A<\/em>, a<\/em> is above every element of E<\/em>, in particular x<\/em>.\u00a0 This means that x<\/em> is the least element of A<\/em>.\u00a0 Put differently: x<\/em> is the least of the upper bounds of D<\/em>.\u00a0 That means that x<\/em> is the supremum of D<\/em> we were looking for all along.\u00a0 \u2610<\/p>\n

Next time<\/h2>\n

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!<\/p>\n

I have already mentioned some of Xiaodong’s results in the past, notably on coherence of dcpos<\/a>.<\/p>\n

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.\u00a0 That is a very non-trivial result, and one which definitely ruins any hope that my discovery of QRB<\/strong>-domains (in 2010) may have spurred.<\/p>\n

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<\/em> whose function space is core-compact, resp. meet-continuous, by the fact that certain bad dcpos do not occur as retracts of X<\/em>.<\/p>\n

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.<\/p>\n

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.<\/p>\n

I am not promising anything, but I might talk about that next time.<\/p>\n

    \n
  1. George Markowsky. Chain-complete posets and directed sets with applications<\/a>. Algebra Universalis<\/em> 6, 1976, pages 53-68.<\/li>\n
  2. Paul Moritz Cohn.\u00a0 Universal Algebra.\u00a0 Harper and Row, 1965.<\/li>\n<\/ol>\n

    \u2014 Jean Goubault-Larrecq<\/a>\u00a0(January 26th, 2018)\"jgl-2011\"<\/p>\n","protected":false},"excerpt":{"rendered":"

    I have already mentioned Markowsky’s Theorem [1]: every chain-complete poset is a dcpo. \u00a0This 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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_crdt_document":"","footnotes":""},"class_list":["post-799","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/799","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=799"}],"version-history":[{"count":16,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/799\/revisions"}],"predecessor-version":[{"id":5364,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/799\/revisions\/5364"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=799"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}