Quasi-continuous domains and the Smyth powerdomain

This is the title of a paper by R. Heckmann and K. Keimel [1], which contains a few pearls, which I would like to mention here. They are:

  1. the supercompact saturated sets are exactly the upward closures of single points—don’t panic, I will say what “supercompact” means, in due time;
  2. the topological Rudin Lemma, a topological analogue and an extension of Rudin’s Lemma (the latter is Proposition 5.2.25 in the book);
  3. a characterization of (quasi-)sober spaces in terms of irreducible families of compact saturated subsets, resembling the definition of well-filteredness.

I will also correct a slight inaccuracy in the original statement of the latter claim.

Supercompact sets

The first pearl has to do with so-called supercompact sets. That sounds like a fancy name, but we will see that those are pretty mundane sets.

Let X be a topological space, and Q be a subset of X. Q is compact if and only if every open cover (Ui)iI of Q has a finite subcover. Q is supercompact if and only if one can require this finite subcover to consist of just one open set: in other words, if and only if for every open cover (Ui)iI of Q, there is an index i in I such that Ui contains Q.

Note that, for every point x of X, {x} is supercompact. The set ↑x is also supercompact, and is saturated (upwards-closed in the specialization preordering ≤). If x and y are two points that are incomparable under ≤, then {x, y} is compact but not supercompact, and similarly for ↑{x, y}. Indeed, since x and y are incomparable, there is an open neighborhood U of x that does not contain y, and there is an open neighborhood V of y that does not contain x, and then {U, V} is an open cover of {x, y} (also, of ↑{x, y}), but neither U nor V covers it entirely.

The following is Fact 2.2 in [1]. Note that it requires no assumption at all on X, not even that it be T0.

Theorem (supercompact subsets). Let X be a topological space. The supercompact saturated subsets of X are exactly the sets of the form ↑x with x in X.

Proof. Let Q be a supercompact saturated subset of X. For every point y of Q, the set UyX–↓y is open, and does not contain Q, since it fails to contain y. It follows that the family (Uy)yQ cannot be an open cover of Q: otherwise, by supercompactness, some Uy would already contain Q. Let U be the union of the sets Uy when y ranges over the points of Q. We have just seen that U cannot contain Q, so let us pick a point x in Q that is not in U.

Since x is not in U, it must be outside Uy for every y in Q. In other words, xy for every y in Q. This shows that Q is included in ↑x. In the reverse direction, we use that fact that x is in Q, and that Q is saturated, so ↑x is included in Q. ☐

This is a very useful little fact. We will use it at the very end of this post, but it is not its only usage! With Matthew de Brecht, Xiaodong Jia, and Zhenchao Lyu, we have used it to show that every countably-based, compactly Choquet-complete space is convergence Choquet- complete [2, Proposition 9.4]. I will not spend too much time on that, but let me still say a few words. A compactly Choquet-complete space is a space X in which player α has a winning strategy in the strong Choquet game, such that the open sets (s)he plays form a base of neighborhoods of some compact saturated set Q. It is convergence Choquet-complete (a notion due to F. Dorais and K. Mummert, see Exercise 7.6.5 in the book) if one can require Q to be the upward closure of a point. Now imagine that X has a countable base, and that the open sets Un played by α during the strong Choquet game form a base of neighborhoods of a compact saturated set Q. One can then show that if Q is contained in the union of two open sets U and V, then Q must be contained in U, or in V. (I will omit the argument, since it involves going into the details of the strong Choquet game, and bases, and so on. The proof is short, and not that hard, but still a bit technical.) Together with the fact that Q is compact, this implies that Q is supercompact, hence of the form ↑x, and this establishes the result.

Intermission: minimal elements of compact sets

I will need the following lemma below. This is something that one needs from time to time, and that keeps being reproved over and over, sometimes with superfluous assumptions.

Given a subset K of a topological space X, let Min K denote its set of minimal elements, with respect to the specialization preordering ≤ of X.

Lemma A. Given any compact subset K of any topological space, every point of K lies above some minimal point of K: namely, K is included in ↑Min K. (As a consequence, if K is non-empty then Min K is non-empty. Also, for every compact saturated subset Q of X, Q = ↑Min Q.)

Proof. Let Y be the collection of closed subsets of X that intersect K. We order Y by reverse inclusion, and we claim that this makes Y a dcpo. Let (Ci)iI be any directed family in Y, namely any filtered family of closed sets, all intersecting K. The intersection C of the sets Ci, iI, then intersects K, because K is compact (see Proposition 4.4.9 in the book). C is obviously closed, so C is in Y, and is therefore the supremum of the family (Ci)iI.

Let x be any point of K. Then ↓x is an element of Y. We use Zorn’s Lemma, which we can because every dcpo is an inductive poset: let C be a maximal element of Y above ↓x. Since the ordering is reverse inclusion, that means that C is a minimal closed set intersecting K and included in ↓x. Let z be any point of CK. Then ↓z is closed, intersects K, and is included in ↓x. Hence by minimality C=↓z. Also, since ↓z is included in ↓x, we have zx.

It remains to show that z is a minimal point of K. If that were not the case, there would be a point z’ in K that is strictly below z. Then ↓z‘ would be a proper subset of C=↓z, still intersecting K, and still included in ↓x, but that would contradict the minimality of C.

Finally, we deal with the consequences inside the parenthesis. If K is non-empty, then we have just shown that every point of K lies above some point of Min K, so Min K must be non-empty as well. For every compact saturated subset Q of X, we have just seen that Q ⊆ ↑Min Q. The reverse inclusion follows from the fact that Min Q is included in Q, and that Q is saturated, namely, upwards-closed. ☐

The topological Rudin Lemma

The topological Rudin Lemma is probably what paper [1] is most cited for. It is an extension of Rudin’s Lemma (Proposition 5.2.25 in the book), so let me first recapitulate (and rephrase) the latter.

Oh, I have already talked about the topological Rudin Lemma! But the version given there, which matches Lemma 3.1 of [1], is not quite an analogue of Rudin’s original lemma. In a sense, it is weaker. I will give an actual topological analogue of Rudin’s lemma below.

Given a poset X, let me call a finitary subset of X any set that is the upward closure ↑E of a non-empty finite subset E of X. Given a finitary subset Q of X, let us write Min Q for its set of minimal points. In general E’ ≝ Min ↑E is a subset of E, and it may be a proper subset of E, but E and E’ have the same upward-closure, so we do not lose any generality by assuming that E is the set Min Q of minimal points of Q.

We order the family Qfin(X) of finitary subsets of X by reverse inclusion: Q is below Q’ if and only if QQ’. That is a bit confusing: notably, a subset D of Qfin(X) is directed if and only if it is non-empty, and any two elements of D contain a third element of D. Hence, as a family of subsets of X, a directed family in Qfin(X) is a filtered family of finitary subsets of X. But, if you have survived the proof of Lemma A, you should have understood that already.

Let D be a filtered family of finitary subsets of X. Rudin’s Lemma states that there is a directed family D of points of X such that:

  1. each element of D is a minimal point of some element Q of D,
  2. and every element Q of D intersects D.

This is a crucial lemma in the study of quasicontinuous domains. Also, it implies that dcpos have certain properties related to well-filteredness.

For example (Proposition 5.2.28 in the book), given a dcpo X, and a filtered family D of finitary subsets of X, if the intersection Q of all the finitary sets in D is included in a Scott-open subset U of X, then some element of D must already be included in U. Moreover, Q is compact saturated in the Scott topology (Corollary 5.2.9). Let me say how this rests on Rudin’s Lemma. We imagine that no element ↑E of D is included in U, and we reason by contraposition, aiming to show that Q is not included in U. For every element ↑E of D, ↑(EU) is again a finitary subset of X (as EU is non-empty), and the family D’ of sets ↑(EU), where ↑E ranges over the elements of D, is again filtered. We apply Rudin’s Lemma and we obtain a directed family D of points of X such that: (1) each element of D is in EU for some E in D, and (2) every set ↑(EU) with ↑E is in D intersects D. Since X is a dcpo, D has a supremum: call it x. Since no element of D is in U, x is not in U either. But x is in the intersection Q of all the elements ↑E of D, since by (2) ↑(EU) intersects D, say at y: then yx, and y is in ↑(EU), hence in ↑E, so that x is also in ↑E. This implies that Q is not included in U.

Lemma 3.1 of [1]—the topological Rudin Lemma—generalizes Rudin’s Lemma in a topological way. We use the following dictionary in order to translate between the order-theoretic world of Rudin’s Lemma and the topological world of the new result.

  • Instead of a poset X, we rely on a topological space X. The case of posets is obtained as the special case where X has the Alexandroff topology of some ordering ≤ (which is then necessarily its specialization ordering; recall that the Alexandroff topology has all upwards-closed subsets as open subsets).
  • Instead of directed subsets, we use irreducible subsets: an irreducible subset A of X is a subset whose closure is irreducible closed, in other words it is a non-empty subset A of X such that whenever A intersects two open sets U and V, it also intersects their intersection UV; every directed subset of X (with respect to its specialization preordering) is irreducible; the converse holds if X has the Alexandroff topology of its specialization preordering.
  • Instead of finitary subsets, we use non-empty compact saturated subsets. Not just the finitary compact subsets ↑E, but all non-empty compact saturated subsets. If X has an Alexandroff topology, this is the same thing: in an Alexandroff space, every compact saturated subset is the upward closure of finitely many points. (Just cover the compact saturated subset Q by the open cover (↑x)xQ, and extract a finite subcover.) In other words, instead of considering Qfin(X), we use the Smyth powerdomain Q(X) (see Proposition 8.3.25 in the book).
  • It is convenient to topologize Q(X) with the upper Vietoris topology. This has a base of open subsets of the form ☐U, where U ranges over the open subsets of X, and ☐U denotes the collection of non-empty compact saturated subsets of X that are included in U. The specialization preordering of that topology is reverse inclusion ⊇ (briefly, Q is below Q’ in the specialization preordering if and only if for every open subset U of X, Q ∈ ☐U implies Q‘ ∈ ☐U, or equivalently, if and only if every open neighborhood of Q contains Q’; since Q is saturated, it is the intersection of its open neighborhoods, so that this means that Q itself contains Q’). When X has the Alexandroff topology of some preordering ≤, then the upper Vietoris topology on Q(X) coincides with the Alexandroff topology of ⊇. (It is enough to show that the upward closure of any QQ(X) is open in the open Vietoris topology. Since X is Alexandroff and Q is saturated, Q is itself open, and the upward closure of Q, namely the set of elements of Q(X) that are included in Q, is just the basic open set ☐Q.)

Let me now state and prove the topological Rudin Lemma. I will formulate it in a manner reminiscent of Rudin’s original lemma. Lemma 3.1 of [1] is stated slightly differently, and actually states a bit less. More is needed, and more was used by Sheng, Xi, Xu and Zhao in at least two papers [3,4]. I have the feeling that the following formulation is what we really need, usually.

Theorem (the Topological Rudin Lemma). Let D be an irreducible subset of Q(X), with the upper Vietoris topology. There is an irreducible subset D of X such that:

  1. each element of D is a minimal point of some element Q of D,
  2. and every element Q of D contains a minimal point (i.e., one in Min Q) that is in D.

Moreover, we may even choose D so as to be included in any fixed closed subset C0 of X that intersects every element Q of D.

Note. Before we embark on the proof, we note that the topological Rudin Lemma (even ignoring the last claim about C0) implies Rudin’s original lemma. Let X be any poset. We give it the Alexandroff topology, and we use the dictionary given above. Then Q(X)=Qfin(X), and the upper Vietoris coincides with the Alexandroff topology of reverse inclusion. It follows that, in that case, the irreducible subsets of Q(X) are simply the directed families in Qfin(X), or equivalently, the filtered families of finitary subsets of X. The irreducible set D obtained by applying the topological Rudin Lemma is directed, since X is Alexandroff, and properties 1 and 2 that the theorem gives us are exactly the two properties we expect in the conclusion of Rudin’s Lemma.

Proof. Let C be the collection of all closed subsets of X that intersect every Q in D. We order C by reverse inclusion, and we will proceed in a manner very much like what we did in order to prove Lemma A. Given any directed family (Ci)iI of elements of C (namely, a filtered family of closed subsets), let C be the intersection of the sets Ci, iI. For every Q in D, each Ci intersects Q. Since Q is compact, it follows that C also intersects Q (see Proposition 4.4.9 in the book). Hence C is in D.

This shows that C is a dcpo under reverse inclusion. Given any closed subset C0 of X that intersects every element of D, namely given any element C0 of C, Zorn’s Lemma implies that C contains a maximal element above C0. (And such a C0 always exists: we can take X for example.) In other words, and taking into account that the ordering on C is reverse inclusion, there is a minimal closed subset C of X included in C0 that intersects every element Q of D.

We claim that C is irreducible. Since D is irreducible, D is non-empty: pick Q in D; Q is non-empty, and Q intersects C, in particular C is non-empty. Now let us consider two arbitrary open subsets U and V of X that intersect C. We wish to show that C also intersects UV. Since U and V both intersect C, CU and CV are proper closed subsets of C. By minimality of C, those proper subsets cannot be in C. In other words, there is an element Q of D that is disjoint from CU, and there is an element Q’ of D that is disjoint from CV. Since Q is disjoint from CU, it is included in its complement (XC) ∪ U, so Q belongs to ☐((XC) ∪ U). This shows that D intersects ☐((XC) ∪ U). Similarly, D intersects ☐((XC) ∪ V). It is time to use the fact that D is irreducible: therefore D also intersects ☐((XC) ∪ U) ∩ ☐((XC) ∪ V), say at Q”. Then Q” is included in (XC) ∪ U, and also in (XC) ∪ V, hence is included in their intersection (XC) ∪ (UV). Since C is in D, C intersects Q”, say at x. Then x, being in Q”, is in (XC) ∪ (UV), and since x is in C, it cannot be in XC, so it is in UV. In other words, C intersects UV, as desired.

Lemma 3.1 of [1] pretty much stops here, namely showing that D contains an irreducible closed subset C of X that intersects every element of D. Shen, Xi, Xu, and Zhao [3,4] regularly use the fact that C is a minimal closed set that intersects every element of D. We turn to proving the existence of the set D, as promised in the statement of the theorem.

Let D be the union of the sets Min (CQ), where Q ranges over D. For each Q in D, CQ is compact, and non-empty by definition of C. By Lemma A, all those sets Min (CQ) are therefore non-empty. We check everything that needs to be checked:

  • Property 1: every point x of D is a minimal point in CQ for some Q in D, by definition of D. For every x’ < x, if x’ were in Q then it would also be in CQ, since C is downwards-closed. That is impossible since x is minimal in CQ. Hence such points x’ cannot be in Q, which shows that x is minimal in Q.
  • Property 2: every element Q of D intersects D, indeed at any point of Min (CQ). We have just seen that any such point x is minimal in Q, and x is in D by definition of D.
  • D is irreducible. We consider the closure cl(D) of D. By definition D is included in the union of the sets CQ, where Q ranges over D, hence is included in C. It follows that cl(D) is included in C. But cl(D) contains D, and by definition D intersects every element Q of D. By minimality of C, cl(D) must therefore be equal to C. Hence cl(D) is, just like C, irreducible, so that D itself is irreducible.
  • D is included in C0: because D is a subset of C, which is included in C0. ☐

Characterizing (quasi-)sober spaces

A final pearl of [1] is their Theorem 3.13, which gives a surprising characterization of sobriety, very much resembling the definition of well-filteredness. Let me recall that a space X is well-filtered if and only if, for every filtered family D of compact saturated subsets of X, any open neighborhood U of the intersection ∩D of the sets in D contains some element of D already. Theorem 3.13 of [1] shows that, if you replace “filtered” by “irreducible” there, you obtain a characterization of sobriety instead.

In writing this, I realized that there is an inaccuracy in that theorem, and in all generality, it only holds for T0, not arbitrary, topological spaces. (I have made the same kind of mistake over and over again myself, so I will not cast the first stone.)

Instead of restricting to T0 spaces, let me replace sober spaces by quasi-sober spaces. A space is quasi-sober if and only if every irreducible closed subset is the closure (equivalently, the downward closure) of some point. Contrarily to sober spaces, that point may fail to be unique. A sober space is the same thing as a quasi-sober, T0 space.

The following is basically Proposition 3.11 of [1], tailored to the case of quasi-sober spaces.

Lemma B. Let X be a quasi-sober space. For every irreducible subset D of Q(X), every open neighborhood U of ∩D contains some element of D already.

Note. Among the irreducible subsets D of Q(X), we find the directed subsets, namely the filtered families of non-empty compact saturated subsets of X. Hence Lemma B implies that, in a quasi-sober space, for every filtered family of non-empty compact saturated subsets (Qi)iI, every open set U that contains ∩iI Qi contains some Qi already. This easily extends to the case of general filtered families of compact saturated subsets, possibly empty, yielding another proof that every sober space is well-filtered, and in fact showing that every quasi-sober space is well-filtered as well.

Proof. Let us fix an arbitrary open neighborhood U of ∩D, and let C0 be its complement. Let us assume that U contains no element of D. Then C0 intersects every element of D. By the topological Rudin Lemma, there is an irreducible subset D of X such that: (1) each element of D is in Min Q for some element Q of D, (2) for every Q in D, Min Q intersects D, and: D is included in C0. Then C ≝ cl(D) is irreducible closed, and since X is quasi-sober, there is a point x in X such that C = ↓x. We note that since D is included in C0, C is also included in included in C0, so that x is in C0.

By (2), for every Q in D, Min Q intersects D, say at y. Then y is in D, hence in C, so that yx. Since Q is upwards-closed, x is in Q. This holds for an arbitrary element Q of D, so x is in ∩D. It follows that x is in U, since U contains ∩D. But that is impossible, since x is in its complement C0. We must therefore conclude that our assumption that U contains no element of D is wrong. ☐

In the situation of Lemma B, we can show more: namely, ∩D is non-empty, compact, and saturated. This is a consequence of the following lemma, a special case of [1, Fact 3.12].

Lemma C. Let D be any subset of Q(X) such that every open neighborhood U of ∩D contains some element of D already. Then ∩D is a non-empty compact saturated subset of X.

Proof.D is non-empty: otherwise the empty set would be an open neighborhood of ∩D, and therefore some element of D would be empty, which is absurd. ∩D is saturated, as the intersection of a family of saturated sets. Finally, we check that ∩D is compact. Let (Ui)iI be any directed family of open subsets of X whose union U contains ∩D. By Proposition 4.4.7 of the book, it will be enough to show that ∩D is included in some Ui. Since U is an open neighborhood of ∩D, it must contain some element Q of D, by assumption. But Q is compact, so Q is included in Ui for some iI (by Proposition 4.4.7). Hence the smaller set ∩D is included in Ui, as desired. ☐

Fact 3.12 of [1] also states the following, which will come in handy below. This is just like Lemma C, replacing “compact” by “supercompact”.

Lemma D. Let D be any family of supercompact saturated subsets of X such that every open neighborhood U of ∩D contains some element of D already. Then ∩D is supercompact saturated.

Proof. The only thing that changes is that we must check that ∩D is supercompact. Let (Ui)iI be any family, not necessarily directed, of open subsets of X whose union U contains ∩D. By assumption, U contains some element Q of D, and since Q is supercompact, Q is included in Ui for some iI. Hence the smaller set ∩D is included in Ui, as desired. ☐

The following is Theorem 3.13 of [1], modulo the T0 glitch. In addition to what we had promised it would say, it also establishes the nifty fact that X is quasi-sober if and only if Q(X) is sober.

Theorem (characterizing sober spaces). For a topological space X, the following three claims are equivalent:

  1. X is quasi-sober;
  2. for every irreducible subset D of Q(X), every open neighborhood U of ∩D contains some element of D already;
  3. Q(X) is quasi-sober;
  4. Q(X) is sober.

Proof. 1 implies 2, by Lemma B.

Let us assume 2, and let us show 3. Let C be an irreducible closed subset of Q(X). (We used to write that D, but we also used to assume D irreducible, not necessarily closed.) By Lemma C, ∩C is an element Q of Q(X). We claim that C is the downward closure of the point Q of Q(X), namely that the elements of C are exactly the non-empty compact saturated sets that contain Q. Since Q = ∩C, every element of C contains Q. Conversely, let Q’ be a non-empty compact saturated set that contains Q. Imagine, for the sake of contradiction, that Q’ is not in C. Hence Q’ is in the complement of C, which is open. By the definition of the upper Vietoris topology, there is an open subset U of X such that Q’ ∈ ☐U, and ☐U is disjoint from C. Since Q’ contains Q, U contains Q, too. By 2, U must contain some element of C. This is impossible since ☐U is disjoint from C. This finishes to prove that C is the downward closure of the point Q of Q(X). Since C is arbitrary, Q(X) is quasi-sober.

3 implies 4. Since the specialization preordering of Q(X) is reverse inclusion, and that is an ordering, Q(X) is T0. We now remember that sober spaces are the same thing as quasi-sober, T0 spaces.

We finally assume 4, and we show 1. Let C be an irreducible closed subset of X. There is a continuous map η from X to Q(X), which maps every point x to ↑x. (Indeed, η–1(☐U)=U.) Then the closure of the direct image cl(η[C]) is irreducible closed (this is a particular case of Lemma 8.2.42 in the book). By 4, cl(η[C]) is the downward closure of a single element Q of Q(X).

Now let D ≝ η[C] = {↑x | xC}. We claim that ∩D = Q. In one direction, Q is above every element of cl(η[C]) (with respect to ⊇), hence also of η[C], meaning that Q is included in ↑x for every xC. Therefore Q is included in ∩D. In the other direction, namely in order to show that ∩D is included in Q, it suffices to show that every open neighborhood U of Q contains ∩D, because Q is saturated. Since QU, Q is in ☐U, so cl(η[C]) intersects ☐U (… at Q). Now the closure of a set A intersects an open set if and only if A itself does, so η[C] intersects ☐U. Hence there is a point x in C such that ↑x is in ☐U, hence is included in U. The set ∩D, which is included in ↑x, must therefore be included in U as well.

Note that, in the course of the latter argument, we have shown that every open neighborhood U of Q (= ∩D) is such that ↑x is included in U for some point x in C. In other words, every open neighborhood of ∩D contains some element ↑x of D. D is a family of supercompact saturated subsets of X, so Lemma D applies: ∩D is supercompact saturated.

By the first theorem of this post, ∩D is therefore equal to ↑z for some point z of X. For every open neighborhood U of z, ↑z = ∩D is included in U. As we have just seen, this implies that ↑x must be included in U for some x in C, so that U intersects C (… at x). Letting U be the complement of C, and reasoning by contraposition, we obtain that this U cannot be an open neighborhood of z, so z is in C.

By definition of D, ∩D is the set of upper bounds of C. The equality ↑z = ∩D shows that z is a least upper bound of C. (Not the least upper bound: we do not assume that X is T0.) Since z is in C, it is a largest element of C. We now use the fact that C is downwards-closed to conclude that C=↓z. ☐

  1. Reinhold Heckmann and Klaus Keimel. Quasi-continuous domains and the Smyth powerdomain. In Proceedings of the 29th Conference on the Mathematical Foundations of Programming Semantics, MFPS XXIX, New Orleans, Louisiana, USA, Dexter Kozen and Michael Mislove, editors, 2013. Electronic Notes in Theoretical Computer Science 298(4), pages 215-232, 2013.
  2. Matthew de Brecht, Jean Goubault-Larrecq, Xiaodong Jia, and Zhenchao Lyu. Domain-complete and LCS-complete Spaces. In Proceedings of the International Symposium on Domain Theory (ISDT’19), volume 345 of Electronic Notes in Theoretical Computer Science, pages 3–35, Yangzhou, China, June 2019. Elsevier Science Publishers. doi:10.1016/j.entcs.2019.07.014.
  3. Chong Shen, Xiaoyong Xi, Xiaoquan Xu, and Dongsheng Zhao. On well-filtered reflections of T0 spaces. Topology and its Applications 267, 1 November 2019, https://doi.org/10.1016/j.topol.2019.106869.
  4. Xiaoquan Xu, Chong Shen, Xiaoyong Xi, and Dongsheng Zhao.  On T0 spaces determined by well-filtered spaces. Topology and its Applications 282, 15 August 2020, https://doi.org/10.1016/j.topol.2020.107323.
jgl-2011

Jean Goubault-Larrecq