Theory and Applications of Categories, Vol. 25, No. 11, 2011, pp. 276–294.

SYMMETRY AND CAUCHY COMPLETION OF QUANTALOID-ENRICHED CATEGORIES

HANS HEYMANS AND ISAR STUBBE

Abstract. We formulate an elementary condition on an involutive quantaloid Q under which there is a distributive law from the Cauchy completion monad over the symmetrisation comonad on the category of Q-enriched categories. For such quantaloids, which we call Cauchy-bilateral quantaloids, it follows that the Cauchy completion of any symmetric Q-enriched category is again symmetric. Examples include Lawvere’s quantale of non-negative real numbers and Walters’ small quantaloids of closed cribles.

1. Introduction

A quantaloid Q is a category enriched in the symmetric monoidal closed category Sup of complete lattices and supremum-preserving functions. Viewing Q as a bicategory, it is natural to study categories, functors and distributors enriched in Q. If Q comes equipped with an involution, it makes sense to consider symmetric Q-enriched categories. An important application of quantaloid-enriched categories was discovered by R.F.C. Walters [1981, 1982]: he proved that the topos of sheaves on a small site (C, J) is equivalent to the category of symmetric and Cauchy complete categories enriched in a suitable “small quantaloid of closed cribles” R(C, J). A decade earlier, F.W. Lawvere [1973] had already pointed out that the category of generalised metric spaces and non-expansive maps is equivalent to the category of categories enriched in the quantale (that is, a one-object quantaloid) ([0, ∞], ⋀, +, 0) of extended non-negative real numbers. This is a symmetric quantale, hence it is trivially involutive; and here too the symmetric and Cauchy complete [0, ∞]-enriched categories are important, if only to connect with the classical theory of metric spaces. Crucial in both examples is thus the use of categories enriched in an involutive quantaloid Q which are both symmetric and Cauchy complete. R. Betti and R.F.C. Walters [1982] therefore raised the question “whether the Cauchy completion of a symmetric [quantaloid-enriched] category is again symmetric”. That is to say, they ask whether it is possible to restrict the Cauchy completion functor (−)_{cc}: Cat(Q) [figure] Cat(Q) along the embedding SymCat(Q) [figure] Cat(Q) of symmetric Q-categories. They show that the answer to their question is affirmative for both R(C, J) and [0, ∞], by giving an ad hoc proof in each case; they also give an example of an involutive quantale for which the answer to their question is negative. Thus, it depends on the base quantaloid Q whether or not the Cauchy completion of a symmetric Q-category is again symmetric.

Received by the editors 2010-05-04 and, in revised form, 2011-06-23.

Transmitted by R. F. C. Walters. Published on 2011-06-25.

2000 Mathematics Subject Classification: 06F07, 18C15, 18D05, 18D20.

Key words and phrases: Quantaloid, enriched category, symmetry, Cauchy completion.

\begin{matrix}c \\ ◯ \end{matrix} Hans Heymans and Isar Stubbe, 2011. Permission to copy for private use granted.

In this paper we address this issue in a slightly different manner to produce a single, simple argument for both Walters’ small quantaloids of closed cribles and Lawvere’s quantale of non-negative real numbers, thus giving perhaps a more decisive answer to Betti and Walters’ question. The embedding SymCat(Q) [figure] Cat(Q) has a right adjoint (−)_{s}: Cat(Q) [figure] SymCat(Q), which we call ‘symmetrisation’. We aim to extend the Cauchy completion functor along the symmetrisation functor. To wit, we define an obvious ‘symmetric completion’ (−)_{sc}: SymCat(Q) [figure] SymCat(Q) (Proposition 3.3) which, by construction, comes with a natural transformation

[figure: Cat(Q); (−)_{cc}; Cat(Q); SymCat(Q); (−)_{sc}; incl.; SymCat(Q); incl.; K; ⟹]

whose components K_{𝔸}: 𝔸_{sc} [figure] 𝔸_{cc} are full embeddings. Considering its mate

[figure: Cat(Q); (−)_{cc}; (−)_{s}; Cat(Q); (−)_{s}; SymCat(Q); (−)_{sc}; SymCat(Q); L; ⟹]

we formulate an elementary necessary-and-sufficient condition on Q under which L is a natural isomorphism (Theorem 3.7); in that case, we say that Q is a Cauchy-bilateral quantaloid (Definition 3.8). If Q is Cauchy-bilateral, then K is in fact the identity transformation, thus in particular is the Cauchy completion of any symmetric Q-category again symmetric. And moreover, as a corollary, we obtain a distributive law of the Cauchy completion monad over the symmetrisation comonad on Cat(Q) (Corollary 3.9). In a separate section we point out a number of examples, including Walters’ small quantaloids of closed cribles and Lawvere’s quantale of non-negative real numbers.

For an overview of the theory of quantaloid-enriched categories, and a list of appropriate historical references, we refer to [Stubbe, 2005], whose notations we adopt.

2. Symmetric quantaloid-enriched categories

In this section, after quickly recalling the notion of involutive quantaloid Q, we give the obvious definition of symmetric Q-category and explain how any Q-category can be symmetrised. Examples are postponed to Section 4.

2.1. Definition. A quantaloid is a Sup-enriched category. An involution on a quantaloid Q is a Sup-functor (−)^{o}: Q^{op} [figure] Q which is the identity on objects and satisfies f^{oo} = f for any morphism f in Q. The pair (Q, (−)^{o}) is then said to form an involutive quantaloid.

We shall often simply speak of “an involutive quantaloid Q”, leaving the notation for the involution understood. Note that the above definition is equivalent to an apparently weaker condition: in fact, any function f ↦ f^{o} on the morphisms of a quantaloid Q such that f ≤ g implies f^{o} ≤ g^{o}, (g ∘ f)^{o} = f^{o} ∘ g^{o}, and f^{oo} = f, is an involution. It is furthermore clear that an involution is an isomorphism between Q and Q^{op}.

Whenever a morphism f: A [figure] B in a quantaloid (or in a locally ordered category, for that matter) is supposed to be a left adjoint, we write f^{∗} for its right adjoint. In many examples there is a big difference between the involute f^{o} and the adjoint f^{∗} of a given morphism f, so morphisms for which involute and adjoint coincide, deserve a name:

2.2. Definition. In a quantaloid Q with involution f ↦ f^{o}, an o-symmetric left adjoint (or simply symmetric left adjoint if the context makes the involution clear) is a left adjoint whose right adjoint is its involute.

Precisely as we write Map(Q) for the category of left adjoints in Q (this notation being motivated by the widespread use of the word “map” synonymously with “left adjoint”), we shall write SymMap(Q) for the category of symmetric left adjoints.

Recall that a category 𝔸 enriched in a quantaloid Q consists of a set 𝔸_{0} of objects, each x ∈ 𝔸_{0} having a type ta ∈ Q_{0}, and for any x, y ∈ 𝔸_{0} there is a hom-arrow 𝔸(y, x): tx [figure] ty in Q, subject to associativity and unit requirements: 𝔸(z, y) ∘ 𝔸(y, x) ≤ 𝔸(z, x) and 1_{tx} ≤ 𝔸(x, x) for all x, y, z ∈ 𝔸_{0}. A functor F: 𝔸 [figure] 𝔹 between such Q-categories is an object-map x ↦ F x such that tx = t(F x) and 𝔸(y, x) ≤ 𝔹(F y, F x) for all x, y ∈ 𝔸. Such a functor is smaller than a functor G: 𝔸 [figure] 𝔹 if 1_{tx} ≤ 𝔹(F x, Gx) for every x ∈ 𝔸. With obvious composition one gets a locally ordered 2-category Cat(Q) of Q-categories and functors.

For two objects x, y ∈ 𝔸, the hom-arrows 𝔸(y, x) and 𝔸(x, y) thus go in opposite directions. Hence, to formulate a notion of “symmetry” for Q-categories, it is far too strong to require 𝔸(y, x) = 𝔸(x, y). Instead, at least for involutive quantaloids, we better do as follows [Betti and Walters, 1982]:

2.3. Definition. Let Q be a small involutive quantaloid, with involution f ↦ f^{o}. A Q-category 𝔸 is o-symmetric (or symmetric if there is no confusion about the involved involution) when 𝔸(x, y) = 𝔸(y, x)^{o} for every two objects x, y ∈ 𝔸.

We shall write SymCat(Q) for the full sub-2-category of Cat(Q) determined by the symmetric Q-categories; it is easy to see that the local order in SymCat(Q) is in fact symmetric (but not anti-symmetric). The full embedding SymCat(Q) ↪ Cat(Q) has a right adjoint functor^{1}:

SymCat(Q) [figure: ⊥; incl.; (−)_{s}]Cat(Q).  (1)

This ‘symmetrisation’ sends a Q-category 𝔸 to the symmetric Q-category 𝔸_{s} whose objects (and types) are those of 𝔸, but for any two objects x, y the hom-arrow is

𝔸_{s}(y, x) := 𝔸(y, x) ∧ 𝔸(x, y)^{o}.

A functor F: 𝔸 [figure] 𝔹 is sent to F_{s}: 𝔸_{s} [figure] 𝔹_{s}: a ↦ F a. Quite obviously, the counit of this adjunction has components S_{𝔸}: 𝔸_{s} [figure] 𝔸: a ↦ a.

Recall that a distributor Φ: 𝔸 [figure] 𝔹 between Q-categories consists of a family arrows Φ(y, x): tx [figure] ty in Q, one for each (x, y) ∈ 𝔸_{0} ×𝔹_{0}, subject to 𝔹(y′, y)∘Φ(y, x) ≤ Φ(y′, x) and Φ(y, x) ∘ 𝔸(x, x′) ≤ Φ(y, x′) for all y, y′ ∈ 𝔹_{0} and x, x′ ∈ 𝔸_{0}. The composite of such a distributor with another Ψ: 𝔹 [figure] ℂ is written as Ψ ⊗ Φ: 𝔸 [figure] ℂ, and its elements are computed with a “matrix formula”: for x ∈ 𝔸_{0} and z ∈ ℂ_{0},

(Ψ ⊗ Φ)(z, x) = ⋁_{y∈𝔹_{0}} Ψ(z, y) ∘ Φ(y, x).

Parallel distributors can be compared elementwise, and in fact one gets a (large) quantaloid Dist(Q) of Q-categories and distributors. Each functor F: 𝔸 [figure] 𝔹 determines an adjoint pair of distributors: 𝔹(−, F −): 𝔸 [figure] 𝔹, with elements 𝔹(y, F x) for (x, y) ∈ 𝔸_{0} × 𝔹_{0}, is left adjoint to 𝔹(F −, −): 𝔹 [figure] 𝔸 in the quantaloid Dist(Q). These distributors are said to be ‘represented by F ’. (More generally, a (necessarily left adjoint) distributor Φ: 𝔸 [figure] 𝔹 is ‘representable’ if there exists a (necessarily essentially unique) functor F: 𝔸 [figure] 𝔹 such that Φ = 𝔹(−, F −).) This amounts to a 2-functor

Cat(Q) [figure] Map(Dist(Q)): (F: 𝔸 [figure] 𝔹) ↦ (𝔹(−, F −): 𝔸 [figure] 𝔹).  (2)

We shall write SymDist(Q) for the full subquantaloid of Dist(Q) determined by the symmetric Q-categories. It is easily verified that the involution f ↦ f^{o} on the base quantaloid Q extends to the quantaloid SymDist(Q): explicitly, if Φ: 𝔸 [figure] 𝔹 is a distributor between symmetric Q-categories, then so is Φ^{o}: 𝔹 [figure] 𝔸, with elements Φ^{o}(a, b) := Φ(b, a)^{o}. And if F: 𝔸 [figure] 𝔹 is a functor between symmetric Q-categories, then the left adjoint distributor represented by F has the particular feature that it is a symmetric left adjoint in SymDist(Q) (in the sense of Definition 2.2). That is to say, the functor in (2) restricts to the symmetric situation as

SymCat(Q) [figure] SymMap(SymDist(Q)): (F: 𝔸 [figure] 𝔹) ↦ (𝔹(−, F −): 𝔸 [figure] 𝔹), (3)

1But the right adjoint is not a 2-functor, for this would imply the local order in Cat(Q) to be symmetric, so this is not a 2-adjunction.

obviously giving a commutative diagram

[figure: Cat(Q); Map(Dist(Q)); SymCat(Q); incl.; SymMap(SymDist(Q)); incl.]  (4)

3. Cauchy completion and symmetric completion

A Q-category 𝔸 is said to be ‘Cauchy complete’ when each left adjoint distributor with codomain 𝔸 is represented by a functor [Lawvere, 1973], that is, when for each Q-category 𝔹 the functor in (2) determines an equivalence

Cat(Q)(𝔹, 𝔸) ≃ Map(Dist(Q))(𝔹, 𝔸).

It is equivalent to require this only for left adjoint presheaves^{2} on 𝔸. The full inclusion of the Cauchy complete Q-categories in Cat(Q) admits a left adjoint:

Cat_{cc}(Q) [figure: ⊥; full incl.; (−)_{cc}]Cat(Q).  (5)

That is to say, each Q-category 𝔸 has a Cauchy completion 𝔸_{cc}, which can be computed explicitly as follows: objects are the left adjoint presheaves on 𝔸, the type of such a left adjoint ϕ: ∗_{X} [figure] 𝔸 is X ∈ Q, and for another such ψ: ∗_{Y} [figure] 𝔸 the hom-arrow 𝔸_{cc}(ψ, ϕ): X [figure] Y in Q is the single element of the composite distributor ψ^{∗} ⊗ ϕ (where ψ ⊣ ψ^{∗}). The component at 𝔸 ∈ Cat(Q) of the unit of this adjunction is a suitable corestriction of the Yoneda embedding: Y_{𝔸}: 𝔸 [figure] 𝔸_{cc}: x ↦ 𝔸(−, x). It is straightforward that (−)_{cc}: Cat(Q) [figure] Cat(Q) sends a functor F: 𝔸 [figure] 𝔹 to F_{cc}: 𝔸_{cc} [figure] 𝔹_{cc}: ϕ ↦ 𝔹(−, F −) ⊗ ϕ. (For details, see e.g. [Stubbe, 2005, Section 7].)

The Cauchy completion can of course be applied to a symmetric Q-category, but the resulting Cauchy complete category need not be symmetric anymore (see Example 4.7)! That is to say, the functor (−)_{cc}: Cat(Q) [figure] Cat(Q) does not restrict to SymCat(Q) in general. However, its very definition suggests the following modification:

3.1. Definition. Let Q be a small involutive quantaloid. A symmetric Q-category 𝔸 is symmetrically complete if, for any symmetric Q-category 𝔹, the functor in (3) determines an equivalence

SymCat(Q)(𝔹, 𝔸) ≃ SymMap(SymDist(Q))(𝔹, 𝔸).

2A ‘presheaf’ on 𝔸 is a distributor into 𝔸 whose domain is a one-object category with an identity hom-arrow. Writing ∗_{X} for the one-object Q-category whose single object ∗ has type X ∈ Q_{0} and whose single hom-arrow is the identity 1_{X}, a presheaf is then typically written as ϕ: ∗_{X} [figure] 𝔸. (These are really the contravariant presheaves on 𝔸; the covariant presheaves are the distributors from 𝔸 to ∗_{X}. In this paper, however, we shall only consider contravariant presheaves.)

In analogy with the notion of Cauchy completeness of a Q-category, it is straightforward to check the following equivalent expressions:

3.2. Proposition. Let Q be a small involutive quantaloid. For a symmetric Q-category 𝔸, the following conditions are equivalent:

1. 𝔸 is symmetrically complete,

2. for any symmetric Q-category 𝔹, every symmetric left adjoint distributor Φ: 𝔹 [figure] 𝔸 is representable,

3. for any X ∈ Q, every symmetric left adjoint presheaf ϕ: ∗_{X} [figure] 𝔸 is representable.

And precisely as the Cauchy completion of a Q-category can be computed explicitly with left adjoint presheaves, we can do as follows for the symmetric completion of a symmetric Q-category:

3.3. Proposition. Let Q be a small involutive quantaloid. The full embedding of the symmetrically complete symmetric Q-categories in SymCat(Q) admits a left adjoint:

SymCat_{sc}(Q) [figure: ⊥; full incl.; (−)_{sc}]SymCat(Q).  (6)

Explicitly, for a symmetric Q-category 𝔸, its symmetric completion 𝔸_{sc} is the full subcategory of 𝔸_{cc} determined by the symmetric left adjoint presheaves. The component at 𝔸 ∈ SymCat(Q) of the unit of this adjunction is a corestriction of the Yoneda embedding: Y_{𝔸}: 𝔸 [figure] 𝔸_{sc}: x ↦ 𝔸(−, x).

Note that (−)_{sc}: SymCat(Q) [figure] SymCat(Q) sends a functor F: 𝔸 [figure] 𝔹 between symmetric Q-categories to F_{sc}: 𝔸_{sc} [figure] 𝔹_{sc}: ϕ ↦ 𝔹(−, F −) ⊗ ϕ. Indeed, because 𝔹 is symmetric, the distributor 𝔹(−, F −) is a symmetric left adjoint, hence its composition with ϕ ∈ 𝔸_{sc} gives an object of 𝔹_{sc}.

All this now raises a natural question: given any Q-category 𝔸, how does the symmetrisation of its Cauchy completion relate to the symmetric completion of its symmetrisation? It is clear that there is a natural transformation

[figure: Cat(Q); (−)_{cc}; Cat(Q); SymCat(Q); (−)_{sc}; incl.; SymCat(Q); incl.; K; ⟹]  (7)

whose components are the full embeddings K_{𝔸}: 𝔸_{sc} [figure] 𝔸_{cc}: ϕ ↦ ϕ of which the construction, in Proposition 3.3, of the symmetric completion speaks. From the calculus of mates [Kelly and Street, 1974] at least part of the following statement is then straightforward:

3.4. Proposition. Let Q be an involutive quantaloid. There is a natural transformation

[figure: Cat(Q); (−)_{cc}; (−)_{s}; Cat(Q); (−)_{s}; SymCat(Q); (−)_{sc}; SymCat(Q); L; ⟹]  (8)

whose component at 𝔸 in Cat(Q) is the full embedding^{3}

L_{𝔸}: (𝔸_{s})_{sc} [figure] (𝔸_{cc})_{s}: ϕ ↦ 𝔸(−, S_{𝔸}−) ⊗ ϕ.

Moreover, each (𝔸_{cc})_{s} is symmetrically complete.

Proof. It is straightforward to check that the explicit definition of L is indeed obtained as the mate of the natural transformation in diagram (7).

Given ϕ, ψ ∈ (𝔸_{s})_{sc}, consider the distributors

[figure: ∗_{X}; ϕ; 𝔸_{s}; 𝔸(−, S_{𝔸}−); 𝔸_{s}; ψ^{o}; ∗_{Y}; 𝔸; 𝔸(S_{𝔸}−, −)]

of which we know that 𝔸_{s} = 𝔸(S_{𝔸}−, S_{𝔸}−) ∧ 𝔸(S_{𝔸}−, S_{𝔸}−)^{o}, and compute that

ψ^{o} ⊗ ϕ = ψ^{o} ⊗ 𝔸_{s} ⊗ ϕ
= ψ^{o} ⊗ (𝔸(S_{𝔸}−, S_{𝔸}−) ∧ 𝔸(S_{𝔸}−, S_{𝔸}−)^{o}) ⊗ ϕ
= (ψ^{o} ⊗ 𝔸(S_{𝔸}−, S_{𝔸}−) ⊗ ϕ) ∧ (ψ^{o} ⊗ 𝔸(S_{𝔸}−, S_{𝔸}−)^{o} ⊗ ϕ)
= (ψ^{o} ⊗ 𝔸(S_{𝔸}−, S_{𝔸}−) ⊗ ϕ) ∧ (ϕ^{o} ⊗ 𝔸(S_{𝔸}−, S_{𝔸}−) ⊗ ψ)^{o}
= (ψ^{o} ⊗ 𝔸(S_{𝔸}−, −) ⊗ 𝔸(−, S_{𝔸}−) ⊗ ϕ) ∧ (ϕ^{o} ⊗ 𝔸(S_{𝔸}−, −) ⊗ 𝔸(−, S_{𝔸}−) ⊗ ψ)^{o}
= (L_{𝔸}(ψ)^{∗} ⊗ L_{𝔸}(ϕ)) ∧ (L_{𝔸}(ϕ)^{∗} ⊗ L_{𝔸}(ψ))^{o}

which asserts precisely the fully faithfulness of L_{𝔸}. (To pass from the second to the third line, we use that ψ^{o} ⊗ − ⊗ ϕ preserves infima, due to ψ ⊣ ψ^{o} and ϕ ⊣ ϕ^{o}. From the third to the fourth line we use the involution on SymDist(Q) provided by the involution on Q. And from line four to line five we use that 𝔸(S_{𝔸}−, S_{𝔸}−) = 𝔸(S_{𝔸}−, −) ⊗ 𝔸(−, S_{𝔸}−).)

3Recall that S_{𝔸}: 𝔸_{s} [figure] 𝔸: a ↦ a is the counit of the adjunction in diagram (1). Trivial as it may seem, it plays a crucial role throughout this section.

For any a ∈ (𝔸_{s})_{0} it is straightforward that L_{𝔸}(𝔸_{s}(−, a)) = 𝔸(−, S_{𝔸}a). Putting ψ = 𝔸_{s}(−, a) in the previous calculation, we thus find for any ϕ ∈ (𝔸_{s})_{sc} that

𝔸_{s}(a, −) ⊗ ϕ = (𝔸(S_{𝔸}a, −) ⊗ L_{𝔸}(ϕ)) ∧ (L_{𝔸}(ϕ)^{∗} ⊗ 𝔸(−, S_{𝔸}a))^{o}.

Letting a vary in 𝔸_{s}, this shows that

ϕ = (𝔸(S_{𝔸}−, −) ⊗ L_{𝔸}(ϕ)) ∧ (L_{𝔸}(ϕ)^{∗} ⊗ 𝔸(−, S_{𝔸}−))^{o}  (9)

which implies that L_{𝔸} is injective on objects.

As for the final part of the proposition, suppose that ℂ is a Cauchy complete Qcategory and that ϕ: ∗_{X} [figure] ℂ_{s} is a symmetric left adjoint. Then there exists a c ∈ ℂ_{0} such that L_{ℂ}(ϕ) = ℂ(−, c) and we use the formula in (9) to compute that

ϕ = (ℂ(S_{ℂ}−, −)⊗L_{ℂ}(ϕ))∧(L_{ℂ}(ϕ)^{∗}⊗ℂ(−, S_{ℂ}−))^{o} = ℂ(S_{ℂ}−, c)∧ℂ(c, S_{ℂ}−)^{o} = ℂ_{s}(−, c).

Therefore ℂ_{s} is symmetrically complete. This of course applies to 𝔸_{cc}. □

Whereas the previous proposition establishes a comparison between (𝔸_{s})_{sc} and (𝔸_{cc})_{s}, we shall now study when these two constructions coincide. This is related with the symmetrisation not only of Q-categories and functors, but also of left adjoint distributors. We start by putting the formula in (9) in a broader context:

3.5. Lemma. If Ψ: 𝔸 [figure] 𝔹 is a left adjoint distributor between categories enriched in a small involutive quantaloid Q, then the distributor

Ψ_{s} := (𝔹(S_{𝔹}−, −) ⊗ Ψ ⊗ 𝔸(−, S_{𝔸}−)) ∧ (𝔸(S_{𝔸}−, −) ⊗ Ψ^{∗} ⊗ 𝔹(−, S_{𝔹}−))^{o}: 𝔸_{s} [figure] 𝔹_{s}

satisfies Ψ_{s}⊗(Ψ_{s})^{o} ≤ 𝔹_{s}. Thus Ψ_{s} is a symmetric left adjoint if and only if 𝔸_{s} ≤ (Ψ_{s})^{o}⊗Ψ_{s}, and if this is the case then it follows that Ψ = 𝔹(−, S_{𝔹}−) ⊗ Ψ_{s} ⊗ 𝔸(S_{𝔸}−, −).

Proof. It is clear that Ψ_{s}: 𝔸_{s} [figure] 𝔹_{s} is a distributor: it is the infimum of two distributors, the first term of which is a composite of three distributors, and the second term is the involute of a composite of three distributors (which makes sense because domain and codomain of this composite are symmetric Q-categories). Precisely because Ψ_{s} is a distributor between symmetric Q-categories, it makes sense to speak of its involute (Ψ_{s})^{o}, and it is straightforward to compute that

Ψ_{s} ⊗ (Ψ_{s})^{o} ≤ (𝔹(S_{𝔹}−, −) ⊗ Ψ ⊗ 𝔸(−, S_{𝔸}−)) ⊗ (𝔸(S_{𝔸}−, −) ⊗ Ψ^{∗} ⊗ 𝔹(−, S_{𝔹}−))^{oo}
≤ 𝔹(S_{𝔹}−, −) ⊗ Ψ ⊗ 𝔸(−, −) ⊗ Ψ^{∗} ⊗ 𝔹(−, S_{𝔹}−)
≤ 𝔹(S_{𝔹}−, −) ⊗ 𝔹(−, −) ⊗ 𝔹(−, S_{𝔹}−)
= 𝔹(S_{𝔹}−, S_{𝔹}−)

and therefore, by involution, also Ψ_{s} ⊗ (Ψ_{s})^{o} ≤ 𝔹(S_{𝔹}−, S_{𝔹}−)^{o} holds, from which we can conclude that Ψ_{s} ⊗ (Ψ_{s})^{o} ≤ 𝔹(S_{𝔹}−, S_{𝔹}−) ∧ 𝔹(S_{𝔹}−, S_{𝔹}−)^{o} = 𝔹_{s}(−, −) as claimed.

Now Ψ_{s} is a symmetric left adjoint if and only if Ψ_{s} ⊣ (Ψ_{s})^{o}, and because the counit inequality of this adjunction always holds, this adjunction is equivalent to the truth of the unit inequality 𝔸_{s} ≤ (Ψ_{s})^{o} ⊗ Ψ_{s}. Suppose that this is indeed the case, then we can compute that

Ψ = Ψ ⊗ 𝔸(−, S_{𝔸}−) ⊗ 𝔸_{s}(−, −) ⊗ 𝔸(S_{𝔸}−, −)
≤ Ψ ⊗ 𝔸(−, S_{𝔸}−) ⊗ (Ψ_{s})^{o} ⊗ Ψ_{s} ⊗ 𝔸(S_{𝔸}−, −)
≤ Ψ ⊗ 𝔸(−, S_{𝔸}−) ⊗ (𝔸(S_{𝔸}−, −) ⊗ Ψ^{∗} ⊗ 𝔹(−, S_{𝔹}−))^{oo} ⊗ Ψ_{s} ⊗ 𝔸(S_{𝔸}−, −)
≤ Ψ ⊗ 𝔸(−, −) ⊗ Ψ^{∗} ⊗ 𝔹(−, S_{𝔹}−) ⊗ Ψ_{s} ⊗ 𝔸(S_{𝔸}−, −)
≤ 𝔹 ⊗ 𝔹(−, S_{𝔹}−) ⊗ Ψ_{s} ⊗ 𝔸(S_{𝔸}−, −)
≤ 𝔹(−, S_{𝔹}−) ⊗ (𝔹(S_{𝔹}−, −) ⊗ Ψ ⊗ 𝔸(−, S_{𝔸}−)) ⊗ 𝔸(S_{𝔸}−, −)
≤ 𝔹(−, −) ⊗ Ψ ⊗ 𝔸(−, −)
= Ψ

which means that Ψ = 𝔹(−, S_{𝔹}−) ⊗ Ψ_{s} ⊗ 𝔸(S_{𝔸}−, −) as claimed. □

The notation introduced in the previous lemma will be used in the remainder of this section. In particular shall we use it in the next proposition.

3.6. Proposition. For a category 𝔸 enriched in a small involutive quantaloid Q, the following conditions are equivalent:

1. the functor L_{𝔸}: (𝔸_{s})_{sc} [figure] (𝔸_{cc})_{s} from Proposition 3.4 is surjective on objects (and therefore an isomorphism, with inverse ψ ↦ ψ_{s}),

2. for every left adjoint presheaf ψ: ∗_{X} [figure] 𝔸, the presheaf ψ_{s}: ∗_{X} [figure] 𝔸_{s} is a symmetric left adjoint,

3. for every left adjoint distributor Ψ: 𝕏 [figure] 𝔸, the distributor Ψ_{s}: 𝕏_{s} [figure] 𝔸_{s} is a symmetric left adjoint.

Proof. (1 ⇔ 2) From (the proof of) Proposition 3.4 we know that L_{𝔸} is injective on objects, and that ϕ = (L_{𝔸}(ϕ))_{s} for any symmetric left adjoint ϕ: ∗_{X} [figure] 𝔸_{s} (this is the formula in (9) rewritten with the notation introduced in Lemma 3.5, taking into account that the domain of ϕ is the symmetric Q-category ∗_{X}, so that S_{∗_{X}} is the identity on ∗_{X}). To say that L_{𝔸} is surjective on objects thus means that for any left adjoint ψ: ∗_{X} [figure] 𝔸 there exists a (necessarily unique) symmetric left adjoint ϕ: ∗_{X} [figure] 𝔸_{s} such that L_{𝔸}(ϕ) = ψ. Thus indeed ψ_{s} = ϕ is a symmetric left adjoint. Conversely, if we assume that for every left adjoint presheaf ψ: ∗_{X} [figure] 𝔸 the presheaf ψ_{s}: ∗_{X} [figure] 𝔸_{s} is a symmetric left adjoint, then Lemma 3.5 implies L(ψ_{s}) = ψ so that L_{𝔸} is surjective on objects.

(3 ⇔ 2) One implication is trivial. For the other, by Lemma 3.5 we only need to prove that

𝕏_{s}(y, x) ≤ (Ψ_{s})^{o}(y, −) ⊗ Ψ_{s}(−, x)

for every left adjoint Ψ: 𝕏 [figure] 𝔸 and every x, y ∈ (𝕏_{s})_{0}. But for every x ∈ 𝕏_{0} we have a left adjoint presheaf Ψ(−, x): ∗_{tx} [figure] 𝔸 and by hypothesis thus also a symmetric left adjoint presheaf Ψ(−, x)_{s}: ∗_{tx} [figure] 𝔸_{s}. Because Ψ(−, x)_{s} = Ψ_{s}(−, x) and (Ψ_{s})^{o}(y, −) = (Ψ_{s}(−, y))^{o} = (Ψ(−, y)_{s})^{o}, the sought-after inequation is equivalent to

𝕏_{s}(y, x) ≤ (Ψ(−, y)_{s})^{o} ⊗ Ψ(−, x)_{s}.

Using the adjunction Ψ(−, x)_{s} ⊣ (Ψ(−, x)_{s})^{o} this is in turn equivalent to

𝕏_{s}(y, x) ⊗ (Ψ(−, x)_{s})^{o} ≤ (Ψ(−, y)_{s})^{o}

which is an instance of the action inequality 𝕏_{s} ⊗ (Ψ_{s})^{o} ≤ (Ψ_{s})^{o} for (Ψ_{s})^{o}: 𝔸_{s} [figure] 𝕏_{s}. □

Now we have everything in place to prove our main theorem, establishing in particular an elementary necessary-and-sufficient condition on the base quantaloid Q under which (𝔸_{s})_{sc} ≅ (𝔸_{cc})_{s} holds for every Q-category 𝔸.

3.7. Theorem. For a small involutive quantaloid Q, the following conditions are equivalent:

1. each functor L_{𝔸}: (𝔸_{s})_{sc} [figure] (𝔸_{cc})_{s} as in Proposition 3.4 is an isomorphism (making diagram (8) commute up to isomorphism),

2. for every left adjoint presheaf ψ: ∗_{X} [figure] 𝔸, the presheaf ψ_{s}: ∗_{X} [figure] 𝔸_{s} is a symmetric left adjoint,

3. for each left adjoint distributor Ψ: 𝔸 [figure] 𝔹, the distributor Ψ_{s}: 𝔸_{s} [figure] 𝔹_{s} is a symmetric left adjoint,

4. the inclusion SymMap(SymDist(Q)) [figure] Map(Dist(Q)) admits a right adjoint making the following square commute:

[figure: Cat(Q); (−)_{s}; Map(Dist(Q)); SymCat(Q); SymMap(SymDist(Q))]

5. for each family (f_{i}: X [figure] X_{i}, g_{i}: X_{i} [figure] X)_{i∈I} of morphisms in Q,

\begin{matrix}∀j, k ∈ I : f_{k} ∘ g_{j} ∘ f_{j} ≤ f_{k} \\ ∀j, k ∈ I : g_{j} ∘ f_{j} ∘ g_{k} ≤ g_{k} \\ 1_{X} ≤ ⋁_{i∈I} g_{i} ∘ f_{i} \end{matrix} \} ⟹ 1_{X} ≤ ⋁_{i∈I}(g_{i} ∧ f_{i}^{o}) ∘ (g_{i}^{o} ∧ f_{i}).

In fact, the right adjoint of which the fourth statement speaks, is

(−)_{s}: Map(Dist(Q)) [figure] SymMap(SymDist(Q)): (Ψ: 𝔸 [figure] 𝔹) ↦ (Ψ_{s}: 𝔸_{s} [figure] 𝔹_{s}). (10)

Proof. (1 ⇔ 2 ⇔ 3) Are taken care of in Proposition 3.6.

(3 ⇒ 4) With the help of Lemma 3.5, it can be checked that the left adjoint distributor ℂ(−, S_{ℂ}−): ℂ_{s} [figure] ℂ displays ℂ_{s} as the coreflection of a Q-category ℂ along the inclusion SymMap(SymDist(Q)) [figure] Map(Dist(Q)): if 𝔸 is a symmetric Q-category and Ψ: 𝔸 [figure] ℂ is a left adjoint distributor, then by assumption we have that Ψ_{s}: 𝔸 [figure] ℂ_{s} is a symmetric left adjoint distributor such that Ψ = ℂ(−, S_{ℂ}−) ⊗ Ψ_{s}; and if Φ: 𝔸 [figure] ℂ_{s} would be another symmetric left adjoint distributor such that Ψ = ℂ(−, S_{ℂ}−) ⊗ Φ (and therefore also Ψ^{∗} = Φ^{o} ⊗ ℂ(S_{ℂ}−, −)), then necessarily

Ψ_{s} = (ℂ(S_{ℂ}−, −) ⊗ Ψ) ∧ (Ψ^{∗} ⊗ ℂ(−, S_{ℂ}−))^{o}
= (ℂ(S_{ℂ}−, −) ⊗ ℂ(−, S_{ℂ}−) ⊗ Φ) ∧ (Φ^{o} ⊗ ℂ(S_{ℂ}−, −) ⊗ ℂ(−, S_{ℂ}−))^{o}
= (ℂ(S_{ℂ}−, S_{ℂ}−) ⊗ Φ) ∧ (ℂ(S_{ℂ}−, S_{ℂ}−)^{o} ⊗ Φ)
= (ℂ(S_{ℂ}−, S_{ℂ}−) ∧ ℂ(S_{ℂ}−, S_{ℂ}−)^{o}) ⊗ Φ
= ℂ_{s} ⊗ Φ
= Φ

(To pass from the third to the fourth line we use that − ⊗ Φ preserves infima because Φ is a left adjoint.) By general theory for adjoint functors, these coreflections ℂ(−, S_{ℂ}−): ℂ_{s} [figure] ℂ determine the right adjoint, which is the functor given in (10).

(4 ⇒ 1) Suppose that G: SymMap(Dist(Q)) [figure] Map(Dist(Q)) is right adjoint to the inclusion and makes the square commute; thus G necessarily acts on objects as ℂ ↦ ℂ_{s}. Writing ε_{ℂ}: ℂ_{s} [figure] ℂ for the counit of the adjunction, G(ε_{ℂ}) is necessarily the identity distributor on ℂ_{s}. But on the other hand, by commutativity of the diagram, G also sends ℂ(−, S_{ℂ}−): ℂ_{s} [figure] ℂ to the identity distributor on ℂ_{s}. By general theory for adjoint functors, G(ε_{ℂ}) = G(ℂ(−, S_{ℂ}−)) implies ε_{ℂ} = ℂ(−, S_{ℂ}−). Thus ℂ(−, S_{ℂ}−): ℂ_{s} [figure] ℂ enjoys a universal property, saying in particular that: for every left adjoint ϕ: ∗_{X} [figure] ℂ there is a unique symmetric left adjoint ψ: ∗_{X} [figure] ℂ_{s} such that ℂ(−, S_{ℂ}−) ⊗ ψ = ϕ. In other words, L_{ℂ}: (ℂ_{s})_{sc} [figure] (ℂ_{cc})_{s}: ψ ↦ ℂ(−, S_{ℂ}−)⊗ψ is surjective on objects, and therefore an isomorphism.

(2 ⇒ 5) Putting 𝔸_{0} = I, ti = X_{i} and 𝔸(j, i) = f_{j} ∘ g_{j} ∨ δ_{ij} defines a Q-category 𝔸 (the “Kronecker delta” δ_{ij}: X_{i} [figure] X_{j} denotes the identity when i = j and the zero morphism otherwise), and putting ψ(i) = f_{i} defines a presheaf ψ: ∗_{X} [figure] 𝔸 with a right adjoint ψ^{∗}: 𝔸 [figure] ∗_{X} which is given by ψ^{∗}(i) = g_{i}. By hypothesis we infer that ψ_{s}: ∗_{X} [figure] 𝔸_{s} is a symmetric left adjoint. This means in particular that 1_{X} ≤ (ψ_{s})^{o} ⊗ ψ_{s}, or in other terms 1_{X} ≤ ⋁_{i}(f_{i}^{o} ∧ g_{i}) ∘ (f_{i} ∧ g_{i}^{o}), as wanted.

(5 ⇒ 2) If ψ: ∗_{X} [figure] 𝔸 is a left adjoint, the family (ψ(a): X [figure] ta, ψ^{∗}(a): ta [figure] X)_{a∈𝔸_{0}} of morphisms in Q is easily seen to satisfy the conditions in the hypothesis, thus

1_{X} ≤ ⋁_{a∈𝔸_{0}} (ψ(a)^{o} ∧ ψ^{∗}(a)) ∘ (ψ(a) ∧ ψ^{∗}(a))^{o}.

The right hand side is exactly ψ_{s}^{o} ⊗ ψ_{s} so this is equivalent to ψ_{s} ⊣ (ψ_{s})^{o} (cf. Lemma 3.5). □

For further reference, we give a name to those quantaloids (small or large) that satisfy the fifth condition in the above Theorem 3.7:

3.8. Definition. A quantaloid Q is Cauchy-bilateral if it is involutive (with involution f ↦ f^{o}) and for each family (f_{i}: X [figure] X_{i}, g_{i}: X_{i} [figure] X)_{i∈I} of morphisms in Q,

\begin{matrix}∀j, k ∈ I : f_{k} ∘ g_{j} ∘ f_{j} ≤ f_{k} \\ ∀j, k ∈ I : g_{j} ∘ f_{j} ∘ g_{k} ≤ g_{k} \\ 1_{X} ≤ ⋁_{i∈I} g_{i} ∘ f_{i} \end{matrix} \} ⟹ 1_{X} ≤ ⋁_{i∈I}(g_{i} ∧ f_{i}^{o}) ∘ (g_{i}^{o} ∧ f_{i}).

Thus, a small Cauchy-bilateral quantaloid Q is precisely one that satisfies the equivalent conditions in Theorem 3.7.

To finish this section we explain an important consequence of Theorem 3.7, containing an answer to R. Betti and R.F.C. Walters’ [1982] question about the symmetry of the Cauchy completion of a symmetric category:

3.9. Corollary. If Q is a small Cauchy-bilateral quantaloid, then the following diagrams commute:

[figure: Cat(Q); (−)_{cc}; Cat(Q); SymCat(Q); (−)_{cc}; incl.; SymCat(Q); incl.; Cat(Q); (−)_{s}; Cat(Q); Cat_{cc}(Q); (−)_{s}; incl.; Cat_{cc}(Q); incl.]

Proof. Suppose that the equivalent conditions in Theorem 3.7 hold. If ψ: ∗_{X} [figure] 𝔸 is a left adjoint presheaf on a symmetric Q-category, then ψ_{s}: ∗_{X} [figure] 𝔸 is a symmetric left adjoint presheaf which satisfies ψ = 𝔸(−, S_{𝔸}−) ⊗ ψ_{s} = ψ_{s} (by Lemma 3.5 and symmetry of 𝔸). So ψ is necessarily a symmetric left adjoint. Hence the full embedding 𝔸_{sc} ↪ 𝔸_{cc} is surjective-on-objects, or in other words, 𝔸_{sc} = 𝔸_{cc}. Therefore the Cauchy completion of a symmetric Q-category is symmetric, making the first square commute. Now suppose that ℂ is a Cauchy complete category. In (the proof of) Proposition 3.4 it was stipulated that ℂ_{s} is symmetrically complete, so – knowing now that the symmetric completion and the Cauchy completion of any symmetric Q-category coincide – it follows that ℂ_{s} is Cauchy complete too, making the second square commute. □

This corollary implies that, whenever a small Q is Cauchy-bilateral, there is a distributive law [Beck, 1969; Street, 1972; Power and Watanabe, 2002] of the Cauchy completion monad over the symmetrisation comonad on the category Cat(Q). More precisely, the reflective subcategory Cat_{cc}(Q) [figure] Cat(Q) is the category of algebras of a monad (T , μ, η) on Cat(Q); and similarly, the coreflective subcategory SymCat(Q) [figure] Cat(Q) is the category of coalgebras of a comonad (D, δ, ε) on Cat(Q). (The functors T and D are precisely (−)_{cc} and (−)_{s}, of course.) As shown in [Power and Watanabe, 2002, Theorems 3.10 and 5.10], the commutativity of the squares in Corollary 3.9 is equivalent to the existence of a natural transformation λ: T ∘ D [figure] D ∘ T making the following diagrams commute:

[figure: T T Dℂ; μ_{Dℂ}; T λ_{ℂ}; T Dℂ; λ_{ℂ}; T DT ℂ; λ_{T ℂ}; Dℂ; η_{Dℂ}; Dη_{ℂ}; DT T ℂ; Dμ_{ℂ}; DT ℂ; T Dℂ; T ε_{ℂ}; T δ_{ℂ}; λ_{ℂ}; T DDℂ; λ_{Dℂ}; T ℂ; DT Dℂ; Dλ_{ℂ}; DT ℂ; ε_{T ℂ}; δ_{T ℂ}; DDT ℂ]

This, in turn, says exactly that λ is a distributive law of the monad T over the comonad D [Power and Watanabe, 2002, Definition 6.1]. Because T and D arise from (co)reflective subcategories, there is at most one such distributive law; its components are necessarily

λ_{ℂ}: (ℂ_{s})_{cc} [figure] (ℂ_{cc})_{s}: ϕ ↦ ℂ(−, S_{ℂ}−) ⊗ ϕ.

(Thus λ_{ℂ} is precisely the functor L_{ℂ} of Proposition 3.4, reckoning that – under the conditions of Theorem 3.7 – the symmetric completion of a symmetric Q-category coincides with its Cauchy completion.) It is a consequence of the general theory of distributive laws that the monad T restricts to the category of D-coalgebras, that the comonad D restricts to the category of T -algebras, and that the categories of (co)algebras for these restricted (co)monads are equivalent to each other and are further equivalent to the category of so-called λ-bialgebras [Power and Watanabe, 2002, Corollary 6.8]. In the case at hand, a λ-bialgebra is simply a Q-category which is both symmetric and Cauchy-complete (the “λ-compatibility” between algebra and coalgebra structure is trivially satisfied), and a morphism between λ-bialgebras is simply a functor between such Q-categories.

4. Examples

4.1. Example. [Commutative quantales] A quantale is, by definition, a one-object quantaloid. (For some authors, a quantale need not be unital, so for them it is not a one-object quantaloid; but for us, a quantale is always unital.) Put differently, a quantale is a monoid in the monoidal category Sup (whereas a quantaloid is a Sup-enriched category). Obviously, a quantale Q is commutative if and only if the identity function 1_{Q}: Q [figure] Q is an involution.

As we shall point out below, many an interesting involutive quantaloid Q satisfies the following condition:

4.2. Definition. A quantaloid Q is strongly Cauchy-bilateral when it is involutive (with involution f ↦ f^{o}) and for any family (f_{i}: X [figure] X_{i}, g_{i}: X_{i} [figure] X)_{i∈I} of morphisms in Q,

1_{X} ≤ ⋁_{i} g_{i} ∘ f_{i} ⟹ 1_{X} ≤ ⋁_{i}(f_{i}^{o} ∧ g_{i}) ∘ (f_{i} ∧ g_{i}^{o}).

Obviously, a strongly Cauchy-bilateral Q is Cauchy-bilateral in the sense of Definition 3.8. For a so-called integral quantaloid – that is, when the top element of each Q(X, X) is 1_{X} – Cauchy-bilaterality and strong Cauchy-bilaterality are equivalent notions, but in general the latter is strictly stronger than the former:

4.3. Example. We take an example of an involutive quantale from [Resende, 2007, Example 3.18]: the complete lattice with Hesse diagram

[figure: ⊤; 1; a; b; 0]

together with the commutative multiplication defined by a ∘ ⊤ = ⊤, a ∘ a = b and a ∘ b = a. This gives a quantale which we can equip with the identity involution. It is straightforward to check that this quantale is Cauchy-bilateral, but not strongly so.

4.4. Example. [Generalised metric spaces] The condition for strong Cauchy-bilaterality is satisfied by the integral and commutative quantale Q = ([0, ∞], ⋀, +, 0) with its trivial involution: for any family (a_{i}, b_{i})_{i∈I} of pairs of elements of [0, ∞], if ⋀_{i}(a_{i} + b_{i}) ≤ 0 is assumed then

⋀_{i} (max{a_{i}, b_{i}} + max{a_{i}, b_{i}}) = 2 · ⋀_{i} max{a_{i}, b_{i}} ≤ 2 · ⋀_{i}(a_{i} + b_{i}) ≤ 0.

This “explains” the well known fact that the Cauchy completion of a symmetric generalised metric space [Lawvere, 1973] is again symmetric.

4.5. Example. [Locales] Any locale (L, ⋁, ∧, ⊤) is a commutative (hence trivially involutive) and integral quantale; it is easily checked that L is strongly Cauchy-bilateral. Splitting the idempotents of the Sup-monoid (L, ∧, ⊤) gives an integral quantaloid with an obvious involution; it too is strongly Cauchy-bilateral.

4.6. Example. [Groupoid-quantaloids with canonical involution] For a category C, let Q(C) be the quantaloid with the same objects as C but where Q(C)(X, Y) is the complete lattice of subsets of C(X, Y), composition is done “pointwise” (for S ⊆ C(X, Y) and T ⊆ C(Y, Z) let T ∘ S := {t ∘ s | t ∈ T, s ∈ S}) and the identity on an object X is the singleton {1_{X}}. With local suprema in Q(C) given by union, it is straightforward to check that Q(C) is a quantaloid; it is the free quantaloid on the category C.

If G is a groupoid, then S ↦ S^{o} := {s^{−1} | s ∈ S} is the canonical involution on Q(G). For any family (T_{i} ⊆ G(X, X_{i}), S_{i} ⊆ G(X_{i}, X))_{i∈I} we can prove that

1_{X} ∈ ⋃_{i} S_{i} ∘ T_{i} ⟹ 1_{X} ∈ ⋃_{i}(S_{i}^{o} ∩ T_{i}) ∘ (S_{i} ∩ T_{i}^{o}).

Indeed, the premise says that there is a i_{0} ∈ I for which we have x ∈ S_{i_{0}} and y ∈ T_{i_{0}} such that 1_{X} = x ∘ y in G. But then y ∈ S_{i_{0}}^{o} ∩ T_{i_{0}} and x ∈ S_{i_{0}} ∩ T_{i_{0}}^{o}, so that the conclusion follows. That is to say, Q(G) is strongly Cauchy-bilateral.

4.7. Example. [Commutative group-quantales with trivial involution] For a commutative group (G, ·, 1), also the group-quantale Q(G) is commutative, and – in contrast with the above example – it can therefore be equipped with the trivial involution S ↦ S^{o} := S. Betti and Walters [1982] gave a simple example of such a commutative group-quantale with trivial involution for which the Cauchy completion of a symmetric enriched category is not necessarily symmetric. We repeat it here: Let G = {1, a, b} be the commutative group defined by a · a = b, b · b = a and a · b = 1; then Betti and Walters showed that the Cauchy completion of the (symmetric) singleton Q(G)-category whose hom is {1}, is not symmetric. In fact, the pair ({a}, {b}) of elements of Q(G) does satisfy the premise but not the conclusion of the condition in Definition 3.8: thus, in retrospect, Theorem 3.7 predicts that there must exist a symmetric category whose Cauchy completion is no longer symmetric.

There is a common generalisation of Examples 4.5 and 4.6, due to [Walters, 1982]: given a small site (C, J), there is an involutive quantaloid R(C, J) such that the category of symmetric and Cauchy complete R(C, J)-categories is equivalent to Sh(C, J). We shall spell out this important example, and show that it is strongly Cauchy-bilateral (and thus also satisfies the equivalent conditions in Theorem 3.7). In retrospect, this proves that the symmetric and Cauchy complete R(C, J)-categories can be computed as the Cauchy completions of the symmetric R(C, J)-categories.

4.8. Example. [Quantaloids determined by small sites] If C is a small category, then the small quantaloid R(C) of cribles in C is the full sub-quantaloid of Rel(Set^{C^{op}}) whose objects are the representable presheaves. It is useful to have an explicit description. We write a span in C as (f, g): D [figure] C, and intend it to be a pair of arrows with dom(f) = dom(g), cod(f) = C and cod(g) = D. A crible R: D [figure] C is then a set of spans D [figure] C such that for any (f, g) ∈ R and any h ∈ C with cod(h) = dom(f), also (f ∘ h, g ∘ h) ∈ R. Composition in R(C) is obvious: for R: D [figure] C and S: E [figure] D the elements of R ∘ S: E [figure] C are the spans (f, g) : E [figure] C for which there exists a morphism h ∈ C such that (f, h) ∈ R and (h, g) ∈ S. The identity crible id_{C}: C [figure] C is the set {(f, f) | cod(f) = C}, and the supremum of a set of cribles is their union. In fact, R(C) is an involutive quantaloid: the involute R^{o}: C [figure] D of a crible R: D [figure] C is obtained by reversing the spans in R.

If J is a Grothendieck topology on the category C, then there is a locally left exact nucleus^{4} j: R(C) [figure] R(C) sending a crible R: D [figure] C to

j(R) := {(f, g): D [figure] C | ∃S ∈ J(dom(f)) : ∀s ∈ S, (g ∘ s, f ∘ s) ∈ R}.

Conversely, if j: R(C) [figure] R(C) is a locally left exact nucleus, then

J(C) := {S is a sieve on C | id_{C} ≤ j({(s, s) |, s ∈ S})}

defines a Grothendieck topology on C. These procedures are each other’s inverse [Betti and Carboni, 1983; Rosenthal, 1996]. For a small site (C, J) we write, following [Walters, 1982], R(C, J) for the quotient quantaloid R(C)_{j} where j is the nucleus determined by the Grothendieck topology J; it is the small quantaloid of closed cribles determined by the site (C, J). Because every locally left exact nucleus on R(C) preserves the involution, R(C, J) too is involutive. (Walters [1982] originally called R(C, J) a ‘bicategory of relations’, wrote it as Rel(C, J), and called its arrows ‘relations’. To avoid confusion with other constructions that have been called ‘bicategories of relations’ since then, we prefer to speak of ‘small quantaloids of closed cribles’. For an axiomatic study of these, we refer to [Heymans and Stubbe, 2011].)

Any locale L can be thought of as a site (C, J), where C is the ordered set L and J is its so-called canonical topology (so J(u) is the set of all covering families of u ∈ L): it is easily verified that R(C, J) is then isomorphic (as involutive quantaloid) to the quantaloid obtained by splitting the idempotents in the Sup-monoid L. And if G is a small groupoid and J is the smallest Grothendieck topology on G, then the quantaloid of relations R(G, J) equals the quantaloid of cribles R(G), which in turn is isomorphic (as involutive quantaloid) to the free quantaloid Q(G) with its canonical involution. Indeed, any crible R: X [figure] Y in G determines the subset F (R) := {h^{−1}∘g | (g, h) ∈ R} of G(X, Y). Conversely, for any subset S of G(X, Y) let G(S) be the smallest crible containing the set of spans {(1_{X}, s) | s ∈ S} in G. Then R ↦ F (R) and S ↦ G(S) extend to functors F: R(G) [figure] Q(G) and G: Q(G) [figure] R(G) which are each other’s inverse and which preserve the involution. Hence both Examples 4.5 and 4.6 are covered by the construction of the quantaloid R(C, J) from a small site (C, J).

Now we show that R(C, J) is strongly Cauchy-bilateral, as in Definition 4.2. This claim is equivalent to saying that for any family (F_{i}: X [figure] X_{i}, G_{i}: X_{i} [figure] X)_{i∈I} of cribles in C we have

j(id_{X}) ⊆ j( ⋃_{i} j(j(G_{i})∘j(F_{i}))) ⟹ j(id_{X}) ⊆ j( ⋃_{i} j((j(F_{i})^{o}∩j(G_{i})∘(j(F_{i})∩j(G_{i})^{o})))

in the involutive quantaloid R(C) with left exact nucleus j constructed from J.

4A nucleus j on a quantaloid Q is a lax functor j: Q [figure] Q which is the identity on objects and such that each j: Q(X, Y) [figure] Q(X, Y) is a closure operator; it is locally left exact if it preserves finite infima of arrows. If j: Q [figure] Q is a nucleus on a quantaloid, then there is a quotient quantaloid Q_{j} of j-closed morphisms, that is, those f ∈ Q for which j(f) = f.

Take the left-hand side: it is equivalent (by general computations with the nucleus j) to id_{X} ⊆ j(⋃_{i} G_{i}∘F_{i}) in R(C). By definition this means that, for any morphism x in C with cod(x) = X, (x, x) ∈ j(⋃_{i} G_{i} ∘ F_{i}), but because j(⋃_{i} G_{i} ∘ F_{i}) is a crible, this is equivalent to requiring simply that (1_{X}, 1_{X}) ∈ j(⋃_{i} G_{i} ∘ F_{i}) (and here 1_{X} denotes the identity on X in C). Spelling out the definition of the nucleus j in terms of the Grothendieck topology J this means that: there exists a covering sieve S ∈ J(X) such that for all s ∈ S there exists an i_{s} ∈ I satisfying (s, s) ∈ G_{i_{s}} ∘F_{i_{s}}. In a similar fashion the right-hand side can be seen to say precisely that: there exists a covering sieve S ∈ J(X) such that for all s ∈ S there exists an i_{s} ∈ I satisfying (s, s) ∈ (F_{i_{s}}^{o} ∩ G_{i_{s}}) ∘ (F_{i_{s}} ∩ G_{i_{s}}^{o}). The implication is now straightforward.

The following example further generalises the previous one.

4.9. Example. [Locally localic and modular quantaloids] Following [Freyd and Scedrov, 1990] we say that a quantaloid Q is locally localic when each Q(X, Y) is a locale; and Q is modular if it is involutive and when for any morphisms f: Z [figure] Y, g: Y [figure] X and h: Z [figure] X in Q we have gf ∧ h ≤ g(f ∧ g^{o}h) (or equivalently, gf ∧ h ≤ (g ∧ hf^{o})f). (Here we write the composition in Q by juxtaposition to avoid overly bracketed expressions.) In fact, every locally localic and modular quantaloid Q is strongly Cauchy-bilateral: suppose that (f_{i}: X [figure] X_{i}, g_{i}: X_{i} [figure] X)_{i∈I} is a family of morphisms in Q such that 1_{X} ≤ ⋁_{i} g_{i}f_{i}, then we can compute that:

1_{X} = 1_{X} ∧ ⋁_{i} g_{i}f_{i}
= ⋁_{i}(1_{X} ∧ g_{i}f_{i})
= ⋁_{i}(1_{X} ∧ (1_{X} ∧ g_{i}f_{i}))
≤ ⋁_{i}(1_{X} ∧ g_{i}(g_{i}^{o}1_{X} ∧ f_{i}))
= ⋁_{i}(1_{X} ∧ g_{i}(g_{i}^{o} ∧ f_{i}))
≤ ⋁_{i}(1_{X}(g_{i}^{o} ∧ f_{i})^{o} ∧ g_{i})(g_{i}^{o} ∧ f_{i})
= ⋁_{i}(g_{i} ∧ f_{i}^{o})(g_{i}^{o} ∧ f_{i}).

To pass from the first to the second line we used that Q(X, X) is a locale, and both inequalities were introduced by use of the modular law.

Any small quantaloid of relations R(C, J) is in fact locally localic and modular, and thus its strong Cauchy-bilaterality follows from the above computation. But to prove that R(C, J) is modular, is not simpler than to prove directly that it satisfies the condition in Definition 4.2, as we did in Example 4.8. (The quantale in Example 4.4 is locally localic but not modular, and the quantale in Example 4.3 is neither locally localic nor modular; but both are Cauchy-bilateral.)

4.10. Example. [Sets and relations] The quantaloid Rel of sets and relations is not small, but it is involutive (by taking opposites: R^{o} = {(y, x) | (x, y) ∈ R}) and it is strongly Cauchy-bilateral. In fact, this holds for any quantaloid Rel(E) of internal relations in a Grothendieck topos E, because it is modular and locally localic [Freyd and Scedrov, 1990].

There is a subtle difference between Examples 4.8 and 4.10: the former deals with the small quantaloid R(C, J) built from a small site, the latter deals with the large quantaloid Rel(Sh(C, J)) of relations between the sheaves on that site. However, both constructions give rise to a Cauchy-bilateral quantaloid. We shall further analyse the interplay between these quantaloids in a forthcoming paper.

Finally we mention a difference between “symmetric” and “discrete” Q-categories.

4.11. Example. [Symmetric vs. discrete] In any locally ordered category K, an object D is said to be discrete when, for any other object X ∈ K, the order K(X, D) is symmetric. It is straightforward to verify that, whenever Q is a small Cauchy-bilateral quantaloid, every symmetric and Cauchy complete Q-category is a discrete object of Cat_{cc}(Q). However, not all discrete objects of Cat_{cc}(Q) need to be symmetric, not even when Q is Cauchybilateral! A counterexample can be found in the theory of generalised metric spaces: Suppose that X is a set and R ⊆ X × X. For x, y ∈ X, a path from x to y is a sequence α = (x_{0}, x_{1}, …, x_{n}) of elements of X with x_{0} = x, x_{n} = y and (x_{i}, x_{i+1}) ∈ R for all i < n; the length l(α) of such a path α is then n. For every x ∈ X, (x) is a path from x to x of length 0. It is easy to verify that

d_{R}(x, y) := ⋀{l(α) | α is a path from x to y}

turns X into a generalised metric space. (This infimum is a minimum, except when there is no path from x to y, in which case d_{R}(x, y) = ∞.) Any such space (X, d_{R}) is Cauchy complete, as is every generalised metric space with values in ℕ ∪ {∞}. And, in fact, it is discrete in the sense given above, because x ≤ y if and only if 0 ≥ d_{R}(x, y), so there is a path with length 0 from x to y, which means that x = y. However, choosing X = {0, 1} and R = {(0, 1)} gives a non-symmetric example: d_{R}(0, 1) = 1 ≠ ∞ = d_{R}(1, 0).

References

Jon Beck, 1969. Distributive laws, Springer Lecture Notes in Mathematics 80, pp. 119– 140. Also in: Reprints in Theory Appl. Categ. 18, pp. 95–112 (2008).

Renato Betti and Aurelio Carboni, 1983. Notion of topology for bicategories, Cahiers Topol. Géom. Différ. Catég. 24, pp. 19–22.

Renato Betti and Robert F. C. Walters, 1982. The symmetry of the Cauchy-completion of a category, Springer Lecture Notes in Math. 962, pp. 8–12.

Peter J. Freyd and Andre Scedrov, 1990. Categories, Allegories, North-Holland Mathematical Library 39, Amsterdam.

Hans Heymans, 2009. Q-∗-categories, Appl. Categ. Structures 17, pp. 1–28.

Hans Heymans and Isar Stubbe, 2011. Elementary characterisation of quantaloids of closed cribles, to appear in J. Pure Appl. Algebra.

G. Max Kelly and Ross Street, 1974. Review of the elements of 2-categories, Lecture Notes in Math. 420, pp. 75–103.

F. William Lawvere, 1973. Metric spaces, generalized logic and closed categories, Rend. Sem. Mat. Fis. Milano 43, pp. 135–166. Also in: Reprints in Theory Appl. Categ. 1, pp. 1–37 (2002).

John Power and Hiroshi Watanabe, 2002. Combining a monad and a comonad, Theoret. Comput. Sci. 280, pp. 137–162.

Pedro Resende, 2007. Étale groupoids and their quantales, Adv. Math. 208, pp. 147–209.

Kimmo I. Rosenthal, 1996. The theory of quantaloids, Pitman Research Notes in Mathematics Series 348, Longman, Harlow.

Ross Street, 1972. The formal theory of monads, J. Pure Appl. Algebra 2, pp. 149–168.

Isar Stubbe, 2005. Categorical structures enriched in a quantaloid: categories, distributors and functors, Theory Appl. Categ. 14, pp. 1–45.

Robert F. C. Walters, 1981. Sheaves and Cauchy-complete categories, Cahiers Topol. Géom. Différ. Catég. 22, pp. 283–286.

Robert F. C. Walters, 1982. Sheaves on sites as cauchy complete categories, J. Pure Appl. Algebra 24, pp. 95–102.

Hans Heymans Department of Mathematics and Computer Science, University of Antwerp Middelheimlaan 1, 2020 Antwerpen, Belgium

Isar Stubbe Laboratoire de Mathématiques Pures et Appliquées, Université du Littoral-Côte d’Opale 50 rue Ferdinand Buisson, 62228 Calais, France

Email: hans.heymans@ua.ac.be
      isar.stubbe@lmpa.univ-littoral.fr

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

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/25/11/25-11.{dvi,ps,pdf}

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

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

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

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

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

Assistant TEX editor Gavin Seal, 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 Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Glasgow, Tom.Leinster@glasgow.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.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 Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca