{"id":1899,"date":"2019-07-20T09:27:08","date_gmt":"2019-07-20T07:27:08","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1899"},"modified":"2022-11-19T15:06:09","modified_gmt":"2022-11-19T14:06:09","slug":"bc-hulls-and-clat-hulls","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1899","title":{"rendered":"Bc-hulls and Clat-hulls"},"content":{"rendered":"\n

Bounded-complete domains (bc-domains) are an incredibly useful form of continuous dcpos. I have just again mentioned them in a recent talk at LICS 2019<\/a>, and Prakash Panangaden<\/a> aptly, and wittily, described them as “bloody convenient domains”. In 1997, Yuri Ershov showed that every C-space can be embedded into a (weakly) universal bc-domain, which he called its bc-hull<\/em> [1]. The construction is rather elaborate, but I claim that it can be made considerably simpler if we consider coherent continuous dcpos instead of general C-spaces. I will also briefly show why the case of algebraic, not necessarily coherent, dcpos, is simple as well, and I will say a word on the general continuous case, without delving into details.<\/p>\n\n\n\n

Bc-hulls and Clat-hulls<\/h2>\n\n\n\n

Let me recall that a bc-domain (see Section 5.7 in the book<\/a>) is a pointed, continuous dcpo in which every pair of elements with an upper bound has a least upper bound; or equivalently, a continuous dcpo in which every family of elements with an upper bound has a least upper bound; or equivalently, a non-empty continuous dcpo in which every non-empty family has a greatest lower bound. Every bc-domain is stably compact in its Scott topology. And the category of bc-domains is Cartesian-closed. And the bc-domains are exactly the densely injective topological spaces. That is all very nice.<\/p>\n\n\n\n

I will also mention their close cousins: continuous complete lattices. (Allow me to call them continuous lattices, for short.) Every continuous lattice is a bc-domain, and conversely, every bc-domain with a top element is a continuous lattice. Continuous lattices also form a Cartesian-closed category, and they are exactly the injective topological spaces.<\/p>\n\n\n\n

Not all continuous dcpos are bc-domains. For example, build a dcpo whose elements are the negative integers \u2013n<\/em> with their usual ordering (so that 0 is above \u20131, which is above \u20132, etc.), all above two incomparable elements a<\/em> and b<\/em>, and the latter two being above a bottom element \u22a5:<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

This is a continuous (even algebraic) dcpo, a<\/em> and b<\/em> have an upper bound, but no least upper bound.<\/p>\n\n\n\n

A natural question is then: given a continuous dcpo X<\/em>, can we embed X<\/em> into a bc-domain bc(X<\/em>)? (respect., a continuous lattice clat(X<\/em>)?) This is of course true, and in fact one can embed any T0<\/sub> topological space X<\/em> into a continuous lattice: just take the powerset of O<\/strong>X<\/em> with the inclusion ordering, and take the map that sends every point x<\/em> of X<\/em> to its set of open neighborhoods. (That construction is originally due to Dana S. Scott.)<\/p>\n\n\n\n

But can we ask for more? For example, is there a free<\/em> bc-domain (resp., continuous lattice) on any given continuous dcpo?<\/p>\n\n\n\n

That is too much to ask, as we will see below. In 1997, Yuri Ershov [1] came up with the following funny, intermediate notion: a bc-hull<\/em> of a continuous dcpo X<\/em> is a bc-domain bc(X<\/em>) with an embedding \u03b7 : X<\/em> \u2192 bc(X<\/em>) such that:<\/p>\n\n\n\n

    \n
  1. for every continuous map f<\/em> : X<\/em> \u2192 Y<\/em> where Y<\/em> is a bc-domain, one can find an extension f<\/em>* : bc(X<\/em>) \u2192 Y<\/em>, where by extension I mean that f<\/em>* o \u03b7 = f<\/em> \u2014 but note that we do not require the extension to be unique;<\/li>\n\n\n\n
  2. the following weak universality<\/em> property holds: the only continuous map g<\/em> : bc(X<\/em>) \u2192 bc(X<\/em>) such that g<\/em> o \u03b7 = \u03b7 is the identity map.<\/li>\n<\/ol>\n\n\n\n

    For example, the bc-hull of the algebraic dcpo we have above as an example of one that is not a bc-domain is the following dcpo, where we have just added a fresh least upper bound to a<\/em> and b<\/em>. (This can be checked by using the forthcoming construction.)<\/p>\n\n\n

    \n
    \"\"<\/figure>\n<\/div>\n\n\n

    We will see later that bc(X<\/em>) cannot be a free bc-domain on X<\/em>, for general X<\/em>, precisely because extensions f<\/em>* cannot be required to be unique. However, we can salvage a few things. For one, weak universality implies that \u03b7* is the identity map on bc(X<\/em>). It also implies that the bc-hull of a continuous dcpo is unique up to isomorphism (if it exists)\u2014a property that we are accustomed to see satisfied with free objects, but freeness is not required for that.<\/p>\n\n\n\n

    Indeed, imagine we had two bc-hulls bc(X<\/em>) and bc'(X<\/em>) of X<\/em>, with respective embeddings \u03b7 and \u03b7’. The map \u03b7’ extends to a map \u03b7’* : bc(X<\/em>) \u2192 bc'(X<\/em>), i.e., \u03b7’* o \u03b7 = \u03b7’, and symmetrically \u03b7 extends to \u03b7\u2020 : bc'(X<\/em>) \u2192 bc(X) (I am using \u2020 instead of * to avoid any confusion), meaning that \u03b7\u2020 o \u03b7’ = \u03b7. This implies that \u03b7’* o \u03b7\u2020 o \u03b7’ = \u03b7’ and \u03b7\u2020 o \u03b7’* o \u03b7 = \u03b7, so by weak universality \u03b7’* o \u03b7\u2020 and \u03b7\u2020 o \u03b7’* are identity maps, showing that \u03b7\u2020 and \u03b7’* form an isomorphism.<\/p>\n\n\n\n

    Ershov has shown [1] that the bc-hull of a continuous dcpo, and more generally of a C-space, always exists. I’ll say a word on his proof later, but the final construction is complicated. My goal is to show that bc(X<\/em>) can be constructed in a fairly simple manner, provided X<\/em> is a coherent<\/em> continuous dcpo.<\/p>\n\n\n\n

    I will also show that the continuous lattice hull clat(X<\/em>) of X<\/em> always exists, too, where clat(X<\/em>) is defined exactly as bc(X<\/em>), replacing “bc-domain” by “continuous lattice” everywhere. Of course, if a continuous lattice hull exists, it is unique by weak universality again.<\/p>\n\n\n\n

    Building bc(X<\/em>) and clat(X<\/em>)<\/h2>\n\n\n\n

    Let us fix a coherent, continuous dcpo X<\/em>. By coherent, I mean that the intersection of two compact saturated sets is compact saturated.<\/p>\n\n\n\n

    Note that since X<\/em> is a continuous dcpo, it is sober, hence well-filtered. Since the intersection of a non-empty family of compact saturated subsets of X<\/em> can be written as a filtered intersection of non-empty finite intersections, and since the latter are compact saturated by coherence, every non-empty intersection of compact saturated sets is compact saturated. Indeed, recall that in a well-filtered space, every filtered intersection of compact saturated sets is compact saturated (Proposition 8.3.6 of the book<\/a>).<\/p>\n\n\n\n

    We define clat(X<\/em>) as the set of all intersections of principal filters \u2191x<\/em>, where x<\/em> ranges over arbitrary subsets E<\/em> of X<\/em>. The idea is that we want to add the least upper bounds of every subset E<\/em> to X<\/em>. If the least upper bound of E<\/em> already exists, then it is a point y<\/em> such that \u2191y<\/em> is equal to the intersection of all \u2191x<\/em>, x<\/em> in E<\/em>. Otherwise, that intersection will serve to represent the supremum of E<\/em> that we must add to X<\/em>.<\/p>\n\n\n\n

    Every principal filter is compact saturated, and every non-empty intersection of compact saturated subsets is again compact saturated, so all the elements of clat(X<\/em>) are compact saturated, except possibly for the intersection of the empty family, namely X<\/em> itself.<\/p>\n\n\n\n

    We order clat(X<\/em>) by reverse inclusion. Every intersection of a family of elements of clat(X<\/em>) is obviously in clat(X<\/em>), and coincides with the supremum of the family. It follows that clat(X<\/em>) is a complete lattice.<\/p>\n\n\n\n

    We also define bc(X<\/em>) as the subset of clat(X<\/em>) obtained by removing the empty set. Every family that is bounded from above in bc(X<\/em>), say by Q<\/em>, consists of elements of bc(X<\/em>) which all contain Q<\/em>, hence their intersection also contains Q<\/em>, and is in particular non-empty. Therefore, in bc(X<\/em>), every upper bounded family has a least upper bound: bc(X<\/em>) is bounded-complete.<\/p>\n\n\n\n

    bc(X<\/em>) and clat(X<\/em>) are dcpos<\/h2>\n\n\n\n

    It is also true that bc(X<\/em>) is a dcpo, with directed suprema computed as filtered intersections. (clat(X<\/em>) is vacuously a dcpo, since it is a complete lattice.) For that, we use the following observation:<\/p>\n\n\n\n

    (*) For every filtered family (Qi<\/sub><\/em>)i <\/em>\u2208 I<\/em><\/sub> in clat(X<\/em>) (resp., in bc(X<\/em>)), for every open subset U<\/em> of X<\/em> that contains the intersection \u2229i<\/em><\/sub> \u2208 I<\/em><\/sub> Qi<\/sub><\/em>, some Qi<\/sub><\/em> is included in U<\/em>.<\/p>\n\n\n\n

    We have already seen that this holds if every Qi<\/sub><\/em> is compact saturated. (Recall that every Qi<\/sub><\/em> is compact saturated or equal to the whole of X<\/em>.) If some Qi<\/sub><\/em> is different from X<\/em>, then removing X<\/em> from the family (Qi<\/sub><\/em>)i <\/em>\u2208 I<\/em><\/sub> still yields a directed family, with the same intersection, and this allows us to conclude. Otherwise, every Qi<\/sub><\/em> is equal to X<\/em>, so U<\/em>=X<\/em>, and the claim is clear.<\/p>\n\n\n\n

    Using (*) with the empty set for U<\/em>, we observe that the intersection of a filtered family of non-empty compact saturated sets must be non-empty, so that filtered intersections of elements of bc(X<\/em>) are again in bc(X<\/em>). It follows that those filtered intersections are exactly the required directed suprema.<\/p>\n\n\n\n

    bc(X<\/em>) and clat(X<\/em>) are continuous<\/h2>\n\n\n\n

    In order to show that bc(X<\/em>) is a bc-domain and that clat(X<\/em>) is a continuous lattice, it remains to show that clat(X<\/em>) and bc(X<\/em>) are continuous.<\/p>\n\n\n\n

    Let me use the following abbreviation: for every subset E<\/em> of X<\/em>, let E<\/em>\u2191<\/sup> denote the set of all upper bounds of E<\/em>. Equivalent, E<\/em>\u2191<\/sup> is the intersection of the sets \u2191x<\/em>, x<\/em> \u2208 E<\/em>, and is therefore an element of clat(X<\/em>) (and of bc(X<\/em>) if non-empty).<\/p>\n\n\n\n

    I will need the following auxiliary lemma:<\/p>\n\n\n\n

    (**) For every E<\/em>\u2191<\/sup> in clat(X<\/em>), for every open subset U<\/em><\/span> of X<\/em>, if E<\/em>\u2191<\/sup> \u2286 U<\/em> then there are finitely many pairs of elements y<\/em>1<\/sub>\u226ax<\/em>1<\/sub>, …, yn<\/sub>\u226axn<\/sub><\/em> such that x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub> are in E<\/em>, and {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> is included in U<\/em>.<\/p>\n\n\n\n

    This is proved as follows. First, we apply (*) to the family of subsets {x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub>}\u2191<\/sup> with x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub> in E<\/em> (the intersection of that family is E<\/em>\u2191<\/sup>, which is included in U<\/em>). Therefore {x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub>}\u2191<\/sup> is included in U<\/em> for some finite family of elements x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub> of E<\/em>. Since X<\/em> is a continuous dcpo, we can write each xi<\/sub><\/em> as a directed supremum sup \u21a1xi<\/sub><\/em>. Then \u2191xi<\/sub><\/em>=\u2229 {\u2191y<\/em> | y<\/em>\u226axi<\/sub><\/em>}, and hence {x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub>}\u2191<\/sup> = \u2229i<\/em>=1<\/sub>n<\/em><\/sup> \u2191x<\/em>i<\/em><\/sub> = \u2229 {{y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> | y<\/em>1<\/sub>\u226ax<\/em>1<\/sub>, …, yn<\/sub>\u226axn<\/sub><\/em>}. The latter intersection is again directed (note that n<\/em> is fixed), as one easily checks. By (*) again, it follows that {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> is included in U<\/em> for some y<\/em>1<\/sub>\u226ax<\/em>1<\/sub>, …, yn<\/sub>\u226axn<\/sub><\/em>.<\/p>\n\n\n\n

    Now that we have proved (**), we also observe the following:<\/p>\n\n\n\n

    (***) Every set E<\/em>\u2191<\/sup> in clat(X<\/em>) is the filtered intersection of the sets {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup>, where y<\/em>1<\/sub>\u226ax<\/em>1<\/sub>, …, yn<\/sub>\u226axn<\/sub><\/em> and x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub> are in E<\/em>.<\/p>\n\n\n\n

    For a proof, first, I will let you check that the family of those sets {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup>, is indeed filtered. We then prove the double inclusion between E<\/em>\u2191<\/sup> and the filtered intersection given in (***). In one direction, E<\/em>\u2191<\/sup> is certainly included in any set {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> as given in (***), because every element of E<\/em>\u2191<\/sup> is above every element of E<\/em>, hence above every x<\/em>i<\/em><\/sub>, hence above every y<\/em>i<\/em><\/sub>. In the converse direction, for every open neighborhood U<\/em> of E<\/em>\u2191<\/sup>, we use (*) and obtain finitely many pairs of elements y<\/em>1<\/sub>\u226ax<\/em>1<\/sub>, …, yn<\/sub>\u226axn<\/sub><\/em> such that x<\/em>1<\/sub>, …, x<\/em>n<\/em><\/sub> are in E<\/em>, and such that {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> is included in U<\/em>. This shows that U<\/em> also contains the intersection of the sets {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> as given in (***). Since E<\/em>\u2191<\/sup> is saturated, it is the intersection of its open neighborhoods U<\/em>, and therefore E<\/em>\u2191<\/sup> itself contains the intersection of the sets {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> as given in (***).<\/p>\n\n\n\n

    With (*), (**), and (***), we can now show that, in clat(X<\/em>) or in bc(X<\/em><\/span>), Q<\/em> \u226a Q’<\/em> if and only if one can find finitely many pairs of elements y<\/em>1<\/sub>\u226ax<\/em>1<\/sub>, …, yn<\/sub>\u226axn<\/sub><\/em> such that Q<\/em> contains {y<\/em>1<\/sub>,<\/em> …, yn<\/sub><\/em>}\u2191<\/sup> and {x<\/em>1<\/sub>, …, xn<\/sub><\/em>}\u2191<\/sup> contains Q’<\/em>.<\/p>\n\n\n\n