Theory and Applications of Categories, Vol. 21, No. 7, 2008, pp. 118–151.

EXTENSIONS IN THE THEORY OF LAX ALGEBRAS

Dedicated to Walter Tholen on the occasion of his 60th birthday

CHRISTOPH SCHUBERT AND GAVIN J. SEAL

Abstract. Recent investigations of lax algebras—in generalization of Barr’s relational algebras—make an essential use of lax extensions of monad functors on Set to the category Rel(V) of sets and V-relations (where V is a unital quantale). For a given monad there may be many such lax extensions, and different constructions appear in the literature. The aim of this article is to shed a unifying light on these lax extensions, and present a symptomatic situation in which distinct monads yield isomorphic categories of lax algebras.

1. Introduction

In addition to a monad 𝕋 on Set and a unital quantale V, the definition of (𝕋, V)-algebras requires a lax extension of the monad functor T to V-Rel, the 2-category of sets and Vrelations. Until recently, such extensions were obtained by using Barr’s original construction [2] (indeed, if 2 denotes the two-chain {⊥, ⊤}, then 2-Rel is just the category Rel of sets and relations). In [3], Clementino and Hofmann describe a process that essentially produces a lax extension to V-Rel out of a lax extension to Rel. Two other constructions were proposed by Seal: the first, in [19], was based on the assumption that 𝕋 was a taut monad, while the second, in [20], required that the monad be conveniently Sup-enriched. In other directions, Schubert [18] showed that Barr’s method could be adapted to an order-based setting, and Hofmann [10] generalized the original construction by exploiting the structure of a particular Eilenberg-Moore algebra on V.

These extensions all yield topological spaces as instances of lax algebras, but they are nonetheless very different in nature, and therefore in their realizations. Roughly put, the lax extensions obtained via Barr’s construction are Set-based and do not take into account any order-related considerations, on the contrary of those introduced by Schubert, which are intrinsically Ord-based; the lax extensions studied by Seal live in-between the previous two, as they are originally defined over Set, but nonetheless exploit an existing underlying order of the monad. Thus, even in the simple case where V = 2, these constructions lead to very different lax extensions (a striking illustration of this is given in Example 4.6(3)). The intent of this article is to study the Kleisli extension introduced in [20] for Sup-enriched monads, and its interaction with four other types of extensions: the initial extension of a Set-functor described below, the canonical and op-canonical extensions of a taut Set-functor defined in [19], the strata extension of a lax Rel-functor [3], and the tower extension of a topological category [21].

The first author gratefully acknowledges a Ph.D.-scholarship from the Ernst A.-C. Lange Stiftung, Bremen. The second author gratefully acknowledges financial support by the Swiss National Science Foundation.

Received by the editors 2007-09-20 and, in revised form, 2008-11-06.

Published on 2008-11-07 in the Tholen Festschrift.

2000 Mathematics Subject Classification: 18C20, 18B30, 54A05.

Key words and phrases: lax algebra, Kleisli extension, initial extension, strata extension, tower extension.

\begin{matrix}c \\ ◯ \end{matrix} Christoph Schubert and Gavin J. Seal, 2008. Permission to copy for private use granted.

The multiplicity of lax extensions is a manifestation of a rich ambient categorical structure; indeed, for a fixed V, lax extensions are the objects of a “topological quasicategory” over the quasicategory of Set-endofunctors (see 3.5 for details). This remark leads us to a central theme of our work: if 𝕋 is provided with a lax extension \overline{T}, then any monad morphism α : 𝕊 → 𝕋 allows for a lax extension \overline{S} of S via the initial lift of α : S → \overline{T}. For example, the “op-canonical” extension of a taut functor described in [19] is obtained as an initial lift of the filter functor’s Kleisli extension.

More generally, if one considers for \overline{T} the Kleisli extension of T, the initial lift construction allows us to identify the category Alg(𝕊, 2) of (𝕊, 2)-algebras with the conceptually simpler category KlMon(𝕋) of Kleisli monoids. This is the theme of Theorem 5.6. The strata extension of \overline{S} then provides a suitable ingredient to pass from Alg(𝕊, 2) to Alg(𝕊, V), while the tower extension of KlMon(𝕋) yields a category KlMon(𝕋, V). Theorem 6.10 exploits the previous result to show that these new categories are again isomorphic, emphasizing in the process the importance of the original V = 2 case.

The examples used throughout this work support the thesis that “topological-related” lax extensions tend to appear either as Kleisli extensions, or as initial lifts of these (Example 4.6(2)). A similar line of investigation has been followed by Colebunders and Lowen in [5], where the authors show that many important lax extensions are initial extensions of a certain “functional power monad”.

2. The setting

2.1. Quantales.. Throughout this article, V = (V, ⊗, k) denotes a unital quantale with tensor ⊗, and unit k. In other words, V is a complete lattice equipped with an associative binary operation ⊗ that preserves suprema in each variable, and admits k as neutral element:

(_{⋁i∈I}u_{i}) ⊗ v = _{⋁i∈I}(u_{i} ⊗ v) ,  u ⊗ (_{⋁i∈I}v_{i}) = _{⋁i∈I}(u ⊗ v_{i}) ,  k ⊗ v = v = v ⊗ k ,

for all u, v, u_{i}, v_{i} ∈ V (i ∈ I). The bottom and top elements of V are denoted by ⊥ and ⊤, respectively. In this article, we always suppose that V is non-trivial, that is, V is not a singleton (or equivalently, ⊥ ≠ k). Moreover, the quantale is said to be integral if k = ⊤.

2.2. Examples.

1. The two-chain 2 = ({⊥, ⊤}, ∧, ⊤) is the simplest non-trivial quantale. Of course, any frame is a unital quantale with binary meet and neutral element ⊤, but 2 already leads to interesting examples of lax algebras.

2. The diamond lattice 2^{2} = ({⊥, u, v, ⊤}, ∧, ⊤) (with u and v incomparable) is obviously isomorphic to the powerset of 2, and provides another meaningful example of a non-trivial quantale.

3. The extended real line P_{+} = ([0, ∞]^{op}, +, 0) with its addition extended via x + ∞ = ∞ = ∞ + x for all x ∈ [0, ∞] is a quantale. Notice that the opposite order has been taken on the chain [0, ∞], so that the neutral element 0 is also the top element of the lattice.

4. The non-integral three-chain 3 = ({⊥, k, ⊤}, ⊗, k) is the smallest non-integral quantale. The tensor is commutative, and necessarily defined by ⊥⊗v = ⊥ and k⊗v = v for all v ∈ 3, while ⊤ ⊗ ⊤ = ⊤.

2.3. V-relations and relations.. The objects of the category V-Rel are sets, and its morphisms r : X \overrightarrow{}Y are V-relations, that is, maps of the form r : X × Y → V. Composition of r : X \overrightarrow{}Y with s : Y \overrightarrow{}Z is given by the “matrix multiplication” formula:

(s · r)(x, z) = ⋁_{y∈Y} r(x, y) ⊗ s(y, z) .

The identity 1_{X} : X \overrightarrow{}X is the V-relation defined by 1_{X}(x, y) = k if x = y and 1_{X}(x, y) = ⊥ otherwise. The category Rel of sets and relations is identified with 2-Rel, and embeds into V-Rel via composition of r : X × Y → 2 with

λ : 2 → V , ⊥ ↦ ⊥ , ⊤ ↦ k .

A V-relation with values in {⊥, k} is called a relation in V-Rel, while the term relation alone means a 2-relation.

Similarly, Set can be embedded into V-Rel by sending each map f : X → Y to its graph (or more precisely its V-graph), defined by

f(x, y) = \{ \begin{matrix}k & if f(x) = y \\ ⊥ & otherwise . \end{matrix}

Note that we will not insist on distinguishing between a map and its graph, since the context will always determine which level we are working on.

Equipped with the pointwise order induced by V, the hom-sets of V-Rel become supsemilattices, and we have

r ≤ r′ , s ≤ s′ ⟹ s · r ≤ s′ · r′

for all r, r′ : X \overrightarrow{}Y and s, s′ : Y \overrightarrow{}Z. The transpose r^{∘} : X \overrightarrow{}Y of a V-relation r : X \overrightarrow{}Y is defined by r^{∘}(y, x) = r(x, y). Since the quantale V is not necessarily commutative, we do not have in general that (s · r)^{∘} = r^{∘} · s^{∘} in V-Rel, although this formula does hold if either r or s is a relation in V-Rel.

By composing a map f : X → Y, a V-relation s : Y \overrightarrow{}Z, and the transpose of h : W → Z, we get the convenient formula

h^{∘} · s · f(x, w) = s(f(x), h(w)) .

Notice also that 1_{X} ≤ f^{∘} · f and f · f^{∘} ≤ 1_{X}, so the following equivalences hold

t ≤ s · f ⟺ t · f^{∘} ≤ s  and  g · r ≤ t ⟺ r ≤ g^{∘} · t

for any V-relation t : X \overrightarrow{}Z and map g : Y → Z.

2.4. Strata.. Let Inf denote the category of inf-semilattices and inf-preserving maps. For a V-relation r : X \overrightarrow{}Y and v ∈ V, the v-stratum of r is the relation r_{v} : X \overrightarrow{}Y defined by

r_{v}(x, y) = ⊤ ⟺ v ≤ r(x, y) .

In the case where s : X \overrightarrow{}Y is a relation in V-Rel, the relation s_{k} is simply the preimage of s via the embedding Rel ↪ V-Rel.

For any A ⊆ V, we have r_{⋁ A} = ⋀_{v∈A} r_{v}, so the map

ϕ_{r} : V^{op} → Rel(X, Y) , v ↦ r_{v}

preserves arbitrary infima. On the other hand, every inf-map ϕ : V^{op} → Rel(X, Y) yields a V-relation

r_{ϕ} : X \overrightarrow{}Y , (x, y) ↦ ⋁\{ v ∈ V | ϕ(v)(x, y) = ⊤ \} .

These correspondences describe an order-preserving isomorphism

V-Rel(X, Y) ≅ Inf(V^{op}, Rel(X, Y)) .

Furthermore, for any maps f : X → Y, g : Y → Z, V-relations r : X \overrightarrow{}Y, s : Y \overrightarrow{}Z and u, v ∈ V, we have

s_{v} · f = (s · f)_{v} ,  g^{∘} · r_{v} = (g^{∘} · r)_{v}  and s_{u} · r_{v} ≤ (s · r)_{v⊗u} .

2.5. Remark. As pointed out to the authors by Walter Tholen, the previous isomorphism is a particular case of the order-preserving isomorphism

Set(A, V) ≅ Inf(V^{op}, P A) .

Indeed, whenever A = X × Y, we have Set(A, V) = V-Rel(X, Y), and P A ≅ Rel(X, Y). Moreover, this isomorphism is the restriction to fixpoints of the adjunction

ϕ ⊣ ψ : Set(A, V) → Set(V, P A) ,

where Set(A, V) and Set(V, P A) are endowed with their respective pointwise order, and

ϕ(f)(a) := ⋁{v ∈ V | a ∈ f(v)} , ψ(g)(v) := {a ∈ A | v ≤ g(a)}

for all maps f : V → P A, g : A → V, and elements a ∈ A, v ∈ V.

2.6. Monads.. Recall that a monad 𝕋 on Set is a triple (T, η, μ), where T : Set → Set is a functor, and the unit η : Id → T and multiplication μ : T^{2} → T of 𝕋 are natural transformations satisfying

μ · T η = 1 = μ · ηT and μ · T μ = μ · μT .

A monad morphism α : 𝕊 → 𝕋 from 𝕊 = (S, δ, ν) to 𝕋 = (T, η, μ) is a natural transformation α : S → T such that

η = α · δ and μ · α^{2} = α · ν (with α^{2} = T α · αS = αT · Sα) .

We say that α is an embedding if the components α_{X} are injections.

2.7. Examples. The following monads will be used throughout the text.

1. The identity monad is the obvious monad 𝕀 = (Id, 1, 1).

2. The powerset monad is ℙ = (P, ι, ⋃) with unit given by ι_{X}(x) := {x}. Note that for A ∈ P X and a map f : X → Y we will often write

f[A] := { f(x) | x ∈ A },

instead of P f(A).

3. The double-dualization monad (also called the “contravariant” double-powerset monad) 𝔻_{2} = (D_{2}, ˙−, Σ) is described by D_{2}X := P P X for every set X, together with the following three equivalences:

B ∈ D_{2}f(𝔣) ⟺ f^{−1}(B) ∈ 𝔣 , A ∈ ẋ ⟺ x ∈ A , A ∈ Σ_{X}(𝔉) ⟺ A^{𝔻_{2}} ∈ 𝔉 ,

for f : X → Y, 𝔣 ∈ D_{2}X, x ∈ X, 𝔉 ∈ D_{2}D_{2}X, and where

A^{𝔻_{2}} := { 𝔣 ∈ D_{2}X | A ∈ 𝔣 } .

It will also be convenient to use the following notation:

f[𝔣] := D_{2}f[𝔣] .

4. An element 𝔣 ∈ D_{2}X = P P X is up-closed if A ∈ 𝔣 and A ⊆ B implies B ∈ 𝔣 for all B ⊆ X. For any 𝔣 ⊆ P X, the up-closure of 𝔣 is defined by

↑𝔣 := { B ⊆ X | ∃A ∈ 𝔣 : A ⊆ B } .

The up-set monad 𝕌 = (U, ˙−, Σ) is just the restriction of 𝔻_{2} to up-closed elements of D_{2}X. In this case, Σ_{X}(𝔉) = { A^{𝕌} | A^{𝕌} ∈ 𝔉 } for 𝔉 ∈ UUX, where A^{𝕌} := { 𝔣 ∈ UX | A ∈ 𝔣 }.

5. The filter monad 𝔽 = (F, ˙−, Σ) is the restriction of the up-set monad to filters. Here, we must use A^{𝔽} := { 𝔣 ∈ F X | A ∈ 𝔣 } in lieu of A^{𝕌} in the definition of the components of Σ : F F → F. Let us point out that we consider the improper filter 𝔣 = P X as an element of F X.

6. The ultrafilter monad 𝔹 = (β, ˙−, Σ) is the restriction of the filter monad to ultrafilters. Here we use the sets A^{𝔹} := { 𝔵 ∈ βX | A ∈ 𝔵 } instead of A^{𝔽}.

7. The previous monads may all be considered as submonads of 𝔻_{2}. Indeed, the powerset monad ℙ embeds into 𝔽 via the principal filter natural transformation τ : P → F, defined componentwise by τ_{X}(A) := ↑{A} for A ∈ P X, and the identity monad 𝕀 obviously embeds both into ℙ and 𝔹. Therefore, we have the following diagram of monad embeddings:

\xymatrix{ & ℙ \ar[dr] \\ 𝕀 \ar[ur] \ar[dr] &  & 𝔽 \ar[r] & 𝕌 \ar[r] & 𝔻_{2} . \\  & 𝔹 \ar[ur]}

2.8. Monads as Kleisli triples.. For our purpose, the alternate description of monads from ([15], Exercise 1.3.12) will be useful. A Kleisli triple (T, η, −^{𝕋}) on Set consists of

(i) a map T : ob Set → ob Set,

(ii) for each set X, a map η_{X} : X → T X,

(iii) an operation −^{𝕋} which sends f : X → T Y to f^{𝕋} : T X → T Y,

subject to the conditions

(η_{X})^{𝕋} = 1_{T X} ,  f^{𝕋} · η_{X} = f  and g^{𝕋} · f^{𝕋} = (g^{𝕋} · f)^{𝕋} .

Each Kleisli triple (T, η, −^{𝕋}) yields a monad 𝕋 = (T, η, μ) by setting

T f := (η_{Y} · f)^{𝕋} and μ_{X} := (1_{T X})^{𝕋} ,

and every monad 𝕋 = (T, η, μ) defines a Kleisli triple via

f^{𝕋} := μ_{Y} · T f .

Since these processes are mutually inverse, we will freely switch between the two descriptions.

Given Kleisli triples (S, δ, −^{𝕊}) and (T, η, −^{𝕋}), a family (α_{X} : SX → T X)_{X∈ob Set} defines a monad morphism α : 𝕊 → 𝕋 if and only if the equalities

α_{X} · δ_{X} = η_{X} and (α_{Y} · f)^{𝕋} · α_{X} = α_{Y} · f^{𝕊}

hold for all sets X and maps f : X → SY.

2.9. Kleisli categories.. We recall that the Kleisli category Set_{𝕋} of a monad 𝕋 = (T, η, −^{𝕋}) has as objects sets, and as morphisms f : X ⇀ Y maps f : X → T Y. The composite of f : X ⇀ Y with g : Y ⇀ Z is given via Set-composition as

g ∘ f := g^{𝕋} · f = μ_{Z} · T g · f ,

and the identity at X is η_{X} : X ⇀ X. Observe that the conditions on a Kleisli triple are equivalent to the left and right unit laws of the identity, and to the associativity of composition, respectively.

Every monad morphism α : 𝕊 → 𝕋 induces a functor Set_{𝕊} → Set_{𝕋} by composing morphisms with α_{X}. The conditions for monad morphisms between Kleisli triples are then equivalent to preservation of identities and composition, respectively.

The Kleisli category Set_{ℙ} of the powerset monad is the category Rel of sets and relations. Using the isomorphism Rel ≅ Rel^{op}, we will exploit the description of a relation r : X \overrightarrow{}Y by its preimage-mapping

r^{♭} : Y → P X , y ↦ { x | r(x, y) = ⊤ }

(notice the transposition). This description is functorial since for s : Y \overrightarrow{}Z, we have

(s · r)^{♭} = (r^{♭})^{ℙ} · s^{♭} = r^{♭} ∘ s^{♭} .

When f : X \overrightarrow{}Y is the graph of a map, the preimage-mapping is related to well-known operations on f:

(f^{♭})^{ℙ} = f^{−1} : P Y → P X and (f^{∘})^{♭} = ι_{Y} · f : X → P Y .

In particular, we have ((f^{∘})^{♭})^{ℙ} = P f : P X → P Y.

3. Lax extensions and lax algebras

3.1. Lax extensions.. A lax extension of a Set-functor T : Set → Set along the embedding Set ↪ V-Rel, (or simply a lax extension of T to V-Rel), is a map

\overline{T} : V-Rel → V-Rel , (r : X \overrightarrow{}Y) ↦ (\overline{T} r : T X \overrightarrow{}T Y)

satisfying for all r : X \overrightarrow{}Y, s : Y \overrightarrow{}Z, and f : X → Y the conditions

(i) s ≤ r ⟹ \overline{T} s ≤ \overline{T} r ,

(ii) \overline{T} s · \overline{T} r ≤ \overline{T} (s · r) ,

(iii) T f ≤ \overline{T} f and (T f)^{∘} ≤ \overline{T} f^{∘} .

The last condition implies in particular that 1_{T X} ≤ \overline{T} 1_{X}, so a lax extension of T : Set → Set is simply a lax functor satisfying the extension conditions (iii). Notice that a lax extension is a structure on a functor and not a mere property. A morphism of lax extensions α : (S, \overline{S}) → (T, \overline{T}) is a natural transformation α : S → T between the underlying Set-functors which extends to an oplax transformation \overline{S} → \overline{T}; that is, α_{Y} · \overline{S}r ≤ \overline{T} r · α_{X}, or equivalently

\overline{S}r ≤ α_{Y}^{∘} · \overline{T} r · α_{X},

for all r : X \overrightarrow{}Y. Often, we simply write α : \overline{S} → \overline{T} instead of α : (S, \overline{S}) → (T, \overline{T}). If \overline{T} : V-Rel → V-Rel is a lax extension of T : Set → Set, then it satisfies

\overline{T} (s · f) = \overline{T} s · \overline{T} f = \overline{T} s · T f and \overline{T} (g^{∘} · s) = \overline{T} g^{∘} · \overline{T} s = (T g)^{∘} · \overline{T} s ,

for all s : Y \overrightarrow{}Z, f : X → Y, and g : W → Z. Indeed, we have

\overline{T} (s · f) ≤ \overline{T} (s · f) · \overline{T} f^{∘} · T f ≤ \overline{T} (s · f · f^{∘}) · T f ≤ \overline{T} s · T f ≤ \overline{T} s · \overline{T} f ≤ \overline{T} (s · f) ,

and the other set of equalities follows in a similar way.

3.2. Associated preorders.. Any lax functor T : V-Rel → V-Rel yields a preorder on the sets T X via

𝔵 ≤_{T} 𝔶 ⟺ k ≤ T 1_{X}(𝔵, 𝔶)

for all 𝔵, 𝔶 ∈ T X. A lax extension \overline{T} : V-Rel → V-Rel of a functor T : Set → Set takes this process one step further and induces a factorization of T through the category Ord of preordered sets and monotone maps. Indeed, a map f : X → Y is sent to a monotone map T f : T X → T Y, since

\overline{T} 1_{X} ≤ \overline{T} (f^{∘} · 1_{Y} · f) = (T f)^{∘} · \overline{T} 1_{Y} · T f .

If α : \overline{S} → \overline{T} is a morphism of lax extensions, then each α_{X} : SX → T X is monotone. Let us stress moreover that ≤\overline{T} is a relation, while \overline{T} 1_{X} is a V-relation so that ≤\overline{T} ≠ \overline{T} 1_{X} even if ≤\overline{T} is seen as a V-relation (this distinction will be important in the definition of an antitone V-relation in 5.4).

When the sets T X are equipped with this order, the V-relation \overline{T} r reverses it in its first variable and preserves it in its second; indeed, if 𝔵′ ≤\overline{T} 𝔵 and 𝔶 ≤\overline{T} 𝔶′, then

\overline{T} r(𝔵, 𝔶) ≤ \overline{T} 1_{X}(𝔵′, 𝔵) ⊗ \overline{T} r(𝔵, 𝔶) ⊗ \overline{T} 1_{Y} (𝔶, 𝔶′) ≤ \overline{T} 1_{Y} · \overline{T} r · \overline{T} 1_{X}(𝔵′, 𝔶′) = \overline{T} r(𝔵′, 𝔶′)

for all 𝔵, 𝔵′ ∈ T X, 𝔶, 𝔶′ ∈ T Y.

3.3. Initial extensions.. Let α : S → T be a natural transformation of Set-functors, and \overline{T} a lax extension of T to V-Rel. The initial extension of S along α is the lax extension given by

α^{∗}\overline{T} r := α_{Y}^{∘} · \overline{T} r · α_{X} ,

for any V-relation r : X \overrightarrow{}Y. The morphism of lax extensions α : (S, α^{∗}\overline{T}) → (T, \overline{T}) is initial in the following sense: if β : R → S is a natural transformation and \overline{R} is a lax extension of R, then β : \overline{R} → α^{∗}\overline{T} is a morphism of lax extensions if and only if α · β : \overline{R} → \overline{T} is one.

In presence of the initial extension α^{∗}\overline{T} of S, the maps α_{X} : SX → T X become order-embeddings with respect to the associated preorders:

𝔵 ≤_{α^{∗}\overline{T}} 𝔵′ ⟺ α_{X}(𝔵) ≤\overline{T} α_{X}(𝔵′)

for all 𝔵, 𝔵′ ∈ SX.

3.4. Proposition. Let α : 𝕊 → 𝕋 be a morphism of Set-monads 𝕊 = (S, δ, ν) and 𝕋 = (T, η, μ). If T has a lax extension \overline{T} to V-Rel for which η : Id → \overline{T} is oplax, then δ : Id → \overline{S} is also oplax for the initial extension \overline{S} = α^{∗}\overline{T} of S along α. Similarly, if μ : \overline{T} \overline{T} → \overline{T} is oplax for \overline{T}, then ν : \overline{S} \overline{S} → \overline{S} is oplax for \overline{S} = α^{∗}\overline{T}.

Proof. Oplaxness of δ follows immediately from η = α · δ. Since α : \overline{S} → \overline{T} is oplax, α^{2} : \overline{S} \overline{S} → \overline{T} \overline{T} is too. Thus, oplaxness of ν follows from μ · α^{2} = α · ν.

3.5. Remark. For a source α = (α_{i} : S → T_{i})_{i∈I}, where each T_{i} carries a lax extension \overline{T}_{i} to V-Rel, we can define an initial lift via the lax extension \overline{S} of S defined by

\overline{S}r := ⋀_{i∈I}(α_{i})_{Y}^{∘} · \overline{T}_{i}r · (α_{i})_{X} ,

for any V-relation r : X \overrightarrow{}Y. In other words, the quasicategory^{1} of lax extensions to V-Rel is topological over the quasicategory of Set-functors.

3.6. Examples.

1. A lax extension of the identity functor Id : Set → Set to V-Rel is given by the identity Id : V-Rel → V-Rel. In this case, the preorder associated with this extension is the discrete order on X.

2. A lax extension of the powerset functor P : Set → Set to V-Rel is given by

\overline{P} r(A, B) = ⋁\{ v ∈ V | A ⊆ r_{v}^{♭}[B] \}

for any A ∈ P X, B ∈ P Y, and V-relation r : X \overrightarrow{}Y. The preorder associated with this extension is just subset inclusion. Moreover, the previous lax extension of the identity functor is the initial extension induced by the unit ι : Id → P of ℙ.

1Due to size restrictions on the hom-sets, the term “quasicategory” is used in lieu of “category”. This distinction is made here because topologicity is classically defined for locally small categories only [1].

3. A lax extension of the up-set functor U : Set → Set to V-Rel is given by

\overline{U}r(𝔣, 𝔤) = ⋁\{ v ∈ V | 𝔣 ⊇ r_{v}^{♭}[𝔤] \}

for r : X \overrightarrow{}Y, 𝔣 ∈ UX, and 𝔤 ∈ UY. The preorder obtained on UX is the “finer than” relation, which is opposite to subset inclusion. One obtains lax extensions of the filter and ultrafilter functors by restricting this lax extension accordingly. The extensions obtained are the initial lifts along the corresponding embeddings (see Example 2.7(7)). Similarly, the extension \overline{P} described above is the initial lift of the restriction \overline{F} along the principal filter transformation τ : ℙ → 𝔽.

The resulting lax extension of the ultrafilter functor is the well-known extension described originally in [2], or in the present form in [3].

4. Another lax extension of the filter functor F is given by

F̃r(A, B) = ⋁{ v ∈ V | 𝔤 ⊇ (r_{v}^{∘})^{♭}[𝔣] }

for any V-relation r : X \overrightarrow{}Y, A ∈ P X, B ∈ P Y. This extension differs from the one above in that it uses and induces the opposite order on the sets F X. The corresponding initial extension of the powerset functor (along the principal filter transformation) is

P̃r(A, B) = ⋁{ v ∈ V | B ⊆ (r_{v}^{∘})^{♭}[A] } .

In [19], these extensions were called the “canonical” extensions of their respective functors.

3.7. Strata extensions.. Reviewing the lax extensions to V-Rel of Examples 3.6, it becomes clear that they are formed from the corresponding extension to Rel according to a certain pattern. These lax extensions are all instances of a construction that allows us to extend any lax functor T : Rel → Rel to a lax functor T_{V} : V-Rel → V-Rel as follows. For a set X, let T_{V}X := T X and

T_{V}r(𝔵, 𝔶) := ⋁{ v ∈ V | T r_{v}(𝔵, 𝔶) = ⊤ } ,

for any V-relation r : X \overrightarrow{}Y. We call T_{V} the strata extension of T. This extension process was extensively studied in [3] and [18], to which we refer for further details. For any V-relation r : X \overrightarrow{}Y and v ∈ V, we obviously have

T r_{v} ≤ (T_{V}r)_{v} ,  (1)

and T_{V} is the least extension of a lax functor T : Rel → Rel to V-Rel for which this inequality holds. By identifying a 2-relation s : X \overrightarrow{}Y with its image in V-Rel, we may write T s = T s_{k} in Rel. This equality can be transported to V-Rel, where we then have

T s = T s_{k} ≤ (T_{V}s)_{k} ≤ T_{V}s .

Let us point out en passant that these inequalities are in fact equalities if V is integral, or if T preserves every empty 2-relation ⊥ : X \overrightarrow{}Y. In any case, this shows that if \overline{T} : Rel → Rel is a lax extension of a Set-functor T, then \overline{T}_{V} is a lax extension of T to V-Rel.

Finally, if α : S → T is a natural transformation between Set-functors, and \overline{T} is a lax Rel-extension of T, then we have

α^{∗}(\overline{T}_{V}) = (α^{∗}\overline{T})_{V} .

In other words, initial lifts commute with strata extensions.

3.8. Proposition. The preorders induced on the sets T X by a lax functor T : Rel → Rel and its strata extension T_{V} coincide.

Proof. Note that we already have (≤_{T}) ≤ (≤_{T_{V}}) by (1) in 3.7 above. For the other inequality, assume that 𝔵 ≤_{T_{V}} 𝔶 holds for 𝔵, 𝔶 ∈ T X, that is, k ≤ ⋁{ v ∈ V | T ((1_{X})_{v})(𝔵, 𝔶) = ⊤ }. Non-triviality of V implies that there is some u in V \ {⊥} with T ((1_{X})_{u})(𝔵, 𝔶) = ⊤. Since u ≠ ⊥, we have (1_{X})_{u} ≤ 1_{X}, and therefore T 1_{X}(𝔵, 𝔶) = ⊤, so that 𝔵 ≤_{T} 𝔶.

3.9. Lax algebras.. Let 𝕋 = (T, η, μ) be a monad on Set equipped with a lax extension \overline{T} of T. The category Alg(𝕋, V) of (𝕋, V)-algebras, or lax algebras, has as objects pairs (X, a), where X is a set, and its structure a : T X \overrightarrow{}X is a reflexive and transitive V-relation:

1_{X} ≤ a · η_{X} and a · \overline{T} a ≤ a · μ_{X} .

Morphisms f : (X, a) → (Y, b) are Set-maps f : X → Y satisfying:

f · a ≤ b · T f ,

and composing as in Set. It will sometimes be useful to identify the lax extension that is being used; in such cases, we will write Alg(𝕋, \overline{T} , V) instead of Alg(𝕋, V).

Using the—not necessarily associative—Kleisli convolution b ∗ a of V-relations a : T X \overrightarrow{}Y, b : T Y \overrightarrow{}Z defined by

b ∗ a := b · \overline{T} a · μ_{X}^{∘},

we can rewrite the reflexivity and transitivity conditions above as

η_{X}^{∘} ≤ a and a ∗ a ≤ a.  (2)

If (X, a) is a lax algebra, then a · (≤\overline{T}) = a · \overline{T} 1_{X} = a, since

a = a · 1_{T X} ≤ a · (≤\overline{T}) ≤ a · \overline{T} 1_{X} ≤ a · \overline{T} a · T η_{X} ≤ a · μ_{X} · T η_{X} = a

by applying \overline{T} to the reflexivity, and combining with the transitivity of a. Therefore, a reverses the order ≤\overline{T} in its first variable:

𝔵 ≤\overline{T} 𝔶 ⟹ k ≤ \overline{T} 1_{X}(𝔵, 𝔶) ⟹ a(𝔶, z) ≤ \overline{T} 1_{X}(𝔵, 𝔶) ⊗ a(𝔶, z) ≤ a · \overline{T} 1_{X}(𝔵, z) = a(𝔵, z)

for all 𝔵, 𝔶 ∈ T X, z ∈ X.

3.10. Examples. Two of the original examples of lax algebras, called relational algebras in [2], are given by the categories Ord of preordered sets, and Top of topological spaces:

Ord ≅ Alg(𝕀, 2) , Top ≅ Alg(𝔹, 2) .

Other examples (as well as a proof of these isomorphisms) will be given further on.

3.11. Remark. Since the structure relation a : T X \overrightarrow{}X of a (𝕋, V)-algebra reverses the preorder on T X in its first variable, it is reasonable to expect that it also preserves a non-trivial preorder in its second. In fact, this depends on the lax extension. To see this, notice first that

η_{X}^{∘} · \overline{T} a = a · η_{X} · η_{X}^{∘} · \overline{T} a ≤ a · \overline{T} a ≤ a · μ_{X} ,

so the inequality η_{X}^{∘} · \overline{T} a · η_{T X} ≤ a always holds. In the case where the unit η : 1 → \overline{T} is oplax, this inequality becomes an equality, and a induces the dual specialization preorder on X via

x ≤_{a} y ⟺ k ≤ a(η_{X}(x), y) .

The structure a is then monotone in its second variable with respect to this preorder:

x ≤_{a} y ⟹ a(𝔵, x) ≤ \overline{T} a(η_{T X}(𝔵), η_{X}(x)) ⊗ a(η_{X}(x), y) ≤ a(𝔵, y)

for all x, y ∈ X, 𝔵 ∈ T X. Notice also that the Kleisli extension introduced further on does make η into an oplax transformation (Proposition 4.8).

3.12. Functoriality of Alg(−, V).. We have seen that every monad 𝕋 equipped with a lax extension \overline{T} : V-Rel → V-Rel of the underlying functor T gives rise to a category Alg(𝕋, V). For a monad 𝕊 equipped with a lax extension \overline{S}, a morphism α : (𝕊, \overline{S}) → (𝕋, \overline{T}) is a monad morphism α : 𝕊 → 𝕋 which is also a morphism of lax extensions. In this case, α induces a 2-functor

F_{α} = Alg(α, V) : Alg(𝕋, V) → Alg(𝕊, V)

sending (X, a) to (X, a · α_{X}), and mapping morphisms identically (see [4], Section 3.7). The correspondence

(α : 𝕊 → 𝕋) ↦ (F_{α} : Alg(𝕋, V) → Alg(𝕊, V))

is functorial, so that F_{α·β} = F_{β}F_{α} and F_{1} = Id for all morphisms β : (ℝ, \overline{R}) → (𝕊, \overline{S}) and α : (𝕊, \overline{S}) → (𝕋, \overline{T}).

3.13. Induced adjunctions.. Let S, T be two Set-functors admitting lax extensions \overline{S}, \overline{T}, and

α ⊣ β : \overline{T} → \overline{S}

a natural adjunction; that is, a pair (α : \overline{S} → \overline{T} , β : \overline{T} → \overline{S}) of morphisms of lax extensions whose components form an adjunction α_{X} ⊣ β_{X} : T X → SX for every set X, so that

1_{X} ≤\overline{S} β_{X} · α_{X} and α_{X} · β_{X} ≤\overline{T} 1_{X} .

In the case where α : 𝕊 → 𝕋, β : 𝕋 → 𝕊 are also monad morphisms, then there is an induced adjunction

F_{α} ⊣ F_{β} : Alg(𝕊, V) → Alg(𝕋, V) .

Indeed, since a reverses the order in its first variable, we obtain the inequalities a ≤ a·(α_{X} ·β_{X}) and b·(β_{X} ·α_{X}) ≤ b, for any lax algebra structures a : T X \overrightarrow{}X, b : SX \overrightarrow{}X. These inequalities yield the unit η : Id → F_{β}F_{α} and co-unit ε : F_{α}F_{β} → Id of the adjunction.

3.14. Proposition. Let \overline{T} be a lax extension of T, and α : 𝕊 → 𝕋 a retraction (so there exists a monad morphism β : 𝕋 → 𝕊 with α · β ≃\overline{T} 1). If \overline{S} is the initial extension induced by α, then Alg(𝕊, V) and Alg(𝕋, V) are concretely equivalent categories.

Proof. By composing each side of the equality \overline{S}r = α_{Y}^{∘} · \overline{T} r · α_{X} with β_{Y}^{∘} on the left and β_{X} on the right, we obtain β_{Y}^{∘} · \overline{S}r · β_{X} = \overline{T} r, so that β is a morphism of lax extensions. Moreover, we have

1_{X} ≤ α_{X}^{∘} · \overline{T} 1_{X} · α_{X} = α_{X}^{∘} · β_{X}^{∘} · α_{X}^{∘} · \overline{T} 1_{X} · α_{X} = α_{X}^{∘} · β_{X}^{∘} · \overline{S}1_{X} ,

so that 1 ≤\overline{S} β · α, and β · α ≤\overline{S} 1 by composing each side of α_{X} · β_{X} ≃ 1_{X} with \overline{S}1_{X}. Therefore we have β · α ≃\overline{S} 1, so that α ∼ β induces a concrete equivalence F_{β} ∼ F_{α}.

4. Kleisli extensions

4.1. Sup-enriched monads.. Let us recall that the Eilenberg-Moore category Set^{ℙ} of the powerset monad is the category Sup of sup-semilattices and sup-maps. A Sup-enriched monad on Set is a pair (𝕋, τ) made up of a monad 𝕋 and a monad morphism τ : ℙ → 𝕋. Any such monad morphism induces a concrete functor Set^{𝕋} → Sup. In particular, every set T X carries the structure of a sup-semilattice, with

⋁ A := μ_{X} · τ_{T X}(A) ,

for all A ⊆ T X; moreover, the multiplications μ_{X} and each T f : T X → T Y preserve these suprema. Thus, every Sup-enriched monad (𝕋, τ) induces a factorization of 𝕋 through Sup. Conversely, given a monad 𝕋 = (T, η, μ) factoring through Sup, one can define a monad morphism τ : ℙ → 𝕋 (as in [20]) via

τ_{X}(A) := ⋁_{x∈A} η_{X}(x) .

Since the operations described above are inverse of each other, Sup-enriched monads and monads factoring through Sup are equivalent concepts.

A morphism of Sup-enriched monads α : (𝕊, σ) → (𝕋, τ) is a monad morphism α : 𝕊 → 𝕋 such that τ = α · σ. As we show below, this is equivalent to stating that the components of α are sup-maps.

We say that a Sup-enriched monad (𝕋, τ) is coherent if the operation −^{𝕋} is monotone with respect to the order induced by τ; that is, for any g, h : X → T Y, we must have

g ≤ h ⟹ g^{𝕋} ≤ h^{𝕋} .

For any Sup-enriched monad (𝕋, τ), coherence is equivalent to the fact that the Kleisli-ca-tegory Set_{𝕋} is a 2-category with respect to the pointwise order, i.e., the Kleisli-composition g ∘ f = g^{𝕋} · f is monotone in each variable.

4.2. Proposition. Let 𝕊 = (S, δ, ν), 𝕋 = (T, η, μ) be monads on Set, and α : 𝕊 → 𝕋 a monad morphism. The following statements are equivalent for Sup-enrichments σ of 𝕊 and τ of 𝕋:

(a) α is a morphism (𝕊, σ) → (𝕋, τ);

(b) each α_{X} : SX → T X preserves suprema.

Proof. Since Sup ≅ Set^{ℙ}, α_{X} preserves suprema if and only if the diagram

\xymatrix{P SX \ar[d]_{ν_{X}·σ_{SX}} \ar[r]^{P α_{X}} & P T X \ar[d]^{μ_{X}·τ_{T X}} \\ SX \ar[r]^{α_{X}} & T X}  (3)

commutes. Thus, if α : (𝕊, σ) → (𝕋, τ) is a morphism, then

α_{X} · ν_{X} · σ_{SX} = μ_{X} · α_{T X} · σ_{T X} · P α_{X} = μ_{X} · τ_{T X} · P α_{X} ,

as required. Conversely, if the diagram above commutes, we have

α_{X} · σ_{X} = α_{X} · ν_{X} · Sδ_{X} · σ_{X} = μ_{X} · τ_{T X} · P (α_{X} · δ_{X})
= μ_{X} · τ_{T X} · P η_{X} = μ_{X} · T η_{X} · τ_{X} = τ_{X} .

4.3. Examples.

1. Although there are two trivial monads on Set, there is only one which is Supenriched, namely the monad 𝕋_{!} for which T_{!}X = {∗} for all sets X.

2. The powerset monad ℙ is coherent Sup-enriched via 1_{ℙ}, and the supremum operation is given by set union. Moreover, (ℙ, 1_{ℙ}) is an initial object in the quasicategory of Sup-enriched monads and their morphisms.

3. The filter monad 𝔽 and the up-set monad 𝕌 are coherent Sup-enriched via the principal filter natural transformations τ : ℙ → 𝔽 and τ : ℙ → 𝕌, respectively. In both cases, supremum is given by intersection.

4. The monad 𝔻_{2} becomes a Sup-enriched monad in at least two different ways. Indeed, there are monad morphisms ♢, □ : ℙ → 𝔻_{2}, defined componentwise for A ∈ P X by

♢_{X}(A) = { B ⊆ X | A ∩ B ≠ ∅ } , □_{X}(A) = { B ⊆ X | A ⊆ B } ,

(see [15], Exercise 3.2.18; the notations □ and ♢ come from coalgebraic modal logic, where these natural transformations play a vital role). This demonstrates that a factorization through Sup is a structure on the monad, and not a property. The suprema induced on D_{2}X by □ are given by intersection, while the ones induced by ♢ are given by union. However, it can be seen that neither (𝔻_{2}, ♢) nor (𝔻_{2}, □) is coherent.

Since the natural transformation τ : ℙ → 𝕌 above is just the restriction of □, the embeddings

(ℙ, 1_{ℙ}) → (𝔽, τ) → (𝕌, τ) → (𝔻_{2}, □)

form a chain of Sup-enriched monads (although only the first three are coherent).

4.4. The Kleisli extension.. Let (𝕋, τ) be a Sup-enriched monad. If r : X \overrightarrow{}Y is a relation, we denote by r^{τ} : T Y → T X the composite

r^{τ} := (τ_{X} · r^{♭})^{𝕋} = μ_{X} · T (τ_{X} · r^{♭}) .

For a relation s : Y \overrightarrow{}Z and a map g, we obtain the following useful formulas:

r^{τ} · η_{X} = τ_{X} · r^{♭},  (s · r)^{τ} = r^{τ} · s^{τ},  (g^{∘})^{τ} = T g.  (4)

The first equation is obvious; the other two follow from the fact that τ is a monad morphism.

The Kleisli extension T^{τ} : Rel → Rel of T with respect to τ is defined by

T^{τ}r(𝔵, 𝔶) = ⊤ ⟺ 𝔵 ≤ r^{τ}(𝔶).

for a relation r : X \overrightarrow{}Y and 𝔵 ∈ T X, 𝔶 ∈ T Y. Using strata extensions, we can define T_{V}^{τ} := (T^{τ})_{V} : V-Rel → V-Rel as

T_{V}^{τ}r(𝔵, 𝔶) = ⋁{ v ∈ V | 𝔵 ≤ (r_{v})^{τ}(𝔶) } ,

for a V-relation r : X \overrightarrow{}Y and 𝔵 ∈ T X, 𝔶 ∈ T Y. This formula was used in [20] to define T_{V}^{τ} in one step. There, it is shown that if τ is a coherent Sup-enrichment, then T_{V}^{τ} is a lax extension of T, and that whenever V is non-trivial (as we assumed in this work), then the preorder ≤_{T_{V}^{τ}} associated with this extension is identical to the original order on T X. In particular, all μ_{X} and T f preserve this order.

4.5. Remark. The previous definition of the Kleisli extension does not require that (𝕋, τ) be coherent Sup-enriched, so that T_{V}^{τ} is not necessarily a lax extension of T. However, one can still exploit this definition to put forth meaningful mechanisms that underly the coherent case (see in particular Example 4.6(3) below, or Corollary 4.13).

4.6. Examples.

1. For the trivial Sup-enriched monad 𝕋_{!}, we have τ_{X} = !_{X} : P X → {∗} and T_{V}^{!}r(∗, ∗) = ⊤ for any V-relation r : X \overrightarrow{}Y. In particular, (T_{!}, T_{V}^{!}) is a final object in the quasicategory of lax extensions.

2. The Kleisli extensions of the powerset, filter and up-set functors are the lax extensions described in 3.6.

3. Example 4.3(4) shows that there are at least two lax extensions obtained as Kleisli extensions of the up-set functor U. Indeed, the monad morphism □ : ℙ → 𝔻_{2} restricts to the principal filter natural transformation τ : ℙ → 𝕌, and ♢ : ℙ → 𝔻_{2} also restricts to a coherent Sup-enrichment σ : ℙ → 𝕌. This demonstrates that the lax extensions presented here are fundamentally different from the extensions obtained by the original construction of Barr in [2]. Indeed, the latter are lax functors if and only if the original Set-functor satisfies the Beck-Chevalley condition of ([3], Section 1.3). However, it can be seen that the up-set functor U does not satisfy this condition, so Barr’s construction fails to yield a lax extension of U.

4.7. Proposition. The Kleisli extension T^{τ} : Rel → Rel preserves composition:

T^{τ}s · T^{τ}r = T^{τ}(s · r)

for all relations r : X \overrightarrow{}Y, s : Y \overrightarrow{}Z.

Proof. This follows immediately from the second equation of (4) in 4.4.

4.8. Proposition. If (𝕋, τ) is a coherent Sup-enriched monad, then η : (Id, Id) → (T, T_{V}^{τ}) is a morphism of lax extensions, that is: η : 1 → \overline{T} is an oplax transformation.

Proof. Take a V-relation r : X \overrightarrow{}Y, and for x ∈ X, y ∈ Y set v := r(x, y). By definition, {x} ⊆ r_{v}^{♭}(y), so that η_{X}(x) = τ_{X}({x}) ≤ τ_{X} · r_{v}^{♭}(y) = (τ_{X} · r_{v}^{♭})^{𝕋} · η_{Y} (y). We conclude that r(x, y) = v ≤ T_{V}^{τ}r(η_{X}(x), η_{Y} (y)), so r ≤ η_{Y}^{∘} · T_{V}^{τ}r · η_{X}, as required.

4.9. Proposition. If α : (𝕊, σ) → (𝕋, τ) is a morphism of coherent Sup-enriched monads, then α : S^{σ} → T^{τ} is a morphism of lax extensions.

Moreover, if the α_{X} are order-embeddings, then we have S^{σ} = α^{∗}(T^{τ}); that is, the initial extension induced by α is the Kleisli extension of S.

Proof. Observe that we have α_{X} · (r_{v})^{σ} = (r_{v})^{τ} · α_{Y} for any V-relation r : X \overrightarrow{}Y and v ∈ V. Therefore,

𝔵 ≤ (r_{v})^{σ}(𝔶) ⟹ α_{X}(𝔵) ≤ α_{X} · (r_{v})^{σ}(𝔶) = (r_{v})^{τ} · α_{Y} (𝔶)

for all 𝔵 ∈ SX, 𝔶 ∈ SY. This implies immediately that α is a morphism between the Kleisli extensions. If moreover α_{X} is an order-embedding, the implication above is an equivalence, so that α is initial.

4.10. Op-canonical extensions of taut monads.. For any taut monad 𝕊 (see [16]), the component at a set X of the support monad morphism supp : 𝕊 → 𝔽 maps 𝔵 ∈ SX to the filter

supp_{X}(𝔵) := { A ⊆ X | 𝔵 ∈ SA } ,

where SA is identified with a subset of SX. One obtains a lax extension \overline{S} = supp^{∗}(F^{τ}), so that

\overline{S}r(𝔵, 𝔶) := ⋁\{ v ∈ V | ∀B ⊆ Y (B ∈ supp_{Y} (𝔶) ⟹ r_{v}^{♭}[B] ∈ supp_{X}(𝔵)) \} ,

for all r : X \overrightarrow{}Y, 𝔵 ∈ SX, and 𝔶 ∈ SY. This lax extension is just the “op-canonical” extension of a taut functor introduced in [19]. The natural inclusion ε : 𝔽 → 𝕌 is an embedding of coherent Sup-enriched monads (𝔽, τ) → (𝕌, τ), and we have F^{τ} = ε^{∗}(U^{τ}) by Proposition 4.9. Thus, the op-canonical extension of 𝕊 arises in fact from the Supenrichment τ of 𝕌:

\overline{S} = supp^{∗}(F^{τ}) = supp^{∗}(ε^{∗}(U^{τ})) = (ε · supp)^{∗}(U^{τ}) .

Note that Proposition 3.14 states that the functor F_{supp} : Alg(𝔽, V) → Alg(𝕊, V) induced by the support morphism does not yield new examples of lax algebras if the monad 𝕊 “contains” 𝔽, that is, if supp : 𝕊 → 𝔽 is a retraction.

4.11. Canonical extensions of taut monads.. The “canonical” extension [19] of a taut monad 𝕊 is described by

S̃r := (\overline{S}(r^{∘}))^{∘} ,

for all r : X \overrightarrow{}Y, where \overline{S} is the “op-canonical” extension given above. This canonical extension arises as an initial lift of U^{σ} along ε · supp, where σ : ℙ → 𝕌 is the codomainrestriction of the natural transformation ♢ : ℙ → 𝔻_{2} (see Example 4.6(3)). To verify our claim, it sufficient to see that

D_{2}^{♢}(r) = (D_{2}^{□}(r^{∘}))^{∘} ,

since one obtains U^{σ}(r) = (U^{τ}(r^{∘}))^{∘} by restriction of the double-dualization monad to the up-set one (see Corollary 4.13 below).

Thus, let us point out first that every Kleisli morphism f : Y → D_{2}X of 𝔻_{2} corresponds uniquely to a map f_{•} : P X → P Y via

f_{•}(A) = { y ∈ Y | A ∈ f(y) } , f(y) = { A ⊆ X | y ∈ f_{•}(A) } .

This operation −_{•} is related to the monad operations via f^{𝔻_{2}} = f_{•}^{−1} and ( ˙−)_{•} = 1_{P}. It is also functorial, since

(f ∘ g)_{•} = (f^{𝔻_{2}} · g)_{•} = g_{•} · f_{•}

holds for all g : Z → D_{2}Y, and we have f ⊆ f′ pointwise if and only if f_{•} ⊆ f′_{•} pointwise.

4.12. Proposition. For any relation r, we have D_{2}^{♢}(r) = (D_{2}^{□}(r^{∘}))^{∘}.

Proof. Let us write [r] := (□_{X} · r^{♭})_{•} : P X → P Y and ⟨r⟩ := (♢_{X} · r^{♭})_{•} : P X → P Y for a relation r : X \overrightarrow{}Y. We remark that

[r](A) = { y | ∀x : r(x, y) = ⊤ ⇒ x ∈ A } and ⟨r⟩(A) = { y | ∃x ∈ A : r(x, y) = ⊤ }

hold; that is, [r] and ⟨r⟩ are just the “necessarily” and “possibly”, respectively, modalities associated to the relation r^{∘}. In any case, we have an adjunction

⟨r^{∘}⟩ ⊣ [r] ,

and r^{□} = (□_{X} · r^{♭})^{𝔻_{2}} = [r]^{−1} is left adjoint to ⟨r^{∘}⟩^{−1} = (♢_{X} · (r^{∘})^{♭})^{𝔻_{2}} = (r^{∘})^{♢}. Thus, recalling the orders induced by □ and ♢, we have, for 𝔵 ∈ D_{2}X and 𝔶 ∈ D_{2}Y:

𝔵 ≤ r^{□}(𝔶) ⟺ r^{□}(𝔶) ⊆ 𝔵 ⟺ 𝔶 ⊆ (r^{∘})^{♢}(𝔵) ⟺ D_{2}^{♢}(r^{∘})(𝔶, 𝔵) = ⊤,

so that D_{2}^{□}(r) = (D_{2}^{♢}(r^{∘}))^{∘}, or equivalently D_{2}^{♢}(r) = (D_{2}^{□}(r^{∘}))^{∘}.

4.13. Corollary. For any relation r, we have U^{σ}(r) = (U^{τ}(r^{∘}))^{∘}.

Proof. This is a direct consequence of the previous Proposition, since σ : ℙ → 𝕌 is the codomain-restriction of ♢ : ℙ → 𝔻_{2}, and the principal filter natural transformation τ : ℙ → 𝕌 is the codomain-restriction of □ : ℙ → 𝔻_{2}.

4.14. Remark. For future use, notice that a map f : Y → D_{2}X factorizes through UX ↪ D_{2}X if and only if f_{•} is monotone, and through F X ↪ D_{2}X if and only if f_{•} preserves finite infima.

4.15. Initial lifts of Kleisli extensions.. Fix a monad morphism α : 𝕊 → 𝕋, where 𝕋 = (T, η, μ) is coherent Sup-enriched via τ, and 𝕊 = (S, δ, ν). We will now study extensions of the form α^{∗}(T_{V}^{τ}). Since initial lifts commute with strata extensions, it actually suffices to study V = 2, and from now on we write \overline{S} := α^{∗}(T^{τ}). In this context, each ν_{X} is monotone: in the commutative diagram

\xymatrix{SSX \ar[r]^{α_{SX}} \ar[d]_{ν_{X}} & T SX \ar[r]^{T α_{X}} & T T X \ar[d]^{μ_{X}} \\ SX \ar[rr]_{α_{X}} &  & T X}

the upper-right path is monotone, so ν_{X} is monotone by initiality of α_{X}. Observe that δ and ν become oplax transformations with respect to \overline{S}.

We introduce a natural transformation α^{∨} : P S → T via

α_{X}^{∨} := ⋁ P α_{X} = μ_{X} · τ_{T X} · P α_{X} = α_{X}^{𝕋} · τ_{SX} ,

or equivalently, α_{X}^{∨}(A) = ⋁ α_{X}[A] for all A ⊆ SX. Each α_{X}^{∨} preserves suprema, and therefore has a right adjoint which we denote by α_{X}^{↓} : T X → P SX. Clearly,

α_{X}^{↓}(𝔣) = { 𝔵 ∈ SX | α_{X}(𝔵) ≤ 𝔣 } .

The maps α_{X}^{↓} allow for a convenient description of \overline{S} = α^{∗}(T^{τ}). Indeed, for r : X \overrightarrow{}Y we have

(\overline{S}r)^{♭} = α_{X}^{↓} · r^{τ} · α_{Y} .

In particular, the order relation ≤\overline{S} on SX satisfies (≤\overline{S})^{♭} = α_{X}^{↓} · α_{X}.

4.16. Sup-generating morphisms.. We say that 𝔵 ∈ T X is α-approachable if it is in the image of α_{X}^{∨}. We call α sup-generating in (𝕋, τ) if each α_{X}^{∨} is surjective, that is, if

α^{∨} · α^{↓} = 1 ,

or equivalently,

∀𝔣 ∈ T X ∃A ⊆ SX : 𝔣 = ⋁ α_{X}[A],

holds. When 𝕊 is a submonad of 𝕋 and the embedding is sup-generating, we simply say that 𝕊 is sup-generating in 𝕋.

Observe that a morphism of Sup-enriched monads is sup-generating if and only if every α_{X} is surjective. Indeed, for α : (𝕊, σ) → (𝕋, τ), α_{X}^{∨} is just the diagonal in (3) of 4.2, and ν_{X} · σ_{SX} is always surjective.

4.17. The first interpolation condition.. We say that a morphism α : 𝕊 → 𝕋 interpolates a relation r : SX \overrightarrow{}Y (in the Sup-enriched monad (𝕋, τ)) if

α_{X}^{↓} · α_{X}^{∨} · r^{♭} ≤ (≤_{\overline{S}X}^{♭} · ν_{X})^{ℙ} · (\overline{S}r)^{♭} · δ_{Y}

holds (where \overline{S} = α^{∗}(T^{τ})). The above condition expands to α_{X}^{↓} · α_{X}^{∨} · r^{♭} ≤ (α_{X}^{↓} · α_{X} · ν_{X})^{ℙ}· α_{SX}^{↓} · r^{τ} · η_{Y} and can be written pointwise as

α_{X}(𝔵) ≤ ⋁{ α_{X}(𝔶) | r(𝔶, y) = ⊤ } ⟹ ∃𝔛 ∈ SSX : 𝔵 ≤ ν_{X}(𝔛) & α_{SX}(𝔛) ≤ r^{τ} · η_{Y} (y)

for all 𝔵 ∈ SX, y ∈ Y; note that α_{SX}(𝔛) ≤ r^{τ} · η_{Y} (y) is equivalent to \overline{S}r(𝔛, δ_{Y} (y)) = ⊤. If 𝕊 is a submonad of 𝕋, the previous condition naturally has a simpler expression, and may be represented graphically by

𝔵 ≤ μ_{X} · r^{τ} · η_{Y} (y)  ⟹  ∃ 𝔛 : \xymatrix{ & 𝔛 \ar@{|->}[d] & ≤ r^{τ} · η_{Y} (y) \\ 𝔵 ≤ & μ_{X}(𝔛)}

The morphism α : 𝕊 → 𝕋 satisfies the first interpolation condition in (𝕋, τ) if it interpolates every relation r : SX \overrightarrow{}Y.

4.18. The second interpolation condition.. A morphism α : 𝕊 → 𝕋 satisfies the second interpolation condition (in the Sup-enriched monad (𝕋, τ)) if the following inequality

α_{X}^{𝕋} · r^{τ} · α_{Y} ≤ α_{X}^{∨} · P ν_{X} · (\overline{S}r)^{♭}

holds for all relations r : SX \overrightarrow{}Y (where \overline{S} = α^{∗}(T^{τ})). In pointwise notation, this condition becomes

μ_{X} · T α_{X} · r^{τ} · α_{Y} (𝔶) ≤ ⋁{ α_{X} · ν_{X}(𝔛) | 𝔛 ∈ SSX : α_{SX}(𝔛) ≤ r^{τ} · α_{Y} (𝔶) } ,

for all 𝔶 ∈ SY. Note that this can be read as an equality, since

α_{X}^{∨} · P ν_{X} · α_{SX}^{↓} · r^{τ} · α_{Y} ≤ α_{X}^{𝕋} · r^{τ} · α_{Y}

always holds. Indeed, we have

α_{X}^{∨} · P ν_{X} = (α_{X} · 1_{SX}^{𝕊})^{𝕋} · τ_{SSX} = (α_{X}^{𝕋} · α_{SX})^{𝕋} · τ_{SSX} = α_{X}^{𝕋} · α_{SX}^{∨}  (5)

so that α_{X}^{∨} · P ν_{X} · α_{SX}^{↓} ≤ α_{X}^{𝕋}, and we can conclude by composing each side with r^{τ} · α_{Y} on the right.

Let us point out that if α is sup-generating, then it satisfies the second interpolation condition. This is immediate from (5) upon composing with α_{SX}^{↓}.

4.19. Interpolating morphisms.. A monad morphism α : 𝕊 → 𝕋 is interpolating in (𝕋, τ) if it satisfies the first and second interpolation conditions. If 𝕊 is a submonad of 𝕋 and the embedding is interpolating, we may simply say that 𝕊 is interpolating in 𝕋.

Notice that α is interpolating whenever it is a morphism of coherent Sup-enriched monads α : (𝕊, σ) → (𝕋, τ). Indeed, if 𝔛 := r^{σ}(𝔶) ∈ SSX, then we get

α_{X} · ν_{X}(𝔛) = μ_{X} · T α_{X} · r^{τ} · α_{Y} (𝔶) and α_{SX}(𝔛) = r^{τ} · α_{Y} (𝔶) .

Therefore, the second interpolation condition is verified, and the first follows by setting 𝔶 := δ_{Y} (y).

4.20. Examples.

1. Any Sup-enriched monad 𝕋 = (T, η, μ) comes with a monad morphism η : 𝕀 → 𝕋. By the fact that τ_{X} = ⋁ P η_{X} (see 4.1), both interpolation conditions may easily be seen to hold. That is, η is always interpolating.

2. If 𝕊 = ℙ is the powerset monad embedded in 𝕋 = 𝔽 via the principal filter morphism τ : ℙ → 𝔽, then the interpolation conditions are immediate since ℙ is Sup-enriched.

3. In the case where 𝕋 = 𝔽 is the filter monad, and 𝕊 = 𝔹 the ultrafilter monad, we simply have for 𝔣 ∈ F Y and r : X \overrightarrow{}Y that r^{τ}(𝔣) is the filter on X given by

r^{τ}(𝔣) = r^{♭}[𝔣] = ↑{ r^{♭}[B] | B ∈ 𝔣 } .

To see that 𝔹 is interpolating in 𝔽, it is sufficient to verify the first interpolation condition, since 𝔹 is sup-generating in 𝔽. For ultrafilters 𝔵, 𝔶 on X and a relation a : βX \overrightarrow{}X, the inequality 𝔵 ≤ Σ_{X} · a^{τ}(𝔶) translates as

∀B ∈ 𝔶 (a^{♭}[B] ⊆ A^{𝔹} ⟹ A ∈ 𝔵) ,

for all A ⊆ X (where A^{𝔹} = { 𝔷 ∈ βX | A ∈ 𝔷 }). If there existed A ∈ 𝔵 and B ∈ 𝔶 with A^{𝔹} ∩ a^{♭}[B] = ∅, we would have a^{♭}[B] ⊆ (A^{𝔹})^{c} = (A^{c})^{𝔹} (here A^{c} denotes the set-complement of A), so that A^{c} ∈ 𝔵, a contradiction. Therefore, A^{𝔹} ∩ a^{♭}[B] ≠ ∅ for all A ∈ 𝔵 and B ∈ 𝔶, and there exists an ultrafilter 𝔛 on βX that refines both { A^{𝔹} | A ∈ 𝔵 } and a^{τ}(𝔶). This implies that Σ_{X}(𝔛) = 𝔵, and we can conclude by setting 𝔶 = η_{X}(y).

5. Kleisli structures and lax algebras

5.1. Kleisli monoids.. Let (𝕋, τ) be a coherent Sup-enriched monad. The category KlMon(𝕋) of Kleisli monoids has as objects pairs (X, c), where X is a set, and its structure c : X → T X is an extensive and idempotent map:

η_{X} ≤ c and c ∘ c ≤ c .

Morphisms f : (X, c) → (Y, d) are Set-maps f : X → Y satisfying:

T f · c ≤ d · f.

Contrasting the conditions on the structure on a Kleisli monoid with the reflexivity and transitivity conditions of a lax algebra as in (2) of 3.9, we note the strong parallel between the two concepts. This parallel will be analyzed in more detail in Theorem 5.6 and its subsequent results.

5.2. Examples.

1. If one takes for 𝕋 the powerset monad ℙ, then KlMon(ℙ) is the category of reflexive and transitive relations. That is, KlMon(ℙ) is concretely isomorphic to the category Ord of preordered sets.

2. Let 𝕋 be the up-set monad 𝕌. Remark 4.14 tells us that a map i : X → UX corresponds to a monotone map i_{•} : P X → P X. The discussion in Section 4.11 then shows that i is extensive and idempotent if and only if i_{•} satisfies

A ⊇ i_{•}(A) and i_{•} · i_{•}(A) ⊇ i_{•}(A)

for all A ∈ P X, that is, if and only if i_{•} is an interior operator on X. One easily checks that KlMon(𝕌)-morphisms correspond to continuous maps f : (X, i_{•}) → (Y, j_{•}), that is, maps f : X → Y such that

f^{−1}(j_{•}(A)) ⊆ i_{•}(f^{−1}(A))

for all A ⊆ Y. Hence, KlMon(𝕌) is concretely isomorphic to the category Int of interior spaces, and therefore also concretely isomorphic to the category Cls of closure spaces.

3. Let us consider now the filter monad 𝔽. From Remark 4.14 and the previous example, it follows that KlMon(𝔽)-structures on a set X correspond to interior operators which preserve finite infima, that is, to topologies on X. Thus, KlMon(𝔽) is concretely isomorphic to the category Top of topological spaces. The “monadic” presentation of topological spaces as Kleisli monoids is exactly Hausdorff’s original definition [9] of topological spaces by way of neighborhood systems, rephrased in categorical terms (and without the Hausdorff separation condition). See [12] for applications and further references.

4. Since there is a monad morphism τ : ℙ → 𝕋, any Eilenberg-Moore algebra (X, a : T X → X) is a sup-semilattice X with supremum given by a · τ_{X} (as in 4.1). Moreover, we have

a · (μ_{X} · τ_{T X}) = a · T a · τ_{T X} = (a · τ_{X}) · P a ,

so a is a sup-map and therefore has a right adjoint a^{∗} : X → T X. On one hand, a · η_{X} ≤ 1_{X} implies η_{X} ≤ a^{∗}. On the other, a · μ_{X} ≤ a · T a yields μ_{X} ≤ a^{∗} · a · T a, so

a^{∗} ∘ a^{∗} = μ_{X} · T a^{∗} · a^{∗} ≤ a^{∗} · a · T (a · a^{∗}) · a^{∗} ≤ a^{∗} .

Therefore, (X, a^{∗}) is a Kleisli 𝕋-algebra, and the Eilenberg-Moore category Set^{𝕋} is a subcategory of KlMon(𝕋). More precisely, there is a faithful functor Set^{𝕋} → KlMon(𝕋) (not necessarily full, as the examples below demonstrate) that is injective on objects.

This example presents the category Sup ≅ Set^{ℙ} of sup-semilattices as a subcategory of Ord, and the category Cnt ≅ Set^{𝔽} of continuous lattices [6] as a subcategory of Top. Moreover, the topology obtained on continuous lattices via the previous considerations is the Scott topology [8].

5.3. Supercategories of the category of Kleisli monoids.. Let us introduce the following supercategories of KlMon(𝕋): the objects of the category K(𝕋) are pairs (X, c : X → T X), and the morphisms f : (X, c) → (Y, d) are maps f : X → Y such that T f · c ≤ d · f. We also introduce the following full subcategories of K(𝕋) = KlMon_{0}(𝕋):

• KlMon_{1}(𝕋) is the full subcategory of KlMon_{0}(𝕋) whose objects have an extensive structure;

• KlMon_{2}(𝕋) is the full subcategory of KlMon_{0}(𝕋) whose objects have an idempotent structure.

Giving a concrete description of the various categories of the form KlMon_{i}(𝕋) for the monads mentioned in Examples 5.2 is straightforward. For instance, KlMon_{1}(𝔽) is concretely isomorphic to the category of pretopological spaces.

5.4. Supercategories of lax algebras.. Let 𝕋 = (T, η, μ) be a monad on Set together with a lax extension \overline{T} of T. We say a V-relation a : T X \overrightarrow{}Y is

• antitone if a · (≤\overline{T}) ≤ a holds, and

• left unitary if η_{Y}^{∘} · \overline{T} a ≤ a · μ_{X} holds.

In the notations of 3.9, the left unitary condition may be rephrased as η_{Y}^{∘} ∗a ≤ a. Observe also that the structure V-relation of a lax algebra (X, a) is antitone as well as left unitary.

Denote by A(𝕋, V) the category whose objects are pairs (X, a) (with a : T X \overrightarrow{}X a V-relation), and whose morphisms f : (X, a) → (Y, b) are the maps f : X → Y satisfying f · a ≤ b · T f. We define the following full subcategories of A(𝕋, V):

• the objects of Alg_{0}(𝕋, V) are those pairs (X, a) whose structure a is antitone and left unitary;

• Alg_{1}(𝕋, V) is the full subcategory of Alg_{0}(𝕋, V) whose objects have a reflexive structure;

• Alg_{2}(𝕋, V) is the full subcategory of Alg_{0}(𝕋, V) whose objects have a transitive structure.

5.5. Relating lax algebras and Kleisli monoids.. Guided by the example of topological spaces, which can be described not only via neighborhood filters or via filter convergence, but also by the convergence of ultrafilters, we are going to compare KlMon(𝕋) to Alg(𝕊, 2), where the monad 𝕊 is related to the coherent Sup-enriched monad (𝕋, τ) by way of a monad morphism α : 𝕊 → 𝕋. The following Theorem will follow directly from Proposition 5.13:

5.6. Theorem. Let α : 𝕊 → 𝕋 be a monad morphism with 𝕋 coherent Sup-enriched via τ, and set \overline{S} = α^{∗}(T^{τ}). If α is sup-generating and interpolating then the dotted arrows in the following diagram are concrete isomorphisms:

[figure: KlMon(𝕋); ≅; KlMon_{1}(𝕋); ≅; Alg(𝕊, 2); Alg_{1}(𝕊, 2); KlMon_{2}(𝕋); ≅; KlMon_{0}(𝕋) = K(𝕋); ≅; Alg_{2}(𝕊, 2); Alg_{0}(𝕊, 2); A(𝕊, 2)]

The case of the inclusion α : 𝔹 → 𝔽 is treated in [11], which inspired the following presentation.

Until the end of this section, we fix a coherent Sup-enriched monad (𝕋, τ) with 𝕋 = (T, η, μ), a monad 𝕊 = (S, δ, ν), a monad morphism α : 𝕊 → 𝕋, and we set \overline{S} = α^{∗}(T^{τ}).

5.7. The underlying adjunction.. For sets X and Y, we define an adjunction

[figure: Rel(SX, Y); ϕ; ⊥; Set(Y, T X); ψ] ,

as follows. By using the isomorphism Rel(SX, Y) ≅ Set(Y, P SX) in Ord, we define

ϕ : Set(Y, P SX) → Set(Y, T X) , r^{♭} ↦ α_{X}^{∨} · r^{♭} ,
ψ : Set(Y, T X) → Set(Y, P SX) ,  c ↦ α_{X}^{↓} · c .

The adjunction ϕ ⊣ ψ follows from α_{X}^{∨} ⊣ α_{X}^{↓}. In pointwise notation, ϕ and ψ can be expressed by

ϕ(r)(y) = ⋁ α_{X}[r^{♭}(y)] and ψ(c)(𝔵, y) = ⊤ ⟺ α_{X}(𝔵) ≤ c(y) ,

for r : SX \overrightarrow{}Y, and c : Y → T X. As usual, ϕ and ψ restrict to mutually inverse isomorphisms between the sets of fixpoints of ψ · ϕ and of ϕ · ψ, respectively.

5.8. Fixpoints of the adjunction.. Obviously, the fixpoints of ϕ · ψ are those maps c : Y → T X such that c(y) is α-approachable for all y ∈ Y. Unwinding the fixpoint condition for ψ · ϕ, we see that the fixpoints are those relations r : SX \overrightarrow{}Y such that r^{♭}(y) is α-closed for all y ∈ Y, where a subset A ⊆ SX is α-closed if

α_{X}(𝔵) ≤ ⋁ α_{X}[A] ⟹ 𝔵 ∈ A .

The latter terminology is borrowed from [11], where α : 𝔹 → 𝔽 is the inclusion, and the α-closed subsets of βX are precisely the closed sets of the so-called Zariski topology, which arises from the free compact Hausdorff space on X.

While the α-closed subsets are closed under arbitrary intersection, they are in general not closed under finite unions.

Observe that r^{♭}(y) is 1_{𝕋}-closed if and only if r is continuous, that is, if and only if

r(⋁ A, y) = ⋀_{x∈A} r(x, y)

holds for any A ⊆ T X. This concept of continuity was used in [20] and [18] to obtain Theorem 5.6 for the special case α = 1_{𝕋}.

5.9. Lemma. A relation r : SX \overrightarrow{}Y is a fixpoint of ψ ·ϕ if and only if it is interpolated by α, left unitary, and antitone.

Proof. Observe that for any antitone and left unitary relation r : SX \overrightarrow{}Y, we have in fact r · (≤\overline{S}) = r (see 3.2) and δ_{Y}^{∘} · \overline{S}r · ν_{X}^{∘} = r. Indeed, to see that the left unitary condition δ_{Y}^{∘} · \overline{S}r · ν_{X}^{∘} ≤ r is in fact an equality, recall that δ : 1 → \overline{S} is oplax, so that r ≤ δ_{Y}^{∘} · \overline{S}r · δ_{SX}, hence

r = r · δ_{SX}^{∘} · ν_{X}^{∘} ≤ δ_{Y}^{∘} · \overline{S}r · δ_{SX} · δ_{SX}^{∘} · ν_{X}^{∘} ≤ δ_{Y}^{∘} · \overline{S}r · ν_{X}^{∘} .

Thus, by applying −^{♭}, we observe that a relation r : SX \overrightarrow{}Y is left unitary precisely when

r^{♭} = P ν_{X} · (\overline{S}r)^{♭} · δ_{Y}

holds, while r is antitone if and only if (≤♭ ; \overline{S})^{ℙ} · r^{♭} = r^{♭}.

Suppose that r : SX \overrightarrow{}Y is antitone and left unitary. We have:

r^{♭} = (≤♭ ; \overline{S})^{ℙ} · r^{♭}  (r antitone)
= (≤♭ ; \overline{S})^{ℙ} · P ν_{X} · (\overline{S}r)^{♭} · δ_{Y}  (r left unitary)

= (≤♭ ; \overline{S} ·ν_{X})^{ℙ} · (\overline{S}r)^{♭} · δ_{Y} .

Therefore, if r is interpolated by α, we have α_{X}^{↓} · α_{X}^{∨} · r^{♭} ≤ (≤♭ ; \overline{S} ·ν_{X})^{ℙ} · (\overline{S}r)^{♭} · δ_{Y} = r^{♭}, that is, r is a fixpoint of ψ · ϕ.

Conversely, any fixpoint r of ψ ·ϕ is of the form ψ(c) for some c, hence clearly antitone. Similarly, if \overline{S}r(𝔛, δ_{X}(y)) = ⊤ holds, we can apply μ_{X} · T α_{X} to each side of the inequality α_{SX}(𝔛) ≤ r^{τ} ·η_{X}(y), and conclude that r(ν_{X}(𝔛), y) = ⊤ by the fixpoint condition. Finally, since any fixpoint is left unitary and antitone, we see that it is interpolated by α due to the displayed equation above.

5.10. Proposition. The ordered sets of all c : Y → T X which are pointwise αapproachable and of all r : SX \overrightarrow{}Y which are antitone, left unitary, and interpolated by α are isomorphic.

Proof. This is immediate from the previous lemma.

5.11. Lemma. The map ϕ satisfies

ϕ(δ_{X}^{∘}) = η_{X}  and  ϕ(s ∗ r) ≤ ϕ(r) ∘ ϕ(s)

for all r : SX \overrightarrow{}Y and s : SY \overrightarrow{}Z. As a consequence, the conditions

δ_{X}^{∘} ≤ ψ(η_{X})  and  ψ(d) ∗ ψ(c) ≤ ψ(c ∘ d)

hold for all c : Y → T X, d : Z → T Y.

Moreover, ϕ satisfies ϕ(s ∗ r) = ϕ(r) ∘ ϕ(s) if and only if α satisfies the second interpolation condition.

Proof. By recalling that (δ_{X}^{∘})^{♭} = ι_{SX} · δ_{X}, we obtain ϕ(δ_{X}^{∘}) = α_{X}^{𝕋} · τ_{SX} · ι_{SX} · δ_{X} = α_{X}^{𝕋} · η_{SX} · δ_{X} = α_{X} · δ_{X} = η_{X}. To show ϕ(s ∗ r) ≤ ϕ(r) ∘ ϕ(s), observe that

(α_{X}^{∨} · r^{♭})^{𝕋} = (α_{X}^{𝕋} · τ_{SX} · r^{♭})^{𝕋} = α_{X}^{𝕋} · (τ_{SX} · r^{♭})^{𝕋} = α_{X}^{𝕋} · r^{τ} ,  (6)

and recall from 4.18 that α_{X}^{𝕋} · r^{τ} · α_{Y} ≥ α_{X}^{∨} · P ν_{X} · (\overline{S}r)^{♭} holds. Therefore, we get

(α_{X}^{∨} · r^{♭})^{𝕋} · α_{Y}^{∨} = α_{X}^{𝕋} · (τ_{SX} · r^{♭})^{𝕋} · α_{Y}^{𝕋} · τ_{SY}
= (α_{X}^{𝕋} · r^{τ} · α_{Y})^{𝕋} · τ_{SY}
≥ (α_{X}^{∨} · P ν_{X} · (\overline{S}r)^{♭})^{𝕋} · τ_{SY}
= α_{X}^{𝕋} · (τ_{SX} · P ν_{X} · (\overline{S}r)^{♭})^{𝕋} · τ_{SY}
= α_{X}^{𝕋} · τ_{SX} · (P ν_{X} · (\overline{S}r)^{♭})^{ℙ}
= α_{X}^{∨} · (P ν_{X} · (\overline{S}r)^{♭})^{ℙ}

so that ϕ(r)∘ϕ(s) = (α_{X}^{∨} ·r^{♭})^{𝕋}·α_{Y}^{∨} ·s^{♭} ≥ α_{X}^{∨} ·P ν_{X} ·((\overline{S}r)^{♭})^{ℙ}·s^{♭} = α_{X}^{∨} ·(s·\overline{S}r·ν_{X}^{∘})^{♭} = ϕ(s∗r).

If the second interpolation condition holds, then the last two inequalities become equalities. To show the converse claim, observe that α_{Y} = α_{Y}^{𝕋} ·η_{SY} = α_{Y}^{𝕋} ·τ_{SY} ·ι_{SY} = α_{Y}^{∨} ·ι_{SY} and ι_{SY} = (1_{SY})^{♭}. Putting these equalities together, using (6) above, and assuming that ϕ(r) ∘ ϕ(s) = ϕ(s ∗ r), we obtain:

α_{X}^{𝕋} · r^{τ} · α_{Y} = (α_{X}^{∨} · r^{♭})^{𝕋} · (α_{Y}^{∨} · 1_{SY}^{♭}) = ϕ(r) ∘ ϕ(1_{SY}) = ϕ(1_{SY} ∗ r)
= α_{X}^{∨} · (1_{SY} · \overline{S}r · ν_{X}^{∘})^{♭} = α_{X}^{∨} · ((ν_{X}^{∘})^{♭})^{ℙ} · (\overline{S}r)^{♭} = α_{X}^{∨} · P ν_{X} · (\overline{S}r)^{♭},

so the second interpolation condition holds. The claims for ψ follow from the adjunction ϕ ⊣ ψ.

5.12. The main adjunction.. We are now in a position to prove Theorem 5.6. Define concrete functors

Ψ : K(𝕋) → A(𝕊, 2) and Φ : A(𝕊, 2) → K(𝕋)

by applying ψ and ϕ to the structures; that is, Ψ(X, c) = (X, ψ(c)) and Φ(X, r) = (X, ϕ(r)). The fact that Ψ and Φ send morphisms to morphisms follows easily from the definitions. These functors yield the isomorphisms of Theorem 5.6. The situation is analyzed in detail in the following result, of which 5.6 is an immediate consequence.

5.13. Proposition. The functor Ψ is right adjoint to Φ. Moreover, Ψ and Φ restrict as the solid arrows in the diagram below, leading to adjunctions between Alg_{i}(𝕊, 2) and KlMon_{i}(𝕋) for i = 0, 1 as in the right vertical face of the diagram below.

[figure: KlMon(𝕋); Ψ; KlMon_{1}(𝕋); Ψ; Alg(𝕊, 2); Φ; Alg_{1}(𝕊, 2); Φ; KlMon_{2}(𝕋); Ψ; KlMon_{0}(𝕋); Ψ; Alg_{2}(𝕊, 2); Φ; Alg_{0}(𝕊, 2); Φ]

If α satisfies the second interpolation condition, we get restrictions of Φ as the dashed arrows above, hence adjunctions between KlMon_{2}(𝕋) and Alg_{2}(𝕊, 2) as well as between KlMon(𝕋) and Alg(𝕊, 2).

If α is sup-generating, then Ψ and all its restrictions in the diagram above are full reflective embeddings.

If α is interpolating, then Φ and all its restrictions as above are full coreflective embeddings.

Proof. The adjunction Φ ⊣ Ψ follows from ϕ ⊣ ψ. The other properties are immediate from 5.9–5.11 (recall that α satisfies the second interpolation condition provided it is supgenerating).

5.14. Corollary. There are concrete isomorphisms

KlMon_{0}(𝕋) ≅ Alg_{0}(𝕋, 2) ,  KlMon_{2}(𝕋) ≅ Alg_{2}(𝕋, 2) ,
KlMon_{1}(𝕋) ≅ Alg_{1}(𝕋, 2) ,  KlMon(𝕋) ≅ Alg(𝕋, 2) .

Proof. The monad morphism 1_{𝕋} is sup-generating and interpolating.

5.15. Corollary. If α : 𝕊 → 𝕋 is interpolating in (𝕋, τ), then Alg_{i}(𝕊, 2) is a coreflective subcategory of Alg_{i}(𝕋, 2) for i = 0, 1, 2, and Alg(𝕊, 2) is a concrete coreflective subcategory of Alg(𝕋, 2). Moreover, if α is also sup-generating, then these coreflections are isomorphisms.

Proof. Simply compose the coreflections from Proposition 5.13 with the isomorphisms from Corollary 5.14.

5.16. Remark. In the case where α is interpolating, the coreflection Alg(𝕋, 2) → Alg(𝕊, 2) is simply the functor F_{α} (considered in 3.12) which sends (X, a : T X \overrightarrow{}X) to (X, a · α_{X} : SX \overrightarrow{}X). The concrete coreflective embedding Alg(𝕊, 2) → Alg(𝕋, 2) then sends a structure a : SX \overrightarrow{}X to â : T X \overrightarrow{}X, where

â(𝔣, y) = ⋀{ a(𝔵, y) | 𝔵 ∈ SX : α_{X}(𝔵) ≤ 𝔣 } ,

for all 𝔣 ∈ T X, y ∈ X.

5.17. Examples.

1. The category RRel of reflexive relations and relation-preserving maps can be described either as Alg_{1}(𝕀, 2), KlMon_{1}(ℙ), or Alg_{1}(ℙ, 2), depending on whether a relation r on a set X is seen as a map

r : X × X → 2 ,  r : X → P X ,  or even r : P X × X → 2

respectively. Similarly, the category Ord of preordered sets can be obtained as any of the three categories

Alg(𝕀, 2) ≅ KlMon(ℙ) ≅ Alg(ℙ, 2) .

2. The category PrTop of pretopological spaces and continuous maps can be presented via convergence of ultrafilters as Alg_{1}(𝔹, 2), via neighborhood systems as KlMon_{1}(𝔽, 2), or via convergence of filters as Alg_{1}(𝔽, 2). The corresponding descriptions of the category Top of topological spaces are

Alg(𝔹, 2) ≅ KlMon(𝔽) ≅ Alg(𝔽, 2) .

3. The concretely isomorphic categories Int and Cls of interior and closure spaces respectively can be described either as Alg(𝕌, 2) or as KlMon(𝕌, 2). The objects of Alg_{1}(𝕌, 2) ≅ KlMon_{1}(𝕌) are preclosure spaces, that is, sets X equipped with a monotone and extensive map P X → P X. The resulting category is denoted by PrCls.

4. Thanks to the previous examples, Corollary 5.15 may be applied to the diagram of 2.7(7) to get either of the two chains of coreflective embeddings below:

\xymatrix{RRel \ar[r] & PrTop \ar[r] & PrCls \\ Ord \ar[r] & Top \ar[r] & Cls .}

5. By example 5.2(4) and Theorem 5.6, every 𝕋-algebra is a (𝕋, 2)-algebra (for the Kleisli extension \overline{T}), so that the latter concept is indeed a generalization of the former. This fact is a priori not obvious because in general T a ≠ \overline{T} a for Set-maps a : T X → X, and should be contrasted with the case of Barr’s extension that satisfies \overline{T} f = T f for any map f : X → Y.

6. Extending Alg(𝕋, 2) to Alg(𝕋, V)

6.1. Tower extensions.. Let us first recall the original definition of a tower extension from [21]. Consider a topological functor G : C → Set, and denote by G_{X} the fiber of G over a set X. By topologicity of G, every G_{X} is a complete lattice with respect to the order

A ≤ B ⟺ 1_{X} : A → B is a C-morphism,

for all A, B ∈ C with GA = X = GB. If V is a complete lattice, the tower extension C[V] of C is the concrete category defined as follows:

(i) objects are V-towers of C-objects, that is, pairs (X, ϕ), with X a set and ϕ : V^{op} → G_{X} an inf-map;

(ii) morphisms f : (X, ϕ) → (Y, ψ) are given by maps f : X → Y such that for each v ∈ V, f : ϕ(v) → ψ(v) is a C-morphism.

For v ∈ V, we call ϕ(v) the component of ϕ at v. Observe that we have C[1] ≅ Set and C[2] ≅ C.

6.2. Proposition. Consider a monad 𝕋 = (T, η, μ) on Set with a lax extension \overline{T} of T to Rel. The concrete functors

A(𝕋, V) → A(𝕋, 2)[V], (X, a) ↦ (X, (v ↦ a_{v})),

and

A(𝕋, 2)[V] → A(𝕋, V), (X, ϕ) ↦ (X, r_{ϕ}),

are mutually inverse and restrict to an isomorphism A_{0}(𝕋, V) ≅ A_{0}(𝕋, 2)[V].

Proof. Using the laws from 2.4, one checks easily that the assignments above define functors. The fact that they are mutually inverse also follows from 2.4.

6.3. Proposition. Let 𝕋 = (T, η, μ) be a monad on Set with a lax Rel-extension \overline{T} of T. For any (X, a) ∈ A(𝕋, V), we have

• a : T X \overrightarrow{}X is reflexive if and only if a_{k} ∈ Rel(T X, X) is reflexive.

• a is transitive if and only if a_{v} ∗ a_{u} ≤ a_{u⊗v} holds for all u, v ∈ V.

Proof. The first statement is obvious.

Assume now that (X, a) is transitive. It suffices to show that a_{v} · (T_{V}a)_{u} ≤ a_{u⊗v} · μ_{X}. For x ∈ X, let 𝔛 ∈ (a_{v} · (T_{V}a)_{u})^{♭}(x), so there exists 𝔵 ∈ T X with v ≤ a(𝔵, x) and u ≤ T_{V}a(𝔛, 𝔵). Therefore,

u ⊗ v ≤ ⋁_{𝔵∈T X} T_{V}a(𝔛, 𝔵) ⊗ a(𝔵, x) = a · T_{V}a(𝔛, x) ≤ a · μ_{X}(𝔛, x) .

Since (a · μ_{X})_{w} = a_{w} · μ_{X} holds, we are done.

Conversely, assume that a_{v} ∗ a_{u} ⊆ a_{u⊗v} holds for all u, v ∈ V. It suffices to show T_{V}a(𝔛, 𝔵) ⊗ a(𝔵, x) ≤ a(μ_{X}(𝔛), x) for all x ∈ X, 𝔵 ∈ T X, 𝔛 ∈ T T X. Fix such x, 𝔵, 𝔛 and set v := a(𝔵, x), A := { u ∈ V | T a_{u}(𝔛, 𝔵) = ⊤ }. We have T_{V}a(𝔛, 𝔵)⊗a(𝔵, x) = ⋁_{u∈A} u⊗v. For any u ∈ A, we have a_{v} · T a_{u} ≤ a_{u⊗v} · μ_{X}, so u ⊗ v ≤ a(μ_{X}(𝔛), x), and the claim is proved.

6.4. Reflexive and transitive towers.. The previous result motivates the following definitions. We say that (X, ϕ) ∈ A(𝕋, 2)[V] is

• reflexive if ϕ(k) is reflexive,

• transitive if ϕ(u) ∗ ϕ(v) ≤ ϕ(v ⊗ u) holds for all u, v ∈ V, and

• lax if it is both reflexive and transitive.

Any lax tower (X, ϕ) in A(𝕋, 2)[V] is componentwise left unitary, hence an element of Alg_{0}(𝕋, 2)[V]. Indeed, we have:

η_{X}^{∘} ∗ ϕ(v) ≤ ϕ(k) ∗ ϕ(v) ≤ ϕ(k ⊗ v) = ϕ(v) .

6.5. Proposition. The functors of Proposition 6.2 restrict to concrete isomorphisms between

• Alg_{1}(𝕋, V) and the full subcategory of Alg_{0}(𝕋, 2)[V] whose objects are the reflexive towers;

• Alg_{2}(𝕋, V) and the full subcategory of Alg_{0}(𝕋, 2)[V] whose objects are the transitive towers;

• Alg(𝕋, V) and the full subcategory of A(𝕋, 2)[V] whose objects are the lax towers.

Proof. This is immediate.

6.6. Corollary. If V is integral, then Alg_{1}(𝕋, V) and Alg_{1}(𝕋, 2)[V] are concretely isomorphic.

Proof. The statement follows from the previous result and the fact that a tower (X, ϕ) in Alg_{0}(𝕋, 2)[V] is reflexive if and only if ϕ(v) is reflexive for each v ≤ k.

6.7. Corollary. If V is a frame, then Alg(𝕋, V) and Alg(𝕋, 2)[V] are concretely isomorphic.

Proof. Assume that ⊗ = ∧ and each ϕ(v) is transitive. Take any u, v ∈ V. For w = u∧v we have ϕ(u) ≤ ϕ(w) and ϕ(v) ≤ ϕ(w), so that ϕ(u) ∗ ϕ(v) ≤ ϕ(w) ∗ ϕ(w) ≤ ϕ(w) = ϕ(v ∧ u). The conclusion follows from the previous results.

6.8. Remark. Observe that if (X, ϕ) is transitive, then ϕ(v) is transitive whenever v is idempotent in V. In particular, ϕ(k) is transitive for any transitive tower. This simple remark turns out to be useful in a number of results where an idempotent structure is sought in the multitude of ϕ(v), v ∈ V.

6.9. Tower extensions of Kleisli monoids.. Let KlMon(𝕋, V) denote the full subcategory of KlMon(𝕋)[V] whose objects are lax towers. Thus, an object of KlMon(𝕋, V) is a pair (X, (a^{v} : X → T X)_{v∈V}) where X is a set and the family (a^{v}) satisfies

a^{⋁ W} = ⋀_{w∈W} a^{w},  η_{X} ≤ a^{k},  a^{v} ∘ a^{u} ≤ a^{u⊗v},

for all W ⊆ V and u, v ∈ V.

6.10. Theorem. Let (𝕋, τ) be a coherent Sup-enriched monad, and α : 𝕊 → 𝕋 an interpolating and sup-generating monad morphism. With respect to the extension \overline{S} = α^{∗}(T_{V}^{τ}), there is a concrete isomorphism

Alg(𝕊, V) ≅ KlMon(𝕋, V).

Proof. By Lemma 5.11, the isomorphism Alg(𝕊, 2) ≅ KlMon(𝕋) from Theorem 5.6 is compatible with the operations ∗ and ∘ on the fibers of Alg(𝕊, 2) and KlMon(𝕋), respectively. Hence, this isomorphism lifts to the lax tower extensions.

6.11. Corollary. Let (𝕋, τ) be a coherent Sup-enriched monad. With respect to the extension T_{V}^{τ}, we have a concrete isomorphism Alg(𝕋, V) ≅ KlMon(𝕋, V).

Proof. One just uses the fact that 1_{𝕋} is interpolating and sup-generating. (Note that a similar result has been obtained in [20] under the additional assumption that V is constructively complete distributive).

6.12. Remark. The previous results suggest that categories fibered in “complete lattices with unital convolutions” provide an adequate setting in which to study laxly indexed towers. The latter are closely related to continuous relational presheaves on the one-object quantaloid V (see [17]).

6.13. Examples.

1. The category PrApp of preapproach spaces [13] can be described as any one of the concretely isomorphic categories below

Alg_{1}(𝔹, P_{+}) ≅ KlMon_{1}(𝔽, P_{+}) ≅ Alg_{1}(𝔽, P_{+}),

and the full subcategory App of approach spaces [14] can be described as

Alg(𝔹, P_{+}) ≅ KlMon(𝔽, P_{+}) ≅ Alg(𝔽, P_{+}).

2. As in [21], the categories of “fuzzy neighborhood convergence spaces” and of “fuzzy neighborhood spaces” are obtained as

Alg_{1}(𝔹, [0, 1]) ≅ KlMon_{1}(𝔽, [0, 1]) ≅ Alg_{1}(𝔽, [0, 1]),
Alg(𝔹, [0, 1]) ≅ KlMon(𝔽, [0, 1]) ≅ Alg(𝔽, [0, 1]).

where [0, 1] carries the quantale structure given by ∧. Analogous results hold for 𝕌, giving rise to various extensions of the category of interior (or closure) spaces.

3. Alg(𝔹, 2^{2}) is the category BiTop of bitopological spaces. This follows from 6.14 below. We can also describe BiTop as KlMon(𝔽, 2^{2}), or as Alg(𝔽, 2^{2}). Similar results hold for interior spaces, pretopological spaces, etc.

4. Tower extensions allow to effectively describe (𝕋, V)-algebras for simple lattices V. For instance, Alg(𝔹, {0, 1, 2}), where {0, 1, 2} carries ∧ as tensor, is concretely isomorphic to the category which has as objects triples (X, τ_{0}, τ_{1}), where τ_{0} ⊆ τ_{1} are topologies, and as morphisms maps which are separately continuous.

5. Another interesting example is given by the identity monad together with the nonintegral three-chain 3 of Example 2.2(4). Indeed, objects of Alg(𝕀, 3) are sets X with a map ϕ : 3 → Rel(X, X) such that ϕ(⊥) = r_{⊥} satisfies r_{⊥}(x, x) = ⊤ for all x ∈ X, ϕ(k) = r_{k} is a reflexive and transitive relation, and ϕ(⊤) = r_{⊤} is a relation such that r_{⊤} ≤ r_{k}, r_{⊤} · r_{k} ≤ r_{⊤}, and r_{k} · r_{⊤} ≤ r_{⊤}; morphisms of Alg(𝕀, 3) are maps that preserve the relations r_{k} and r_{⊤}. Therefore, Alg(𝕀, 3) is concretely isomorphic to the category whose objects are preordered sets (X, ≤) equipped with an auxiliary relation (see [8]), that is, a relation ≺ on X such that

x ≺ y ⟹ x ≤ y and x ≤ x′ ≺ y′ ≤ y ⟹ x ≺ y ,

for all x, x′, y, y′ ∈ X, and whose morphisms are ≺-preserving monotone maps.

6.14. Proposition. Let I be a set. For any topological category G : C → Set, the tower extension C[P I] by the powerset of I is concretely isomorphic to the category I-C, whose objects are pairs (X, (A_{i})_{I}) (with X a set, and each A_{i} an element of the fibre G_{A}), and morphisms f : (X, (A_{i})) → (Y, (B_{i})) are maps f : X → Y such that f : A_{i} → B_{i} is a C-morphism for each i ∈ I.

Proof. Recall that P I is the free Sup-lattice on I, therefore maps s : I → G_{B} correspond to inf-maps \overline{s} : P I^{op} → G_{B} via A ↦ ⋀ s(a), where ⋀ denotes the infimum in the fiber, that is, the initial lift.

Thus, we only need to show that this assignment is compatible with morphisms in the following sense: if f : A_{j} → B_{j} is a morphism for each j ∈ J, J ⊆ I, then f : (⋀_{J} A_{j}) → (⋀_{J} B_{j}) is also a morphism. To prove this, recall that each map f : X → Y gives rise to a monotone map f_{∗} : G_{X} → G_{Y} by forming final lifts along f. Thus, for each i ∈ J we have f_{∗}(⋀ A_{j}) ≤ f_{∗}(A_{i}) ≤ B_{i} since f : A_{i} → B_{i} is a morphism. Hence, f_{∗}(⋀ A_{j}) ≤ ⋀ B_{j} also holds, that is, f is a morphism (⋀ A_{j}) → (⋀ B_{j}).

References

[1] J. Adámek, H. Herrlich, and G.E. Strecker. Abstract and concrete categories: The joy of cats. Repr. Theory Appl. Categ., (17):1–507 (electronic), 2006. Reprint of the 1990 original.

[2] M. Barr. Relational algebras. In Reports of the Midwest Category Seminar, IV, number 137 in Lecture Notes in Mathematics, pages 39–55. Springer, 1970.

[3] M.M. Clementino and D. Hofmann. On extensions of lax monads. Theory Appl. Categ., 13(3):41–60 (electronic), 2004.

[4] M.M. Clementino, D. Hofmann, and W. Tholen. One setting for all: Metric, topology, uniformity, approach structure. Appl. Categ. Structures, 12(2):127–154, 2004.

[5] E. Colebunders and R. Lowen. Lax monads and algebras via initial monad morphisms. 2007. Preprint.

[6] A. Day. Filter monads, continuous lattices and closure systems. Canad. J. Math., 27:50–59, 1975.

[7] B. Fawcett and R.J. Wood. Constructive complete distributivity. I. Math. Proc. Camb. Phil. Soc., 107(1):81–89, 1990.

[8] G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M. Mislove, and D.S. Scott. Continuous Lattices and Domains. Number 93 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2003.

[9] F. Hausdorff. Grundzüge der Mengenlehre. Chelsea, 1949.

[10] D. Hofmann. Topological theories and closed objects. Adv. Math., 215(2):789–824, 2007.

[11] D. Hofmann and W. Tholen. Kleisli operations for topological spaces. Topology Appl., 153(15):2952–2961, 2006.

[12] U. Höhle. Many Valued Topology and its Applications. Kluwer, Boston, 2001.

[13] E. Lowen and R. Lowen. Topological quasitopos hulls of categories containing topological and metric objects. Cahiers Top. et Géom. Diff., 30(3):213–228, 1989.

[14] R. Lowen. Approach Spaces. Oxford Mathematical Monographs. Oxford University Press, New York, 1997. The missing link in the topology-uniformity-metric triad.

[15] E.G. Manes. Algebraic Theories. Springer-Verlag, New York, 1976. Graduate Texts in Mathematics, No. 26.

[16] E.G. Manes. Taut monads and T 0-spaces. Theoret. Comput. Sci., 275(1–2):79–109, 2002.

[17] K.I. Rosenthal. The Theory of Quantaloids, volume 348 of Pitman Research Notes in Mathematics Series. Longman, Harlow, 1996.

[18] C. Schubert. Lax Algebras—A Scenic Approach. PhD thesis, Universität Bremen, 2006.

[19] G.J. Seal. Canonical and op-canonical lax algebras. Theory Appl. Categ., 14(10):221– 243 (electronic), 2005.

[20] G.J. Seal. A Kleisli-based approach to lax algebras. Appl. Categ. Structures, 2007. To appear.

[21] D. Zhang. Tower extension of topological constructs. Comment. Math. Univ. Carolin., 41(1):41–51, 2000.

Fakultät für Informatik, Lehrstuhl X Technische Universität Dortmund 44221 Dortmund, Germany

School of Computer Science McGill University H3A 2A7 Montreal, Canada

Email: christoph.schubert@uni-dortmund.de
      gseal@fastmail.fm

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/21/7/21-07.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, McGill University: gavin seal@fastmail.fm

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Cuill Inc.: valeria@cuill.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca