{"id":737,"date":"2015-09-26T11:54:43","date_gmt":"2015-09-26T09:54:43","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=737"},"modified":"2023-03-31T14:08:14","modified_gmt":"2023-03-31T12:08:14","slug":"domains-xii","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=737","title":{"rendered":"Domains XII"},"content":{"rendered":"

In my last post, I said I would have trouble finding time to write anything up in August, and sadly, this came out true. Late August, I went to the Domains XII<\/a> conference, and it may be a good idea if I gave a report on a few of the things I learned there. \u00a0Some, but not all, of the slides of talks are present on the conference page.<\/p>\n

Before I start, let me mention I gave a talk<\/a> there, which roughly covers Sections 7.1 through 7.5 of the book<\/a> on quasi-metric spaces, completeness and completions. \u00a0If you are interested in this, it may give a shorter and more efficient introduction to those topics, before you read about them in the book<\/a>. \u00a0Some of the proofs are also simpler.<\/p>\n

All cartesian closed categories of quasi continuous domains consist of domains<\/h2>\n

Probably one of the most stunning results announced there, or so I think, was announced by Achim Jung<\/a>. \u00a0This is common work with Kou Hui<\/a>, Jia Xiaodong, Li Qingguo, and Zhao Haoran. \u00a0Achim did not use any slide, so I cannot direct you to any, but his blackboard talk was fantastic. \u00a0The result is, too. \u00a0It was recently published as\u00a0All cartesian closed categories of quasicontinuous domains consist of domains<\/a>. Theor. Comput. Sci. 594<\/a>: 143-150 (2015).<\/p>\n

Achim started his talk as follows. \u00a0We know of quite a few cartesian closed categories of domains, that is, whose objects are continuous dcpos. \u00a0(We always take morphisms to be all continuous maps, and I will always assume that in the sequel.) \u00a0There are the algebraic complete lattices, the continuous complete lattices, the algebraic bc-domains, the (continuous) bc-domains, the bifinite domains, RB<\/strong>-domains, FS<\/strong>-domains, and L<\/strong>-domains. \u00a0There are others as well, for example, any of the latter restricted to second-countable spaces.<\/p>\n

That is fine. \u00a0However, all of them conflict in some precise sense with Claire Jones’ probabilistic powerdomain construction. \u00a0The latter is needed in giving semantics to higher-order\u00a0probabilistic<\/em> functional languages, and was developed in her PhD thesis<\/a>. \u00a0The probabilistic powerdomain V<\/strong>(X<\/em>) of a space X<\/em> is, roughly speaking, the set of measures on X<\/em>. \u00a0Jones uses the slightly different notion of continuous valuation instead of measure, as this is more practical, but that does not make much of a difference. \u00a0One of the landmark result in her PhD thesis (1990) is that the probabilistic powerdomain V<\/strong>(X<\/em>) of a continuous dcpo\u00a0X<\/em> is again a continuous dcpo. \u00a0This is non-trivial.<\/p>\n

We need the probabilistic powerdomain to interpret probabilistic choice (as one would expect), and we need cartesian-closedness to interpret higher-order computation, that is, functions as first-class objects, functions taking functions as arguments, etc. \u00a0Since continuous dcpos form a cosy category to do mathematics in, we would like to find a category of continuous dcpos that is both cartesian closed and closed under the probabilistic powerdomain construction.<\/p>\n

Jones had already shown that this would be hard. \u00a0Precisely, the categories of bc-domains (or Scott-domains, whether algebraic or merely continuous) do not qualify. \u00a0She shows that, for one of the simplest bc-domains\u00a0X<\/em>,\u00a0V<\/strong>(X<\/em>) is not a bc-domain (p.88 of her PhD thesis). \u00a0X<\/em> is just the three element set {0, 1, \u22a4} with\u00a0\u22a4 above 0, 1, and 0 and 1 incomparable. \u00a0She shows that the measures \u00bd\u03b40<\/sub> and \u00bd\u03b41<\/sub> have no least upper bound, although they do have an upper bound (for example, \u00bd\u03b4\u22a4<\/sub>, or \u00bd\u03b40<\/sub>+\u00bd\u03b41<\/sub>). In fact they have uncountably many minimal upper bounds, which is (almost) as far as we can imagine from being bounded-complete.<\/p>\n

Our next hope would be to show that some other known category of continuous dcpos would be closed under the probabilistic powerdomain functor\u00a0V<\/strong>. \u00a0Jones’ argument also rules out the L<\/strong>-domains, so only RB<\/strong>-domains and FS<\/strong>-domains remain (bifinite domains are excluded since\u00a0V<\/strong>(X<\/em>) is never algebraic).<\/p>\n

Almost twenty years ago, Achim Jung and Regina Tix examined the question. \u00a0Their paper, aptly named the troublesome probabilistic powerdomain<\/a>\u00a0(in Third Workshop on Computation and Approximation<\/em>, Proceedings,\u00a0Electronic Notes in Theoretical Computer Science, vol 13<\/a>, 1998, 23 pp.) gives incredibly weak results in that direction, but nobody has been able to say more since then. \u00a0What they showed is: the probabilistic powerdomain of a finite rooted tree is an\u00a0RB<\/strong>-domain (in fact even a bc-domain), and the probabilistic powerdomain of a finite reversed rooted tree is an\u00a0FS<\/strong>-domain. \u00a0They also showed that the probabilistic powerdomain of a stably compact dcpo is again stably compact, but simpler and more general proofs of that latter result have been given since then.<\/p>\n

In an attempt to go beyond the difficulty, I turned to the larger category of quasi-continuous domains, and I have shown that the category of\u00a0QRB<\/strong>-domains\u00a0is<\/em> closed under the probabilistic powerdomain functor. \u00a0In fact, I have invented QRB<\/strong>-domains precisely for that purpose \u2014 although showing that QRB<\/strong>-domains are closed under the probabilistic powerdomain functor is not trivial either. \u00a0The relevant papers are QRB-domains and the probabilistic powerdomain<\/a>,\u00a0Logical Methods in Computer Science\u00a08(1:14)<\/a>, 2012, which shows that result under the additional constraint that the\u00a0QRB<\/strong>-domains under consideration are second-countable; and QRB, QFS, and the probabilistic powerdomain<\/a>,\u00a0MFPS’14<\/acronym>, ENTCS\u00a0308, pages\u00a0167-182<\/a>. Elsevier Science Publishers, 2014, which shows the general result (i.e., not assuming second-countability), in addition to showing that\u00a0QRB<\/strong>-domains are exactly the same as Li and Xu’s\u00a0QFS<\/strong>-domains, and are also exactly the locally finitary, stably compact spaces. \u00a0I have discussed the latter in a previous post<\/a>.<\/p>\n

However,\u00a0QRB<\/strong>-domains are themselves not<\/em> a cartesian-closed category, as found by an anonymous referee of my first\u00a0QRB<\/strong> paper. \u00a0Still, there was renewed hope that one might find other, cartesian-closed categories of\u00a0quasi<\/em>-continuous dcpos that would be closed under the probabilistic powerdomain functor.<\/p>\n

What Jung, Kou, et al., have proved is that this hope is doomed.<\/p>\n

This is great! \u00a0At least we know there is nothing new to look for here.<\/p>\n

What they have proved is that, if you happened to find some new cartesian-closed category of quasi-continuous dcpos, then it would in fact consist of continuous dcpos\u00a0only<\/em>.<\/p>\n

Since this post is starting to be a bit long, I will not try to tell you how this works, or at least not yet. \u00a0Let me just say their result relies on several ingredients:<\/p>\n