Theory and Applications of Categories, Vol. 11, No. 15, 2003, pp. 337–352.

EXPONENTIABILITY IN CATEGORIES OF LAX ALGEBRAS

Dedicated to Nico Pumplün on the occasion of his seventieth birthday

MARIA MANUEL CLEMENTINO, DIRK HOFMANN AND WALTER THOLEN

ABSTRACT. For a complete cartesian-closed category V with coproducts, and for any pointed endofunctor T of the category of sets satisfying a suitable Beck-Chevalley-type condition, it is shown that the category of lax reflexive (T, V)-algebras is a quasitopos. This result encompasses many known and new examples of quasitopoi.

1. Introduction

Failure to be cartesian closed is one of the main defects of the category of topological spaces. But often this defect can be side-stepped by moving temporarily into the quasitopos hull of Top, the category of pseudotopological (or Choquet) spaces, see for example [11, 14, 7]. A pseudotopology on a set X is most easily described by a relation 𝔵 → x between ultrafilters 𝔵 on X and points x in X, the only requirement for which is the reflexivity condition x^{•} → x for all x ∈ X, with x^{•} denoting the principal ultrafilter on x. In this setting, a topology on X is a pseudotopology which satisfies the transitivity condition

𝔛 → 𝔶 & 𝔶 → z ⇒ m(𝔛) → z

for all z ∈ X, 𝔶 ∈ UX (the set of ultrafilters on X) and 𝔛 ∈ UUX; here the relation → between UX and X has been naturally extended to a relation between UUX and UX, and m = m_{X} : UUX → UX is the unique map that gives U together with e_{X}(x) = x^{•} the structure of a monad U = (U, e, m). Barr [2] observed that the two conditions, reflexivity and transitivity, are precisely the two basic laws of a lax Eilenberg-Moore algebra when one extends the Set-monad U to a lax monad of Rel(Set), the category of sets with relations as morphisms. In [9] Barr’s presentation of topological spaces was extended to include Lawvere’s presentation of metric spaces as V-categories with V = \overline{ℝ}_{+}, the extended real half-line. Thus, for any symmetric monoidal category V with coproducts preserved by the tensor product, and for any Set-monad T that suitably extends from Set-maps to all V-matrices (or “V-relations”, with ordinary relations appearing for V = 2, the twoelement chain), the paper [9] develops the notion of reflexive and transitive (T, V)-algebra, investigates the resulting category Alg(T, V), and presents many examples, in particular Top = Alg(U, 2).

The authors acknowledge partial financial assistance by Centro de Matemática da Universidade de Coimbra/FCT, Unidade de Investigação e Desenvolvimento Matemática e Aplicações da Universidade de Aveiro/FCT and NSERC.

Received by the editors 2003-01-23 and, in revised form, 2003-09-04.

Transmitted by Richard Wood. Published on 2003-09-18.

2000 Mathematics Subject Classification: 18C20, 18D15, 18A05, 18B30, 18B35.

Key words and phrases: lax algebra, partial product, locally cartesian-closed category, quasitopos.

\begin{matrix}c \\ ◯ \end{matrix} Maria Manuel Clementino, Dirk Hofmann and Walter Tholen, 2003. Permission to copy for private use granted.

The purpose of this paper is to show that dropping the transitivity condition leads us to a quasitopos not only in the case of Top, but rather generally. In order to define just reflexive (T, V)-algebras, one indeed needs neither the tensor product of V (just the “unit” object) nor the “multiplication” of the monad T. Positively speaking then, we start off with a category V with coproducts and a distinguished object I in V and any pointed endofunctor T of Set and define the category Alg(T, V). Our main result says that when V is complete and locally cartesian closed and a certain Beck-Chevalley condition is satisfied, also Alg(T, V) is locally cartesian closed (Theorem 3.7).

Defining reflexive (T, V)-algebras for the “truncated” data T, V entails a considerable departure from [9], as it is no longer possible to talk about the bicategory Mat(V) of V-matrices. The missing tensor product prevents us from being able to introduce the (horizontal) matrix composition; however, “whiskering” by Set-maps (considered as 1cells in Mat(V)) is still well-defined and well-behaved, and this is all that is needed in this paper.

We explain the relevant properties of Mat(V) in Section 2 and define the needed Beck-Chevalley condition. Briefly, this condition says that the comparison map that “measures” the extent to which the T -image of a pullback diagram in Set still is a pullback diagram must be cofully faithful when considered a 1-cell in Mat(V). Having presented our main result, at the end of Section 3 we show that this condition is equivalent to asking T to preserve pullbacks or, if V is thin (i.e., a preordered class), to transform pullbacks into weak pullback diagrams (barring trivial choices for I and V). In certain cases, (BC) turns out to be even a necessary condition for local cartesian closedness of Alg(T, V), see 3.10. In Section 4 we show how to construct limits and colimits in Alg(T, V) in general, and Section 5 presents the construction of partial map classifiers, leading us to the theorem stated in the Abstract. A list of examples follows in Section 6.

Acknowledgements. We dedicate this paper in great admiration to Nico Pumplün with whom the third-named author started off studying Lawvere-Linton theories and monads in the late sixties. The authors are also grateful to Ross Street and Richard Wood for pointing them to their respective articles [15] and [3].

2. V-matrices

2.1. Let V be a category with coproducts and a distinguished object I. A V-matrix (or V-relation) r from a set X to a set Y, denoted by r : X ↛ Y, is a functor r : X ×Y → V, i.e. an X × Y -indexed family (r(x, y))_{x,y} of objects in V. With X, Y fixed, such Vmatrices form the objects of a category Mat(V)(X, Y), the morphisms φ : r → s of which are natural transformations, i.e. families (φ_{x,y} : r(x, y) → s(x, y))_{x,y} of morphisms in V; briefly,

Mat(V)(X, Y) = V^{X×Y} .

2.2. Every Set-map f : X → Y may be considered as a V-matrix f : X ↛ Y when one puts

f(x, y) = \{ \begin{matrix}I & if f(x) = y, \\ 0 & else, \end{matrix}

with 0 denoting a fixed initial object in V. This defines a functor

\xymatrix{Set(X, Y) \ar[r] & Mat(V)(X, Y),}

of the discrete category Set(X, Y), and the question is: when do we obtain a full embedding, for all X and Y? Precisely when

V(I, 0) = ∅ and |V(I, I)| = 1  (∗)

as one may easily check. In the context of a cartesian-closed category V, we usually pick for I a terminal object 1 in V, and then condition (∗) is equivalently expressed as

0 ≅ 1̸  (∗∗)

preventing V from being equivalent to the terminal category.

2.3. While in this paper we do not need the horizontal composition of V-matrices in general, we do need the composites sf and gr for maps f : X → Y, g : Y → Z and V-relations r : X ↛ Y, s : Y ↛ Z, defined by

\begin{aligned}(sf)(x, z) & = & s(f(x), z), \\ (gr)(x, z) & = & ∑_{y: g(y)=z} r(x, y), \end{aligned}

for x ∈ X, z ∈ Z; likewise for morphisms φ : r → r′ and ψ : s → s′. Hence, we have the “whiskering” functors

−f : Mat(V)(Y, Z) → Mat(V)(X, Z),
g− : Mat(V)(X, Y) → Mat(V)(X, Z),

giving Mat(V) the structure of an equipment in the sense of [3]. Accordingly, the horizontal composition with Set-maps from either side is associative up to coherent isomorphisms whenever defined; hence, if h : U → X and k : Z → V, then

(sf)h = s(fh) and k(gr) ≅ (kg)r.

Although Mat(V) falls short of being a bicategory, even a sesquicategory [15], we refer to sets as 0-cells of Mat(V), V-matrices as its 1-cells, and natural transformations between them as its 2-cells.

2.4. The transpose r^{∘} : Y ↛ X of a V-matrix r : X ↛ Y is defined by r^{∘}(y, x) = r(x, y) for all x ∈ X, y ∈ Y. Obviously r^{∘∘} = r, and with

(sf)^{∘} = f^{∘}s^{∘}, (gr)^{∘} = r^{∘}g^{∘}

we can also introduce whiskering by transposes of Set-maps from either side, also for 2-cells.

A Set-map f : X → Y gives rise to 2-cells

η : 1_{X} → f^{∘}f, ε : ff^{∘} → 1_{Y}

satisfying the triangular identities (εf)(fη) = 1_{f}, (f^{∘}ε)(ηf^{∘}) = 1_{f}.

As a consequence one obtains adjoints to the whiskering functors of 2.3:

\frac{t → sf}{tf^{∘} → s}  \frac{gr → t}{r → g^{∘}t}

for all r, s, f, g as in 2.3 and t : X ↛ Z; briefly,

(−f^{∘}) ⊣ (−f), (g−) ⊣ (g^{∘}−).

2.5. For a functor T : Set → Set, we denote by κ : T W → U the comparison map from the T -image of the pullback W := Z ×_{Y} X of (g, f) to the pullback U := T Z ×_{T Z} T X of (T g, T f)

\xymatrix{T W \ar[drr]^{T k} \ar[ddr]_{T h} \ar@{-->}[dr]^{κ} \\  & U \ar[r]^{π_{2}} \ar[d]_{π_{1}} & T X \ar[d]^{T f} \\  & T Z \ar[r]^{T g} & T Y.}  (1)

We say that the Set-functor T satisfies the Beck-Chevalley Condition (BC) if the 1-cell κ is cofully faithful; that is, if the “whiskering” functor −κ : Mat(V)(U, S) → Mat(V)(T W, S) is full and faithful, for every set S.

In the next section we will relate this condition with other known formulations of the Beck-Chevalley condition.

3. Local cartesian closedness of Alg(T, V)

3.1. Let (T, e) be a pointed endofunctor of Set and V category with coproducts and a distinguished object I. A lax (reflexive) (T, V)-algebra (X, a, η) is given by a set X, a 1-cell a : T X ↛ X and a 2-cell η : 1_{X} → ae_{X} in Mat(V). The 2-cell η is completely determined by the V-morphisms

\xymatrix{η_{x} := η_{x,x} : I \ar[r] & a(e_{X}(x), x),}

x ∈ X. As we shall not change the notation for this 2-cell, we write (X, a) instead of (X, a, η). A (lax) homomorphism (f, φ) : (X, a) → (Y, b) of (T, V)-algebras is given by a map f : X → Y in Set and a 2-cell φ : fa → b(T f) which must preserve the units: (φe_{X})(fη) = ηf. The 2-cell φ is completely determined by a family of V-morphisms

\xymatrix{f_{𝔵,x} : a(𝔵, x) \ar[r] & b(T f(𝔵), f(x)),}

x ∈ X, 𝔵 ∈ T X, and preservation of units now reads as f_{e_{X}(x),x}η_{x} = η_{f(x)} for all x ∈ X. For simplicity, we write f instead of (f, φ), and when we write

\xymatrix{f_{𝔵,x} : a(𝔵, x) \ar[r] & b(𝔶, y)}

this automatically entails 𝔶 = T f(𝔵) and y = f(x); these are the V-components of the homomorphism f. Composition of (f, φ) with (g, ψ) : (Y, b) → (Z, c) is defined by

(g, ψ)(f, φ) = (gf, (ψ(T f))(gφ))

which, in the notation used more frequently, means

\xymatrix{(gf)_{𝔵,x} = (a(𝔵, x) \ar[r]^{f_{𝔵,x}} & b(𝔶, y) \ar[r]^{g_{𝔶,y}} & c(𝔷, z)).}

We obtain the category Alg(T, V) (denoted by Alg(T, e; V) in [9]).

3.2. Let V be finitely complete. The pullback (W, d) of f : (X, a) → (Z, c) and g : (Y, b) → (Z, c) in Alg(T, V) is constructed by the pullback W = X ×_{Z} Y in Set and a family of pullback diagrams in V, as follows:

\xymatrix{d(𝔴, w) \ar[r]^{f′_{𝔴,w}} \ar[d]_{g′_{𝔴,w}} & b(𝔶, y) \ar[d]^{g_{𝔶,y}} \\ a(𝔵, x) \ar[r]^{f_{𝔵,x}} & c(𝔷, z)}

for all w ∈ W; hence,

d(𝔴, w) = a(T g′(𝔴), g′(w)) ×_{c} b(T f′(𝔴), f′(w))

in V, where g′ : W → X and f′ : W → Y are the pullback projections in Set. For each w = (x, y) in W, we define η_{w} :=< η_{x}, η_{y} >.

3.3. Every set X carries the discrete (T, V)-structure e_{X}^{∘}. In fact, the 2-cell η : 1_{X} → e_{X}^{∘}e_{X} making (X, e_{X}^{∘}) a (T, V)-algebra is just the unit of the adjunction e_{X} ⊣ e_{X}^{∘} in Mat(V). Now X ↦ (X, e_{X}^{∘}) defines the left adjoint of the forgetful functor

\xymatrix{Alg(T, V) \ar[r] & Set}

since every map f : X → Y into a (T, V)-algebra (Y, b) becomes a homomorphism f : (X, e_{X}^{∘}) → (Y, b); indeed the needed 2-cell fe_{X}^{∘} → b(T f) is obtained from the unit 2cell η : 1 → be_{Y} with the adjunction e_{X} ⊣ e_{X}^{∘}: it is the mate of fη : f → be_{Y} f = b(T f)e_{X}. In pointwise notation, for

\xymatrix{f_{𝔵,x} : e_{X}^{∘}(𝔵, x) \ar[r] & b(𝔶, y)}

one has f_{𝔵,x} = 1_{I} if e_{X}(x) = 𝔵; otherwise its domain is the initial object 0 of V, i.e. it is trivial.

3.4. We consider the discrete structure in particular on a one-element set 1. Then, for every (T, V)-algebra (X, a), an element x ∈ X can be equivalently considered as a homomorphism x : (1, e_{1}^{∘}) → (X, a) whose only non-trivial component is the unit η_{x} : I → a(e_{X}(x), x).

3.5. Assume V to be complete and locally cartesian closed. For a homomorphism f : (X, a) → (Y, b) and an additional (T, V)-algebra (Z, c) we form a substructure of the partial product of the underlying Set-data (see [10]), namely

\xymatrix{Z & Q \ar[l]_{ev} \ar[d]_{f′} \ar[r]^{q} & X \ar[d]^{f} \\  & P \ar[r]^{p} & Y,}  (2)

with

P = Z^{f} = {(s, y) | y ∈ Y, s : (X_{y}, a_{y}) → (Z, c)},
Q = Z^{f} ×_{Y} X = {(s, x) | x ∈ X, s : (X_{f(x)}, a_{f(x)}) → (Z, c)},

where (X_{y} = f^{−1}y, a_{y}) is the domain of the pullback

\xymatrix{i_{y} : (X_{y}, a_{y}) \ar[r] & (X, a)}

of y : (1, e_{1}^{∘}) → (Y, b) along f. Of course, p and q are projections, and ev is the evaluation map. We must find a structure d : T P ↛ P which, together with a 2-cell η, will make these maps morphisms in Alg(T, V).

For (s, y) ∈ P and 𝔭 ∈ T P, in order to define d(𝔭, (s, y)), consider each pair x ∈ X and 𝔮 ∈ T Q with f(x) = y and T f′(𝔮) = 𝔭 and form the partial product

\xymatrix{c(𝔷, s(x)) & c(𝔷, s(x))^{f_{𝔵,x}} ×_{b} a(𝔵, x) \ar[l]_{^{ẽv^{𝔮,x}}} \ar[d] \ar[r] & a(𝔵, x) \ar[d]^{f_{𝔵,x}} \\  & c(𝔷, s(x))^{f_{𝔵,x}} \ar[r]^{p̃_{𝔮,x}} & b(𝔶, y)}  (3)

in V, where 𝔷 = T ev(𝔮), and then the multiple pullback d(𝔭, (s, y)) of the morphisms p̃_{𝔮,x} in V, as in:

\xymatrix{ & c(𝔷, s(x))^{f_{𝔵,x}} \ar[dr]^{p̃_{𝔮,x}} \\ d(𝔭, (s, y)) \ar[ur]^{π_{𝔮,x}} \ar[rr]_{p_{𝔭,(s,y)}} &  & b(𝔶, y).}

3.6. We define the 2-cell η : 1_{P} → de_{P} componentwise. Let (s, y) ∈ P and consider each x ∈ X and 𝔮 ∈ T Q with f(x) = y and T f′(𝔮) = e_{P} (s, y) = T (s, y)e_{1} (where (s, y) : 1 → P). Consider the pullback j_{y} : X_{y} → Q of (s, y) : 1 → P along f′ in Set; whence, j_{y}(x) = s(x). By (BC) there is 𝔵 ∈ T X_{y} such that T j_{y}(𝔵) = 𝔮 and T!(𝔵) = e_{1}(∗) (where ! : X_{y} → 1 and ∗ is the only point of 1). Since evj_{y} = s, we may form the diagram

\xymatrix{c(𝔷, s(x)) & a_{y}(𝔵, x) \ar[l]_{s_{𝔵,x}} \ar[d] \ar[r]^{(i_{y})_{𝔵,x}} & a(𝔵, x) \ar[d]^{f_{𝔵,x}} \\  & I \ar[r]^{η_{y}} & b(e_{Y} (y), y)}

in V, where 𝔷 = T ev(𝔮) = T s(𝔵), and the square is a pullback. The universal property of (3) guarantees the existence of η̃_{𝔮,x} : I → c(𝔷, s(x))^{f_{𝔵,x}} such that p̃_{𝔮,x}η̃_{𝔮,x} = η_{y} and ẽv_{𝔮,x}(η̃_{𝔮,x} ×_{b} 1) = s_{𝔵,x}. Then, with the multiple pullback property, the morphisms η̃_{𝔮,x} define jointly η_{(s,y)} : I → d(e_{P} (s, y), (s, y)).

3.7. Theorem. If the pointed Set-functor T satisfies (BC) and V is complete and locally cartesian closed, then also Alg(T, V) is locally cartesian closed.

Proof. Continuing in the notation of 3.5 and 3.6, we equip Q with the lax algebra structure r : T Q ↛ Q that makes the square of diagram (2) a pullback diagram in Alg(T, V). Then the 2-cell defined by

\xymatrix{r(𝔮, (s, x)) \ar[r]^{π_{𝔮,x}×_{b}1} & c(𝔷, s(x))^{f_{𝔵,x}} ×_{b} a(𝔵, x) \ar[r]^{^{ẽv^{𝔮,x}}} & c(𝔷, s(x))}

makes ev : (Q, r) → (Z, c) a homomorphism.

In order to prove the universal property of the partial product, given any other pair (h : (L, u) → (Y, b), k : (M, v) → (Z, c)), where M := L ×_{Y} X, we consider the map t : L → P, defined by t(l) := (s_{l}, h(l)), with

\xymatrix{((X_{h(l)}, a_{h(l))}) \ar[r]^{s_{l}} & (Z, c)) = ((X_{h(l)}, a_{h(l)}) \ar[r]^{j_{l}} & (M, v) \ar[r]^{k} & (Z, c)),}

where j_{l} is the pullback of l : (1, e_{1}^{∘}) → (L, u) along f′′ : (M, v) → (L, u). We remark that in the commutative diagram

\xymatrix{Z &  & Q \ar[ll]_{ev} \ar[rr]^{q} \ar[dd]^{f′} &  & X \ar[dd]^{f} \\  & M \ar@{-->}[ul]^{k} \ar@{-->}[ur]^{t′} \ar[dd]_{f′′} &  & X_{h(l)} \ar@{-->}[ur]_{i_{h(l)}} \ar[ll]_{j_{l}} \ar[dd] \\  &  & P \ar[rr]^{p} &  & Y \\  & L \ar[ur]^{t} &  & 1 \ar[ll]^{l} \ar[ur]_{h(l)}}

every vertical face of the cube is a pullback in Set.

Now, for each l ∈ L and 𝔩 ∈ L we define t_{𝔩,l} : u(𝔩, l) → d(T t(𝔩), t(l)) componentwise. Since evt′ = k we observe that T k factors through the comparison map κ : T M → T L ×_{T P} T Q, defined by the diagram

\xymatrix{T M \ar[drr]^{T t′} \ar[ddr]_{T f′′} \ar@{-->}[dr]^{κ} \\  & T L ×_{T P} T Q \ar[r]^{π_{2}} \ar[d]_{π_{1}} & T Q \ar[d]^{T f′} \\  & T L \ar[r]^{T t} & T P;}

that is T k = (T ev)(T t′) = (T ev)π_{2}κ. Since also kv factors through κ, i.e., kv = kṽκ, with (BC) we conclude that the 2-cell kv → c(T k) is of the form

[figure: φ; M; κ; T L ×_{T P} T Q; kṽ; (T ev)π_{2}; Z.]

For each x ∈ X and 𝔮 ∈ T Q such that f(x) = h(l) and T f′(𝔮) = T t(𝔩), let 𝔪 ∈ T M be such that (T f′′)(𝔪) = 𝔩 and (T t′)(𝔪) = 𝔮. In the diagram

\xymatrix{c(𝔷, s_{l}(x)) & v(𝔪, (l, x)) \ar[l]_{k_{𝔪,(l,x)}} \ar[d] \ar[r] & a(𝔵, x) \ar[d]^{f_{𝔵,x}} \\  & u(𝔩, l) \ar[r]^{h_{𝔩,l}} & b(𝔶, y)}

in V one has 𝔷 = (T ev)(𝔮) and the morphism k_{𝔪,(l,x)} depends only on 𝔮 and 𝔩. Moreover, the square is a pullback, hence there is a V-morphism t̃_{𝔩,l} : u(𝔩, l) → c(𝔷, s_{l}(x))^{f_{𝔵,x}} such that p̃_{𝔮,x}t̃_{𝔩,l} = h_{𝔩,l} and k_{𝔪,(l,x)}(t̃_{𝔩,l} ×_{b} 1) = ẽv_{𝔮,x}. With the multiple pullback property, the morphisms t̃_{𝔩,l} define the unique 2-cell that makes t : (L, u) → (P, d) a homomorphism.

If in the proof we take for (Y, b) the terminal object of Alg(T, V), that is, the pair (1, ⊤) where the lax structure ⊤ is constantly equal to the terminal object of V, we conclude:

3.8. Corollary. If the pointed Set-functor T satisfies (BC) and V is complete and cartesian closed, then also Alg(T, V) is cartesian closed.

We explain now the strength of our Beck-Chevalley condition.

3.9. Proposition. For T and V as in 2.5, let V(I, 0) = ∅. Then:

(a) If T satisfies (BC), then T transforms pullbacks into weak pullbacks. The two conditions are actually equivalent when V is thin (i.e. a preordered class).

(b) If V is not thin, satisfaction of (BC) by T is equivalent to preservation of pullbacks by T.

(c) If V is cartesian closed, with I = 1 the terminal object, then T satisfies (BC) if and only if (T f)^{∘}T g = T k(T h)^{∘}, for every pullback diagram

\xymatrix{W \ar[r]^{k} \ar[d]_{h} & X \ar[d]^{f} \\ Z \ar[r]^{g} & Y}  (4)

in Set.

Proof. (a) Let κ : T W → U be the comparison map of diagram (1). By (BC) the 2-cell κη : κ → κκ^{∘}κ is the image by −κ of a 2-cell σ : 1_{U} → κκ^{∘}. Hence, for each u ∈ U there is a V-morphism

I → κκ^{∘}(u, u) = ∑_{𝔴∈T W : κ(𝔴)=u} κ(𝔴, u).

Therefore the set {𝔴 ∈ T W | κ(𝔴) = u} cannot be empty, that is, κ is surjective.

If V is thin and κ is surjective, there is a (necessarily unique) 2-cell 1_{U} → κκ^{∘}. Then each 2-cell ψ : κr → κs induces a 2-cell φ : r → s defined by

\xymatrix{r \ar[r]^{rσ} & rκκ^{∘} \ar[r]^{ψκ^{∘}} & sκκ^{∘} \ar[r]^{sε} & s}

whose image under −κ is necessarily ψ.

(b) If T preserves pullbacks, then κ is an isomorphism and (BC) holds.

Conversely, let T satisfy (BC) and let κ : T W → U be a comparison map as in (1). We consider 𝔴_{0}, 𝔴_{1} ∈ T W with κ(𝔴_{0}) = κ(𝔴_{1}) and V-morphisms α, β : v → v′ with α ≠ β, and define r : U × U → V by r(u, u′) = v and s : U × U → V by s(u, u′) = v′.

The 2-cell ψ : rκ → sκ, with ψ_{𝔴,u} = α if 𝔴 = 𝔴_{0} and ψ_{𝔴,u} = β elsewhere, factors through κ only if 𝔴_{0} = 𝔴_{1}.

(c) For any commutative diagram (4) there is a 2-cell kh^{∘} → f^{∘}g, defined by

\xymatrix{kh^{∘} \ar[r]^{ηkh^{∘}} & f^{∘}fkh^{∘} = f^{∘}ghh^{∘} \ar[r]^{f^{∘}gε} & f^{∘}g,}

which is an identity morphism in case the diagram is a pullback.

If T satisfies (BC) and V is not thin, the equality T k(T h)^{∘} = (T f)^{∘}T g follows from (b). If V is thin, then in the diagram (1) the 2-cell σ : 1 → κκ^{∘} considered in (a) gives rise to a 2-cell

\xymatrix{(T f)^{∘}T g = π_{2}π_{1}^{∘} \ar[r]^{π_{2}σπ_{1}^{∘}} & π_{2}κκ^{∘}π_{1}^{∘} = T k(T h)^{∘},}

and the equality follows.

Conversely, the equality (T f)^{∘}T g = T k(T h)^{∘} guarantees the surjectivity of κ, hence (BC) follows in case V is thin, by (a). If V is not thin, we first observe that a coproduct ∑_{X} I is isomorphic to I only if X is a singleton, due to the cartesian closedness of V. Now, (T f)^{∘}T g = T k(T h)^{∘} means that, for every 𝔷 ∈ T Z and 𝔵 ∈ T X with T g(𝔷) = T f(𝔵),

\begin{aligned}I & = T f(𝔵, T g(𝔷)) = T f^{∘}T g(𝔷, 𝔵) = T kT h^{∘}(𝔷, 𝔵) \\ & = ∑\{I | 𝔴 ∈ T W : T k(𝔴) = 𝔵 & T h(𝔴) = 𝔷\}. \end{aligned}

From this equality we conclude that there exists exactly one such 𝔴, i.e. T W = T Z ×_{T Y} T X.

3.10. Finally we remark that, in some circumstances, the 2-categorical part of (BC) is essential for local cartesian-closedness of Alg(T, V). Indeed, if V is extensive [4], T transforms pullback diagrams into weak pullback diagrams and Alg(T, V) is locally cartesian closed, then T satisfies (BC), as we show next. To check (BC) we consider a 2-cell ψ : rκ → sκ, with κ : T W → U the comparison map of diagram (1) and r, s : U → S. We need to check that ψ = φκ for a unique 2-cell φ : r → s. This 2-cell exists, and it is unique if and only if

∀𝔴_{0}, 𝔴_{1} ∈ T W ∀s ∈ S κ(𝔴_{0}) = κ(𝔴_{1}) ⇒ ψ_{𝔴_{0},s} = ψ_{𝔴_{1},s}.

For v := r(κ(𝔴_{0}), s) and v′ := s(κ(𝔴_{0}), s), and α := ψ_{𝔴_{0},s} and β = ψ_{𝔴_{1},s}, we want to show that α = β.

For that, in the pullback diagram (4) we consider structures a, b, c, d, on X, Y, Z and W respectively, constantly equal to I + v, with η : I → I + v the coproduct injection. For d′ constantly equal to I + v′, in the diagram

\xymatrix{(W, d′) & (W, d) \ar[l]_{(id,ε)} \ar[d]_{(h,1)} \ar[r]^{(k,1)} & (X, a) \ar[d]^{(f,1)} \\  & (Z, c) \ar[r]^{(g,1)} & (Y, b)}

we define ε by:

ε_{𝔴,w} = \{ \begin{matrix}1 + α & if 𝔴 = 𝔴_{0}, \\ 1 + β & elsewhere. \end{matrix}

The square is a pullback. Hence the morphism (id, ε) factors through the partial product via t ×_{Y} id, with t : Z → P. Since the 2-cell of t ×_{Y} id is obtained by a pullback construction and κ(𝔴_{0}) = κ(𝔴_{1}), its 2-cell “identifies” 𝔴_{0} and 𝔴_{1}, hence ε_{𝔴_{0},w} = ε_{𝔴_{1},w}, that is, 1 + α = 1 + β. Therefore α = β, by extensitivity of V.

4. (Co)completeness of the category Alg(T, V)

4.1. We assume V to be complete and cocomplete. The construction of limits in Alg(T, V) reduces to a combined construction of limits in Set and V, as we show next.

The limit of a functor

\begin{matrix}F : D & → & Alg(T, V) \\ D & ↦ & (F D, a_{D}) \\ D →^{f} E & ↦ & (F D, a_{D}) →^{F f} (F E, a_{E}) \end{matrix}

is constructed in two steps.

First we consider the composition of F with the forgetful functor into Set

\xymatrix{D \ar[r]^{F} & Alg(T, V) \ar[r] & Set,}  (5)

and construct its limit in Set

\xymatrix{(L \ar[r]^{p^{D}} & F D)_{D∈D}.}

Then, we define the (T, V)-algebra structure a : T L ↛ L, that is the map a : T X × X → V, pointwise. For every 𝔩 ∈ T L and l ∈ L, we consider now the functor

\begin{matrix}F_{𝔩,l} : D & → & V \\ D & ↦ & a_{D}(T p^{D}(𝔩), p^{D}(l)) \\ D →^{f} E & ↦ & \xymatrix{a_{D}(T p^{D}(𝔩), p^{D}(l)) \ar[r]^{F f_{T p^{D}(𝔩),p^{D}(l)}} & a_{E}(T p^{E}(𝔩), p^{E}(l))} \end{matrix}

and its limit in V

\xymatrix{(a(𝔩, l) \ar[r]^{p_{𝔩,l}^{D}} & a_{D}(T p^{D}(𝔩), p^{D}(l)))_{D∈D}.}

This equips p^{D} : (L, a) → (F D, a_{D}) with a 2-cell p^{D}a → a_{D}T p^{D}.

By construction

\xymatrix{(L, a) \ar[r]^{p^{D}} & (F D, a_{D})}  (6)

is a cone for F. To check that it is a limit, let

\xymatrix{(Y, b) \ar[r]^{g^{D}} & (F D, a_{D})}

be a cone for F. By construction of (L, p^{D}), there exists a map t : Y → L such that p^{D}t = g^{D} for each D ∈ D. For each 𝔶 ∈ T Y and y ∈ Y,

\xymatrix{b(𝔶, y) \ar[r]^{g_{𝔶,y}^{D}} & a_{D}(T p^{D}(T t(𝔶)), p^{D}(t(y)))}

is a cone for the functor F_{T t(𝔶),t(y)}. Hence, by construction of a(T t(𝔶), t(y)), there exists a unique V-morphism t_{𝔶,y} making the diagram

\xymatrix{a(T t(𝔶), t(y)) \ar[r]^{p_{𝔶,y}^{D}} & a_{D}(T p^{D}(T t(𝔶)), p^{D}(t(y))) \\ b(𝔶, y) \ar@{-->}[u]^{t_{𝔶,y}} \ar[ur]_{g_{𝔶,y}^{D}}}

commutative. These V-morphisms define pointwise the unique 2-cell gb → p^{D}a. For each l ∈ L, η_{l} : I → a(e_{L}(l), l) is the morphism induced by the cone

(η_{p^{D}(l),p^{D}(l)}^{D} : I → a_{D}(e_{F D}(p^{D}(l)), p^{D}(l)))_{D∈D}.

4.2. Cocompleteness. To construct the colimit of a functor F : D → Alg(T, V) we first proceed analogously to the limit construction. That is, we form the colimit in Set

\xymatrix{(F D \ar[r]^{i^{D}} & Q)_{D∈D}}

of the functor (5).

To construct the structure c : T Q ↛ Q, for each 𝔮 ∈ T Q and q ∈ Q, we consider the functor F^{𝔮,q} : D → V, with

F^{𝔮,q}(D) = ∑ {a_{D}(𝔵, x) | T i^{D}(𝔵) = 𝔮, i^{D}(x) = q},

and, for f : D → E, the morphism F^{𝔮,q}(f) : F^{𝔮,q}(D) → F^{𝔮,q}(E) is induced by

\xymatrix{a_{D}(𝔵, x) \ar[r]^{F f_{𝔵,x}} & a_{E}(T f(𝔵), f(x)) \ar[r] & ∑ \{a_{E}(𝔶, y) | T i^{E}(𝔶) = 𝔮, i^{E}(y) = q\} = F^{𝔮,q}(E).}

and denote by c̃(𝔮, q) the colimit of F^{𝔮,q}. If 𝔮 ≠ e_{Q}(q) for q ∈ Q, then c̃(𝔮, q) is in fact the structure c(𝔮, q) on the colimit. For 𝔮 = e_{Q}(q), the multiple pushout

\xymatrix{ &  & c̃(e_{Q}(q), q) \ar[ddr] \\  & a_{D}(e_{F D}(x), x) \ar@{-->}[ur]^{i_{e_{F D}(x),x}^{D}} \\ I \ar[ur]^{η_{x}} \ar[rrr]^{η_{q}} &  &  & c(e_{Q}(q), q),}

defines c(e_{Q}(q), q), with D ∈ D and x ∈ F D such that i^{D}(x) = q.

5. Representability of partial morphisms

5.1. Let 𝒮 be a pullback-stable class of morphisms of a category C. An 𝒮-partial map from X to Y is a pair ( \xymatrix{X & U \ar[l]_{s} \ar[r] & Y} ) where s ∈ 𝒮. We say that 𝒮 has a classifier if there is a morphism true : 1 → ˜1 in 𝒮 such that every morphism in 𝒮 is, in a unique way, a pullback of true; C has 𝒮-partial map classifiers if, for every Y ∈ C, there is a morphism true_{Y} : Y → Ỹ in 𝒮 such that every 𝒮-partial map ( \xymatrix{X & U \ar[l]_{s} \ar[r] & Y} ) from X to Y can be uniquely completed so that the diagram

\xymatrix{U \ar[d]_{s} \ar[r] & Y \ar[d]^{_{true_{Y}}} \\ X \ar@{-->}[r] & Ỹ .}

is a pullback.

From Corollary 4.6 of [10] it follows that:

5.2. Proposition. If 𝒮 is a pullback-stable class of morphisms in a finitely complete locally cartesian-closed category C, then the following assertions are equivalent:

(i) 𝒮 has a classifier;

(ii) C has 𝒮-partial map classifiers.

5.3. Our goal is to investigate whether the category Alg(T, V) has 𝒮-partial map classifiers, for the class 𝒮 of extremal monomorphisms. For that we first observe:

5.4. Lemma. An Alg(T, V)-morphism s : (U, c) → (X, a) is an extremal monomorphism if and only if the map s : U → X is injective and, for each 𝔲 ∈ T U and u ∈ U, s_{𝔲,u} : c(𝔲, u) → a(𝔵, x) is an isomorphism in V.

5.5. Proposition. In Alg(T, V) the class of extremal monomorphisms has a classifier.

Proof. For ˜1 = (1 + 1, ˜⊤), where ˜⊤ is pointwise terminal, we consider the inclusion true : 1 → ˜1 onto the first summand. For every extremal monomorphism s : (U, c) → (X, a), we define χ_{U} : (X, a) → ˜1 with χ_{U} : X → 1 + 1 the characteristic map of s(U), and the 2-cell constantly ! : a(𝔵, x) → 1. Then the diagram below

\xymatrix{(U, s) \ar[d]_{s} \ar[r]^{!} & 1 \ar[d]^{true} \\ (X, a) \ar[r]^{χ_{U}} & ˜1}

is a pullback diagram; it is in fact the unique possible diagram that presents s as a pullback of true.

Using Theorem 3.7 and Proposition 5.5, we conclude that:

5.6. Theorem. If the pointed Set-functor T satisfies (BC) and V is a complete and cocomplete locally cartesian closed category, then Alg(T, V) is a quasitopos.

5.7. Remark. Representability of (extremal mono)-partial maps can also be proved directly, and in this way one obtains a slight improvement of Theorem 5.6: Alg(T, V) is a quasi-topos whenever T satisfies (BC) and V is a complete and cocomplete cartesian closed category, not necessarily locally so.

6. Examples.

6.1. We start off with the trivial functor T which maps every set to a terminal object 1 of Set. T preserves pullbacks. Choosing for I the top element of any (complete) lattice V we obtain with Alg(T, V) nothing but the topos Set. This shows that local cartesian closedness of V is not a necessary condition for local cartesian closedness of Alg(T, V). We also note that T does not carry the structure of a monad.

If, for the same T, we choose V = Set, then Alg(T, Set) is the formal coproduct completion of the category Set_{∗} of pointed sets, i.e. Alg(T, Set) ≅ Fam(Set_{∗}).

6.2. Let T = Id, e = id. Considering for V as in [9] the two-element chain 2, the extended half-line \overline{ℝ}_{+} = [0, ∞] (with the natural order reversed), and the category Set, one obtains with Alg(T, V) the category of

− sets with a reflexive relation

− sets with a fuzzy reflexive relation

− reflexive directed graphs,

respectively.

More generally, if we let T X = X^{n} for a non-negative integer n, with the same choices for V one obtains

− sets with a reflexive (n + 1)-ary relation

− sets with a fuzzy reflexive (n + 1)-ary relation

− reflexive directed “multigraphs” given by sets of vertices and of edges, with an edge having an ordered n-tuple of vertices as its source and a single edge as its target; reflexivity means that there is a distinguished edge (x, ⋯, x) → x for each vertex x.

Note that the case n = 0 encompasses Example 6.1.

6.3. For a fixed monoid M, let T belong to the monad T arising from the adjunction

\xymatrix{Set^{M} \ar[r]|{⊥} & Set, \ar[l]}

i.e. T X = M × X with e_{X}(x) = (0, x), with 0 neutral in M (writing the composition in M additively). T preserves pullbacks. The quasitopos Alg(T, Set) may be described as follows. Its objects are “M-normed reflexive graphs”, given by a set X of vertices and sets a(x, y) of edges from x to y which come with a “norm” v_{x,y} : a(x, y) → M for all x, y ∈ X; there is a distinguished edge 1_{x} : x → x with v_{x,x}(1_{x}) = 0. Morphisms must preserve the norm. Of course, for trivial M we are back to directed graphs as in 6.2.

It is interesting to note that if one forms Alg(T, Set) for the (untruncated) monad T (see [9]), then Alg(T, Set) is precisely the comma category Cat/M, where M is considered a one-object category; its objects are categories which come with a norm function v for morphisms satisfying v(gf) = v(g) + v(f) for composable morphisms f, g.

6.4. Let T = U be the ultrafilter functor, as mentioned in the Introduction. U transforms pullbacks into weak pullback diagrams. Hence, for V = 2 we obtain with Alg(T, 2) the quasitopos of pseudotopological spaces, and for V = \overline{ℝ}_{+} the quasitopos of (what should be called) quasiapproach spaces (see [9, 8]). If we choose for V the extensive category Set, then the resulting category Alg(U, Set) is a rather naturally defined supercategory of the category of ultracategories (as defined in [9]) but fails to be locally cartesian closed, according to 3.9(b) and 3.10.

References

[1] J. Adámek, H. Herrlich and G.E. Strecker, Abstract and concrete categories (Wiley Interscience, New York 1990).

[2] M. Barr, Relational algebras, in: Springer Lecture Notes in Math. 137 (1970), pp. 39-55.

[3] A. Carboni, G.M. Kelly, D. Verity and R. Wood, A 2-categorical approach to change of base and geometric morphisms II, Theory Appl. Categories 4 (1998) 82-136.

[4] A. Carboni, S. Lack and R.F.C. Walters, Introduction to extensive and distributive categories, J. Pure Appl. Algebra 84 (1993) 145-158.

[5] M. M. Clementino and D. Hofmann, Triquotient maps via ultrafilter convergence, Proc. Amer. Math. Soc. 130 (2002) 3423-3431.

[6] M. M. Clementino and D. Hofmann, Topological features of lax algebras, Applied Cat. Struct. 11 (2003) 267-286.

[7] M. M. Clementino, D. Hofmann and W. Tholen, The convergence approach to exponentiable maps, Port. Math. 60 (2003) 139-160.

[8] M. M. Clementino, D. Hofmann and W. Tholen, One setting for all: metric, topology, uniformity, approach structure, Appl. Categ. Structures (to appear).

[9] M. M. Clementino and W. Tholen, Metric, Topology and Multicategory – A common approach, J. Pure Appl. Algebra 179 (2003) 13-47.

[10] R. Dyckhoff and W. Tholen, Exponentiable morphisms, partial products and pullback complements, J. Pure Appl. Algebra 49 (1987) 103-116.

[11] H. Herrlich, E. Lowen-Colebunders and F. Schwarz, Improving Top: PrTop and PsTop, in: Category Theory at Work (Heldermann Verlag, Berlin 1991), pp 21-34.

[12] F.W. Lawvere, Metric spaces, generalized logic, and closed categories, Rend. Sem. Mat. Fis. Milano 43 (1973) 135-166.

[13] S. Mac Lane, Categories for the Working Mathematician, 2nd. ed. (Springer, New York 1998).

[14] J. Reiterman and W. Tholen, Effective descent maps of topological spaces, Top. Appl. 57 (1994) 53-69.

[15] R. Street, Categorical structures, in: Handbook of Algebra, vol.1 (editor M. Hazewinkel) (Elsevier, Amsterdam 1996), pp. 529-577.

Dep. de Matemática, Univ. de Coimbra, 3001-454 Coimbra, PORTUGAL

Dep. de Matemática. Univ. de Aveiro, 3810-193 Aveiro, PORTUGAL

Dep. of Math. and Stat, York University, Toronto, CANADA M3J 1P3

Email: mmc@mat.uc.pt
      dirk@mat.ua.pt
      tholen@mathstat.yorku.ca

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/11/15/11-15.{dvi,ps}

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.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. 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}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au 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@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 Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz 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