Theory and Applications of Categories, Vol. 30, No. 21, 2015, pp. 751–774.

CATEGORIES ENRICHED OVER A QUANTALOID: ALGEBRAS

QIANG PU AND DEXUE ZHANG

Abstract. Given a small quantaloid Q with a set of objects Q_{0}, it is proved that complete skeletal Q-categories, completely distributive skeletal Q-categories, and Qpowersets of Q-typed sets are all monadic over the slice category of Set over Q_{0}.

1. Introduction

A quantaloid [Ros1996] is a category enriched over the symmetric monoidal closed category Sup consisting of complete lattices and suprema-preserving functions. Since a quantaloid Q is a bicategory [Ben1967] (a 2-category indeed), following [BC1982, BCSW1983, Str1981, Wal1981], a theory of categories enriched over Q (or Q-categories for short) has been developed, see e.g. [Stu2005, Stu2006, Stu2007].

Given a small quantaloid Q, with Q_{0} its set of objects, objects in the slice category Set ↓ Q_{0} are called Q-typed sets. Then Q-categories can be treated as structured Qtyped sets. In this paper, we emphasize this aspect of Q-categories. That is to say, we treat the theory of Q-categories as one on the topos Set ↓ Q_{0}. It should be stressed that this theory is not developed within the topos Set ↓ Q_{0}, but rather, it depends heavily on the structure of Q which is formed outside of that topos. The role of Q is something like a “dynamic table of truth values” (c.f. [Stu2007]). The purpose of this paper is to show that some interesting classes of Q-categories are exactly the Eilenberg-Moore algebras corresponding to certain monads on the topos Set ↓ Q_{0}. These results show that the relationship between Q-categories and Q-typed sets are analogous to that between preordered sets and sets, exemplifying a benefit of treating Q-categories as structured Q-typed sets (instead of structured sets).

First, both the category Q-Sup consisting of complete skeletal Q-categories and cocontinuous Q-functors and the category Q-CD consisting of completely distributive skeletal Q-categories and bicontinuous Q-functors are monadic over Set ↓ Q_{0}. These conclusions extend the classical results that both the category Sup of complete lattices and joinpreserving maps, and the category CD of completely distributive lattices and complete lattice homomorphisms, are monadic over Set.

Second, the correspondence that sends each object A in Set ↓ Q_{0} to its Q-powerset |PA| (defined below) yields a monadic functor (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0}. We hasten to remark that the monadicity of (Set ↓ Q_{0})^{op} over Set ↓ Q_{0} is a special case of a general result in topos theory [MM1992] that states that for each topos E, the opposite category E^{op} is monadic over E. The point of the result presented here is that for each non-empty set X, there exist many monadic functors from (Set ↓ X)^{op} to Set ↓ X.

This work is supported by the National Natural Science Foundation of China (No. 11371265).

Received by the editors 2014-02-22 and, in revised form, 2015-05-29.

Transmitted by Stephen Lack. Published on 2015-06-01.

2010 Mathematics Subject Classification: 18A40, 18C20, 18D20, 18D35.

Key words and phrases: Quantaloid, Q-category, complete Q-category, completely distributive Qcategory, Q-powerset, Eilenberg-Moore algebra, monadicity.

\begin{matrix}c \\ ◯ \end{matrix} Qiang Pu and Dexue Zhang, 2015. Permission to copy for private use granted.

The contents are arranged as follows. In Section 2 we recall some basic concepts and results about Q-categories and fix notations for later use. Section 3 proves that both Q-Sup and Q-CD are monadic over Set ↓ Q_{0}. Section 4 proves the monadicity of the functor (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} that sends each object A in Set ↓ Q_{0} to its Q-powerset.

2. Categories enriched over a quantaloid

We refer to [Stu2005, Stu2006] for an overview of the theory of quantaloid-enriched categories. In this preliminary section, we recall some basic concepts and fix some notations for later use. It should be noted that the theory of quantaloid-enriched categories is a special case of that of W-categories; and that some of the results in this section are also known to be valid for W-categories, for example, the construction of P𝔸 and the Yoneda lemma. The reader is referred to [BC1982, BCSW1983, Str1981, Str1983, Wal1981, Wal1982] for more on these categories.

Q-categories, Q-functors, and Q-distributors. A quantaloid Q is a category such that Q(X, Y) is a complete lattice for any objects X, Y in Q and that the composition ∘ of arrows preserves suprema in both variables, i.e.

g ∘ ⋁_{i} f_{i} = ⋁_{i} g ∘ f_{i} and ⋁_{i} g_{i} ∘ f = ⋁_{i} g_{i} ∘ f

whenever the operations are defined. The identity arrow on an object X is written 1_{X}. The top and bottom elements in Q(X, Y) are denoted by ⊤_{X,Y} and ⊥_{X,Y} respectively. The identity 1_{X} is required to be different from the bottom element ⊥_{X,X} for all objects X in Q. However, for different objects X and Y, it may happen that ⊤_{X,Y} = ⊥_{X,Y}. The class of objects in Q is denoted by Q_{0} as usual.

For any arrow f : X [figure] Y and any object Z in a quantaloid Q, both of the maps

− ∘ f : Q(Y, Z) [figure] Q(X, Z), f ∘ − : Q(Z, X) [figure] Q(Z, Y)

have respective right adjoints

− ↙ f : Q(X, Z) [figure] Q(Y, Z), f ↘ − : Q(Z, Y) [figure] Q(Z, X).

The operators ↘ and ↙ are called the right and left implication respectively. In this paper, Q is assumed to be a small quantaloid. This means that Q_{0} is a set. A Q-typed set A is a pair (A_{0}, t) with A_{0} being a set and t a function A_{0} [figure] Q_{0}. The

function t is called the type function of A with the value tx the type of x. Type functions of Q-typed sets are all denoted by “t”, as usual. A type-preserving map F : A [figure] B between Q-typed sets is a function F : A_{0} [figure] B_{0} such that t(F x) = tx for all x ∈ A_{0}. The category of Q-typed sets and type-preserving maps is exactly the slice category Set ↓ Q_{0}.

For each X ∈ Q_{0}, we write ∗_{X} for the Q-typed set with exactly one element ∗ that is of type X.

For a Q-typed set A = (A_{0}, t), the underlying set A_{0} is often written A for simplicity if no confusion would arise.

A Q-matrix ϕ : A [figure: ∘] B between Q-typed sets is a function that assigns to each pair (x, y) ∈ A × B an arrow ϕ(x, y) ∈ Q(tx, ty). In particular, if A (resp. B) is of the form ∗_{X}, then we write ϕ(x) for ϕ(∗, x) (resp. ϕ(x, ∗)).

Q-typed sets and Q-matrices constitute a quantaloid Q-Mat in which

• The composition ψ ∘ ϕ : A [figure: ∘] C of ϕ : A [figure: ∘] B and ψ : B [figure: ∘] C is given by

(ψ ∘ ϕ)(x, z) = ⋁_{y∈B} ψ(y, z) ∘ ϕ(x, y).

• The identity Q-matrix id_{A} : A [figure: ∘] A on a Q-typed set A is given by

id_{A}(x, y) = \{ \begin{matrix}1_{tx}, & x = y; \\ ⊥_{tx,ty}, & otherwise. \end{matrix}

• The local order is defined pointwise, that is,

ϕ_{1} ≤ ϕ_{2} : A [figure: ∘] B if and ony if ϕ_{1}(x, y) ≤ ϕ_{2}(x, y) for all (x, y) ∈ A × B.

• For any Q-matrices ϕ : A [figure: ∘] B, ψ : B [figure: ∘] C and λ : A [figure: ∘] C, λ ↙ ϕ : B [figure: ∘] C and ψ ↘ λ : A [figure: ∘] B are respectively given by

(λ ↙ ϕ)(y, z) = ⋀_{x∈A} λ(x, z) ↙ ϕ(x, y), (ψ ↘ λ)(x, y) = ⋀_{z∈C_{0}} ψ(y, z) ↘ λ(x, z).

A Q-category 𝔸 is a monad in the 2-category Q-Mat. Explicitly, a Q-category is a pair (A, 𝔸) where A is a Q-typed set and 𝔸 : A [figure: ∘] A is a Q-matrix such that id_{A} ≤ 𝔸 and 𝔸 ∘ 𝔸 ≤ 𝔸.

In the following we write 𝔸 for a Q-category, |𝔸| for its underlying Q-typed set and 𝔸_{0} for the underlying set of |𝔸|.

A Q-functor F : 𝔸 [figure] 𝔹 between Q-categories is a type-preserving map F : |𝔸| [figure] |𝔹| such that 𝔸(x, y) ≤ 𝔹(F x, F y) for all objects x, y in 𝔸. The category of Q-categories and Q-functors is denoted by Q-Cat.

The correspondence 𝔸 ↦ |𝔸| defines a (forgetful) functor |-| : Q-Cat [figure] Set ↓ Q_{0}. Conversely, each Q-typed set A together with the identity Q-matrix on A is a Q-category. Such Q-categories are said to be discrete. In this paper, we do not distinguish Q-typed sets and discrete Q-categories.

For a Q-functor F : 𝔸 [figure] 𝔹 between Q-categories, we write F instead of |F | for the underlying type-preserving map |𝔸| [figure] |𝔹|.

The underlying order of a Q-category 𝔸 [Stu2005] refers to the preorder on the set of objects in 𝔸 defined by

x ≤ y ⟺ tx = ty and 1_{tx} ≤ 𝔸(x, y).

It is trivial that Q-functors preserve underlying orders of Q-categories. Two objects x, y of 𝔸 are isomorphic, in symbols x ≅ y, if x ≤ y and y ≤ x. A Q-category 𝔸 is skeletal if its underlying order is antisymmetric.

The underlying order of a Q-category 𝔹 induces a preorder on the set of all Q-functors from a Q-category 𝔸 to 𝔹:

F ≤ G ⟺ ∀x ∈ 𝔸, F x ≤ Gx.

Thus, Q-Cat is indeed a locally ordered category. Two Q-functors F, G : 𝔸 [figure] 𝔹 are isomorphic, in symbols F ≅ G, if F ≤ G and G ≤ F.

A pair of Q-functors F : 𝔸 [figure] 𝔹 and G : 𝔹 [figure] 𝔸 is said to form an adjunction, written F ⊣ G : 𝔸 ⇀ 𝔹, if 1_{𝔸} ≤ G ∘ F and F ∘ G ≤ 1_{𝔹}. In this case, F is called a left adjoint of G and G a right adjoint of F.

A Q-distributor ϕ : 𝔸 [figure: ∘] 𝔹 between Q-categories is a Q-matrix ϕ : |𝔸| [figure: ∘] |𝔹| that is compatible with the structures on 𝔸 and 𝔹 in the sense that

𝔹(y, y′) ∘ ϕ(x, y) ≤ ϕ(x, y′) and ϕ(x, y) ∘ 𝔸(x′, x) ≤ ϕ(x′, y)

for any objects x, x′ in 𝔸 and y, y′ in 𝔹; or equivalently, ϕ ∘ 𝔸 = ϕ = 𝔹 ∘ ϕ in Q-Mat. Q-categories and Q-distributors constitute a quantaloid Q-Dist in which compositions, the left and right implications are calculated as in Q-Mat.

Following [Lack2010], for a 2-category C, we denote by C^{op} (C^{co}, resp.) the 2-category obtained by reversing the 1-arrows (the 2-arrows, resp.) in C. For each quantaloid Q, Q^{op} is also a quantaloid, but Q^{co} is not in general. Given a Q-category 𝔸, there is a corresponding Q^{op}-category 𝔸^{op} with the same underlying Q-typed set as that of 𝔸 and with 𝔸^{op}(x, y) = 𝔸(y, x).^{1} For each Q-distributor ϕ : 𝔸 [figure: ∘] 𝔹, the assignment ϕ^{op}(y, x) = ϕ(x, y) defines a Q^{op}-distributor 𝔹^{op} [figure: ∘] 𝔸^{op}. If F : 𝔸 [figure] 𝔹 is a Q-functor, then

F^{op} : 𝔸^{op} [figure] 𝔹^{op}, x ↦ F x

is a Q^{op}-functor. Furthermore, F ≤ G in Q-Cat if and only if G^{op} ≤ F^{op} in Q^{op}-Cat. Therefore, (Q-Cat)^{co} is isomorphic to Q^{op}-Cat [Stu2005].

1We would like to point out that the terminologies adopted here are not exactly the same as in our main references, [Stu2005, Stu2006], on quantaloid-enriched categories. Our Q-categories and Qdistributors are exactly the Q^{op}-categories and Q^{op}-distributors in the sense of Stubbe. The difference arises in the interpretations of 𝔸(x, y) for a Q-category 𝔸: it is interpreted as the hom-arrow from y to x in [Stu2005, Stu2006], but from x to y here. Note that this difference also leads to the swap of presheaves and co-presheaves.

The graph and cograph of a Q-functor F : 𝔸 [figure] 𝔹 refer to the Q-distributors F_{♮} = 𝔹(F −, −) : 𝔸 [figure: ∘] 𝔹 and F^{♮} = 𝔹(−, F −) : 𝔹 [figure: ∘] 𝔸 respectively. F_{♮} is a left adjoint of F^{♮} in Q-Dist, i.e., 𝔸 ≤ F^{♮} ∘ F_{♮} and F_{♮} ∘ F^{♮} ≤ 𝔹.

The following proposition is a special case of an observation in [BCSW1983] about modules (= distributors) between W-categories. We record it here because of its usefulness.

2.1. Proposition. Let F : 𝔸 [figure] 𝔹 be a Q-functor.

(1) F is fully faithful in the sense that 𝔸(x, y) = 𝔹(F x, F y) for all x, y ∈ 𝔸 if and only if F^{♮} ∘ F_{♮} = 𝔸.

(2) If F is essentially surjective in the sense that there is some x ∈ 𝔸 such that F x ≅ y in 𝔹 for all y ∈ 𝔹, then F_{♮} ∘ F^{♮} = 𝔹.

A presheaf [Stu2005] on a Q-category 𝔸 is a Q-distributor of the form ϕ : 𝔸 [figure: ∘] ∗_{X}. All presheaves on 𝔸 constitute a skeletal Q-category P𝔸 with

tϕ = X and P𝔸(ϕ, ϕ′) = ϕ′ ↙ ϕ

for any ϕ : 𝔸 [figure: ∘] ∗_{X} and ϕ′ : 𝔸 [figure: ∘] ∗_{Y}.

Dually, a co-presheaf on 𝔸 is a Q-distributor of the form ψ : ∗_{X} [figure: ∘] 𝔸. All copresheaves on 𝔸 constitute a skeletal Q-category P^{†}𝔸 with

tψ = X and P^{†}𝔸(ψ, ψ′) = ψ′ ↘ ψ

for any ψ : ∗_{X} [figure: ∘] 𝔸 and ψ′ : ∗_{Y} [figure: ∘] 𝔸.

It should be stressed that the underlying order of P𝔸 coincides with the local order in Q-Dist while the underlying order of P^{†}𝔸 is the reverse local order in Q-Dist.

The correspondences

x ↦ 𝔸(−, x) : 𝔸 [figure: ∘] ∗_{tx}

and

x ↦ 𝔸(x, −) : ∗_{tx} [figure: ∘] 𝔸

define two Q-functors

Y_{𝔸} : 𝔸 [figure] P𝔸

and

Y_{𝔸}^{†} : 𝔸 [figure] P^{†}𝔸

which are called respectively the Yoneda and the co-Yoneda embedding due to the following:

2.2. Lemma. (Yoneda lemma, [Stu2005]) P𝔸(Y_{𝔸}(x), ϕ) = ϕ(x) and P^{†}𝔸(ψ, Y_{𝔸}^{†}(x)) = ψ(x) for any x ∈ 𝔸, ϕ ∈ P𝔸, and ψ ∈ P^{†}𝔸.

The correspondence 𝔸 ↦ P𝔸 gives a contravariant functor

P : (Q-Cat)^{op} [figure] Q-Cat

that sends a Q-functor F : 𝔸 [figure] 𝔹 to

PF : P𝔹 [figure] P𝔸, PF (ψ) = ψ ∘ F_{♮}.

Dually, the correspondence 𝔸 ↦ P^{†}𝔸 gives a contravariant functor

P^{†} : Q-Cat [figure] (Q-Cat)^{op}

that sends a Q-functor F : 𝔸 [figure] 𝔹 to

P^{†}F : P^{†}𝔹 [figure] P^{†}𝔸, P^{†}F (ψ) = F^{♮} ∘ ψ.

2.3. Theorem. [Hoh2014, Stu2005] The functor P^{†} : Q-Cat [figure] (Q-Cat)^{op} is left adjoint to P : (Q-Cat)^{op} [figure] Q-Cat.

2.4. Proposition. [Stu2013] Let F : 𝔸 [figure] 𝔹 be a Q-functor.

(1) The Q-functor PF has a left adjoint ∃_{F} : P𝔸 [figure] P𝔹 and a right adjoint ∀_{F} : P𝔸 [figure] P𝔹 given by ∃_{F} (ϕ) = ϕ ∘ F^{♮} and ∀_{F} (ϕ) = ϕ ↙ F_{♮}, respectively.

(2) The Q-functor P^{†}F : P^{†}𝔹 [figure] P^{†}𝔸 has a left adjoint ∀_{F}^{†} : P^{†}𝔸 [figure] P^{†}𝔹 and a right adjoint ∃_{F}^{†} : P^{†}𝔸 [figure] P^{†}𝔹 given by ∀_{F}^{†} (ψ) = F^{♮} ↘ ψ and ∃_{F}^{†} (ψ) = F_{♮}∘ψ, respectively.

Different notations have been used for the Q-functors ∃_{F} , ∀_{F} , ∃_{F}^{†} and ∀_{F}^{†} in [SZ2013a, Stu2013]. The notations adopted here originate from topos theory [MM1992].

2.5. Proposition. Given a pair of Q-functors F : 𝔸 [figure] 𝔹 and G : 𝔹 [figure] 𝔸, the following are equivalent:

(1) F ⊣ G : 𝔸 ⇀ 𝔹.

(2) ∃_{F} ⊣ ∃_{G} : P𝔸 ⇀ P𝔹.

(3) PF ⊣ PG : P𝔹 ⇀ P𝔸.

(4) ∃_{F}^{†} ⊣ ∃_{G}^{†} : P^{†}𝔸 ⇀ P^{†}𝔹.

(5) P^{†}F ⊣ P^{†}G : P^{†}𝔹 ⇀ P^{†}𝔸.

Proof. We prove the equivalence of (1) and (2) for example.

(1) ⇒ (2) This follows from the fact that a 2-functor preserves adjunctions [Lack2010].

(2) ⇒ (1) For any object x in 𝔸,

Y_{𝔸}(x) ≤ ∃_{G} ∘ ∃_{F} (Y_{𝔸}(x)) = Y_{𝔸}(x) ∘ (G ∘ F)^{♮} = Y_{𝔸}(GF x)

showing that x ≤ GF x. Thus 1_{𝔸} ≤ G ∘ F. Similarly it can be verified that F ∘ G ≤ 1_{𝔹}. Hence F ⊣ G : 𝔸 ⇀ 𝔹.

It is clear that the assignments F ↦ ∃_{F} and F ↦ ∃_{F}^{†} give rise to two functors:

P_{∃} : Q-Cat [figure] Q-Cat and P_{∃}^{†} : Q-Cat [figure] Q-Cat.

Both P_{∃} and P_{∃}^{†} preserve the local order in Q-Cat, hence both of them are 2-functorial Q-Cat [figure] Q-Cat. Both of the contravariant functors P and P^{†} reverse the local order, so, both of them are 2-functorial from Q-Cat^{coop} to Q-Cat.

For any Q-functor F, it follows from Proposition 2.4 that P^{†}F ⊣ P_{∃}^{†}F. Thus, P_{∃}(P^{†}F) ⊣ P_{∃}(P_{∃}^{†}F) by Proposition 2.5(2). Also by Proposition 2.4 one has P_{∃}(P^{†}F) ⊣ P(P^{†}F). Thus, P(P^{†}F) = P_{∃}(P_{∃}^{†}F). This proves the following:

2.6. Corollary. [Hoh2014, Stu2013] P ∘ P^{†} = P_{∃} ∘ P_{∃}^{†}.

[figure: Q-Cat; Q-Cat; P_{∃}^{†}; Q-Cat; Q-Cat; P_{∃}; Q-Cat; Q-Cat^{op}; P^{†}; Q-Cat^{op}; Q-Cat; P]

The following conclusion is a direct consequence of Proposition 2.1, it will be useful in the last section.

2.7. Proposition. Let F : 𝔸 [figure] 𝔹 be a Q-functor.

(1) F is fully faithful if and only if PF ∘ ∃_{F} = 1_{P𝔸} if and only if P^{†}F ∘ ∃_{F}^{†} = 1_{P^{†}𝔸}.

(2) If F is essentially surjective, then ∃_{F} ∘ PF = 1_{P𝔹} and ∃_{F}^{†} ∘ P^{†}F = 1_{P^{†}𝔹}.

Complete and completely distributive Q-categories. Let 𝔸 be a Q-category and ϕ : 𝔸 [figure: ∘] ∗_{X} a presheaf on 𝔸. A supremum of ϕ is an object sup ϕ in 𝔸 of type X such that for any x in 𝔸,

𝔸(sup ϕ, x) = P𝔸(ϕ, Y_{𝔸}(x));

or equivalently, 𝔸(sup ϕ, −) = 𝔸 ↙ ϕ. It is clear that the supremum of a presheaf 𝔸 [figure: ∘] ∗_{X}, if exists, is unique up to isomorphism. Dually, the infimum of a co-presheaf ψ : ∗_{X} [figure: ∘] 𝔸 is an object inf ψ in 𝔸 of type X such that for any x in 𝔸,

𝔸(x, inf ψ) = P^{†}𝔸(Y_{𝔸}^{†}(x), ψ);

or equivalently, 𝔸(−, inf ψ) = ψ ↘ 𝔸.

2.8. Definition. [Stu2005] A Q-category 𝔸 is cocomplete if every presheaf on 𝔸 has a supremum; 𝔸 is complete if every co-presheaf on 𝔸 has an infimum.

It is known that (i) 𝔸 is cocomplete if and only if the Yoneda embedding Y_{𝔸} : 𝔸 [figure] P𝔸 has a left adjoint sup_{𝔸} : P𝔸 [figure] 𝔸; (ii) 𝔸 is complete if the co-Yoneda embedding Y_{𝔸}^{†} : 𝔸 [figure] P^{†}𝔸 has a right adjoint inf_{𝔸} : P^{†}𝔸 [figure] 𝔸; and (iii) 𝔸 is complete if and only if it is cocomplete.

2.9. Example. [Stu2005] Let 𝔸 be a Q-category. Then both P𝔸 and P^{†}𝔸 are complete, hence cocomplete. Explicitly, for any Φ ∈ P(P𝔸) and Ψ ∈ P^{†}(P𝔸),

sup Φ = Φ ∘ (Y_{𝔸})_{♮}, and inf Ψ = Ψ ↘ (Y_{𝔸})_{♮};

for any Φ ∈ P(P^{†}𝔸) and Ψ ∈ P^{†}(P^{†}𝔸),

sup Φ = (Y_{𝔸}^{†})^{♮} ↙ Φ, and inf Ψ = (Y_{𝔸}^{†})^{♮} ∘ Ψ.

In particular, sup_{P𝔸} = PY_{𝔸} and inf_{P^{†}𝔸} = P^{†}Y_{𝔸}^{†}.

A Q-functor F : 𝔸 [figure] 𝔹 is said to be cocontinuous if it preserves suprema in the sense that F (sup_{𝔸}ϕ) is a supremum of ∃_{F} (ϕ) whenever sup_{𝔸}ϕ exists. Dually, F : 𝔸 [figure] 𝔹 is continuous if it preserves infima in the sense that F (inf_{𝔸}ϕ) is an infimum of ∃_{F}^{†} (ψ) whenever inf_{𝔸}ψ exists. F : 𝔸 [figure] 𝔹 is bicontinuous if it is both cocontinuous and continuous.

It is known [Stu2005] that a Q-functor F : 𝔸 [figure] 𝔹 between complete Q-categories is a left adjoint (resp. right adjoint) if and only if F is cocontinuous (resp. continuous). In particular, for each Q-functor F : 𝔸 [figure] 𝔹, PF : P𝔹 [figure] P𝔸 is bicontinuous; ∃_{F} : P𝔸 [figure] P𝔹 is cocontinuous; and ∀_{F} : P𝔸 [figure] P𝔹 is continuous.

2.10. Definition. [Stu2007] A Q-category 𝔸 is completely distributive if it is cocomplete and the left adjoint sup_{𝔸} : P𝔸 [figure] 𝔸 of the Yoneda embedding Y_{𝔸} : 𝔸 [figure] P𝔸 has a left adjoint ⇓_{𝔸}: 𝔸 [figure] P𝔸.

Note that completely distributive Q-categories are said to be totally continuous in [Stu2007]. Here we call them completely distributive following the practice in lattice theory, e.g. [Joh1982, Ran1952, Wood2004].

2.11. Example. [Stu2007] For a Q-category 𝔸, it follows from Example 2.9 that sup_{P𝔸} = PY_{𝔸}. Thus, sup_{P𝔸} is a right adjoint by Proposition 2.4. This shows that P𝔸 is completely distributive.

2.12. Proposition. Let 𝔸, 𝔹 be skeletal Q-categories, F : 𝔸 [figure] 𝔹 a left and right adjoint Q-functor.

(1) If F is an epimorphism in Q-Cat and 𝔸 is completely distributive, then so is 𝔹.

(2) If F is a monomorphism in Q-Cat and 𝔹 is completely distributive, then so is 𝔸.

Proof. (1) Suppose that H ⊣ F ⊣ G. Then F ∘ G ∘ F = F, hence F ∘ G = 1_{𝔹} since F is an epimorphism. It follows that for any y ∈ 𝔹,

(PG ∘ Y_{𝔸} ∘ G)(y) = PG(Y_{𝔸}(Gy)) = 𝔸(G−, Gy) = 𝔹(F ∘ G−, y) = 𝔹(−, y) = Y_{𝔹}(y),

showing that PG ∘ Y_{𝔸} ∘ G = Y_{𝔹}.

By assumption, the Yoneda embedding Y_{𝔸} has a left adjoint sup_{𝔸} that also has a left adjoint ⇓_{𝔸}. By virtue of Proposition 2.5 it holds that PH ⊣ PF ⊣ PG, hence

(PH∘ ⇓_{𝔸} ∘H) ⊣ (F ∘ sup_{𝔸} ∘ PF) ⊣ PG ∘ Y_{𝔸} ∘ G = Y_{𝔹}.

Therefore, 𝔹 is completely distributive with sup_{𝔹} = F ∘ sup_{𝔸} ∘PF.

(2) Suppose that H ⊣ F ⊣ G. Then F ∘ H ∘ F = F ∘ G ∘ F = F, and thus H ∘ F = G ∘ F = 1_{𝔸} since F is a monomorphism. Hence, for each x in 𝔸,

(PF ∘ Y_{𝔹} ∘ F)(x) = PF (Y_{𝔹}(F x)) = 𝔹(F −, F x) = 𝔸(H ∘ F −, x) = 𝔸(−, x) = Y_{𝔸}(x).

That means PF ∘ Y_{𝔹} ∘ F = Y_{𝔸}. Since ∃_{F} ⊣ PF, sup_{𝔹} ⊣ Y_{𝔹}, and H ⊣ F, it follows that H ∘ sup_{𝔹} ∘ ∃_{F} is a left adjoint of Y_{𝔸} = PF ∘ Y_{𝔹} ∘ F. Therefore, 𝔸 is complete with sup_{𝔸} = H ∘ sup_{𝔹} ∘∃_{F}. Since F is cocontinuous (being a left adjoint), we have that F ∘ sup_{𝔸} = sup_{𝔹} ∘∃_{F}. Hence

sup_{𝔸} = G ∘ F ∘ sup_{𝔸} = G ∘ sup_{𝔹} ∘ ∃_{F} .

This shows that sup_{𝔸} : P𝔸 ⟶ 𝔸 is a composite of right adjoints (∃_{F} is a right adjoint by Proposition 2.5, sup_{𝔹} is a right adjoint by complete distributivity of 𝔹), hence it is itself a right adjoint. The conclusion thus follows.

Now we form the following categories:

• Q-Sup, the category of skeletal cocomplete Q-categories and cocontinuous Q-func-tors.

• Q-Inf, the category of skeletal complete Q-categories and continuous Q-functors.

• Q-CD, the category of skeletal completely distributive Q-categories and bicontinuous Q-functors.

The categories Q-Sup and Q-Inf are dually isomorphic. For each cocontinuous Qfunctor F : 𝔸 [figure] 𝔹 between complete Q-categories, let F^{⊣} denote its right adjoint. Dually, for each continuous Q-functor G : 𝔹 [figure] 𝔸 between complete Q-categories, let G^{⊢} denote its left adjoint. Then we obtain a pair of functors

[figure: Q-Inf; Q-Sup^{op}; (-)^{⊣}; Q-Inf; Q-Sup^{op}; (-)^{⊢}]

that are inverse to each other.

The questions. The categories Q-Sup, Q-CD are respectively the Q-analogue of the category Sup of complete lattices and join-preserving maps, and the category CD of completely distributive lattices and complete lattice homomorphisms. Since both Sup and CD are monadic over Set [Joh1982], our first question is whether the categories Q-Sup and Q-CD are monadic over Set ↓ Q_{0}?

The forgetful functor |-| : Q-Cat [figure] Set ↓ Q_{0} has a left adjoint I : Set ↓ Q_{0} [figure] Q-Cat, given by identifying Q-typed sets with discrete Q-categories. Consider the adjunction |P^{†}| ⊣ |P| obtained by composing the following

[figure: Set ↓ Q_{0}; Q-Cat; I; Q-Cat; Q-Cat^{op}; P^{†}; Q-Cat^{op}; (Set ↓ Q_{0})^{op}.; |-|^{op}; Set ↓ Q_{0}; Q-Cat; |-|; Q-Cat; Q-Cat^{op}; P; Q-Cat^{op}; (Set ↓ Q_{0})^{op}.; I^{op}]

It is clear that |P^{†}| ⊣ |P| is the Q-version of the adjunction P^{op} ⊣ P : Set [figure] Set^{op}. It is known that P : Set^{op} [figure] Set is monadic and the corresponding algebras are the complete atomic Boolean algebras [Joh1982]. So, it is natural to ask what are the algebras of the monad determined by the adjunction |P^{†}| ⊣ |P|? This is the second question we’ll consider in this paper.

Before proceeding, we list below some known facts about Q-Cat, Q-Sup, and Q-CD.

(a) The monad corresponding to the adjunction I ⊣ |-| : Set ↓ Q_{0} [figure] Q-Cat is the identity monad on Set ↓ Q_{0}, hence its Eilenberg-Moore category is Set ↓ Q_{0}. Therefore, the forgetful functor |-| : Q-Cat [figure] Set ↓ Q_{0} is not monadic. This is an extension of the well-known fact that the forgetful functor from preordered sets to sets is not monadic.

(b) The composite of the adjunctions

[figure: Q-Cat; Q-Inf; P_{∃}^{†}; Q-Inf; Q-Sup^{op}; (-)^{⊢}; Q-Sup^{op}; Q-Cat^{op}; E^{op}; Q-Cat; Q-Inf; E^{†}; Q-Inf; Q-Sup^{op}; (-)^{⊣}; Q-Sup^{op}; Q-Cat^{op}; P_{∃}^{op}]

is exactly the adjunction P^{†} ⊣ P : Q-Cat ⇀ Q-Cat^{op} in Theorem 2.3. It is proved in [Stu2013] that the algebras of the monad corresponding to the adjunction P^{†} ⊣ P are the completely distributive Q-categories with bicontinuous Q-functors as morphisms. Hence, the category Q-CD is monadic over Q-Cat.

(c) Restricting the codomain of the 2-functor P_{∃} : Q-Cat [figure] Q-Cat to Q-Sup gives a left adjoint, also written P_{∃}, to the forgetful functor E : Q-Sup [figure] Q-Cat. It is proved in [Stu2013] that the forgetful functor Q-Sup [figure] Q-Cat is lax-idempotent monadic (see Theorem 3.16 below).

3. Q-Sup and Q-CD are monadic over Set ↓ Q_{0}

The aim of this section is to show that both Q-Sup and Q-CD are strictly monadic over Set ↓ Q_{0}. Recall that a right adjoint functor G : D [figure] C is monadic (resp. strictly monadic) [Mac1998, MM1992] if the comparison functor K : D [figure] C^{T} is an equivalence (resp. isomorphism) of categories, where T is the corresponding monad and C^{T} is the Eilenberg-Moore category of T-algebras and homomorphisms. A category D is (strictly) monadic over a category C if there exists a (strictly) monadic functor G : D [figure] C.

For an object x in a Q-category 𝔸 and an arrow f : tx [figure] Y in Q, the tensor of f and x, denoted by f ⊗ x, is an object in 𝔸 of type Y such that 𝔸(f ⊗ x, −) = 𝔸(x, −) ↙ f. Dually, for an arrow g : Y [figure] tx, the cotensor of g and x, denote by g ↣ x, is an object in 𝔸 of type Y such that 𝔸(−, g ↣ x) = g ↘ 𝔸(−, x). A Q-category 𝔸 is tensored if the tensor f ⊗ x exists for all objects x in 𝔸 and all arrows f in Q with codomain tx [Stu2006]. The dual notion is cotensored.

It is easy to see that the tensor f ⊗ x is the supremum of the presheaf f ∘ 𝔸(−, x); the cotensor g ↣ x is the infimum of the co-presheaf 𝔸(x, −) ∘ g. So, a complete Q-category is both tensored and cotensored.

For each Q-category 𝔸 and each object X in Q, write 𝔸_{X} for the preordered set consisting of objects of type X in 𝔸 together with the underlying order. It is known that if 𝔸 is a complete Q-category then 𝔸_{X} is a complete preordered set for each X in Q. The following proposition was observed in [LZ09] for quantale-enriched categories and in [Shen2014] for the general setting.

3.1. Proposition. Let 𝔸 and 𝔹 be Q-categories, and F : |𝔸| [figure] |𝔹| be a type-preserving map. If both 𝔸 and 𝔹 are tensored, then F : 𝔸 [figure] 𝔹 is a Q-functor if and only if

(1) For any object x in 𝔸 and arrow f : tx [figure] Y, f ⊗ F x ≤ F (f ⊗ x);

(2) For any object X in Q, F : 𝔸_{X} [figure] 𝔹_{X} is order-preserving.

Dually, if both 𝔸 and 𝔹 are cotensored, then F : 𝔸 [figure] 𝔹 is a Q-functor if and only if

(1’) For any object x in 𝔸 and arrow g : Y [figure] tx, F (g ↣x) ≤ g ↣F x;

(2’) For any object X in Q, F : 𝔸_{X} [figure] 𝔹_{X} is order-preserving.

3.2. Proposition. [Stu2006] Let 𝔸 and 𝔹 be Q-categories, F : |𝔸| [figure]|𝔹| a typepreserving map. If 𝔸 is tensored, then F : 𝔸 [figure] 𝔹 is a left adjoint Q-functor if and only if

(1) F preserves tensors in the sense that F (f ⊗ x) = f ⊗ F x for all objects x in 𝔸 and all arrows f : tx [figure] Y;

(2) For all objects X in Q, F : 𝔸_{X} [figure] 𝔹_{X} is a left adjoint.

Dually, if 𝔸 is cotensored, then F : 𝔸 [figure] 𝔹 is a right adjoint Q-functor if and only if

(1’) F preserves cotensors in the sense that F (g ↣ x) = g ↣ F x for all objects x in 𝔸 and all arrows g : Y [figure] tx;

(2’) For all objects X in Q, F : 𝔸_{X} [figure] 𝔹_{X} is a right adjoint.

3.3. Definition. [SZ2013a] A closure operator on a Q-category 𝔸 is a Q-functor c : 𝔸 [figure] 𝔸 such that 1_{𝔸} ≤ c and c^{2} ≤ c.

3.4. Lemma. If c : 𝔸 [figure] 𝔸 is a closure operator on a skeletal Q-category 𝔸, then c(𝔸) = {x ∈ 𝔸 | c(x) = x} and c : 𝔸 [figure] c(𝔸) is left adjoint to the inclusion i : c(𝔸) ↪ 𝔸.

Proof. Since 𝔸 is skeletal and c^{2}(x) is isomorphic to c(x) for each x in 𝔸, it follows immediately that c(𝔸) = {x ∈ 𝔸 | c(x) = x}.

Since c ∘ i(y) = c(y) = y for any y in c(𝔸) and i ∘ c(x) = c(x) ≥ x for any x in 𝔸, it follows that c ∘ i = 1_{c(𝔸)} and i ∘ c ≥ 1_{𝔸}. Hence, c is left adjoint to i.

3.5. Definition. A congruence on a complete skeletal Q-category 𝔸 is an equivalence relation R on the underlying set 𝔸_{0} subject to the following conditions:

(i) (x, y) ∈ R implies tx = ty, that is, equivalent elements have the same type.

(ii) For each object X in Q, the subset R ∩(𝔸_{X} ×𝔸_{X}) is closed w.r.t. joins in 𝔸_{X} ×𝔸_{X}.

(iii) If (x, y) ∈ R, then (f ⊗ x, f ⊗ y) ∈ R for all f : tx [figure] Y.

A congruence R is complete if it satisfies moreover:

(iv) For each object X in Q, the subset R∩(𝔸_{X} ×𝔸_{X}) is closed w.r.t. meets in 𝔸_{X} ×𝔸_{X}.

(v) If (x, y) ∈ R, then (g ↣x, g ↣y) ∈ R for all g : Y [figure] tx in Q.

For a congruence R on a complete skeletal Q-category 𝔸, define a map c : 𝔸_{0} [figure] 𝔸_{0} by putting c(x) to be the greatest element in the equivalence class of x (which is a subset of the complete lattice 𝔸_{tx}). Then c is clearly type-preserving.

3.6. Lemma. If R is a congruence on a complete skeletal Q-category 𝔸, then c : 𝔸 [figure] 𝔸 is a closure operator. Furthermore, if R is complete then c : 𝔸 [figure] 𝔸 is also a right adjoint.

Proof. It is easy to check that c has the following properties:

(a) c : 𝔸_{X} [figure] 𝔸_{X} preserves order for each object X in Q.

(b) For each x in 𝔸, x ≤ c(x) = c^{2}(x).

(c) For any object x in 𝔸 and any f : tx [figure] Y in Q, f ⊗ c(x) ≤ c(f ⊗ x).

Properties (a) and (c) ensure that c : 𝔸 [figure] 𝔸 is a Q-functor by virtue of Proposition 3.1, hence a closure operator by (b).

It remains to show that c : 𝔸 [figure] 𝔸 is a right adjoint if R is a complete congruence. We apply Proposition 3.2 to accomplish this.

Since c : 𝔸 [figure] 𝔸 is a Q-functor, one has that g ↣ c(x) ≥ c(g ↣ x) for all x and g : Y [figure] tx by Proposition 3.1. Meanwhile, condition (v) ensures that g ↣c(x) ≤ c(g ↣x). Therefore, g ↣c(x) = c(g ↣x). This proves that c preserves cotensors.

Let {x_{i}} be a family of elements in 𝔸_{X}. On one hand, since (x_{i}, c(x_{i})) ∈ R for any x_{i} and R is closed w.r.t. meets, it follows that (⋀ x_{i}, ⋀ c(x_{i})) ∈ R. Thus, c(⋀ x_{i}) ≥ ⋀ c(x_{i}). On the other hand, since c : 𝔸_{X} [figure] 𝔸_{X} preserves order, it is clear that c(⋀ x_{i}) ≤ ⋀ c(x_{i}). Therefore, c : 𝔸_{X} [figure] 𝔸_{X} is meet-preserving, hence a right adjoint since A_{X} is a complete lattice.

3.7. Lemma. Let 𝔸 be a skeletal complete Q-category, c : 𝔸 [figure] 𝔸 a closure operator. Then c(𝔸), as a subcategory of 𝔸, is complete.

Proof. Let i be the embedding c(𝔸) ↪ 𝔸. It is easy to check that Pi ∘ Y_{𝔸} ∘ i = Y_{c(𝔸)}. Since c ⊣ i (Lemma 3.4), sup_{𝔸} ⊣ Y_{𝔸} (𝔸 is cocomplete) and Pc ⊣ Pi (Proposition 2.5), then

c ∘ sup_{𝔸} ∘ Pc ⊣ Pi ∘ Y_{𝔸} ∘ i = Y_{c(𝔸)},

showing that the Yoneda embedding Y_{c(𝔸)} has a left adjoint, hence c(𝔸) is cocomplete, hence complete.

3.8. Theorem. The forgetful functor |-| : Q-Sup [figure] Set ↓ Q_{0} is strictly monadic.

Proof. Since both of the forgetful functors Q-Sup [figure] Q-Cat and Q-Cat [figure] Set ↓ Q_{0} are right adjoints, it follows that the forgetful functor |-| : Q-Sup [figure] Set ↓ Q_{0}, being a composite of right adjoints, is itself a right adjoint. Thus, by virtue of Beck’s theorem (Theorem 1 on page 151 in [Mac1998]), it suffices to show that |-| : Q-CD [figure] Set ↓ Q_{0} creates split coequalizers.

Given a pair of cocontinuous Q-functors F, G : 𝔸 [figure] 𝔹 between complete skeletal Q-categories, a split coequalizer of F, G : |𝔸| [figure] |𝔹| in Set ↓ Q_{0} is, by definition, a type-preserving map H : |𝔹| [figure] C with type-preserving maps C [figure: K] |𝔹| [figure: L] |𝔸| such that

H ∘ F = H ∘ G, F ∘ L = 1, H ∘ K = 1, G ∘ L = K ∘ H.

Define a relation R on 𝔹_{0} by

R = {(y_{1}, y_{2}) ∈ 𝔹_{0} × 𝔹_{0} | H(y_{1}) = H(y_{2})}.

Claim 1: For any y_{1}, y_{2} ∈ 𝔹_{0}, (y_{1}, y_{2}) ∈ R if and only if there is a pair (x_{1}, x_{2}) ∈ 𝔸_{0} × 𝔸_{0} such that G(x_{1}) = G(x_{2}) and y_{1} = F (x_{1}), y_{2} = F (x_{2}).

Sufficiency is easy. For necessity, let x_{1} = L(y_{1}) and x_{2} = L(y_{2}). Then

G(x_{1}) = G ∘ L(y_{1}) = K ∘ H(y_{1}) = K ∘ H(y_{2}) = G ∘ L(y_{2}) = G(x_{2}),

and

F (x_{1}) = F ∘ L(y_{1}) = y_{1}, F (x_{2}) = F ∘ L(y_{2}) = y_{2}.

Claim 2: The relation R is a congruence on 𝔹.

This follows from Claim 1 and the fact that both F and G preserve tensors and joins (with respect to the underlying orders).

Thus, R determines a closure operator c : 𝔹 [figure] 𝔹 by Lemma 3.6. It follows from Lemma 3.7 that c(𝔹) is complete. Since the underlying Q-typed set of c(𝔹) is essentially the Qtyped set C, hence C can be made into a complete Q-category ℂ (which is isomorphic to c(𝔹)) such that H : 𝔹 [figure] ℂ is a cocontinuous Q-functor. This proves that the forgetful functor |-| : Q-CD [figure] Set ↓ Q_{0} creates split coequalizers.

Since (Q-Inf)^{co} is isomorphic to Q^{op}-Sup as 2-categories, applying the above theorem to Q^{op} yields:

3.9. Theorem. The forgetful functor Q-Inf [figure] Set ↓ Q_{0} is strictly monadic.

Our next task is to show that the forgetful functor |-| : Q-CD [figure] Set ↓ Q_{0} is strictly monadic. We show that it is a right adjoint first. Given a continuous Q-functor F : 𝔸 [figure] 𝔹 between complete Q-categories, it follows from Proposition 2.4 and 2.5 that P_{∃}F : P𝔸 [figure] P𝔹 is bicontinuous. Therefore, by restricting the domain and the codomain of the functor P_{∃} : Q-Cat [figure] Q-Sup one obtains a functor P_{∃}^{inf} : Q-Inf [figure] Q-CD that is left adjoint to the forgetful functor E^{inf} : Q-CD [figure] Q-Inf. Then the forgetful functor |-| : Q-CD [figure] Set ↓ Q_{0}, as a composite of right adjoints, is a right adjoint.

3.10. Lemma. Let 𝔸 be a skeletal completely distributive Q-category; c : 𝔸 [figure] 𝔸 be a right adjoint and a closure operator. Then c(𝔸) is completely distributive.

Proof. This follows from Proposition 2.12(1) and the fact that c : 𝔸 [figure] c(𝔸) is both a left and a right adjoint.

3.11. Theorem. The forgetful functor |-| : Q-CD [figure] Set ↓ Q_{0} is strictly monadic.

Proof. It suffices to check that the forgetful functor |-| : Q-CD [figure] Set ↓ Q_{0} creates split coequalizers. We only include here a sketch of the proof since it is similar to that of Theorem 3.8.

Suppose F, G : 𝔸 [figure] 𝔹 are bicontinuous Q-functors between completely distributive skeletal Q-categories and H : |𝔹| [figure] C is a split coequalizer of F, G : |𝔸| [figure] |𝔹| in Set ↓ Q_{0}. By definition there exist type-preserving maps C [figure: K] |𝔹| [figure: L] |𝔸| such that

H ∘ F = H ∘ G, F ∘ L = 1, H ∘ K = 1, G ∘ L = K ∘ H.

Define a relation R on 𝔹_{0} by R = {(y_{1}, y_{2}) ∈ 𝔹_{0} × 𝔹_{0} | H(y_{1}) = H(y_{2})}. Then R is a complete congruence on 𝔹. This follows easily from Claim 1 in Theorem 3.8 and the fact that both F and G preserve tensors, cotensors, joins and meets (with respect to the underlying orders). By virtue of Lemma 3.6, the relation R determines a Q-functor c : 𝔹 [figure] 𝔹 which is both a closure operator and a right adjoint. Then c(𝔹) is completely distributive by Lemma 3.10. Since the underlying Q-typed set of c(𝔹) is isomorphic to C, it follows that C can be made into a completely distributive Q-category ℂ (isomorphic to c(𝔹)) such that H : 𝔹 [figure] ℂ is a bicontinuous Q-functor. This proves that the forgetful functor |-| : Q-CD [figure] Set ↓ Q_{0} creates split coequalizers.

In the remainder of this section, we show that the forgetful functor Q-CD [figure] Q-Inf is monadic. But, we do not know whether so is the forgetful functor Q-CD [figure] Q-Sup.

Consider the adjunction P_{∃} ⊣ E : Q-Cat ⇀ Q-Sup. The corresponding monad is given by

P_{∃} = {P_{∃} : Q-Cat [figure] Q-Cat, Y : 1 ⇒ P_{∃}, sup : P_{∃}^{2} ⇒ P_{∃}}.

The monad P_{∃} is an example of monads that are of Kock-Zöberlein type. The following proposition, extracted from [Kock1995, Zob1976], is taken from [Hof2013].

3.12. Proposition. Let T = (T, e, m) be a monad on a locally ordered category C with T a 2-functor. Then the following are equivalent:

(1) T e_{X} ≤ e_{T X} for all objects X.

(2) T e_{X} ⊣ m_{X} for all objects X.

(3) m_{X} ⊣ e_{T X} for all objects X.

(4) For any object X and morphism h : T X [figure] X, the pair (X, h) is a T-algebra if and only if h ∘ e_{X} = 1_{X}. In this case, h ⊣ e_{X}.

A monad on a locally-ordered category is said to be of Kock-Zöberlein type, if it satisfies one (hence all) of the equivalent conditions in Proposition 3.12. This kind of monads are examples of lax-idempotent 2-monads on 2-categories introduced by G.M. Kelly and S. Lack [KL1997], so, we’ll call them lax-idempotent in this paper.

A 2-functor T : C [figure] D between locally-ordered categories is lax-idempotent monadic if it is monadic and the corresponding monad is lax-idempotent.

3.13. Proposition. [Stu2013] The monad P_{∃} = (P_{∃}, Y, sup) is lax-idempotent.

Proof. The conclusion was proved in [Stu2013]. Here we repeat the proof for later use. For any Q-category 𝔸, since sup_{P𝔸} = PY_{𝔸} (Example 2.9) and P_{∃}Y_{𝔸} ⊣ PY_{𝔸} (Proposition 2.4), it follows that P_{∃}Y_{𝔸} ⊣ sup_{P𝔸}. Hence P_{∃}Y_{𝔸} = P_{∃}Y_{𝔸} ∘ sup_{P𝔸} ∘ Y_{P𝔸} ≤ Y_{P𝔸}, completing the proof.

3.14. Corollary. [Stu2013] For a Q-category 𝔸, the following are equivalent:

(1) 𝔸 is complete.

(2) The Yoneda embedding Y_{𝔸} : 𝔸 [figure] P𝔸 has a left inverse P𝔸 [figure] 𝔸.

3.15. Corollary. Given a Q-category 𝔸 and a Q-functor F : P𝔸 [figure] 𝔸, (𝔸, F) is a P_{∃}-algebra if and only if 𝔸 is a skeletal complete Q-category and F = sup_{𝔸}.

It follows from Corollary 3.15 that the category of P_{∃}-algebras is equivalent to the category of skeletal complete Q-categories and cocontinuous Q-functors.

3.16. Theorem. [Stu2013] The forgetful functor Q-Sup [figure] Q-Cat is lax-idempotent monadic.

A 2-functor T : C [figure] D between locally-ordered categories is colax-idempotent monadic if T^{co} : C^{co} [figure] D^{co} is lax-idempotent monadic. Since the 2-category (Q-Cat)^{co} is isomorphic to Q^{op}-Cat, and (Q-Inf)^{co} to Q^{op}-Sup, applying the above theorem to Q^{op} we obtain:

3.17. Corollary. The forgetful functor Q-Inf [figure] Q-Cat is colax-idempotent monadic.

Now we come to the last conclusion in this section.

3.18. Proposition. The forgetful functor Q-CD [figure] Q-Inf is lax-idempotent monadic.

Proof. Consider the monad P_{∃}^{inf} generated by the adjunction P_{∃}^{inf} ⊣ E^{inf} (see the paragraph following Theorem 3.9). By the same argument for P_{∃} one deduces that the monad P_{∃}^{inf} is lax-idempotent. So, it remains to check that the forgetful functor E^{inf} : Q-CD [figure] Q-Inf is monadic.

Let 𝔸 be a complete skeletal Q-category and F : P𝔸 [figure] 𝔸 a continuous Q-functor. If (𝔸, F) is a P_{∃}^{inf}-algebra, then F is a left inverse of the Yoneda embedding Y_{𝔸} by Proposition 3.12(4), hence 𝔸 is complete and F = sup_{𝔸} by corollaries 3.14 and 3.15. Thus, sup_{𝔸} is a right adjoint, showing that 𝔸 is completely distributive. Therefore, the correspondence (𝔸, F) ↦ 𝔸 defines a functor Q-Inf^{P_{∃}^{inf}} [figure] Q-CD that is inverse to the comparison functor

Q-CD [figure] Q-Inf^{P_{∃}^{inf}}, 𝔸 ↦ (𝔸, sup_{𝔸}).

The conclusion thus follows.

The monadicity of the forgetful functor Q-CD [figure] Set ↓ Q_{0} does not follow from that of the forgetful functors Q-Inf [figure] Q-Cat and Q-CD [figure] Q-Inf, since the composite of monadic functors need not be monadic, see [Bor1994], page 214.

4. Q-powersets as algebras

It is well-known (e.g. [Joh1982, MM1992]) that the contravariant powerset functor P : Set^{op} [figure] Set is monadic with a left adjoint given by P^{op} : Set [figure] Set^{op}; and that the algebras corresponding to the monad generated by the adjunction P^{op} ⊣ P are powersets (or equivalently, complete atomic Boolean algebras). In this section, we establish a Qversion of this conclusion. That is, if we denote by |P^{†}| ⊣ |P| the adjunction obtained by composing the following

[figure: Set ↓ Q_{0}; Q-Cat; I; Q-Cat; Q-Cat^{op}; P^{†}; Q-Cat^{op}; (Set ↓ Q_{0})^{op}.; |-|^{op}; Set ↓ Q_{0}; Q-Cat; |-|; Q-Cat; Q-Cat^{op}; P; Q-Cat^{op}; (Set ↓ Q_{0})^{op},; I^{op}]

then the functor |P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} is monadic and the corresponding Eilenberg-Moore algebras are exactly the Q-powersets of Q-typed sets.

The monadicity of the powerset functor P : Set^{op} [figure] Set is a special case of a general result in topos theory [MM1992] that states that for each topos E, the opposite category E^{op} is monadic over E. In particular, for each set X, (Set ↓ X)^{op} is monadic over Set ↓ X with the (internal) powerset functor being a monadic one. We’d like to remark that the conclusion presented here shows that, for each non-empty set X, there exist many monadic functors from (Set ↓ X)^{op} to Set ↓ X.

Before proceeding, we spell out some facts of the adjunction |P^{†}| ⊣ |P|.

First, the functor |P| sends each Q-typed set A to the underlying Q-typed set |PA| of PA, where A is regarded as a discrete Q-category. The Q-typed set |PA| is called the Q-powerset of A.

Second, for each type-preserving map F : A [figure] B between Q-typed sets, |P|F is the underlying type-preserving map of PF : PB [figure] PA. Similarly, |P^{†}|F is the underlying type-preserving map of P^{†}F : P^{†}B [figure] P^{†}A. So, for a type-preserving map F between Q-typed sets, we simply write PF (P^{†}F, resp.) for |P|F (|P^{†}|F, resp.) if no confusion would arise.

Third, the unit and counit of the adjunction |P^{†}| ⊣ |P| are respectively given by

ϵ_{A} = Y_{|P^{†}A|} ∘ Y_{A}^{†} : A [figure] |P^{†}A| [figure] |P|P^{†}A||

and

γ_{A} = Y_{|PA|}^{†} ∘ Y_{A} : A [figure] |PA| [figure] |P^{†}|PA||

for any Q-typed set A.

The following lemma is a counterpart of the Beck-Chevalley condition in [MM1992], Theorem 2, page 206.

4.1. Lemma. Let

[figure: A; C; F; A; B; H; C; D; K; B; D; G]

be a pullback square in Set ↓ Q_{0}. Then the square of Q-distributors between discrete Q-categories

[figure: A; C; F_{♮}; ∘; B; A; H^{♮}; ∘; D; C; K^{♮}; ∘; B; D; G_{♮}; ∘]

commutes; or equivalently, the square of Q-functors

[figure: PC; PA; PF; PC; PD; ∃_{K}; PA; PB; ∃_{H}; PD; PB; PG]

commutes.

Proof. By hypothesis, we can assume that the underlying set of A is

{(y, z) ∈ B × C | Gy = Kz},

the type function is given by t[(y, z)] = ty = tz for all (y, z) ∈ A, and that both H and F are projections. For all b ∈ B and c ∈ C,

(F_{♮} ∘ H^{♮})(b, c) = ⋁_{(y,z)∈A} id_{C}(z, c) ∘ id_{B}(b, y) = \{ \begin{matrix}1_{tb}, & Gb = Kc; \\ ⊥_{tb,tc}, & otherwise. \end{matrix}

It follows that

K^{♮} ∘ G_{♮}(b, c) = ⋁_{d∈D} id_{D}(d, Kc) ∘ id_{D}(Gb, d) = id_{D}(Gb, Kc) = F_{♮} ∘ H^{♮}(b, c).

That is, the second square commutes.

It remains to check that the second square commutes if and only if so does the third one. Since ∃_{H} ∘ PF (ϕ) = ϕ ∘ F_{♮} ∘ H^{♮} and PG ∘ ∃_{K}(ϕ) = ϕ ∘ K^{♮} ∘ G_{♮} for all ϕ ∈ PC, the commutativity of the third square follows trivially from that of the second one. Conversely, if the third square commutes, then for all c ∈ C,

F_{♮} ∘ H^{♮}(−, c) = id_{C}(−, c) ∘ F_{♮} ∘ H^{♮} = ∃_{H} ∘ PF (id_{C}(−, c))

and

K^{♮} ∘ G_{♮}(−, c) = id_{C}(−, c) ∘ K^{♮} ∘ G_{♮} = PG ∘ ∃_{K}(id_{C}(−, c)),

hence, the second one commutes.

4.2. Theorem. The functor |P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} is monadic.

Proof. Since Set ↓ Q_{0} is a complete category, we apply Corollary 3 on page 180 in [MM1992] to prove the conclusion. That is, we show that |P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} reflects isomorphisms and preserves coequalizers of reflexive pairs.

Since |P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} is faithful, it reflects both monomorphisms and epimorphisms. Since the slice category Set ↓ Q_{0} is a topos, an arrow in Set ↓ Q_{0} is an isomorphism if and only if it is both a monomorphism and an epimorphism. Consequently, |P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} reflects isomorphisms.

It remains to check that |P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} preserves coequalizers of reflexive pairs. Recall that a pair of arrows r, s : X [figure] Y in a category is reflexive if there exists an arrow i : Y [figure] X such that r ∘ i = 1_{Y} = s ∘ i. So, a reflexive pair in (Set ↓ Q_{0})^{op} is a pair of arrows F, G : A [figure] B in Set ↓ Q_{0} together with an arrow K : B [figure] A such that K ∘ F = K ∘ G = 1_{A}. We must show that if H : C [figure] A is an equalizer of F and G in Set ↓ Q_{0} then |P|H = PH : |PC| [figure] |PA| is a coequalizer of PF and PG. That is, for each L : |PA| [figure] D in Set ↓ Q_{0} with L ∘ PF = L ∘ PG, there exists a unique L̄ : |PC| [figure] D such that L̄ ∘ PH = L.

Uniqueness. It is obvious that, as an equalizer, H : C [figure] A is a monomorphism in Set ↓ Q_{0}. Hence H is a fully faithful Q-functor between discrete Q-categories C and A. Thus, L̄ = L̄ ∘ PH ∘ ∃_{H} = L ∘ ∃_{H} by Proposition 2.7(1).

Existence. It suffices to verify that L ∘ ∃_{H} ∘ PH = L. First, we check that the square

[figure: C; A; H; C; A; H; A; B; F; A; B; G]

is a pullback in Set ↓ Q_{0}. Given a pair of arrows F′, G′ : D [figure] A with F ∘ F′ = G ∘ G′, since K ∘ F = K ∘ G = 1_{A}, we have that

F′ = K ∘ F ∘ F′ = K ∘ G ∘ G′ = G′.

Because H : C [figure] A is an equalizer of F and G, there is a unique U : D [figure] A such that F′ = H ∘ U = G′. This proves that the square is a pullback. Then it follows from Lemma 4.1 that PG ∘ ∃_{F} = ∃_{H} ∘ PH. Finally, since K ∘ F = 1_{A}, it follows that F : A [figure] B is a fully faithful Q-functor if we treat A and B as discrete Q-categories. Thus, PF ∘∃_{F} = 1_{PA} by Proposition 2.7(1). Therefore,

L = L ∘ PF ∘ ∃_{F} = L ∘ PG ∘ ∃_{F} = L ∘ ∃_{H} ∘ PH.

The proof is thus completed.

4.3. Remark. In general, the monadic functor |P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} is different from the “internal” powerset functor for the topos Set ↓ Q_{0}. It is easily verified that |P| coincides with the internal powerset functor if Q is given by

Q(X, Y) = \{ \begin{matrix}2 = \{0, 1\}, & if X = Y; \\ 1 = \{0\}, & otherwise. \end{matrix}

Furthermore, if there exist different objects X, Y in Q with Q(X, Y) containing at least two elements, then the functor |P| cannot be isomorphic to the internal powerset functor [−, B] : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0} for any B in Set ↓ Q_{0}. To see this, we first note that for each A in Set ↓ Q_{0} and Z in Q_{0}, an element in [A, B] with type Z is exactly a function A_{Z} [figure] B_{Z}, where A_{Z} is the set of elements in A with type Z, and likewise for B_{Z}. Now, let C be a Q-typed set consisting of only one element with type X. Then there is exactly one element in [C, B] that is of type Y (namely, the unique map from the empty set to B_{Y}), but there are at least two elements in |P|C that are of type Y. Therefore, [−, B] and |P| cannot be isomorphic.

In the following we describe the Eilenberg-Moore algebras of the monad generated by the adjunction |P^{†}| ⊣ |P|. The corresponding monad is given by

|B| = {|B| : Set ↓ Q_{0} [figure] Set ↓ Q_{0}, ϵ : 1 ⇒ |B|, δ : |B|^{2} ⇒ |B|}

where

• |B|F = |P|(|P^{†}|F) : |P|P^{†}A|| [figure] |P|P^{†}B|| for any type-preserving map F : A [figure] B,

• ϵ_{A} = E_{P^{†}A} ∘ Y_{A}^{†} : A [figure] |P^{†}A| [figure] |P|P^{†}A|| for any Q-typed set A,

• δ_{A} = Pγ_{|P^{†}A|} : |B|^{2}A [figure] |B|A for any Q-typed set A.

For each Q-typed set B, (|PB|, Pγ_{B}) is a |B|-algebra. The following theorem says that all |B|-algebras are of this form.

4.4. Theorem. Every |B|-algebra is of the form (|PB|, Pγ_{B}) for some Q-typed set B.

Proof. Suppose that (A, F) is a |B|-algebra. That is, A is a Q-typed set, F : |B|A [figure] A is a type-preserving map such that F ∘ ϵ_{A} = 1_{A} and F ∘ δ_{A} = F ∘ |B|F. We show that there is some Q-typed set B such that (A, F) is isomorphic to (|PB|, Pγ_{B}).

Consider the pullback

[figure: B; |P^{†}A|; i; B; |P^{†}A|; i′; |P^{†}A|; |P^{†}|BA||; P^{†}F; |P^{†}A|; |P^{†}|BA||; γ_{|P^{†}A|}]

in Set ↓ Q_{0}. We claim that B satisfies the requirement. The proof is divided into three steps.

Step 1. i = i′. This follows easily from the triangular identity P^{†}ϵ_{A} ∘ γ_{|P^{†}A|} = 1_{|P^{†}A|} and the equality P^{†}ϵ_{A} ∘ P^{†}F = P^{†}(F ∘ ϵ_{A}) = 1_{|P^{†}A|}. Consequently, i is an equalizer of P^{†}F and γ_{|P^{†}A|}.

Step 2. K_{A} = Pi ∘ ϵ_{A} : (A, F) [figure] (|PB|, Pγ_{B}) is a homomorphism between |B|- algebras, i.e., K_{A} ∘ F = Pγ_{B} ∘ |B|K_{A}. To see this, we calculate:

K_{A} ∘ F = Pi ∘ ϵ_{A} ∘ F
= Pi ∘ |B|F ∘ ϵ_{|B|A}  (naturailty of ϵ)
= P(P^{†}F ∘ i) ∘ ϵ_{|B|A}  (P^{†}F : |P^{†}A| [figure] |P^{†}(|B|A)|)
= P(γ_{|P^{†}A|} ∘ i) ∘ ϵ_{|B|A}  (i equalizes P^{†}F and γ_{|P^{†}A|})
= Pi ∘ Pγ_{|P^{†}A|} ∘ ϵ_{|B|A}
= Pi ∘ δ_{A} ∘ ϵ_{|B|A}
= Pi  (δ_{A} ∘ ϵ_{|B|A} = 1_{|B|A})
= Pi ∘ |B|F ∘ |B|ϵ_{A}  (F ∘ ϵ_{A} = 1_{A})
= P(γ_{|P^{†}A|} ∘ i) ∘ |B|ϵ_{A}  (i equalizes P^{†}F and γ_{|P^{†}A|})
= P(|P^{†}|(Pi) ∘ γ_{B}) ∘ |B|ϵ_{A}  (naturailty of γ)
= Pγ_{B} ∘ |B|(Pi) ∘ |B|ϵ_{A}
= Pγ_{B} ∘ |B|K_{A}.

Step 3. K_{A} : (A, F) [figure] (|PB|, Pγ_{B}) is an isomorphism between |B|-algebras. It suffices to check that K_{A} : A [figure] |PB| is an isomorphism in Set ↓ Q_{0}.

Let L_{A} = F ∘ ∃_{i}. On the one hand, it follows from the calculations in Step 2 that

K_{A} ∘ L_{A} = Pi ∘ ϵ_{A} ∘ F ∘ ∃_{i} = Pi ∘ ∃_{i} = 1_{|PB|},

where the last equality holds due to Proposition 2.7(1).

On the other hand, by virtue of Lemma 4.1 and the definition of δ_{A} one has that

∃_{i} ∘ Pi = Pγ_{|P^{†}A|} ∘ ∃_{P^{†}F} = δ_{A} ∘ ∃_{P^{†}F} .

Since P^{†}F : |P^{†}A| [figure] |P^{†}(|B|A)| is fully faithful (P^{†}ϵ_{A} ∘ P^{†}F = 1_{|P^{†}A|}), it holds that

|B|F ∘ ∃_{P^{†}F} = P(P^{†}F) ∘ ∃_{P^{†}F} = 1_{|B|A}

by Proposition 2.7(1). Consequently,

L_{A} ∘ K_{A} = F ∘ ∃_{i} ∘ Pi ∘ ϵ_{A}
= F ∘ δ_{A} ∘ ∃_{P^{†}F} ∘ ϵ_{A}
= F ∘ |B|F ∘ ∃_{P^{†}F} ∘ ϵ_{A}  ((A, F) is a |B|-algebra)
= F ∘ ϵ_{A}  (|B|F ∘ ∃_{P^{†}F} = 1_{|B|A})
= 1_{A}.

Therefore, K_{A} : A [figure] |PB| is an isomorphism between Q-typed sets.

4.5. Remark. From the point of view of fuzzy sets [Zad1965], a Q-typed set is nothing but a “fuzzy set valued in Q_{0}”. Viewed in this perspective, the functor

|P| : (Set ↓ Q_{0})^{op} [figure] Set ↓ Q_{0}

is a fuzzy counterpart of the contravariant powerset functor P : Set^{op} [figure] Set; the above theorem can be thought of as a fuzzy version of the Stone duality between sets and complete atomic Boolean algebras. Thus, it is not surprising that the functor |P| has applications in the theory of fuzzy sets. Interested readers are referred to [Hoh2014, SZ2013b, Stu2014] for more discussions on related topics.

Finally, consider the adjunction |-|^{op}∘P^{†} ⊣ P∘I^{op} obtained by composing the following adjunctions

[figure: Q-Cat; Q-Cat^{op}; P^{†}; Q-Cat^{op}; (Set ↓ Q_{0})^{op}.; |-|^{op}; Q-Cat; Q-Cat^{op}; P; Q-Cat^{op}; (Set ↓ Q_{0})^{op}.; I^{op}]

Let τ be the counit of the adjunction |-|^{op} ∘ P^{†} ⊣ P ∘ I^{op} and let B be the monad on Q-Cat corresponding to this adjunction. Then the following theorem says that the Eilenberg-Moore algebras of B are also the Q-powersets of Q-typed sets.

4.6. Theorem. If (𝔸, F) is a B-algebra, then there exists a Q-typed set B such that (𝔸, F) is isomorphic to (PB, Pτ_{B}).

Proof. Consider the pullback

[figure: B; |P^{†}𝔸|; i; B; |P^{†}𝔸|; i′; |P^{†}𝔸|; |P^{†}(B𝔸)|; P^{†}F; |P^{†}𝔸|; |P^{†}(B𝔸)|; τ_{|P^{†}𝔸|}]

in Set ↓ Q_{0}, where B = P ∘ I^{op} ∘ |-|^{op} ∘ P^{†}. Then B satisfies the requirement. The proof is similar to that of Theorem 4.4 and is thus omitted here.

References

J. Bénabou. Introduction to bicategories. In: Reports of the Midwest Category Seminar, Volume 47 of Lecture Notes in Mathematics, pages 1-77. Springer, Berlin, 1967.

R. Betti, A. Carboni. Cauchy-completion and the associated sheaf. Cahiers de Topologie et Géométrie Différentielle Catégoriques 23(3): 243-256, 1982.

R. Betti, A. Carboni, R. H. Street, R. F. C. Walters. Variation through enrichment. Journal of Pure and Applied Algebra 29: 109-127, 1983.

F. Borceux. Handbook of Categorical Algebra: Volume 2, Categories and Structures, Volume 51 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1994.

D. Hofmann. Duality for distributive spaces. Theory and Applications of Categories 28(3): 66-122, 2013.

U. Höhle. Categorical foundations of topology with applications to quantaloid enriched topological spaces. Fuzzy Sets and Systems 256: 166-210, 2014.

P. T. Johnstone. Stone Spaces. Cambridge University Press, Cambridge, 1982.

G. M. Kelly, S. Lack. On property-like structures. Theory and Applications of Categories, 3(9): 213-250, 1997.

A. Kock. Monads for which structures are adjoint to units. Journal of Pure and Applied Algebra 104(1): 41-59, 1995.

S. Lack. A 2-categories companion. In: Towards Higher Categories, Volume 152 of The IMA Volumes in Mathematics and its Applications, pages 105-191. Springer, New York, 2010.

H. Lai, D. Zhang. Concept lattices of fuzzy contexts: Formal concept analysis vs. rough set theory. International Journal of Approximate Reasoning 50(5): 695-707, 2009.

S. Mac Lane. Categories for the Working Mathematician, 2nd Edition. Volume 5 of Graduate Texts in Mathematics. Springer, New York, 1998.

S. Mac Lane, I. Moerdijk. Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Springer, New York, 1992.

G. N. Raney. Completely distributive complete lattices. Proceedings of the American Mathematical Society 3(5): 677-680, 1952.

K. I. Rosenthal. The Theory of Quantaloids. Volume 348 of Pitman Research Notes in Mathematics Series. Longman, Harlow, 1996.

L. Shen. Adjunctions in Quantaloid-enriched Categories. PhD thesis, Sichuan University, Chengdu, 2014. arXiv:1408.0321.

L. Shen, D. Zhang. Categories enriched over a quantaloid: Isbell adjunctions and Kan adjunctions. Theory and Applications of Categories 28(20): 577-615, 2013.

L. Shen, D. Zhang. Formal concept analysis on fuzzy sets. In: Proceedings of the IFSA World Congress and NAFIPS Annual Meeting (IFSA/NAFIPS), 2013 Joint, pages 215-219, IEEE Conference Publications, 2013.

R. H. Street. Cauchy characterization of enriched categories. Rendiconti del Seminario Matemático e Fisico di Milano 51: 217-233, 1981.

R. H. Street. Enriched categories and cohomology. Proceedings of the Symposium on Categorical Algebra and Topology (Cape Town, 1981). Quaestiones Mathematicae 6: 265-283, 1983.

I. Stubbe. Categorical structures enriched in a quantaloid: categories, distributors and functors. Theory and Applications of Categories 14(1): 1-45, 2005.

I. Stubbe. Categorical structures enriched in a quantaloid: tensored and cotensored categories. Theory and Applications of Categories 16(14): 283-306, 2006.

I. Stubbe. Towards “dynamic domains”: totally continuous cocomplete Q-categories. Theoretical Computer Science 373: 142-160, 2007.

I. Stubbe. The double power monad is the composite power monad. Preprint, 2013.

I. Stubbe. An introduction to quantaloid-enriched categories. Fuzzy Sets and Systems 256: 95-116, 2014.

R. F. C. Walters. Sheaves and Cauchy-complete categories. Cahiers de Topologie et Géométrie Différentielle Catégoriques 22: 283-286, 1981.

R. F. C. Walters. Sheaves on sites as Cauchy-complete categories. Journal of Pure and Applied Algebra 24: 95-102, 1982.

R. J. Wood. Ordered sets via adjunctions. In: Categorical Foundations, Volume 97 of Encyclopedia of Mathematics and its Applications, pages 5-47. Cambridge University Press, Cambridge, 2004.

L. A. Zadeh. Fuzzy sets. Information and Control 8: 338-353, 1965.

V. Zöberlein. Doctrines on 2-categories. Mathematische Zeitschrift 148(3): 267-279, 1976.

School of Mathematics, Sichuan University, Chengdu 610064, China

Email: puqiang0630@163.com, dxzhang@scu.edu.cn
This article may be accessed at http://www.tac.mta.ca/tac/

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 is 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, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr 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

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Radboud University Nijmegen: i.moerdijk@math.ru.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Edinburgh: Alex.Simpson@ed.ac.uk James Stasheff, University of North Carolina: jds@math.upenn.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 R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca