{"id":585,"date":"2015-03-25T15:38:56","date_gmt":"2015-03-25T14:38:56","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=585"},"modified":"2022-11-19T15:30:37","modified_gmt":"2022-11-19T14:30:37","slug":"powerdomains-and-hyperspaces-i-closed-and-open-subsets","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=585","title":{"rendered":"Powerdomains and hyperspaces I: closed and open subsets"},"content":{"rendered":"<p>While a topological space is a space of points, a hyperspace is a space of subsets, with a suitable topology.\u00a0 Examples abound in the literature.\u00a0 For example, the so-called Smyth powerdomain (Proposition 8.3.25) is one.\u00a0 This is an example of particular importance in denotational semantics, and elsewhere, too.\u00a0 However, this time I&#8217;ll concentrate on the Hoare hyperspace, and I&#8217;ll give you some of the topological properties it enjoys.\u00a0 Next time, I will talk about its algebraic theory, and monads.<\/p>\n<p><strong>The space of closed subsets of a space<\/strong><\/p>\n<p>Consider the space <strong>H<\/strong>(<em>X<\/em>) of all closed subsets of <em>X<\/em>.\u00a0 This is mentioned in Exercise 9.7.14, where it is proved that <strong>H<\/strong>(<em>X<\/em>) is Noetherian for every Noetherian space <em>X<\/em> (there is an additional V subscript in the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a>, too, for &#8220;Vietoris&#8221;, which I will simply dispense with here).<\/p>\n<p>The topology we take is the so-called lower Vietoris topology, whose subbasic open subsets are those of the form \u25ca<em>U<\/em>, <em>U<\/em> open in <em>X<\/em>.\u00a0 By definition \u25ca<em>U<\/em> is the set of closed sets <em>F<\/em> of X that intersect <em>U<\/em>.\u00a0 This yields a topology whose specialization ordering is ordinary inclusion.<\/p>\n<p>I call\u00a0<strong>H<\/strong>(<em>X<\/em>) the <em>Hoare hyperspace<\/em>, because a similar construction is used in denotational semantics, using the Scott topology instead, which is called the Hoare powerdomain.\u00a0 (This construction is due to Mike Smyth, but one had to make a distinction with the Smyth hyperspace, also due to Mike Smyth.)\u00a0 There is also a variant where the empty set is excluded, but I won&#8217;t be fussy about that.<\/p>\n<p>It is easy to see that the lower Vietoris topology on <strong>H<\/strong>(<em>X<\/em>) is just a fancy other name for the upper topology, so that it is always coarser than the Scott topology.\u00a0 The two topologies coincide when <em>X<\/em> is a continuous dcpo, or more generally, a c-space\u2014as we shall see as the very last result of this post.<\/p>\n<p>In general, given a space <strong>T<\/strong><em>X<\/em> of subsets of <em>X<\/em>, the lower Vietoris topology is generated by subsets of the form \u25ca<em>U<\/em>, consisting of those elements of\u00a0<strong>T<\/strong><em>X<\/em> that intersect <em>U<\/em>, while the <em>upper Vietoris topology<\/em> is generated by subsets of the form \u25a1<em>U<\/em>, <em>U<\/em> open, defined as the set of elements of <strong>T<\/strong><em>X<\/em> that are included in <em>U<\/em>.\u00a0 (See Lemma 8.3.26.)\u00a0 The <em>Vietoris topology<\/em> is the coarsest topology containing both.\u00a0 So we consider just a one-sided version here.<\/p>\n<p>There are many things we can say about the Hoare powerspace.\u00a0 For example:<\/p>\n<p><strong>Proposition. H<\/strong>(<em>X<\/em>) is always sober, for every space<em> X<\/em>.<\/p>\n<p>This is due to Andrea Schalk in her PhD thesis [1, Proposition 1.7].\u00a0 More generally, she proved that every complete lattice <em>L<\/em> is sober in its upper topology.\u00a0 The application to <strong>H<\/strong>(<em>X<\/em>) is direct: <strong>H<\/strong>(<em>X<\/em>) has all infima, hence all suprema, and is therefore a complete lattice, (suprema are computed as the closure of the union), and we have seen that the lower Vietoris topology was the upper topology.<\/p>\n<p>It remains to prove that every complete lattice <em>L<\/em> is sober in its upper topology.\u00a0 Consider any irreducible closed subset <em>F<\/em> of <em>L<\/em>.\u00a0 We can write it as an intersection of finitary closed subsets \u2193<em>E<sub>i<\/sub><\/em>, <em>i<\/em> in <em>I<\/em>.\u00a0 Writing the finite set <em>E<sub>i<\/sub><\/em> as the union of finitely many closed sets \u2193<em>x<\/em>, <em>x<\/em> in <em>E<sub>i<\/sub><\/em>, and realizing that <em>F<\/em> is included in that finite union, <em>F<\/em> must be included in \u2193<em>x<\/em> for just one point <em>x<\/em> of <em>E<sub>i<\/sub><\/em>, by irreducibility.\u00a0 Call <em>x<sub>i<\/sub><\/em> that point.\u00a0 Since <em>F<\/em> \u2286\u00a0\u2193<em><em>x<sub>i<\/sub><\/em><\/em> \u2286 \u2193<em>E<sub>i<\/sub><\/em>, we see that <em>F<\/em> is equal to the intersection of the sets \u2193<em>x<sub>i<\/sub><\/em>, <em>i<\/em> in <em>I<\/em>.\u00a0 But that is just the downward closure of the infimum of the points <em>x<sub>i<\/sub><\/em>, <em>i<\/em> in <em>I<\/em>.\u00a0 Since <em>L<\/em> is clearly T<sub>0<\/sub>, this concludes the proof.<\/p>\n<p>Another useful property is that the sobrification <strong>S<\/strong>(<em>X<\/em>) of <em>X<\/em> embeds into <strong>H<\/strong>(<em>X<\/em>).\u00a0 This takes one of the simplest possible forms:<\/p>\n<p><strong>Proposition.<\/strong> <strong>S<\/strong>(<em>X<\/em>) is a subspace of <strong>H<\/strong>(<em>X<\/em>).<\/p>\n<p>Indeed, every element of <strong>S<\/strong>(<em>X<\/em>) (an irreducible closed subset) is a closed subset of <em>X<\/em> in particular.\u00a0 What the proposition says, as well, is that the subspace topology is the hull-kernel topology on <strong>S<\/strong>(<em>X<\/em>).\u00a0 But the open subsets in the hull-kernel topology are precisely the sets of irreducible closed subsets that intersect a fixed open subset <em>U<\/em> of <em>X<\/em>, and these are exactly the sets of the form \u25ca<em>U<\/em> \u2229 <strong>S<\/strong>(<em>X<\/em>).<\/p>\n<p>In particular, the map \u03b7<em><sub>X<\/sub><\/em>: <em>X<\/em> \u2192 <strong>S<\/strong>(<em>X<\/em>), which sends every point <em>x<\/em> to its closure, and which is an embedding of <em>X<\/em> into <strong>S<\/strong>(<em>X<\/em>) (provided <em>X<\/em> is T<sub>0<\/sub>), gives rise to an embedding of <em>X<\/em> into <strong>H<\/strong>(<em>X<\/em>).\u00a0 I&#8217;ll again write that embedding \u03b7<em><sub>X<\/sub><\/em>.<\/p>\n<p>While we are examining the structural properties of <strong>H<\/strong>(<em>X<\/em>), I&#8217;ll show you what happens when\u00a0<em>X<\/em> is core-compact (for example, locally compact).\u00a0 Andrea Schalk had proved that <strong>H<\/strong>(<em>X<\/em>) was locally compact in that case, but we can say much more.\u00a0 As we shall see, <strong>H<\/strong>(<em>X<\/em>) is even <em>stably compact<\/em> in that case.\u00a0 A funny way to show that is to examine another, related powerspace: the space <strong>O<\/strong>(<em>X<\/em>) of all open subsets of <em>X<\/em>.<\/p>\n<p><strong>The space of opens of a space<br \/>\n<\/strong><\/p>\n<p>Let <strong>O<\/strong>(<em>X<\/em>) be the space of all open subsets of <em>X<\/em>.\u00a0 Since it is a dcpo, we might think that the important topology on <strong>O<\/strong>(<em>X<\/em>) should be the Scott topology, but let us not commit to any specific choice yet.<\/p>\n<p>This is an important hyperspace, although it is rarely considered as such in the literature.\u00a0 We encounter it in Definition 5.2.1 of the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a>.\u00a0 In Section 5.2.1, we see that a space <em>X<\/em> is core-compact (a slight generalization of local compactness) if and only if <strong>O<\/strong>(<em>X<\/em>) is a continuous dcpo.\u00a0 In fact, I cheated and defined the core-compact spaces <em>X<\/em> as those such that <strong>O<\/strong>(<em>X<\/em>) is a continuous dcpo, and then we have seen:<\/p>\n<ul>\n<li>a more concrete definition: <em>X<\/em> is core-compact if and only if, for every point <em>x<\/em> of <em>X<\/em>, every open neighborhood <em>V<\/em> of <em>x<\/em> contains an open neighborhood <em>U<\/em> of <em>x<\/em> that is way-below <em>V<\/em>, namely such that every open cover of <em>V<\/em> contains a finite subcover of <em>U<\/em>;<\/li>\n<li>an equivalent caracterization: <em>X<\/em> is core-compact if and only if <em>X<\/em> is exponentiable in the category <strong>Top<\/strong> of topological spaces (Theorem 5.4.4);<\/li>\n<li>an important special case: every locally compact space is core-compact, and in that case <em>U<\/em> is way-below <em>V<\/em> if and only if there is a compact saturated set <em>Q<\/em> that we can insert between <em>U<\/em> and <em>V<\/em>;<\/li>\n<li>a strengthening of the latter, showing that the core-compact spaces are exactly those spaces whose sobrification is locally compact (Proposition 8.3.11).<\/li>\n<\/ul>\n<p>Consider the <em>lower<\/em> topology on <strong>O<\/strong>(<em>X<\/em>).\u00a0 In general, the lower topology on a poset <em>L<\/em> has a subbasis of closed subsets formed by the finitary closed subsets \u2191<em>E<\/em>, where <em>E<\/em> is a finite subset of <em>L<\/em>.\u00a0 Here we consider <em>L<\/em>=<strong>O<\/strong>(<em>X<\/em>), ordered by inclusion.\u00a0 Notice that we use upward arrows here: we would obtain the <em>upper<\/em> topology if we had used downward arrows (\u2193<em>E<\/em>) instead, as we did in discussing the Hoare powerspace earlier.\u00a0 (I know, it <em>is<\/em> confusing.) Note that the lower topology on <em>L<\/em> is the same as the upper topology on <em>L<sup>op<\/sup><\/em>.<\/p>\n<p>The complements of open subsets are the closed subsets, hence we have the trivial observation:<\/p>\n<p><strong>Fact.<\/strong>\u00a0 The map \u2201 that sends every open set to its complement is a homeomorphism from <strong>O<\/strong>(<em>X<\/em>) with its lower topology onto <strong>H<\/strong>(<em>X<\/em>) with its upper (=lower Vietoris) topology.<\/p>\n<p>This means, for example, that <strong>S<\/strong>(<em>X<\/em>) also embeds into <strong>O<\/strong>(<em>X<\/em>).\u00a0 Explicitly, the embedding maps every irreducible closed subset to its complement.\u00a0 Those complements of irreducible closed subsets are exactly the prime elements of the lattice <strong>O<\/strong>(<em>X<\/em>) (see Proposition 8.1.20), namely the elements of <strong>pt<\/strong>(<strong>O<\/strong>(<em>X<\/em>)).\u00a0 That should come as no surprise since we know that the latter is homeomorphic to <strong>S<\/strong>(<em>X<\/em>).<\/p>\n<p>The new thing is that we can also examine the <em>Scott<\/em> topology on <strong>O<\/strong>(<em>X<\/em>).\u00a0 We know that it coincides with the Isbell topology (Exercise 5.4.12).\u00a0 The Isbell topology is splitting (Exercise 5.4.10), and the Scott topology is conjoining if and only if <em>X<\/em> is core-compact (this is what Exercise 5.2.7 states, in disguise).\u00a0 In particular:<\/p>\n<p><strong>Lemma.<\/strong>\u00a0 The Scott topology on <strong>O<\/strong>(<em>X<\/em>) is conjoining (namely, the graph of the membership relation is open in the product topology, of <em>X<\/em> and <strong>O<\/strong>(<em>X<\/em>) with its Scott topology) if and only if it is exponential, if and only if <em>X<\/em> is exponentiable, if and only if <em>X<\/em> is core-compact.<\/p>\n<p>There is little point in comparing the Scott topology with the lower topology (which we examined earlier).\u00a0 The specialization ordering of the former is inclusion, while that of the latter is <em>reverse<\/em> inclusion.<\/p>\n<p>Instead, let us consider the Lawson topology, namely, the coarsest topology that contains both the Scott and the lower topology (Exercise 9.1.21).\u00a0 The Lawson topology on a continuous (or even a quasi-continuous) poset is T<sub>2<\/sub>, and in fact a pospace.\u00a0 Therefore <strong>O<\/strong>(<em>X<\/em>) is\u00a0T<sub>2<\/sub> in its Lawson topology as soon as <em>X<\/em> is core-compact, and a pospace when equipped with inclusion.\u00a0 By the way, Exercise 9.1.36 establishes that the Lawson topology on <strong>O<\/strong>(<em>X<\/em>) is the same as the patch topology, if <em>X<\/em> is a continuous poset or a quasi-continuous dcpo.<\/p>\n<p>We have much more: if <em>X<\/em> is core-compact, then <strong>O<\/strong>(<em>X<\/em>) is a continuous complete lattice, hence is stably compact in its Scott topology (Fact 9.1.6).\u00a0 It follows that <strong>O<\/strong>(<em>X<\/em>) is a compact pospace in its Lawson (=patch) topology\u2014one of the nicest kind of spaces in existence.\u00a0 This deserves a formal statement:<\/p>\n<p><strong>Proposition<\/strong>.\u00a0 For every core-compact space\u00a0<em>X<\/em>, <strong>O<\/strong>(<em>X<\/em>) is compact T<sub>2<\/sub> in its Lawson (=patch) topology.\u00a0 With inclusion, it is a compact pospace.<\/p>\n<p>Exercise 9.1.36 also establishes that the lower topology on <strong>O<\/strong>(<em>X<\/em>) is the de Groot dual of the Scott topology.\u00a0 In particular, we have obtained, the following, where the second statement is obtained from the first using the fact that the two spaces are homeomorphic.<\/p>\n<p><strong>Theorem.<\/strong>\u00a0 If <em>X<\/em> is core-compact, then:<\/p>\n<ul>\n<li><strong>O<\/strong>(<em>X<\/em>) is stably compact in its lower topology, and<\/li>\n<li><strong>H<\/strong>(<em>X<\/em>) is stably compact in its upper (=lower Vietoris) topology.<\/li>\n<\/ul>\n<p>In particular, both powerspaces are compact T<sub>2<\/sub> in the corresponding patch topologies.<\/p>\n<p><strong>Continuous dcpos of closed subsets<\/strong><\/p>\n<p>We finish this tour of the structural properties of the spaces <strong>H<\/strong>(<em>X<\/em>) and <strong>O<\/strong>(<em>X<\/em>) by mentioning the fact that, when <em>X<\/em> is a c-space (e.g., a continuous dcpo), then <strong>O<\/strong>(<em>X<\/em>) is a prime-continuous complete lattice (Lemma 8.3.41).\u00a0 Raney&#8217;s Theorem (Exercise 8.3.16) says that this is equivalent to: <strong>O<\/strong>(<em>X<\/em>) is a completely distributive lattice.\u00a0 Exercise 8.3.18 tells us that this is equivalent to: <strong>O<\/strong>(<em>X<\/em>)<em><sup>op<\/sup><\/em> is a completely distributive lattice.\u00a0 But <strong>O<\/strong>(<em>X<\/em>)<em><sup>op<\/sup><\/em> is order-isomorphic to <strong>H<\/strong>(<em>X<\/em>), using the complement map \u2201.\u00a0 This gives us the first part of the following proposition.<\/p>\n<p><strong>Proposition.<\/strong> For every c-space <em>X<\/em>, <strong>O<\/strong>(<em>X<\/em>) and <strong>H<\/strong>(<em>X<\/em>) are completely distributive lattices.\u00a0 The lower Vietoris topology on <strong>H<\/strong>(<em>X<\/em>) coincides with the Scott topology, and <strong>H<\/strong>(<em>X<\/em>) is a continuous dcpo.<\/p>\n<p>The second part of the proposition is proved as follows.\u00a0 Since <strong>H<\/strong>(<em>X<\/em>) is completely distributive, it is prime-continuous, hence in particular continuous.\u00a0 (Continuity is the only thing we care about in denotational semantics, usually, but note that we have much more: prime-continuity is <em>really<\/em> a stronger property.)\u00a0 I will leave the rest of the proof mostly implicit.\u00a0 Using the fact that every closed subset of <em>X<\/em> is a directed union of finitary closed subsets, we can show that <em>F<\/em> \u226a <em>F&#8217;<\/em> in <strong>H<\/strong>(<em>X<\/em>) if and only if there is a finite set <em>E<\/em> such that <em>F<\/em> is included in \u2193<em>E<\/em>, and such that for every <em>x<\/em> in <em>E<\/em>, there is an <em>y<\/em> in <em>F&#8217;<\/em> such that <em>x<\/em> \u226a<em> y<\/em> in <em>X<\/em>.\u00a0 The basic Scott-open subset \u219f<em>F<\/em> = {<em>F&#8217;<\/em> in <strong>H<\/strong>(<em>X<\/em>) | <em>F<\/em> \u226a <em>F&#8217;<\/em>} is then the union over all finite subsets <em>E<\/em> of <em>F<\/em> of the Scott-open subsets {<em>F&#8217;<\/em> in <strong>H<\/strong>(<em>X<\/em>) | for every <em>x<\/em> in <em>E<\/em>, there is an <em>y<\/em> in <em>F&#8217;<\/em> such that <em>x<\/em> \u226a<em> y<\/em> in <em>X<\/em>}.\u00a0 The latter are equal to the intersection over all <em>x<\/em> in <em>E<\/em> of \u25ca(\u219f<em>x<\/em>), hence are open in the lower Vietoris topology.\u00a0 Conversely, the lower Vietoris (=upper) topology is always coarser than the Scott topology, so the two topologies coincide.<\/p>\n<p>Note that the above lemma has a kind of converse, assuming\u00a0<em>X<\/em> sober.\u00a0 This is Lemma 8.3.42: if <strong>O<\/strong>(<em>X<\/em>), equivalently <strong>H<\/strong>(<em>X<\/em>), is a completely distributive lattice, then <em>X<\/em> is a c-space (hence a continuous dcpo in its Scott topology).<\/p>\n<p>In denotational semantics, the <em>Hoare powerdomain<\/em> is <strong>H<\/strong>(<em>X<\/em>), viewed as a dcpo.\u00a0 Directed suprema are obtained, as for any supremum, as closure of unions.\u00a0 This is always given with the Scott topology, just like any other dcpo.\u00a0\u00a0 However, most of the nice properties of the Hoare powerdomain stem from the nice properties of the Hoare hyperspace (namely, with the lower Vietoris topology).\u00a0 We have just seen that the two coincide when <em>X<\/em> is a c-space, e.g., a continuous dcpo.\u00a0 This is one of a long list of examples that support the idea that the mathematics of dcpos works (much) better with continuous dcpos.<\/p>\n<p style=\"text-align: right;\">\u2014 <a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/~goubault\/?l=en\" rel=\"attachment wp-att-993\">Jean Goubault-Larrecq<\/a>\u00a0(March 25th, 2015)<img loading=\"lazy\" decoding=\"async\" class=\"wp-image-993 alignright\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2016\/08\/jgl-2011.png\" alt=\"jgl-2011\" width=\"32\" height=\"44\" \/><\/p>\n<p>[1] Andrea Schalk.\u00a0 <a title=\"Andrea Schalk's PhD thesis\" href=\"https:\/\/www.cs.man.ac.uk\/~schalk\/publ\/diss.ps.gz\"><em>Algebras for Generalized Power Constructions<\/em><\/a>. PhD Thesis, TU Darmstadt, 1993.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>While a topological space is a space of points, a hyperspace is a space of subsets, with a suitable topology.\u00a0 Examples abound in the literature.\u00a0 For example, the so-called Smyth powerdomain (Proposition 8.3.25) is one.\u00a0 This is an example of &hellip; <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=585\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"footnotes":""},"class_list":["post-585","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/585","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=585"}],"version-history":[{"count":25,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/585\/revisions"}],"predecessor-version":[{"id":5959,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/585\/revisions\/5959"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=585"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}