Algebras of filter-related monads: II. KZ-monads

Alan Day [1] and Oswald Wyler [2] proved that the algebras of the filter monad on the category Top0 of T0 topological spaces are exactly the continuous (complete) lattices. Martín Escardó later gave a very interesting proof of this fact [3], using a category-theoretic construction due to Anders Kock [4] which he calls KZ-monads. My purpose is to talk about Escardó’s argument; but mostly, really, to put forward his notion of KZ-monad, which is a true categorical gem. I will show that, although KZ-monads are not as common as general monads, it is always useful to wonder whether a given monad is a KZ-monad, as this simplifies the study of its algebras considerably.

The filter monad on T0

The monad that Day [1] and Wyler [2] studied, the so-called filter monad, is defined as follows. Given any T0 topological space X, we form its filter space FOX as follows:

  • The points of FOX are the non-trivial filters of open subsets of X, namely the collections F of open subsets of X that are non-empty, upwards-closed, closed under binary intersections, and do not contain the empty set (i.e., are not the whole collection OX of open subsets of X). Note that, contrarily to Part I of this series of posts, we are considering filters of open sets, not filters of subsets.
  • The topology of FOX is generated by the subsets ☐U ≝ {FFOX | UF}, where U ranges over the open subsets of X. Those subsets form a base, not just a subbase, of the topology, since ☐U ∩ ☐V = ☐(UV), owing to the fact that filters are closed under binary intersections.

I will also consider FOX, the space of all filters (including the trivial filter OX), with a similarly defined topology. Their specialization ordering is inclusion.

We are not requiring the filters to be Scott-open, just filters of open sets. This construction is studied in Exercise 9.3.10 of the book, where it is asked to show that X embeds into FOX through ηX : x ↦ {UOX | xU}, mapping each point to its filter of open neighborhoods; additionally, the image of ηX is dense in FOX (with its Scott topology), FOX is an algebraic bc-domain, and its finite elements are the principal filters ■U ≝ {VOX | UV}. The upward closure of ■U in FOX is what we wrote as ☐U above, so the topology we gave to FOX is the Scott topology. The same happens with FOX.

In Exercise 9.3.11, it is required to show that every continuous map f : XZ, where Z is a bc-domain (with its Scott topology), extends to a continuous map f† : FOXZ, in the sense that f† o ηX = f. (Moreover, there is a largest such extension.) This entails that every bc-domain Z is densely injective, namely that every continuous map f from any space X to Z extends to any superspace of X in which X embeds as a dense subspace; see Exercise 9.3.12, where it is also required to prove that every densely injective topological space must be a bc-domain.

Using FOX instead of FOX, using a similar argument, we would obtain another proof of Scott’s theorem (Exercise 9.3.9) that the injective topological spaces are the complete continuous lattices.

Escardó showed that those notions of injectivity were strongly related to properties of the filter monads FO and FO. The complete details are given in [5], but I will not go to that level of generality.

The filter monad

Let me recall that a monad on a category C is a triple (T, η, †) consisting of the following data:

  • for each object X of C, an object TX in C
  • for each object X of C, a morphism ηXX → TX called the unit of the monad
  • an extension operation †, transforming every morphism fX → TY into a morphism fTX → TY, so that the following equations are satisfied:
    1. ηX = idTX
    2. for every morphism fX → TYf o ηX = f
    3. for all morphisms fX → TY and gY → TZ, (g o f) = g o f.

In that case, T gives rise to a functor from C to C, the various units assemble as a natural transformation, and there is also a multiplication natural transformation μ : TTT, defined on each object X by μX ≝ idTX. This satisfies a few monad laws, among which μX o ηTX = μX o TηX = idTX. (There is a third one, which I will not make any use of here.)

FO is a monad on Top (and on Top0). We have already defined the space FOX, the map ηX : x ↦ {UOX | xU} will serve as unit, and for every continuous map fX → FOY, we will use the largest extension f† of f to FOX introduced earlier. The action of FO on morphisms fX → Y is given by FO(f)(F) = f[F], the “image filter” map, namely f[F] = {VOY | f–1(V) ∈ F}. Similarly, FO is a monad.

For future reference, we note that ηX–1(☐U) = U.

KZ-monads

Here “KZ” is an abbreviation for “of Kock-Zöberlein type”. Technically, KZ-monads are monads on 2-categories [4], but, just like Escardó [3], we will be content with the more restricted setting of poset-enriched categories. This will relieve us of much of the complications of general 2-categories.

A poset-enriched category is a category C, equipped with orderings ≤ on each homset HomC(X, Y), in such a way that composition o is monotonic in each of its arguments. Top0 is poset-enriched: we simply write fg, for every pair of maps f, g ∈ HomC(X, Y), if and only if f(x) ≤Y g(x) for every xX, where ≤Y is the specialization ordering of Y; the fact that composition is monotonic in its arguments is due to the fact that every continuous map is monotonic with respect to the specialization orderings of its domain and of its codomain.

A functor F between poset-enriched categories is poset-enriched if and only if F is monotone on every homset, namely if and only if for all objects X and Y in the source category, for all morphisms f, g : X → Y, if fg then F(f)≤F(g).

A right KZ-monad (T, η, †) on a poset-enriched category C is one such that T is a poset-enriched functor, and such that ηTXTηX for every object X [3,5].

Now, look: FO is a right KZ-monad on TOP0. (Does that surprise you?)

This is proved as follows. First, let us consider two continuous maps f, g : X → Y such that fg. Then FOf(F) = f[F] = {VOY | f–1(V) ∈ F} is included in FOg(F) = g[F] = {VOY | g–1(V) ∈ F}, since if f–1(V) ∈ F, then g–1(V) contains f–1(V) (since fg and V is upwards-closed), hence g–1(V) is in F, since F is upwards-closed.

Second, for every filter FFOX, ηFOX(F) is the collection of open neighborhoods of F in FOX, while FOηX(F) = ηX[F] = {UOFOY | ηX–1(U) ∈ F}. In order to show that ηFOX(F) ⊆ FOηX(F), we consider any element of ηFOX(F), namely any open neighborhood U of F in FOX. By definition, U contains a basic open subset ☐U such that F ∈ ☐U, namely such that UF. Then ηX–1(U) contains ηX–1(☐U) = U, which is in F; by definition of FOηX(F), U is therefore in FOηX(F), which completes the argument.

Similarly, FO is also a right KZ-monad on TOP0.

The algebras of a right KZ-monad

In a poset-enriched category, there is a notion of adjoint maps. (No, not adjunctions—a different notion, but in the same spirit; in fact, in a 2-categorical perspective, they are really adjoint 1-cells, as defined with respect to the 2-cell structure.) We say that f : X → Y is left-adjoint to g : Y → X if and only if f o g ≤ idY and idXg o f . Then we write fg, and we also say that g is right-adjoint to f.

As in the usual case of poset adjunctions, right-adjoints are unique if they exist. (Similarly with left-adjoints.) Indeed, let us assume that we have two right-adjoints g, g’ to f : X → Y. Then g’ o f o gg’ since fg, and gg’ o f o g since fg‘, so gg’; symmetrically, g’g, so g=g’.

Let me remind you that an algebra of a monad (T, η, †) is an object X together with a morphism α : TXX (the structure map of the algebra) such that: α o ηX = idX and α o μX = α o Tα. I will simply call α itself the T-algebra.

The following lemma, in this form, is due to Escardó [5, Lemma 4.1.1], and is a restatement of a result of Kock, who proved it in a more general 2-categorical context [4]. This yields a rather unexpected characterization of the algebras of a right KZ-monad T: they are exactly certain right-adjoints to the unit ηX. In particular, since right-adjoints are unique if they exist, there is at most one structure of T-algebra on every object X, which is a pretty amazing feat.

Lemma (Kock-Escardó). Let (T, η, †) be a monad on a poset-enriched category C, where T is a poset-enriched functor. The following are equivalent:

  1. ηTXTηX for every object X (namely, T is a right KZ-monad);
  2. ηTX ⊣ μX for every object X;
  3. μXTηX for every object X;
  4. a morphism α : TXX is a T-algebra if and only if ηX ⊣ α and α o ηX = idX (i.e., iff it is a coreflective right-adjoint to the unit ηX);

Proof. We follow Escardó’s proof. We decompose claim 4 into its ‘if’ part and its ‘only if’ part, and we will call them [4⇐] and [4⇒], respectively.

1 ⇒ [4⇒]. The equality α o ηX = idX holds for every T-algebra α, by definition. We show that ηX o α ≤ idTX as follows: by naturality of η, ηX o α = Tα o ηX; that is ≤ Tα o TηX by 1 (and the fact that T is poset-enriched); then Tα o TηX = T(α o ηX) = idTX, since α o ηX = idX.

[4⇒] ⇒ 2. This is because μX : μ : TTXTX is a T-algebra (the free T-algebra) on TX, and is therefore right-adjoint to ηTX.

2 ⇒ [4⇐]. This is the clever part. Let us assume ηTX ⊣ μX, and let us consider a coreflective right-adjoint α to the unit ηX; namely, ηX ⊣ α and α o ηX = idX. The latter is one of the two conditions we need to ensure that is a T-algebra. The other one is α o μX = α o Tα, and we will prove it by showing that the two sides of the equality are right-adjoint to the same morphism.

  • By composing the adjunctions ηTX ⊣ μX with ηX ⊣ α, we obtain ηTX o ηX ⊣ α o μX. Explicitly, (ηTX o ηX) o (α o μX) = ηTX o (ηX o α) o μX ≤ ηTX o μX (because ηX ⊣ α, so ηX o α ≤ idTX) ≤ idTTX (because ηTX ⊣ μX); and (α o μX) o (ηTX o ηX) = α o (μX o ηTX) o ηX (because ηTX ⊣ μX) ≥ α o ηX = idX (really, μX o ηTX = idTX, by the monad laws, so we have an equality here).
  • Hence it remains to show that ηTX o ηX ⊣ α o Tα. Since η is natural, we have ηY o f = Tf o ηX for every morphism f : X → Y. In particular, if we take f ≝ ηTX (and YTX), we obtain that ηTX o ηX = TηX o ηX. Hence, instead of showing that ηTX o ηX ⊣ α o Tα, we will show that equivalent claim that TηX o ηX ⊣ α o Tα.
  • In order to show that TηX o ηX ⊣ α o Tα, we compute: (TηX o ηX) o (α o Tα) = TηX o (ηX o α) o Tα ≤ TηX o Tα = TX o α) ≤ idTTX; and (α o Tα) o (TηX o ηX) = α o (Tα o TηX) o ηX = α o ηX = idX.

Hence, as promised, both α o μX and α o Tα are right-adjoint to the same morphism, namely ηTX o ηX = TηX o ηX; so they are equal.

At this point, we have the chain of implications 1 ⇒ [4⇒] ⇒ 2 ⇒ [4⇐]. In particular, 1 implies both [4⇒] and [4⇐], hence implies 4; and 4, which implies [4⇐], therefore implies 2. In summary, we have proved 1 ⇒ 4 ⇒ 2.

2 ⇒ 1. Assumption 2 is that ηTX ⊣ μX. We wish to show that ηTXTηX. This is immediate: since ηTX ⊣ μX, (ηTX o μX) ≤ idTTX; we compose with TηX, so that ηTX o μX o TηXTηX. By one of the monad laws, μX o TηX = idTX, whence ηTXTηX.

Together with 1 ⇒ 4 ⇒ 2, we obtain that 1, 2, and 4 are equivalent.

1 ⇒ 3. Assumption 1 entails that ηTXTηX, and also that ηTTXTηTX. We wish to show that μXTηX. We have (μX o TηX) = idTX by one of the monad laws. In order to show that TηX o μX ≥ idTTX, we first use the naturality of μ in order to derive TηX o μX = μTX o TTηX. Since TηX ≥ ηTX, this is larger than or equal to μTX o TηTX. Since TηTX ≥ ηTTX, this is in turn larger than or equal to μTX o ηTTX = idTTX (using a monad law).

3 ⇒ 1. Assumption 3 is that μXTηX, so (TηX o μX) ≥ idTX. We compose with ηTX, so TηX o μX o ηTX ≥ ηTX. By one of the monad laws, μX o ηTX = idTX, so TηX ≥ ηTX. ☐

The algebras of the FO monad

Since the FO monad on TOP0 is a right KZ-monad, the above Lemma immediately tells us what its algebras are. Those are exactly the coreflective right-adjoints to the unit, namely the continuous maps α : FOXX such that ηX o α ≤ idFOX and α o ηX = idX.

In particular, if X has such an FO-algebra structure, then X must be a retract of FOX. Since FOX is a bc-domain and since bc-domain are closed under retracts, X must be a bc-domain.

Conversely, for every bc-domain X, there is a unique largest continuous extension of the identity map on X to the larger space FOX, as we have seen earlier: this is because bc-domains are densely injective spaces, and because X embeds as a dense subspace of FOX through ηX. Let us write α for this map. The fact that α extends idX means that α o ηX = idX. Exercise 9.3.11 of the book gives us an explicit formula for α: for every FFOX, α(F) = supUF inf U. (The notation inf U denotes the infimum of the non-empty collection of elements of U. That always exists in any bc-domain.) Since F is a filter, and inf U depends antitonically on U, the family of points inf U, when U ranges over F, is directed. Since the topology of X is the Scott topology, it follows that every open neighborhood V of α(F) contains inf U for some UF; if so, V contains the whole of U, since V is upwards-closed, and therefore V itself is in F. This shows that ηX(α(F)) is included in F. Therefore ηX o α ≤ idFOX.

By the above Lemma of right KZ-monads, this is enough to show that α is the structure map of an FO-algebra on X. Additionally, this is the only possible FO-algebra on X.

Similarly, the FO-algebras are exactly the continuous (complete) lattices, in a unique way, and we have retrieved the result we started this post with, due to Day and Wyler.

Are KZ-monads frequent?

That is hard to say. My impression is that KZ-monads are relatively rare, but that it is always a good idea to check, given any monad you might be interested in, whether it is KZ. If so, determining its algebras is really a lot simpler.

A first reason is that you need to work in a poset-enriched category. On Set, there is only one way to obtain a poset-enriched structure, and that is to equip each homset with the equality relation as ordering. A right KZ-monad is then one such that ηTX = TηX for every every object X, and the Kock-Escardó Lemma then says that it is equivalent to require that ηTX and μX are inverses for every object X, or that μX and TηX are inverses; or that, finally, there is a (unique) T-algebra on a set X if and only if ηX is an isomorphism, and the structure map must then be its inverse. Those are exactly the idempotent monads on Set.

For example, the powerset monad is not idempotent on Set, hence not right KZ.

On general poset-enriched category, any idempotent monad, namely any monad in which ηTX = TηX for every every object X, is a right KZ-monad, whatever poset enrichment we choose. For example, the sobrification monad S on Top0 is idempotent, hence right KZ. (Its algebras are the sober spaces.)

The Hoare powerspace monad H on Top0 is not idempotent. For every closed subset C of X, ηHX(C) is the collection of closed subsets of C, while HηX(C) is the closure cl {↓x | xC}. Hence, for example, taking X ≝ {a, b} with the discrete topology, and CX, ηHX(C) is the collection of all subsets of X, while HηX(C) only contains the empty set, {a}, and {b}.

However, HηX(C) is included in ηHX(C), because every set of the form ↓x with xC is a closed subset of C. This show that H is a left KZ-monad… not a right KZ-monad, but I am sure you had wondered whether those things existed from the very start (if there are right KZ-monads, then surely there must also be left KZ-monads).

A left KZ-monad is defined exactly as right KZ-monads, except with ≤ replaced by ≥. (In other words, left KZ-monads are right KZ-monads on the same category, except with the orderings on each homset reversed.) Explicitly, a left KZ-monad is a monad T such that ηTXTηX for every object X. The Kock-Escardó lemma for left KZ-monads reads as follows.

Lemma (Kock-Escardó). Let (T, η, †) be a monad on a poset-enriched category C, where T is a poset-enriched functor. The following are equivalent:

  1. ηTXTηX for every object X (namely, T is a left KZ-monad);
  2. μX ⊣ ηTX for every object X;
  3. TηX ⊣ μX for every object X;
  4. a morphism α : TXX is a T-algebra if and only if α ⊣ ηX and α o ηX = idX (i.e., iff it is a reflective left-adjoint to the unit ηX);

There is also a so-called Smyth powerspace monad Q on Top0, where QX is the space of compact saturated subsets of X, with the upper Vietoris topology, see this page for example. Apparently I have not yet stated here that this yields a monad. It does, and the unit maps every point x in a space X to the compact saturated set ↑x. The specialization ordering is reverse inclusion. In that case, QηX(Q) (the set of compact saturated subsets Q’ of X that are above, namely included in, Q) contains ηQX(C) (the set of compact saturated subsets Q’ of X that are included in ↑x for some x in Q). This looks like the opposite relation as with H, but remember that the specialization ordering is reverse inclusion. Hence Q is also a left KZ-monad.

It follows immediately that the Q-algebras, just like the H-algebras, are determined as the reflective left-adjoints to the unit, and are unique if they exist. That is all the nicer as we never had to look at the multiplication of the monad, thus saving us some complications! Indeed, the equivalence between 1 and 4 in the Kock-Escardó lemma does not mention multiplication at all.

The continuous valuation monad, which I have briefly talked about, for example here, is neither a left nor a right KZ-monad, though. The Plotkin powerspace monad, which is implicit here, is neither.

However, and to conclude with a positive note, the formal ball monad B on the category of quasi-metric spaces and 1-Lipschitz continuous maps is a left KZ-monad [6]. That allowed me to swiftly characterize the B-algebras α : BXX as the 1-Lipschitz maps that send every formal ball (x, r) to some point in the closed ball centered at x of radius r, and which send (x, 0) to x [6, Proposition 3.4]. This result extends to the category of standard quasi-metric spaces and 1-Lipschitz continuous maps, but that is a more technical result.

  1. Alan Day. Filter monads, continuous lattices and closure systems. Canadian Journal of Mathematics, XXVII(1):50–59, 1975.
  2. Oswald Wyler. Algebraic theories for continuous semilattices. Archive for Rational Mechanics and Analysis, 90(2):99–113, 1985.
  3. Martín Hötzel Escardó. Injective spaces via the filter monad. Topology Proceedings 22(2), 1997.
  4. Anders Kock. Monads for which structures are adjoint to units (version 3). Journal of Pure and Applied Algebra, 104:41–59, 1995.
  5. Martín Hötzel Escardó. Properly injective spaces and function spaces. Topology and its Applications 89:75–120, 1998.
  6. Jean Goubault-Larrecq. Formal ball monads. Topology and its Applications 263:372–391, 2019.
jgl-2011

Jean Goubault-Larrecq (August 20th, 2022)