Powerdomains and hyperspaces III: the theory of H

Last time, we have seen that the Hoare powerspace construction defined a monad H on Top.  I also said that H(X) obeyed the following (in)equational theory:

  • (unit) a ∨ 0 = a
  • (associativity) (ab) ∨ c = a ∨ (bc)
  • (commutativity) ab = ba
  • (idempotence) aa = a
  • (inflationary) aab

This is true, in the following, very weak sense: if you interpret ∨ as binary union of closed sets, 0 as the empty set, and ≤ as inclusion, then those (in)equalities are trivially satisfied.  A topological space with a continuous map ∨ satisfying the above (in)equalities is called a unital inflationary topological semi-lattice.

We shall see a much stronger fact: for each space X, H(X) is the free sober inflationary unital topological semi-lattice above X. This is again due to Schalk [1]. I’ll also explain what the relation to monads is.

The theory of H

A semi-lattice is a set together with a binary operation ⋁ that is associative, commutative, and idempotent. It is unital if and only if there is an element 0 such that 0 ⋁ a = a ⋁ 0 = a for every a. (Think of a sup-semi-lattice, where 0 is bottom, and ⋁ is supremum.) It is topological if the underlying set is a topological space, and ⋁ is continuous. In that case, the topological space has a specialization ordering ≤, and it makes sense to define a topological semi-lattice to be inflationary if and only if aab for all a, b.

There is a category SUITopSLat (I apologize for the barbaric name; I could not think of any better name) of sober, unital, inflationary topological semi-lattices whose objects are those we just described, and whose morphisms are continuous maps that send 0 to 0 and preserve the semi-lattice operation ⋁.

There is a forgetful functor U : SUITopSLatTop, which maps every such topological semi-lattice to the underlying topological space, forgetting about 0, ⋁, and sobriety. In the other direction, there is a function H that maps every topological space X to its Hoare powerspace. Remember also that there is a continuous map ηX from X to H(X), which sends every point x to its closure ↓x. Categorically speaking, ηX is a morphism in Top from X to UH(X).

To show that H extends to a functor that is left adjoint to U, we only have to show that H(X) is the free sober unital inflationary topological semi-lattice over X (Diagram (5.2), p.175, in the book). That means the following: for every morphism f: XUL in Top (i.e., continuous map from X to L, where L is any sober unital inflationary topological semi-lattice), there should be a unique morphism h from H(X) to L in SUITopSLat such that Uh o ηX = f —namely, such that h(↓x)=f(x) for every x in X.

If h exists, then we claim that we have no choice. For every finite subset E={x1, …, xn} of X, h(↓E) must be equal to h(↓x1 ⋃ … ⋃ ↓xn) = h(↓x1) ⋁ … ⋁ h(↓xn) = f(x1) ⋁ … ⋁ f(xn). Write the latter as ⋁f(E), at least temporarily. This tells us what the values of h must be on finitary closed subsets of X: h(↓E)=⋁f(E).  By continuity, this will also determine h on every element of H(X), as we now observe.

For every element F of H(X), the finite subsets E of F form a directed family I, ordered by inclusion. When E is included in E’, we can write E’ as the union of E and of some other finite set E”, and then ⋁f(E‘) = ⋁f(E) ⋁ ⋁f(E”), which is above ⋁f(E) since L is inflationary. It follows that the family of all elements ⋁f(E), when E ranges over the finite subsets of F, is a directed family. Since L is sober, those elements have a supremum y=sup {⋁f(E) | E finite subset of F} and cl {⋁f(E) | E finite subset of F} = ↓y (Proposition 8.2.34). Because h is monotonic (if it exists), we must have y = sup {h(↓E) | E finite subset of F} ≤ h(F).

Observe now that F is a limit (in fact, the largest limit) of the monotone net {↓E | E finite subset of F}. Indeed, if F is in ◊U, then F intersects U, say at x, and then any finite subset E of F that contains x will be in ◊U. Since h is continuous, h(F) must therefore be a limit of the monotone net {⋁f(E) | E finite subset of F}. However, all these limits are in cl {⋁f(E) | E finite subset of F} = ↓y, so h(F) ≤ y. This shows that h(F) is uniquely determined, and must be equal to the element y defined above.

We have no choice for h. So let us define it as above: h(F) = sup {⋁f(E) | E finite subset of F}, and recall that cl {⋁f(E) | E finite subset of F} = ↓h(F). We use the latter to show that h is continuous.

For every open subset V of L that contains h(F), V must intersect cl {⋁f(E) | E finite subset of F}, so V must also intersect {⋁f(E) | E finite subset of F}. Let E={x1, …, xn} be a finite subset of F such that ⋁f(E) = f(x1) ⋁ … ⋁ f(xn) belongs to V. Since ⋁ is continuous, there are n open neighborhoods V1, …, Vn, of f(x1), …, f(xn) respectively, such that y1 ⋁ … ⋁ yn is in V for all y1 in V1, …, yn in Vn. Then ◊f-1 (V1) ∩ … ∩ ◊f-1 (Vn) is an open neighborhood of F in H(X). Moreover, for every F’ in ◊f-1 (V1) ∩ … ∩ ◊f-1 (Vn), there must be n points x’1, …, x’n in F’ such that f(x’1), …, f(x’n) are in V1, …, Vn respectively, hence so that ⋁f(E‘) is in V, for E’={x’1, …, x’n}. This implies that h(F’) is in V, and as V is arbitrary, that h is continuous at F. Since F is arbitrary, h is continuous.

Verifying that h preserves 0 and ⋁ is much easier, as is the fact that h(↓x)=f(x) for every x in X. This concludes the proof. We sum that up.  The result is due to A. Schalk, again.

Theorem. [1, Theorem 6.1] For every topological space XH(X) is the free sober unital inflationary topological semi-lattice over X.

Monad algebras

The above theorem establishes the existence of an adjunction H ⊣ U, but does it say anything about the monad H?

We need to say a few more things about monads, and their relationship to adjunctions.

There is an automatic way of building monads: every adjunction FU gives rise to a monad T=UF. (The latter means U o F.) The unit of the monad is just the unit ηX: XUFX of the adjunction. The extension f of f: X → UFY is given by composing UεFX with UF(f), where ε is the counit of the adjunction; alternatively, f = U(ranX, FY f). (See Section 5.5.2 for a refresher on adjunctions!)

I’ll let you check that the monad is equal to the monad obtained in this way from the adjunction H ⊣ U.  (I hope you’re not troubled by the two functors H.  The first one is really UH.)

Conversely, does every monad T stem from an adjunction this way? Yes, and yes.

I mean: yes, in at least two different ways.

The first way is provided by the Kleisli construction, and the second way will require a new notion: (Eilenberg-Moore) T-algebras.

  • (Kleisli) There is an adjunction between the Kleisli category CT and the original category C. On the one hand, FCCT maps every object X to itself, and every morphism f: XY to ηY o f. On the other hand, U: CTC maps every object X to TX, and every morphism fX → Y in CT (namely, a morphism fX → TY in C!) to f.  If you love pushing symbols, it is a fun exercise to check that F is left adjoint to U and that UF=T.
  • (Eilenberg-Moore) We build the category CT of T-algebras as follows.  (Note that T is now a superscript instead of a subscript…)
    T-algebra is, by definition, a pair of an object X of C and of a morphism sTX → X (the so-called structure map) such that s o ηX = idX and sTss o μX. Recall that μX = idTX: T2X → TX is the multiplication of the monad T.  A morphism of T-algebras, from (Xs) to (Yt) is just a morphism f from X to Y in C such that tTffs.
    With that construction, the left adjoint FCCT maps every object X to the algebra (TX, μX), and the right adjoint U: CTC maps every T-algebra (X, s) to X. If you love pushing symbols, it is even funnier to check that F is left adjoint to U, and that UF=T. (If you don’t love pushing symbols, then it’s just boring.)

We shall look at the H monad below.  We shall see that the H-algebras are the sober unital inflationary semi-lattices… again!  (This is a cunning plan meant to keep you reading.)

To get our hands on the notion of T-algebra, let us look at the powerset monad P on Set.

I claim that the algebras of the powerset monad P on Set are exactly the sup-semi-lattices (with bottom), more precisely, a P-algebra (Xs) is just a set X, together with a map s that sends every subset of X to its supremum.  For which ordering, you might ask?  (This is on sets, not topological spaces, so we do not have an underlying specialization preordering.)  Well, the only possible one: x ≤ y if and only if ys ({xy}). The algebra equations s o ηX = idX and sTss o μX require that s ({x}) = x and that, for every family (Fi)i in I, s (∪i in I Fi) = s ({s (Fi) | i in I}).  If you believe that s is a form of supremum, the latter says that the sup of a union of sets Fi can also be computed as the sup of the collection of individual suprema s (Fi), so that sounds reasonable.  Checking that ≤ is an ordering and that s is indeed the supremum operation for that ordering follows from those two equations alone (exercise!).

In general, it is hard to identify what the T-algebras are for a given monad T.  For example, the algebras of the ultrafilter monad on Set are exactly the compact Hausdorff spaces (the structure map s maps every ultrafilter to its unique limit), but this is a pretty hard theorem by Michael Barr—that such algebras are kinds of filter spaces is clear, what is harder is to show that the convergence structures must stem from a topology.

The algebras of the H monad

The case of the algebras of the H monad is comparatively easy.  Similarly to the case of the powerset monad, an H-algebra is a pair (Xs) where X is a topological space and s is a continuous map from H(X) to X, such that s(↓x)=x, and such that, for every family (Fi)i in I of closed subsets of Xs (cl (∪i in I Fi)) = s (cl {s (Fi) | i in I}).

Given s, we can define a binary operation ∨ on X by xy = s (↓{x, y}). This is automatically continuous, and the above equations (taking finite families) show that ∨ is unital, associative, commutative, and idempotent. (The unit 0 is the empty set.) For example, associativity is proved as follows. Consider the family (↓{x, y}, ↓{z}). The equations imply that s (↓{x, y, z}) = s (↓{s ({xy}), s (↓x)}) = (x ∨ y) ∨ z.  We obtain a second equation s (↓{xyz}) =  x ∨ (y ∨ z) by considering the family (↓{x}, ↓{yz}).  Associativity follows.

The ∨ operation is also inflationary: since s is continuous, hence monotonic, s (↓x) ≤ s (↓{xy}), namely xx ∨ y.

You may see a difference with the powerset monad here.  In the case of P, we needed an infinitary operation s, which worked as a supremum.  In the case of H, we only need a binary supremum operation ∨, and the infinitary suprema will be obtained by continuity.

Finally, the space X must be sober.  Indeed, the pair (s, ηX) defines a retraction of H(X) onto X, by definition of the structure map s. Recall that H(X) is sober (from Part I), and use the fact that every retract of a sober space is sober. The latter is Exercise 8.2.43 in the book (the proof proceeds by checking the definition, and contains no technical difficulty: try it!).
We have proved half of the following, of which we prove the other half right away.  This is again due to A. Schalk.

Theorem.  [1, Theorem 6.10] The algebras of the H monad are the sober unital inflationary topological semi-lattices.

We have just proved that all H-algebras are sober unital inflationary topological semi-lattices.  Conversely, let (X, ∨, 0) be a sober unital inflationary topological semi-lattice.  We use Schalk’s previous theorem, that H(X) is the free sober unital inflationary topological semi-lattice on X (=U(X, ∨, 0)).  The very definition of freeness (see Diagram (5.2), p.175), applied to the identity map from X to U(X, ∨, 0), implies that there is a unique morphism of sober unital inflationary topological semi-lattices t : H(X) → (X, ∨, 0) such that Ut o ηX is the identity.  We let s = Ut, and claim this is our structure map.  Verifying the algebra equations is done purely categorically: s o ηX = id is given; for the other equation, s o Hs = s o μX, we realize that both sides are morphisms of sober unital inflationary topological semi-lattices (as compositions of such morphisms), and we now just have to resort to freeness: we show that both sides of the equation are the unique morphism f such that Uf o ηHX = s (exercise!  use the naturality of η and the defining equation of s on the left-hand side, and one of the monad equations on the right-hand side).

A coincidence?

We have an intriguing coincidence here:

  • The algebras of the H monad are the objects of a certain category (sober unital inflationary topological semi-lattices); although we have not checked so, the morphisms are the right ones, too;
  • For every space XH(X) is the free object of the same category.
In other words: take the adjunction H ⊣ U, build the associated monad T = UH, giving rise to an Eilenberg-Moore category C (with C = Top here), which in turns gives rise to an adjunction. It turns out that the adjunction we get in the end is exactly the same as the one we started with (up to equivalence of categories, formally).
When this happens, we say that the adjunction is monadic.  This is a desirable property to have.  There is a whole theory on that: look for comparison functors, Beck’s monadicity theorem, and also Duskin’s monadicity theorem (on nLab).  If you are seriously into categorical stuff, have a look at the recent book [2] (Section II.3).  This would lead me too far, and I have really said a lot already.

In any case, and somewhat more vaguely, we can sum up the nice situation we are in by the motto:

The theory of H is the theory of (sober) unital inflationary topological semi-lattices.

We recapitulate that theory, for completeness:
  • (unit) a ∨ 0 = a
  • (associativity) (a ∨ b) ∨ c = a ∨ (b ∨ c)
  • (commutativity) a ∨ b = b ∨ a
  • (idempotence) a ∨ a = a
  • (inflationary) a ≤ a ∨ b

Jean Goubault-Larrecqjgl-2011

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

[2] Dirk Hofmann, Gavin J. Seal, Walter Tholen, eds.  Monoidal Topology—A Categorical Approach to Order, Metric, and Topology.   Encyclopedia of Mathematics and its Applications 153, Cambridge University, Sep. 2014.


Leave a Reply