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 Top₀ of T₀ 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 T₀

The monad that Day [1] and Wyler [2] studied, the so-called filter monad, is defined as follows. Given any T₀ 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 ≝ {F ∈ FOX | U ∈ F}, where U ranges over the open subsets of X. Those subsets form a base, not just a subbase, of the topology, since ☐U ∩ ☐V = ☐(U ∩ V), owing to the fact that filters are closed under binary intersections.

I will also consider FO^⊤X, 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 ↦ {U ∈ OX | x ∈ U}, 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 ≝ {V ∈ OX | U ⊆ V}. 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 FO^⊤X.

In Exercise 9.3.11, it is required to show that every continuous map f : X → Z, where Z is a bc-domain (with its Scott topology), extends to a continuous map f† : FOX → Z, 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 FO^⊤X 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 η_X : X → TX called the unit of the monad
• an extension operation †, transforming every morphism f : X → TY into a morphism f^† : TX → TY, so that the following equations are satisfied:
  1. η_X^† = id_TX
  2. for every morphism f : X → TY, f^† o η_X = f
  3. for all morphisms f : X → TY and g: Y → 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 μ : TT → T, defined on each object X by μ_X ≝ id_TX^†. This satisfies a few monad laws, among which μ_X o η_TX = μ_X o Tη_X = id_TX. (There is a third one, which I will not make any use of here.)

FO is a monad on Top (and on Top₀). We have already defined the space FOX, the map η_X : x ↦ {U ∈ OX | x ∈ U} will serve as unit, and for every continuous map f : X → FOY, we will use the largest extension f† of f to FOX introduced earlier. The action of FO on morphisms f : X → Y is given by FO(f)(F) = f[F], the “image filter” map, namely f[F] = {V ∈ OY | 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 Hom_C(X, Y), in such a way that composition o is monotonic in each of its arguments. Top₀ is poset-enriched: we simply write f≤g, for every pair of maps f, g ∈ Hom_C(X, Y), if and only if f(x) ≤_Y g(x) for every x ∈ X, 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 f≤g 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 η_TX ≤ Tη_X for every object X [3,5].

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

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

Second, for every filter F ∈ FOX, η_FOX(F) is the collection of open neighborhoods of F in FOX, while FOη_X(F) = η_X[F] = {U ∈ OFOY | η_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 U ∈ F. 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 TOP₀.

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 ≤ id_Y and id_X ≤ g o f . Then we write f ⊣ g, 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 g ≤ g’ since f ⊣ g, and g ≤ g’ o f o g since f ⊣ g‘, so g ≤ g’; 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 α : TX → X (the structure map of the algebra) such that: α o η_X = id_X 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. η_TX ≤ Tη_X for every object X (namely, T is a right KZ-monad);
2. η_TX ⊣ μ_X for every object X;
3. μ_X ⊣ Tη_X for every object X;
4. a morphism α : TX → X is a T-algebra if and only if η_X ⊣ α and α o η_X = id_X (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 = id_X holds for every T-algebra α, by definition. We show that η_X o α ≤ id_TX 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) = id_TX, since α o η_X = id_X.

[4⇒] ⇒ 2. This is because μ_X : μ : TTX → TX 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 = id_X. 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 α ≤ id_TX) ≤ id_TTX (because η_TX ⊣ μ_X); and (α o μ_X) o (η_TX o η_X) = α o (μ_X o η_TX) o η_X (because η_TX ⊣ μ_X) ≥ α o η_X = id_X (really, μ_X o η_TX = id_TX, 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 Y ≝ TX), 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α = T (η_X o α) ≤ id_TTX; and (α o Tα) o (Tη_X o η_X) = α o (Tα o Tη_X) o η_X = α o η_X = id_X.

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 η_TX ≤ Tη_X. This is immediate: since η_TX ⊣ μ_X, (η_TX o μ_X) ≤ id_TTX; we compose with Tη_X, so that η_TX o μ_X o Tη_X ≤ Tη_X. By one of the monad laws, μ_X o Tη_X = id_TX, whence η_TX ≤ Tη_X.

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

1 ⇒ 3. Assumption 1 entails that η_TX ≤ Tη_X, and also that η_TTX ≤ Tη_TX. We wish to show that μ_X ⊣ Tη_X. We have (μ_X o Tη_X) = id_TX by one of the monad laws. In order to show that Tη_X o μ_X ≥ id_TTX, 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 = id_TTX (using a monad law).

3 ⇒ 1. Assumption 3 is that μ_X ⊣ Tη_X, so (Tη_X o μ_X) ≥ id_TX. We compose with η_TX, so Tη_X o μ_X o η_TX ≥ η_TX. By one of the monad laws, μ_X o η_TX = id_TX, so Tη_X ≥ η_TX. ☐

The algebras of the FO monad

Since the FO monad on TOP₀ 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 α : FOX → X such that η_X o α ≤ id_FOX and α o η_X = id_X.

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 id_X means that α o η_X = id_X. Exercise 9.3.11 of the book gives us an explicit formula for α: for every F ∈ FOX, α(F) = sup_{U ∈ F} 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 U ∈ F; 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 α ≤ id_FOX.

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 Top₀ is idempotent, hence right KZ. (Its algebras are the sober spaces.)

The Hoare powerspace monad H on Top₀ 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 | x ∈ C}. Hence, for example, taking X ≝ {a, b} with the discrete topology, and C ≝ X, η_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 x ∈ C 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 η_TX ≥ Tη_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. η_TX ≥ Tη_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 α : TX → X is a T-algebra if and only if α ⊣ η_X and α o η_X = id_X (i.e., iff it is a reflective left-adjoint to the unit η_X);

There is also a so-called Smyth powerspace monad Q on Top₀, 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 α : BX → X 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.

— Jean Goubault-Larrecq (August 20th, 2022)