Theory and Applications of Categories, Vol. 18, No. 6, 2007, pp. 157–171.

CCD LATTICES IN PRESHEAF CATEGORIES

G. S. H. CRUTTWELL, F. MARMOLEJO AND R. J. WOOD

Abstract. In this paper we give a characterization of constructively completely distributive (CCD) lattices in set^{Cop}, for C a small category with pullbacks.

1. Introduction

Recall that an ordered set L is a sup lattice if and only if the down-segment embedding of L into its complete lattice of down-sets, ↓ : L → DL, has a left adjoint ⋁: DL → L. It is well-known that a sup lattice L is a locale, meaning that binary meet distributes over arbitrary sup, if and only if ⋁: DL → L preserves binary meets. Since [Fawcett and Wood, 1990] a complete lattice has been said to be constructively completely distributive (CCD) if ⋁: DL → L preserves all infima, equivalently, if ⋁: DL → L has itself a left adjoint. Classically, (CCD) is equivalent to ordinary complete distributivity (CD). In fact, it was shown in [Fawcett and Wood, 1990] that

(AC) ⟺ ((CD) ⟺ (CCD))

and thus, (CCD) is an appropriate version of complete distributivity in an elementary topos. It is therefore natural to seek characterizations of (CCD) lattices in familiar toposes.

We envision our present results, though not our proof techniques, in the tradition of [Joyal and Tierney, 1984], wherein sup(set^{Cop}), the category of sup lattices and suppreserving arrows with respect to the topos of presheaves set^{Cop}, for C small with pullbacks, is given in terms of functors L: C^{op} → sup. Here sup is the category of sup-lattices and sup-preserving arrows with respect to the base topos set. We recall the statement of their result (Proposition 1, Section 2, Chapter VI, op. cit.):

A sup-lattice L in set^{Cop} is a functor L: C^{op} → sup such that for every f : B → C in C, Lf : LC → LB has a left adjoint ⋁_{f} : LB → LC, and these adjunctions satisfy the Beck-Chevalley condition with respect to pullbacks. An arrow α: L → M in sup(set^{Cop}) is a natural transformation between such functors such that, for each f : B → C in C,

The second author acknowledges the financial support received from DGAPA of UNAM that made his sabbatical stay at Dalhousie University possible, and also the hospitality of this latter institution.

The third author thanks NSERC Canada for financial support.

Received by the editors 2006-10-09 and, in revised form, 2007-03-27.

Transmitted by Susan Niefield. Published on 2007-03-29.

2000 Mathematics Subject Classification: 18B35, 06D10, 06B23.

Key words and phrases: Constructive complete distributivity, presheaves, Beck-Chevalley condition, Frobenius reciprocity, change of base.

\begin{matrix}c \\ ◯ \end{matrix} G. S. H. Cruttwell, F. Marmolejo and R. J. Wood, 2007. Permission to copy for private use granted.

\xymatrix{LB \ar[r]^{αB} \ar[d]_{_{⋁f}} & MB \ar[d]^{_{⋁f}} \\ LC \ar[r]_{αC} & MC,}

commutes.

Observe too that because the Lf : LC → LB, for f : B → C in C, are shown to take values in sup, it follows that for each f there is also an adjunction Lf ⊣ ⋀_{f} (and these adjunctions necessarily satisfy the Beck-Chevalley condition too).

Thus, we also assume throughout that C has pullbacks and we characterize CCD lattices in set^{Cop} in terms of functors L: C^{op} → ccd, where ccd is the category of constructively completely distributive (CCD) lattices, with respect to set, and functions that preserve both suprema and infima. The characterization is surprising in the appearance of a right adjoint for each ⋀_{f}. While an ordered object L in a topos has a left adjoint, ⋁, for ↓ : L → DL if and only if it has a right adjoint, ⋀, for ↑ : L → UL, where UL is the complete lattice of up-subobjects of L ordered by reverse inclusion, this symmetry does not extend to further adjoints. For ⋀: UL → L to have a right adjoint is for L^{op} to be (CCD), a condition which in terms of L is called (^{op}CCD). In [Rosebrugh and Wood, 1991] it was shown that

(BLN) ⟺ ((CCD) ⟺ (^{op}CCD))

where (BLN) is the Boolean axiom for the topos under consideration. Of course (BLN) does not generally hold for the toposes set^{Cop}.

These extra adjunctions do not suffice. A generalization of Frobenius reciprocity is needed to construct left adjoints to the components ⋁_{C} : DL(C) → LC of the natural transformation ⋁: DL → L and a further distributivity condition is required to show that such left adjoints constitute the components of a natural transformation L → DL.

This characterization was begun by Cruttwell in his thesis [G. S. H. Cruttwell, 2005]. There we find a generalization of the Frobenius reciprocity law called wide Frobenius reciprocity. As explained there, the requirement needed to express this condition is for C to have wide pullbacks. It is noted there that this is a very strong condition: for C small with a terminal object, the existence of wide pullbacks implies that C is a poset. More importantly, the characterization theorem, even in this case, is incomplete, as the example 2 → 1 in set^{Cop}, for C = {0 → 1}, shows (see below).

We duly give a new version of this condition, that we call complete Frobenius reciprocity, which does not require wide pullbacks, and add a further condition, along with the afore-mentioned right adjoints to the ⋀_{f}, which enable us to characterize CCD lattices in set^{Cop}.

2. Comparison transformation for evaluation

We will write L generically for an object of ord(set^{Cop}). The object of down-subobjects of L is then DL: C^{op} → set given, for C ∈ C, by

DL(C) = {F [figure] L × C(−, C)|(b, f) ∈ F B and b′ ≤ b imply (b′, f) ∈ F B}

while, for f : B → C in C, DL(f) is given by pulling back along L × C(−, f). The arrow ↓ : L → DL is given by

↓_{C} c (B) = {(b, f)|b ≤ Lf(c)}

for c in L(C).

Any left exact functor Γ : E → S between toposes gives rise to a natural transformation γ: ΓD_{E} → D_{S}Γ, where the D’s are considered to be functorial via inverse image. For L in ord(E), γ_{L} classifies the order ideal ΓDL → ΓL obtained by applying Γ to the order ideal ↓^{+} : DL → L which is right adjoint to the map ↓ : L → DL considered as an order ideal. (Note that for x in L and S in DL, one has x ↓^{+} S if and only if x ∈ S.) This natural transformation was introduced in [Rosebrugh and Wood, 1992] where it was called the ‘logical comparison transformation’. In the case at hand, and taking Γ : set^{Cop} → set to be evaluation at C, we have γ = γ_{L} : DL(C) → D(LC), where D(LC) is the set of down-sets of the ordered set LC. It is not hard to show that, for F ∈ DL(C),

γ(F) = {c ∈ LC|(c, 1_{C}) ∈ F C}

2.1. Lemma. The component γ: DL(C) → D(LC) has a left adjoint γ^{∗} and a right adjoint γ_{∗}.

Proof. It is not hard to see that the left adjoint γ^{∗} is given by

γ^{∗}(S)(B) = {(b, f)|there is c ∈ S with b ≤ Lf(c)}

for any S ∈ D(LC), and that the right adjoint is given by

γ_{∗}(S)(B) = {(b, f)|for every s: C → B with fs = 1_{C}, Ls(b) ∈ S}.

Observe that γ^{∗} ⊣ γ ⊣ γ_{∗} is a fully faithful adjoint string.

We will need the following property of γ^{∗}:

2.2. Lemma. γ^{∗} ↓_{LC}=↓_{C}.

Proof. For c ∈ LC and B ∈ C we have

(γ^{∗} ↓_{LC} (c))(B) = {(b, f)|b ≤ Lf(c′) for some c′ ∈↓_{LC} (c)}
= {(b, f)|b ≤ Lf(c′) for some c′ ≤ c}
= {(b, f)|b ≤ Lf(c)} = ↓_{C} (c)(B).

For f : B → C in C, the left adjoint ⋁_{f}^{DL} of DL(f) is given by the image

\xymatrix{G \ar@{^{(}->}[r] \ar@{->>}[d] & L × C(−, B) \ar[d]^{L×C(−,f)} \\ ⋁_{f}^{DL}(G) \ar@{^{(}->}[r] & L × C(−, C)}

for any G ∈ DL(B). In what follows, the elements in the image of

\xymatrix{LB \ar[r]^{↓_{B}} & DL(B) \ar[r]^{^{⋁{DL \atop f}}} & DL(C)}

will become important, so we give them a name:

2.3. Definition. For f : B → C in C and b ∈ LB, we define

↓_{C} (b, f) = ⋁_{f}^{DL}(↓_{B} b).

Therefore

↓_{C} (b, f)(A) = {(a, h)|there is g: A → B such that h = fg and a ≤ Lg(b)}

Observe that this extends our existing notation, in the sense that ↓_{B} b =↓_{B} (b, 1_{B}). The main properties that we need of these objects are given by the following lemma and corollary:

2.4. Lemma. For f : B → C in C and b ∈ LB, ↓_{C} (b, f) is the smallest element F ∈ DL(C) such that (b, f) ∈ F B.

Proof. Clearly (b, f) ∈ (↓_{C} (b, f))(B). Assume now that F ∈ DL(C) and that (b, f) ∈ F B. If (y, k) ∈ (↓_{C} (b, f))(Y), then we can find s: Y → B such that k = fs and y ≤ Ls(b). Since (b, f) ∈ F B, we have (Ls(b), k) = (Ls(b), fs) ∈ F Y. This together with y ≤ Ls(b) imply that (y, k) ∈ F Y.

2.5. Corollary. For any C ∈ C and F ∈ DL(C),

F = ⋃{↓_{C} (b, f)|B ∈ C, (b, f) ∈ F B}.

We turn now to the possibility of a left adjoint to γ^{∗}.

2.6. Proposition. Assume that LC is complete. The map γ^{∗} has a left adjoint γ_{!} if and only if for every f : B → C in C, Lf has a left adjoint ⋁_{f}.

Proof. Assume that for every f : B → C we have ⋁_{f} ⊣ Lf. Define

γ_{!}(F) = {c ∈ LC|c ≤ ⋁_{f}(b) for some B ∈ C and some (b, f) ∈ F B}.

Then

F ⊆ γ^{∗}(S)
for every B, F B ⊆ γ^{∗}(S)(B)
for every B, if (b, f) ∈ F B, then there is c ∈ S with b ≤ Lf(c)
for every B, if (b, f) ∈ F B, then there is c ∈ S with ⋁_{f}(b) ≤ c
for every B, if (b, f) ∈ F B, then ⋁_{f}(b) ∈ S
γ_{!}(F) ⊆ S,

where we use the adjunction ⋁_{f} ⊣ Lf from the third to the fourth line, and the fact that S is downclosed on the next one.

Assume now that γ_{!} ⊣ γ^{∗} and take f : B → C in C. Define ⋁_{f} as the composite

\xymatrix{LB \ar[r]^{↓_{B}} & DL(B) \ar[r]^{^{⋁{DL \atop f}}} & DL(C) \ar[r]^{γ_{!}} & D(LC) \ar[r]^{^{⋁^{LC}}} & LC,}

where ⋁_{LC} ⊣ ↓_{LC} : LC → D(LC). For b ∈ LB and c ∈ LC we have

⋁_{f}(b) ≤ c
⋁_{LC}γ_{!}⋁_{f}^{DL} ↓_{B} b ≤ c
⋁_{f}^{DL} ↓_{B} b ≤ γ^{∗} ↓_{LC} (c)
↓_{C} (b, f) ≤ ↓_{C} (c)
(b, f) ∈ ↓_{C} (c)(B)
b ≤ Lf(c),

where we have applied first the definition of ⋁_{f}, then the adjunction ⋁_{LC}γ_{!} ⊣ γ^{∗} ↓_{LC}, the definition of ↓_{C} (b, f), Lemma 2.2 and Lemma 2.4.

2.7. Lemma. If LC is a sup lattice and γ_{!} exists, then ⋁_{LC}γ_{!} ⊣↓_{C}. In particular, if L is a sup lattice in set^{Cop}, then ⋁_{C} = ⋁_{LC}γ_{!}.

Proof. We have ⋁_{LC} ⊣↓_{LC} and γ_{!} ⊣ γ^{∗}, thus ⋁_{LC}γ_{!} ⊣ γ^{∗} ↓_{LC}=↓_{C}, by Lemma 2.2.

2.8. Remark. When L ∈ sup(set^{Cop}), the formula for ⋁_{f} given in the proof of Proposition 2.6 becomes

\xymatrix{LB \ar[r]^{↓_{B}} & DL(B) \ar[r]^{^{⋁{DL \atop f}}} & DL(C) \ar[r]^{^{⋁^{C}}} & LC.}

3. A new perspective on an old theorem

We use the adjoints from the previous section to give a different proof of Proposition 1, Section 2, Chapter VI of [Joyal and Tierney, 1984]:

3.1. Theorem. An object L ∈ sup(set^{Cop}) is a functor L: C^{op} → sup(set) such that for every f : B → C in C, Lf has a left adjoint ⋁_{f} ⊣ Lf, and the Beck-Chevalley condition with respect to pullbacks is satisfied for these adjoints.

We begin by assuming L ∈ sup(set^{Cop}) and deriving the conditions. First of all we observe that when L is a sup lattice, we have

[figure: LC; DL(C); D(LC),; ↓_{C}; ⊥; ^{⋁^{C}}; γ; ⊥; γ^{∗}; ↓_{LC}]  (1)

We know from [Rosebrugh and Wood, 1992] (or directly) that γ ↓_{C}=↓_{LC}. Thus ⋁_{C}γ^{∗} is a left adjoint to ↓_{LC}, and LC turns out to be a sup lattice.

It is easy to see that for every f : B → C in C, the square on the left in the diagram

\xymatrix{D(LC) \ar[r]_{γ^{∗}} \ar[d]_{D(Lf)} \ar[rr]^{^{⋁^{LC}}} & DL(C) \ar[d]_{DL(f)} \ar[r]_{_{⋁_{C}}} & LC \ar[d]^{Lf} \\ D(LB) \ar[r]^{γ^{∗}} \ar[rr]_{_{⋁_{LB}}} & DL(B) \ar[r]^{_{⋁_{B}}} & LB}

commutes. Since the square on the right also commutes, we have that Lf preserves sups or, equivalently, that Lf has a right adjoint Lf ⊣ ⋀_{f}. Thus, L: C^{op} → sup(set) is a functor. A dual argument with upclosed sets instead of downclosed sets, and the general remark that every sup lattice is an inf lattice, gives us that Lf has a left adjoint ⋁_{f} ⊣ Lf.

We are thus left with the Beck-Chevalley condition. For this we need:

3.2. Lemma. For any L ∈ ord(set^{Cop}), the adjunctions ⋁_{f}^{DL} ⊣ DL(f) : DL(C) → DL(B) with f : B → C in C, satisfy the Beck-Chevalley condition.

Proof. Take a pullback diagram

\xymatrix{P \ar[r]^{r} \ar[d]_{q} & B \ar[d]^{f} \\ Z \ar[r]_{h} & C}  (2)

in C. Thus, the inner square in

[figure: DL(r)(F); F; L × C(−, P); L × C(−, B); L × C(−, Z); L × C(−, C); DL(h)⋁_{f}^{DL}(F); ⋁_{f}^{DL}(F); L×C(−,r); L×C(−,q); L×C(−,f); L×C(−,h)]

is a pullback. A general F ∈ DL(B) is depicted on the upper right corner of the previous diagram. Now ⋁_{f}^{DL}(F) is calculated as the image of F under L × C(−, f), as shown on the right of the diagram. Now, DL(h)⋁_{f}^{DL}(F) is the pullback along L × C(−, h) as shown on the bottom of the diagram. On the other hand, we calculate DL(r)(F) as the pullback along L×C(−, r). Thus, to calculate ⋁_{q}^{DL}DL(r)(F) we have to calculate the image of this along L × C(−, q). But since we are dealing here with a regular category, we have that the image is given by the dotted arrow, that is ⋁_{q}^{DL}DL(r)(F) = DL(h)⋁_{f}^{DL}(F). Thus, the diagram

\xymatrix{DL(B) \ar[r]^{^{⋁{DL \atop f}}} \ar[d]_{DL(r)} & DL(C) \ar[d]^{DL(h)} \\ DL(P) \ar[r]_{_{⋁{DL \atop q}}} & DL(Z)}

commutes. This is the Beck-Chevalley condition.

Assume again that L ∈ sup(set^{Cop}). To show Beck-Chevalley in this case, take a pullback as in (2) and consider the diagram

[figure: LB; LC; DL(B); DL(C); DL(P); DL(Z); LP; LZ.; ^{⋁^{B}}; ^{⋁^{f}}; Lh; Lr; _{⋁_{q}}; _{⋁_{P}}; _{⋁_{Z}}; ^{⋁^{C}}; ^{⋁{DL \atop f}}; DL(r); DL(h); _{⋁{DL \atop q}}]

Observe that the right and left faces commute by the naturality of ⋁: DL → L. The commutativity of the top is equivalent, by taking right adjoints, to ↓_{B} Lf = DL(f) ↓_{C}, which is just the naturality of ↓ : L → DL. The bottom commutes for the same reason. The middle square commutes by the previous lemma. We thus deduce the commutativity of the exterior square by recalling that ⋁_{B} ↓_{B}= 1_{LB}.

A morphism α: L → M in sup(set^{Cop}) is a natural transformation α: L → M such that the diagram

\xymatrix{DL \ar[d]_{⋁} \ar[r]^{Dα} & DM \ar[d]^{⋁} \\ L \ar[r]_{α} & M}  (3)

commutes.

3.3. Lemma. If α: L → M is a morphism in sup(set^{Cop}), then α: L → M is a natural transformation in sup(set)^{C^{op}} such that the diagram

\xymatrix{LB \ar[r]^{αB} \ar[d]_{_{⋁f}} & MB \ar[d]^{_{⋁f}} \\ LC \ar[r]_{αC} & MC}

commutes for every f : B → C in C.

Proof. Since α is a morphism of sup lattices, it has a right adjoint α_{∗}. Thus for every C ∈ C, αC ⊣ α_{∗}C, and α turns out to be a natural transformation in sup(set)^{C^{op}}. Furthermore, the naturality of α_{∗} produces the commutative diagram

\xymatrix{MC \ar[r]^{α_{∗}C} \ar[d]_{Mf} & LC \ar[d]^{Lf} \\ MB \ar[r]_{α_{∗}B} & LB,}

for every f : B → C. By taking left adjoints we obtain the commutativity of the square in the statement of the lemma.

Assume now that we have a functor L: C^{op} → sup(set) with the property that for every f : B → C in C, Lf has a left adjoint ⋁_{f} ⊣ Lf, and that these adjunctions satisfy the Beck-Chevalley condition.

Lemma 2.7 gives us a left adjoint to ↓_{C} : LC → DL(C), namely ⋁_{LC}γ_{!} (the existence of γ_{!} is guaranteed by Proposition 2.6, whereas ⋁_{LC} exists since L takes values in sup(set)). We are thus left with the task of showing that these left adjoints fit together to form a natural transformation, that is, we need to show the commutativity of the exterior rectangle in the diagram

\xymatrix{DL(C) \ar[r]^{γ_{!}} \ar[d]_{DL(f)} & D(LC) \ar[r]^{^{⋁^{LC}}} \ar[d]_{D(Lf)} & LC \ar[d]^{Lf} \\ DL(B) \ar[r]_{γ_{!}} & D(LB) \ar[r]_{_{⋁_{LB}}} & LB}

for every f : B → C in C. Since Lf has a right adjoint (recall that L takes values in sup(set)), we have that the right square in the above diagram commutes, so it suffices to show that the left square commutes. This is taken care of in:

3.4. Lemma. Let L ∈ ord(set^{Cop}). Assume that LC is a sup lattice for every C ∈ C, that for every f : B → C in C, Lf has a left adjoint, and that these adjoints satisfy the Beck-Chevalley condition. Then the diagram

\xymatrix{DL(C) \ar[r]^{γ_{!}} \ar[d]_{DL(f)} & D(LC) \ar[d]^{D(Lf)} \\ DL(B) \ar[r]_{γ_{!}} & D(LB)}

commutes.

Proof. Observe that γ_{!} exists by Proposition 2.6. For γ_{!}DL(f)(F) ⊆ D(Lf)γ_{!}(F) it suffices to show that, if (w, fk) ∈ F W, then ⋁_{k}w ∈ D(Lf)γ_{!}(F). But the condition (w, fk) ∈ F W implies that Lf(⋁_{fk}w) ∈ D(Lf)γ_{!}(F), and ⋁_{k}w ≤ Lf⋁_{f}⋁_{k}w = Lf⋁_{fk}w, using the unit of ⋁_{f} ⊣ Lf. Thus ⋁_{k}w ∈ D(Lf)γ_{!}(F).

To prove the other containment is suffices to show that for any (z, h) ∈ F Z, Z ∈ C, we have Lf(⋁_{h}z) ∈ γ_{!}(D(Lf)F). Take the pullback

\xymatrix{P \ar[r]^{d} \ar[d]_{e} & B \ar[d]^{f} \\ Z \ar[r]_{h} & C.}

Since (z, h) ∈ F Z, we have (Le(z), fd) = (Le(z), he) ∈ F P. But by the Beck-Chevalley condition we also have Lf(⋁_{h}z) = ⋁_{d}Le(z). Thus Lf(⋁_{h}z) ∈ γ_{!}(DL(f)F).

To complete the picture, we have to deal with morphisms.

3.5. Lemma. If L and M are sup lattices in set^{Cop}, and α: L → M is a natural transformation in sup(set)^{C^{op}} with the property that for every f : B → C in C the diagram

\xymatrix{LB \ar[r]^{αB} \ar[d]_{_{⋁f}} & MB \ar[d]^{_{⋁f}} \\ LC \ar[r]_{αC} & MC}

commutes, then α: L → M is a morphism in sup(set^{Cop}).

Proof. Since α takes values in sup(set), for every C ∈ C, αC has a right adjoint α_{∗}C. The naturality of α_{∗} is obtained by taking right adjoints on the commutative square on the statement of the lemma. Thus α ⊣ α_{∗}, and α is a morphism of sup lattices.

4. An extra right adjoint for CCD lattices

Take L ∈ sup(set^{Cop}). According to the theorem from [Joyal and Tierney, 1984] mentioned in the Introduction and for which we gave an alternative proof in Theorem 3.1, this is equivalent to the conditions: LC is a sup lattice for every C ∈ C, for every f : B → C we have adjunctions ⋁_{f} ⊣ Lf ⊣ ⋀_{f}, and the adjunctions ⋁_{f} ⊣ Lf satisfy the Beck-Chevalley condition. If L ∈ ccd(set^{Cop}), then for every C ∈ C we have the diagram

[figure: LC; DL(C); D(LC),; ↓_{C}; ⊥; ^{⋁^{C}}; ⊥; ⇓_{C}; γ; ⊥; γ^{∗}; ⊥; γ_{!}; ↓]  (4)

where ⇓_{C} is the instance at C of ⇓⊣ ⋁: DL → L, and, as before, γ ↓_{C}=↓_{LC} : LC → D(LC). Thus we have

4.1. Lemma. If L ∈ ccd(set^{Cop}), then for every C ∈ C, LC is a CCD lattice.

Proof. It follows immediately that supremum on downsets for LC is given by ⋁_{C}γ^{∗}. Thus the defining left adjoint for LC to be CCD is provided by γ_{!} ⇓_{C}.

We can obtain from (4) a right adjoint to ⋀_{f}, for every f in C. To do that we paste together the diagram of Lemma 3.4 with diagram (4), assuming L ∈ ccd(set^{Cop}), to obtain, for f : B → C in C, the commutativity of the diagram

\xymatrix{LC \ar[r]^{⇓_{LC}} \ar[d]_{Lf} & D(LC) \ar[d]^{D(Lf)} \\ LB \ar[r]_{⇓_{LB}} & D(LB),}

where ⇓_{LC}⊣ ⋁_{LC} : D(LC) → LC. If we take right adjoints, we have the commutativity of the diagram

\xymatrix{LC & D(LC) \ar[l]_{^{⋁^{LC}}} \\ LB \ar[u]^{_{⋀_{f}}} & D(LB). \ar[l]^{_{⋁_{LB}}} \ar[u]_{D(⋀_{f})}}

This means that ⋀_{f} preserves sups, thus it has a right adjoint. We have shown:

4.2. Proposition. If L ∈ ccd(set^{Cop}), then for any f : B → C in C we have an adjoint string ⋁_{f} ⊣ Lf ⊣ ⋀_{f} ⊣ ⇑_{f}.

5. Complete Frobenius Reciprocity

In this section we assume that L ∈ sup(set^{Cop}). We modify the condition called wide Frobenius reciprocity in [G. S. H. Cruttwell, 2005] so as not to need wide pullbacks in C, and we show that the condition is closely related to every ⋁_{C} : DL(C) → LC having a left adjoint. The condition is

5.1. Definition. L satisfies complete Frobenius reciprocity at C ∈ C if for any family of the form

⟨(a_{ij}, f_{ij})⟩_{i∈I,j∈J_{i}}

with f_{ij}: A_{ij} → C and a_{ij} ∈ LA_{ij}, we have

⋁{⋀_{i}c_{i}|⟨c_{i}⟩_{i∈I} ⊆ LC is such that for every i there is j ∈ J_{i} with c_{i} ≤ ⋁_{f_{ij}}a_{ij}} =

⋁{⋁_{h}z|for every i ∈ I there are j ∈ J_{i} and [figure: Z; A_{ij}; s]with h = f_{ij}s and z ≤ Ls(a_{ij})}.

5.2. Remark. If we take an element ⋁_{h}z as in the second term of the previous definition, and we consider the constant family ⟨⋁_{h}z⟩_{i∈I}, we have that for every i there are j ∈ J_{i} and s: Z → A_{ij} such that h = f_{ij}s and z ≤ Ls(a_{ij}). Thus ⋁_{h}z ≤ ⋁_{h}Ls(a_{ij}) = ⋁_{f_{ij}}⋁_{s}Ls(a_{ij}) ≤ ⋁_{f_{ij}}a_{ij}, using the counit of the adjunction ⋁_{s} ⊣ Ls. Thus, the second term in the definition is always less than or equal to the first.

5.3. Proposition. Assume that C ∈ C is such that LC is a CCD lattice. Then L satisfies complete Frobenius reciprocity at C if and only if ⋁_{C} : DL(C) → LC has a left adjoint.

Proof. Given any family ⟨F_{i}⟩_{i∈I} in DL(C), we have that

⋁_{C}(_{⋂i}F_{i}) = ⋁_{Z∈C}⋁_{(z,h)∈(⋂_{i} F_{i})(Z)}⋁_{h}z.

On the other hand, define S_{i} = {c ∈ LC|c ≤ ⋁_{h}z for some Z ∈ C and (z, h) ∈ F_{i}Z}. We have that S_{i} ∈ D(LC). If we use the fact that LC is a CCD lattice, we have

\begin{aligned}⋀_{i}⋁_{C}F_{i} & = & ⋀_{i}⋁_{Z∈C}⋁_{(z,h)∈F_{i}Z}⋁_{h}z = ⋀_{i}⋁_{LC}S_{i} \\ & = & ⋁_{⟨c_{i}⟩_{i}∈∏_{i} S_{i}}⋀_{i}c_{i}. \end{aligned}

Assume now that ⋁_{C} : DL(C) → LC has a left adjoint, and that ⟨(a_{ij}, f_{ij})⟩_{ij}, i ∈ I, j ∈ J_{i} is a family as in Definition 5.1. For every i ∈ I define F_{i} = ⋃_{j∈J_{i}} ↓_{C} (a_{ij}, f_{ij}) (recall Definition 2.3). Since ⋁_{C} preserves infs, we have that ⋁_{C}(⋂_{i} F_{i}) = ⋀_{i}⋁_{C}F_{i}. Observe that, in this case, the condition (z, h) ∈ ( ⋂_{i} F_{i})(Z) is exactly the one expressed on the second term in Definition 5.1. So all we have to do prove complete Frobenius reciprocity is to take a family ⟨c_{i}⟩_{i∈I} that satisfies the condition expressed in the first term of Definition 5.1, and show that ⟨c_{i}⟩_{i∈I} ∈ ∏_{i} S_{i}. But for every i ∈ I there is a j ∈ J_{i} such that c_{i} ≤ ⋁_{f_{ij}}a_{ij}. So all we have to do is to take s = 1_{A_{ij}} and (z, h) = (a_{ij}, f_{ij}).

Assume now that L satisfies the condition of Definition 5.1. As always, we have ⋁_{C}(⋂_{i} F_{i}) ≤ ⋀_{i}⋁_{C}F_{i}. Thus, to show that ⋁_{C} preserves infs, it suffices to show that for every ⟨c_{i}⟩_{i} ∈ ∏_{i} S_{i} we have

⋀_{i}c_{i} ≤ ⋁_{Z∈C}⋁_{(z,h)∈(⋂_{i} F_{i})(Z)}⋁_{h}z.

According to Corollary 2.5, we can express every F_{i} in the form F_{i} = ⋃_{j∈J_{i}} ↓_{C} (a_{ij}, f_{ij}). We thus have that

S_{i} = {⋁_{h}z|Z ∈ C, (z, h) ∈ _{⋃j∈J_{i}} ↓_{C} (a_{ij}, f_{ij})(Z)}^{↓}.

If ⟨c_{i}⟩_{i} ∈ ∏_{i} S_{i}, then for every i we can find j ∈ J_{i}, s: Z → C, with h = f_{ij}s, z ∈ LZ such that z ≤ Ls(a_{ij}) and c ≤ ⋁_{h}z. Then

c_{i} ≤ ⋁_{h}z = ⋁_{h}Ls(a_{ij}) = ⋁_{f_{ij}}⋁_{s}Ls(a_{ij}) ≤ ⋁_{f_{ij}}a_{ij},

using the counit of the adjunction ⋁_{s} ⊣ Ls. The family ⟨c_{i}⟩_{i} satisfies the condition on the first term of Definition 5.1, and thus we have

⋀_{i}c_{i} ≤ ⋁{⋁_{h}z|for every i ∈ I there are j ∈ J_{i} and
s: Z → A_{ij} such that h = f_{ij}s and z ≤ Ls(a_{ij})}

As before, the right hand side is precisely ⋁_{C}( ⋂_{i} F_{i}). Thus ⋁_{C} has a left adjoint

5.4. Example. Even assuming that L ∈ sup(set^{Cop}) satisfies complete Frobenius reciprocity at every C ∈ C, and that every LC is CCD, there is no reason why the corresponding left adjoints of the ⋁_{C} : DL(C) → LC would form a natural transformation L → DL. To see this, take C = {0 → 1}, and take as L the only function ! : 2 → 1 seen as an object of set^{Cop}. Since ! ⊣ ⊤ and ⊤ does not have a right adjoint, Proposition 4.2 tells us that L is not a CCD lattice. However, it is not hard to see that it does satisfy complete Frobenius reciprocity. Thus, in this case the left adjoint of ⋁_{0} : DL(0) → L0 and the left adjoint of ⋁_{1} : DL(1) → L1 cannot form a natural transformation L → DL (because it would be a left adjoint to ⋁: DL → L, which we know to not exist).

6. Characterization of CCD’s in set^{C^{op}}

In this section we prove a characterization theorem for CCD lattices in set^{Cop} by adding a condition that guarantees that the left adjoints to the ⋁_{C}’s match together to form a left adjoint to ⋁: DL → L. We consider the category ccd(set) whose objects are CCD lattices, and whose arrows are those order functions that have both, a left adjoint and a right adjoint. Given L ∈ sup(set^{Cop}) we observe that for any f : B → C in C, the map ⋀_{f}^{DL}: DL(B) → DL(C) is given by

⋀_{f}^{DL}(G)(Z) = {(z, h)|(Le(z), d) ∈ GP with [figure: P; B; Z; C; d; e; f; h] a pullback}.

6.1. Theorem. A CCD lattice in set^{Cop} is a functor L: C^{op} → ccd(set) such that

i) The adjunctions ⋁_{f} ⊣ Lf, f ∈ C, satisfy Beck-Chevalley.

ii) L satisfies complete Frobenius reciprocity at every C ∈ C.

iii) For every f : B → C in C, there is an extra right adjoint ⋀_{f} ⊣ ⇑_{f}.

iv) For every A [figure: g]B [figure: f]C in C, and any a ∈ LA,

⋀_{f}⋁_{g}(a) ≤ ⋁{⋁_{h}⋀_{e}Ls(a)| [figure: g; s; d; e; f; h] in C with the square a pullback}.

Proof. Assume L is a CCD lattice in set^{Cop}. Then Lemma 4.1 tells us that LC is a CCD lattice for every C ∈ C. Since L is, in particular, a sup lattice, we have that Lf : LC → LB has left and right adjoints ⋁_{f} ⊣ Lf ⊣ ⋀_{f} for every f : B → C in C, and i) is also satisfied. Proposition 5.3 gives us ii) and Proposition 4.2 gives us iii). We are thus left with condition iv). Take a ∈ LA and f, g as shown in iv). Let c ∈ LC be the sup shown on the right hand side of the inequality in iv). We want to show that ⋀_{f}^{DL}(↓_{B} (a, g)) ≤ ↓_{C} c. But (z, h) ∈ ⋀_{f}^{DL}(↓_{B} (a, g))(Z) when there is an s: P → A such that Le(z) ≤ Ls(a) and d = gs, with

\xymatrix{P \ar[r]^{d} \ar[d]_{e} & B \ar[d]^{f} \\ Z \ar[r]_{h} & C}

a pullback diagram. But then z ≤ ⋀_{e}Ls(a), which implies that ⋁_{h}z ≤ ⋁_{h}⋀_{e}Ls(a) ≤ c. Thus z ≤ Lh(c). That is (z, h) ∈↓_{C} c. Since L is a CCD lattice, we have that ⇓⊣ ⋁: DL → L. Since the square

\xymatrix{LC \ar[r]^{⇓_{C}} \ar[d]_{Lf} & DL(C) \ar[d]^{DL(f)} \\ LB \ar[r]_{⇓_{B}} & DL(B)}

commutes, we obtain, by taking the right adjoints of the right adjoints of the arrows shown, that

\xymatrix{LC \ar[r]^{↓_{C}} \ar[d]_{⇑_{f}} & DL(C) \ar[d]^{⇑_{f}^{DL}} \\ LB \ar[r]_{↓_{B}} & DL(B)}

commutes. We have that ⋀_{f}^{DL}(↓_{C} c) = ⋃{G|⋀_{f}^{DL}(G) ≤↓_{C} c}, and since ⋀_{f}^{DL}(↓_{B} (a, g)) ≤↓_{C} c, we have that ↓_{B} (a, g) ≤↓_{B}⇑_{f} (c). In particular a ≤ Lg ⇑_{f} (c), which is equivalent to ⋀_{f}⋁_{g}a ≤ c, which is what we wanted.

Assume now that L: C^{op} → ccd(set^{Cop}) is such that conditions i) to iv) are satisfied. Clearly L is a sup lattice and Proposition 5.1 tells us that for every C ∈ C we have an adjunction Φ_{C} ⊣ ⋁_{C} : DL(C) → LC. We need to show that these left adjoints form a natural transformation. So take f : B → C in C. Since Lf⋁_{C} = ⋁_{B}DL(f) we immediately obtain Φ_{B}Lf ≤ DL(f)Φ_{C}. Thus we are left with showing the other inequality DL(f)Φ_{C} ≤ Φ_{B}Lf. Observe that by taking right adjoints twice, the inequality we need to prove is ⇑_{f}^{DL}↓_{C}≤↓_{B}⇑_{f}. Now, for any c ∈ LC we have

⇑_{f}^{DL}↓_{C} c = ⋃{G|⋀_{f}^{DL}(G) ≤↓_{C} c} = ⋃{↓_{B} (a, g)|⋀_{f}^{DL}(↓_{B} (a, g)) ≤↓_{C} c},

according to corollary 2.5. But the condition ⋀_{f}^{DL}(↓_{B} (a, g)) ≤↓_{C} c means that for any commutative diagram of the form

\xymatrix{ & A \ar[d]^{g} \\ P \ar[r]_{d} \ar[d]_{e} \ar[ur]^{s} & B \ar[d]^{f} \\ Z \ar[r]_{h} & C,}

with the square a pullback, if Le(z) ≤ Ls(a) then z ≤ Lh(c). Since, in particular, Le⋀_{e}Ls(a) ≤ Ls(a) (counit of the adjunction Le ⊣ ⋀_{e}), we have ⋀_{e}Ls(a) ≤ Lh(c), or ⋁_{h}⋀_{e}Ls(a) ≤ c. If we take the sup of all the possible elements on the left hand side and apply iv), we end up with ⋀_{f}⋁_{g}a ≤ c, or a ≤ Lg ⇑_{f} (c). This is equivalent to ↓_{B} (a, g) ≤↓_{B}⇑_{f} (c).

The question of the arrows in ccd(set^{Cop}) is quickly settled (see Lemmas 3.3 and 3.5). If L, M ∈ ccd(set^{Cop}), a morphism α: L → M is one that has a left as well as a right adjoint. These are characterized as 6.2. Proposition. A morphism α: L → M in ccd(set^{Cop}) is a natural transformation α: L → M : C^{op} → ccd(set) such for every f : B → C in C, the squares

\xymatrix{LB \ar[r]^{αB} \ar[d]_{_{⋁f}} & MB \ar[d]^{_{⋁f}} & LB \ar[r]^{αB} \ar[d]_{_{⋀f}} & MB \ar[d]^{_{⋀f}} \\ LC \ar[r]_{αC} & MC, & LC \ar[r]_{αC} & MC}

are commutative.

References

G. S. H. Cruttwell. A study of CCD lattices in a functor category. Master’s degree thesis. Dalhousie University 2005.

B. Fawcett and R. J. Wood. Constructive complete distributivity I. Math. Proc. Cambridge Philos. Soc. 107 (1990), 81–89.

A. Joyal and M. Tierney. An extension of the Galois theory of Grothendieck. Mem. Amer. Math. Soc. 51 (1984), no. 309,

R. Rosebrugh and R. J. Wood. Constructive complete distributivity II. Math. Proc. Cambridge Philos. Soc. 110 (1991), 245–249.

R. Rosebrugh and R. J. Wood. Constructive complete distributivity III. Canad. Math. Bull. Vol 35 (1992) no. 4 537-547.

R. Rosebrugh and R. J. Wood. Constructive complete distributivity IV. Appl. Categ. Structures 2 (1994) no.2, 119–144.

Department of Mathematics and Statistics, Dalhousie University Chase Building, Halifax, Nova Scotia, Canada B3H 3J5

Instituto de Matemáticas, Universidad Nacional Autónoma de México Área de la investigación científica, Circuito Exterior, Ciudad Universitaria Coyoacán 04510, México, D.F. México

Department of Mathematics and Statistics, Dalhousie University Chase Building, Halifax, Nova Scotia, Canada B3H 3J5

Email: cruttw@mathstat.dal.ca
      quico@matem.unam.mx
      rjwood@mathstat.dal.ca

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/18/6/18-06.{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: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)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 G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca