Last time, we talked about quasi-continuous domains, locally finitary compact spaces and their Stone duals, the hypercontinuous distributive complete lattices.
From time to time, we happen to discover that several distinct notions are in fact the same, and this is exactly what happened in 2013-2014, in two papers that appeared about at the same time, with similar discoveries. One is due to Jimmie Lawson and Xiaoyong Xi [3], the other one is due to Achim Jung and myself [2].
I’ll give an introduction to each of the various kinds of spaces that play a role here, separately, and I’ll conclude by telling you… that they all coincide.
QRB-domains
I invented QRB-domains as a quasi-continuous imitation of RB-domains during the summer of 2009, and published a few results about them at the LICS (Logics in Computer Science) conference in 2010 [4], then later in the LMCS (Logical Methods in Computer Science) journal in 2012 [5].
Here is the idea. Among the several equivalent definitions of an RB-domain, one is: X is an RB-domain if and only if there is a directed family of deflations (fi)i in I whose sup is the identity on X (see Theorem 9.6.22 in the book). A deflation is a continuous map from X to X, below the identity, and with finite image. We know that fi(x) is way-below x for every x in X, so every RB-domain is a continuous dcpo.
What if we required every point to be approximated, not by points fi(x), but by finitary compacts depending continuously on x? The idea is the same as when we went from continuous to quasi-continuous posets.
Formally, let Q(X) denote the Smyth powerdomain of X, consisting of compact saturated subsets ordered by reverse inclusion (see Proposition 8.3.25 in the book). Let
Qfin(X) be its subspace of finitary compacts. We call quasi-deflation any map φ from X to Qfin(X) that is continuous, has finite image, and is “below the identity” in the sense that x is in φ(x) for every x in X. Alternatively, write η(x) for ↑x; η is a continuous map from X to Qfin(X), and φ is “below the identity” in that new sense if and only if it is below η in the pointwise ordering.
Now call X a QRB-domain if and only if there is a directed family of quasi-deflations (φi)i in I on X whose supremum is η. Explicitly, we require that ⋂i in I φi (x)=↑x for every x in X.
Unsurprisingly, QRB-domains are quasi-continuous domains. However, they are more than that: they are all stably compact.
Among the properties defining stable compactness, all are satisfied by quasi-continuous domains except two: compactness and coherence. So QRB-domains are pretty well-behaved: quasi-continuous domains that are also compact and coherent.
The dcpo N2 of Figure 5.1, which I have already mentioned in my last post on quasi-continuous dcpo, is a QRB-domain, for example. It is also algebraic; but it is not an RB-domain.
Incidentally, QRB-domains have a rich theory, which parallels that of RB-domains. Notably, I proved [4, 5] that the QRB-domains are exactly the quasi-retracts of bifinite domains (provided all domains are second-countable, see below). Compare this with the fact that the RB-domains are exactly the retracts of bifinite domains. I won’t define what quasi-retracts are, except that they are “retracts in the quasi sense”, and that a variant of this result says that the second-countable QRB-domains are exactly the images of second-countable bifinite domains by proper maps [5]. (Every proper map defines a canonical kind of quasi-retraction, which I called quasi-projection at some point to stress the parallel with projections in the theory of bifinite domains.)
One open question here is whether second-countability is needed here. I would hope that it is not the case, and would conjecture that every QRB-domain is the quasi-retract of a bifinite domain.
I did all this as an attempt to solve a conjecture in probabilistic domain theory [7]. One distinguishing feature is that the probabilistic powerdomain of a QRB-domain is again a QRB-domain, as I’ve shown in [4, 5] in the second-countable case, and in [2], with Achim Jung, in the general case. The probabilistic powerdomain is a domain of so-called continuous valuations, a variant of the notion of probability measure, and was introduced by Claire Jones in her PhD thesis [6].
QFS-domains
Independently, and by a similar intellectual process, Li and Xu invented a quasi-continuous imitation of FS-domains, see [1].
This really works as for QRB-domains. Say that a map φ : X → Q(X) is quasi-finitely separated from the identity (in short, qfs) if and only if there is a finite subset M of X such that for every x in X, there is an m in M such that x ∈ ↑m ⊆ φ(x). A QFS-domain is a dcpo X that has a directed family of qfs maps (φi)i in I (not necessarily quasi-deflations) on X whose supremum is η. Again, that means that ⋂i in I φi (x)=↑x for every x in X.
Every QRB-domain is a QFS-domain. Li and Xu also showed that every QFS-domain, just like every QRB-domain, is a compact, coherent quasi-continuous dcpo. Is there any QFS-domain that is not a QRB-domain? No. Indeed, we have:
Theorem [2, 3]. The following classes of spaces are the same:
|
In fact, there are 4 other classes of spaces that also coincide with those, and which may have an interest in their own right, see Theorem 5.7 of [2]. Notably, these spaces are exactly the stably compact spaces that are locally finitary compact (including the fact that their topology must be the Scott topology).
It is time we talked about the proof, and about spaces of kind 3.
Compact, coherent quasi-continuous domains
To prove the theorem, remember that we already know that every QRB-domain is a QFS-domain, and that every QFS-domain is a compact, coherent quasi-continuous domain.
We also know that every quasi-continuous domain is a locally finitary compact space. To put the final nail on the proof of the theorem, we show that every stably compact, locally finitary compact space X is a QRB-domain. This is Proposition 5.6 of [2].
Concretely, fix a stably compact, locally finitary compact space X. We build quasi-deflations φi on X, and show that we have enough of them so as to ensure that ⋂i in I φi (x)=↑x for every x in X. The fact that X has the Scott topology is due to the fact that this already holds for every sober locally finitary compact space.
The preparatory Proposition 5.4 of [2] gives the main idea already, and there is a similar idea used in Proposition 9.5.31 in the book. Fix a finite semi-lattice M of compact saturated subsets of X, by which we mean a finite collection of compact saturated subsets that is closed under intersection. Define φM as mapping each x in X to the smallest element Q of M (with respect to inclusion) whose interior contains x. One checks that φM is a continuous map from X to Q(X), with finite image. The family of these maps, when M varies, is directed, and this uses the fact that X is compact and coherent. Moreover, the sup of these maps φM is η, as desired.
Let us check the latter. We need to show that ⋂M φM (x)=↑x for every x in X, where M ranges over the finite semi-lattices of compact saturated subsets of X. The right-hand side is always included in the left-hand side. To show the converse inclusion, since X is T0, it suffices to show that every open neighborhood U of x contains φM (x) for some M; it suffices to find a compact saturated neighborhood Q of x included in U (by local compactness), and to take M = {Q, X}. Indeed, for this choice of Q, φM (x) is equal to Q, which is contained in U.
This looks like a proof, but a crucial ingredient is missing: φM takes its values in Q(X), not Qfin(X). So this does not prove that X is a QRB-domain. Also, we have not used the (crucial) assumption that X is locally finitary compact.
Instead, we massage each φM to a new continuous map, replacing each compact saturated subset Q in its image by a slightly larger finitary compact subset neighborhood, using local finitary compactness. This requires some care, notably to keep φM monotonic, but the fact that φM has finite image allows us to use induction to ensure this. The argument is not difficult; see the proof of Proposition 5.6 in [2]. (In Appendix A, I’ll discuss why a slightly simpler argument does not work.)
Once we have done so, the problem is fixed, and our arbitrary stably compact, locally finitary compact space X has been revealed as a QRB-domain: our proof is finished.
I would like to state an anecdote, showing how brilliant Achim Jung is. He came to my place (LSV) for a one-month visit from mid-March to mid-April 2013. We discussed a few scientific questions we might explore while he was here, and he expressed the desire to learn about my QRB-domains. After I had explained the basic theory, he walked up to the whiteboard. In his extremely mild-mannered way, he said “Now, Jean, tell me if I am wrong, but we can certainly do this […] and that […]”. In a few minutes, he had found the essential argument that I’ve described above. That is how Achim learned the theory… by proving a new, fundamental result about it in a matter of minutes.
— Jean Goubault-Larrecq (January 19th, 2015)
[1] Gaolin Li and Luoshan Xu. QFS-Domains and their Lawson Compactness. Order (2013) 30, pp. 233–248.
[2] Jean Goubault-Larrecq and Achim Jung. QRB, QFS, and the Probabilistic Powerdomain. Proceedings of the 30th Intl. Conf. on Mathematical Foundations of Programming Semantics, ENTCS, pp. 170-185, 2014.
[3] Jimmie Lawson and Xiaoyong Xi. The equivalence of QRB, QFS, and compactness for quasicontinuous domains. ORDER, 2014. DOI 10.1007/s11083-014-9327-7.
[4] Jean Goubault-Larrecq. ωQRB-Domains and the Probabilistic Powerdomain. In LICS’10, pages 352-361. IEEE Computer Society Press, 2010.
[5] Jean Goubault-Larrecq. QRB-Domains and the Probabilistic Powerdomain. Logical Methods in Computer Science 8(1:14), 2012.
[6] Claire Jones. Probabilistic Non-Determinism. Ph.D. thesis, University of Edinburgh (1990), technical Report ECS-LFCS-90-105.
[7] Achim Jung and Regina Tix. The troublesome probabilistic powerdomain. In: A. Edalat, A. Jung, K. Keimel and M. Kwiatkowska, editors, Proc. 3rd Workshop on Computation and Approximation, Electronic Lecture Notes in Computer Science 13 (1998), pp. 70–91, 23pp.
Appendix A
Here is another idea for proving that the stably compact, locally finitary compact space X is a QRB-domain. This is an idea we explored, and dismissed, because it fails, and I’ll explain why.
Recall that φM maps every point x in X to the smallest Q in M that is a neighborhood of x. We lamented ourselves that φM(x) was a compact saturated subset, not necessarily a finitary compact subset of X, and we fixed that by modifying φM in a second step, using local finitary compactness.
It would seem much simpler to do everything in just one step, and for this the cure seems obvious: only allow M to range over finite semi-lattices of finitary compact subsets, not general compact saturated subsets. This way, φM (x) would automatically be in Qfin(X).
This does not work, or at least not in any way that would be simpler. The problem lies in showing that the family of maps φM, where M now ranges over the semi-lattices of finitary compact subsets, is directed. In our previous proof, where M was allowed to be any finite semi-lattice of compact saturated subsets, I said that directedness relied on the fact that X was compact and coherent. Indeed, to find a map φM” above φM and φM’, it sufficed to define M” as the collection of pairwise intersections Q ∩ Q’, Q in M, Q’ in M’. These intersections were compact saturated because X is coherent.
In our new setting, Q and Q’ are now finitary compact… but the best thing we can say about the intersection Q ∩ Q’ is that it is compact saturated, not finitary compact! We could proceed if we could assume that Q ∩ Q’ is finitary compact. Doing so, we would show that every stably compact, locally finitary compact space satisfying the property “every finite intersection of locally finitary compact subsets is locally finitary compact” is a QRB-domain.
However, the additional property fails in some stably compact, locally finitary spaces. In fact, it already fails for some QRB-domains. One example is the space of all triples (a,b,c) in [0, 1]3 such that a+b+c≤1, with the ordering defined by (a,b,c) ≤ (a’,b’,c’) if and only if c≤c’, a+b≤a’+b’, b+c≤b’+c’, and a+b+c≤a’+b’+c’. I claim that X is a QRB-domain that does not satisfy the extra condition. The proof is not exactly elementary, but here it goes. X is the space of all subprobability valuations on the three-element domain {1, 2, ⊤} with 1 and 2 incomparable and below ⊤, encoded as a δ1 + b δ⊤ + c δ2, where δx is the Dirac point mass at x. It has been well-known since Jones’ PhD thesis [6] that δ1=(1,0,0) and δ2=(0,0,1) have uncountably many minimal upper bounds in X, showing that the extra condition fails. X is a QRB-domain because it is the probabilistic powerspace of a QRB-domain [2, 5]; in fact it is even an FS-domain [7].