Powerdomains and hyperspaces I: closed and open subsets

While a topological space is a space of points, a hyperspace is a space of subsets, with a suitable topology.  Examples abound in the literature.  For example, the so-called Smyth powerdomain (Proposition 8.3.25) is one.  This is an example of particular importance in denotational semantics, and elsewhere, too.  However, this time I’ll concentrate on the Hoare hyperspace, and I’ll give you some of the topological properties it enjoys.  Next time, I will talk about its algebraic theory, and monads.

The space of closed subsets of a space

Consider the space H(X) of all closed subsets of X.  This is mentioned in Exercise 9.7.14, where it is proved that H(X) is Noetherian for every Noetherian space X (there is an additional V subscript in the book, too, for “Vietoris”, which I will simply dispense with here).

The topology we take is the so-called lower Vietoris topology, whose subbasic open subsets are those of the form ◊U, U open in X.  By definition ◊U is the set of closed sets F of X that intersect U.  This yields a topology whose specialization ordering is ordinary inclusion.

I call H(X) the Hoare hyperspace, because a similar construction is used in denotational semantics, using the Scott topology instead, which is called the Hoare powerdomain.  (This construction is due to Mike Smyth, but one had to make a distinction with the Smyth hyperspace, also due to Mike Smyth.)  There is also a variant where the empty set is excluded, but I won’t be fussy about that.

It is easy to see that the lower Vietoris topology on H(X) is just a fancy other name for the upper topology, so that it is always coarser than the Scott topology.  The two topologies coincide when X is a continuous dcpo, or more generally, a c-space—as we shall see as the very last result of this post.

In general, given a space TX of subsets of X, the lower Vietoris topology is generated by subsets of the form ◊U, consisting of those elements of TX that intersect U, while the upper Vietoris topology is generated by subsets of the form □U, U open, defined as the set of elements of TX that are included in U.  (See Lemma 8.3.26.)  The Vietoris topology is the coarsest topology containing both.  So we consider just a one-sided version here.

There are many things we can say about the Hoare powerspace.  For example:

Proposition. H(X) is always sober, for every space X.

This is due to Andrea Schalk in her PhD thesis [1, Proposition 1.7].  More generally, she proved that every complete lattice L is sober in its upper topology.  The application to H(X) is direct: H(X) 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.

It remains to prove that every complete lattice L is sober in its upper topology.  Consider any irreducible closed subset F of L.  We can write it as an intersection of finitary closed subsets ↓Ei, i in I.  Writing the finite set Ei as the union of finitely many closed sets ↓x, x in Ei, and realizing that F is included in that finite union, F must be included in ↓x for just one point x of Ei, by irreducibility.  Call xi that point.  Since F ⊆ ↓xi ⊆ ↓Ei, we see that F is equal to the intersection of the sets ↓xi, i in I.  But that is just the downward closure of the infimum of the points xi, i in I.  Since L is clearly T0, this concludes the proof.

Another useful property is that the sobrification S(X) of X embeds into H(X).  This takes one of the simplest possible forms:

Proposition. S(X) is a subspace of H(X).

Indeed, every element of S(X) (an irreducible closed subset) is a closed subset of X in particular.  What the proposition says, as well, is that the subspace topology is the hull-kernel topology on S(X).  But the open subsets in the hull-kernel topology are precisely the sets of irreducible closed subsets that intersect a fixed open subset U of X, and these are exactly the sets of the form ◊US(X).

In particular, the map ηX: XS(X), which sends every point x to its closure, and which is an embedding of X into S(X) (provided X is T0), gives rise to an embedding of X into H(X).  I’ll again write that embedding ηX.

While we are examining the structural properties of H(X), I’ll show you what happens when X is core-compact (for example, locally compact).  Andrea Schalk had proved that H(X) was locally compact in that case, but we can say much more.  As we shall see, H(X) is even stably compact in that case.  A funny way to show that is to examine another, related powerspace: the space O(X) of all open subsets of X.

The space of opens of a space

Let O(X) be the space of all open subsets of X.  Since it is a dcpo, we might think that the important topology on O(X) should be the Scott topology, but let us not commit to any specific choice yet.

This is an important hyperspace, although it is rarely considered as such in the literature.  We encounter it in Definition 5.2.1 of the book.  In Section 5.2.1, we see that a space X is core-compact (a slight generalization of local compactness) if and only if O(X) is a continuous dcpo.  In fact, I cheated and defined the core-compact spaces X as those such that O(X) is a continuous dcpo, and then we have seen:

  • a more concrete definition: X is core-compact if and only if, for every point x of X, every open neighborhood V of x contains an open neighborhood U of x that is way-below V, namely such that every open cover of V contains a finite subcover of U;
  • an equivalent caracterization: X is core-compact if and only if X is exponentiable in the category Top of topological spaces (Theorem 5.4.4);
  • an important special case: every locally compact space is core-compact, and in that case U is way-below V if and only if there is a compact saturated set Q that we can insert between U and V;
  • a strengthening of the latter, showing that the core-compact spaces are exactly those spaces whose sobrification is locally compact (Proposition 8.3.11).

Consider the lower topology on O(X).  In general, the lower topology on a poset L has a subbasis of closed subsets formed by the finitary closed subsets ↑E, where E is a finite subset of L.  Here we consider L=O(X), ordered by inclusion.  Notice that we use upward arrows here: we would obtain the upper topology if we had used downward arrows (↓E) instead, as we did in discussing the Hoare powerspace earlier.  (I know, it is confusing.) Note that the lower topology on L is the same as the upper topology on Lop.

The complements of open subsets are the closed subsets, hence we have the trivial observation:

Fact.  The map ∁ that sends every open set to its complement is a homeomorphism from O(X) with its lower topology onto H(X) with its upper (=lower Vietoris) topology.

This means, for example, that S(X) also embeds into O(X).  Explicitly, the embedding maps every irreducible closed subset to its complement.  Those complements of irreducible closed subsets are exactly the prime elements of the lattice O(X) (see Proposition 8.1.20), namely the elements of pt(O(X)).  That should come as no surprise since we know that the latter is homeomorphic to S(X).

The new thing is that we can also examine the Scott topology on O(X).  We know that it coincides with the Isbell topology (Exercise 5.4.12).  The Isbell topology is splitting (Exercise 5.4.10), and the Scott topology is conjoining if and only if X is core-compact (this is what Exercise 5.2.7 states, in disguise).  In particular:

Lemma.  The Scott topology on O(X) is conjoining (namely, the graph of the membership relation is open in the product topology, of X and O(X) with its Scott topology) if and only if it is exponential, if and only if X is exponentiable, if and only if X is core-compact.

There is little point in comparing the Scott topology with the lower topology (which we examined earlier).  The specialization ordering of the former is inclusion, while that of the latter is reverse inclusion.

Instead, let us consider the Lawson topology, namely, the coarsest topology that contains both the Scott and the lower topology (Exercise 9.1.21).  The Lawson topology on a continuous (or even a quasi-continuous) poset is T2, and in fact a pospace.  Therefore O(X) is T2 in its Lawson topology as soon as X is core-compact, and a pospace when equipped with inclusion.  By the way, Exercise 9.1.36 establishes that the Lawson topology on O(X) is the same as the patch topology, if X is a continuous poset or a quasi-continuous dcpo.

We have much more: if X is core-compact, then O(X) is a continuous complete lattice, hence is stably compact in its Scott topology (Fact 9.1.6).  It follows that O(X) is a compact pospace in its Lawson (=patch) topology—one of the nicest kind of spaces in existence.  This deserves a formal statement:

Proposition.  For every core-compact space X, O(X) is compact T2 in its Lawson (=patch) topology.  With inclusion, it is a compact pospace.

Exercise 9.1.36 also establishes that the lower topology on O(X) is the de Groot dual of the Scott topology.  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.

Theorem.  If X is core-compact, then:

  • O(X) is stably compact in its lower topology, and
  • H(X) is stably compact in its upper (=lower Vietoris) topology.

In particular, both powerspaces are compact T2 in the corresponding patch topologies.

Continuous dcpos of closed subsets

We finish this tour of the structural properties of the spaces H(X) and O(X) by mentioning the fact that, when X is a c-space (e.g., a continuous dcpo), then O(X) is a prime-continuous complete lattice (Lemma 8.3.41).  Raney’s Theorem (Exercise 8.3.16) says that this is equivalent to: O(X) is a completely distributive lattice.  Exercise 8.3.18 tells us that this is equivalent to: O(X)op is a completely distributive lattice.  But O(X)op is order-isomorphic to H(X), using the complement map ∁.  This gives us the first part of the following proposition.

Proposition. For every c-space X, O(X) and H(X) are completely distributive lattices.  The lower Vietoris topology on H(X) coincides with the Scott topology, and H(X) is a continuous dcpo.

The second part of the proposition is proved as follows.  Since H(X) is completely distributive, it is prime-continuous, hence in particular continuous.  (Continuity is the only thing we care about in denotational semantics, usually, but note that we have much more: prime-continuity is really a stronger property.)  I will leave the rest of the proof mostly implicit.  Using the fact that every closed subset of X is a directed union of finitary closed subsets, we can show that FF’ in H(X) if and only if there is a finite set E such that F is included in ↓E, and such that for every x in E, there is an y in F’ such that x y in X.  The basic Scott-open subset ↟F = {F’ in H(X) | FF’} is then the union over all finite subsets E of F of the Scott-open subsets {F’ in H(X) | for every x in E, there is an y in F’ such that x y in X}.  The latter are equal to the intersection over all x in E of ◊(↟x), hence are open in the lower Vietoris topology.  Conversely, the lower Vietoris (=upper) topology is always coarser than the Scott topology, so the two topologies coincide.

Note that the above lemma has a kind of converse, assuming X sober.  This is Lemma 8.3.42: if O(X), equivalently H(X), is a completely distributive lattice, then X is a c-space (hence a continuous dcpo in its Scott topology).

In denotational semantics, the Hoare powerdomain is H(X), viewed as a dcpo.  Directed suprema are obtained, as for any supremum, as closure of unions.  This is always given with the Scott topology, just like any other dcpo.   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).  We have just seen that the two coincide when X is a c-space, e.g., a continuous dcpo.  This is one of a long list of examples that support the idea that the mathematics of dcpos works (much) better with continuous dcpos.

Jean Goubault-Larrecqjgl-2011

[1] Andrea Schalk.  Algebras for Generalized Power Constructions. PhD Thesis, TU Darmstadt, 1993.

 

Leave a Reply