Theory and Applications of Categories, Vol. 24, No. 12, 2010, pp. 288–301.

LAX PRESHEAVES AND EXPONENTIABILITY

SUSAN NIEFIELD

Abstract. The category of Set-valued presheaves on a small category B is a topos. Replacing Set by a bicategory S whose objects are sets and morphisms are spans, relations, or partial maps, we consider a category Lax(B, S) of S-valued lax functors on B. When S = Span, the resulting category is equivalent to Cat/B, and hence, is rarely even cartesian closed. Restricting this equivalence gives rise to exponentiability characterizations for Lax(B, Rel) in [9] and for Lax(B, Par) in this paper. Along the way, we obtain a characterization of those B for which the category UFL/B is a coreflective subcategory of Cat/B, and hence, a topos.

1. Introduction

If B is a small category, then the category Set^{B} of functors B [figure] Set and natural transformations is a topos (c.f., [6]). But, what happens if we replace Set by the bicategories Rel, Par, and Span, whose objects are sets and morphisms are relations, partial maps, and spans, respectively? Given a bicategory S, we consider the categories Lax(B, S) and Pseudo(B, S) whose objects are lax functors and pseudo functors B [figure] S, respectively, and morphisms are function-valued op-lax transformation. We will see that Lax(B, S) is rarely cartesian closed, when S is Rel, Par, and Span, whereas Pseudo(B, Span) is often a topos, but rarely in the other two cases.

Although it appears that exponentiability in Lax(B, Span) has not explicitly been considered, Lax(B, Span) is known to be equivalent to the slice category Cat/B, and exponentiable objects in Cat/B were characterized independently by Giraud [5] and Conduché [4] as those functors satisfying a factorization lifting property, sometimes called the Giraud-Conduché condition. More recently, using the equivalence with Cat/B with category Lax(B, Prof) of normal lax functors B [figure] Prof and map-valued op-lax transformations, Street [11] showed that X [figure] B is exponentiable in Cat if and only if the corresponding lax functor is a pseudo functor. Inspired by Street’s note and a preprint of Stell [10] using lax functors B [figure] Rel to model data varying over time, we established an equivalence between Lax(B, Rel) and the full subcategory Cat_{f}/B of Cat/B consisting of faithful functors. Using this, we showed that a faithful functor p: X [figure] B is exponentiable if and only if the corresponding lax functor B [figure] Rel preserves composition up to isomorphism if and only if p satisfies a weak factorization lifting condition WFL [9].

Received by the editors 2008-09-09 and, in revised form, 2010-07-06.

Transmitted by Walter Tholen. Published on 2010-07-19.

2000 Mathematics Subject Classification: 18A22, 18A25, 18A40, 18B10, 18B25, 18D05, 18F20.

Key words and phrases: span, relation, partial map, topos, cartesian closed, exponentiable, presheaf.

\begin{matrix}c \\ ◯ \end{matrix} Susan Niefield, 2010. Permission to copy for private use granted.

We begin this paper, in Section 2, describing Lax(B, Par) as a category of variable sets, and then, in Section 3, obtain an equivalence with a full subcategory of Cat/B, by restricting that of Lax(B, Rel) and Cat_{f}/B. Necessary and sufficient conditions for exponentiability in Lax(B, Par) are presented in Section 4. In Section 5, we give a short and simple proof that Pseudo(B, Span) is a topos, whenever it is a coreflective subcategory of Lax(B, Span), and then show that this occurs precisely when B satisfies the interval glueing property IG defined in [3]. We conclude, in Section 6, by showing that Pseudo(B, Rel) is rarely a topos, and present conditions under which it is a cartesian closed coreflective subcategory of Lax(B, Rel). We do not consider the analogous question for Pseudo(B, Par) since, in this case, there are pseudo functors which are not exponentiable in Lax(B, Par).

Our interest in Pseudo(B, Span) began when Robin Cockett mentioned its equivalence to the full subcategory UFL/B of Cat/B consisting of functors satisfying the unique factorization lifting condition. In a 1996 talk [8], Lamarche had conjectured that UFL/B is a topos. Subsequently, Bunge and Niefield [3] showed that if B satisfies IG, then UFL/B is coreflective in Cat/B, and used this to show that UFL/B is a topos. Then Johnstone [7] showed that it is not a topos when B is a commutative square, and used sheaves to show that UFL/B is a topos when B satisfies certain cancellation and fill-in properties (CFI). Shortly thereafter, Bunge and Fiore gave an alternate sheaf-theoretic proof, using IG, and also showed that the conditions IG and CFI are, in fact, equivalent. Our theorem (see 5.5) shows that these conditions hold whenever UFL/B is coreflective in Cat/B, thus providing a converse to the Bunge and Niefield result from [3].

2. Lax functors as variable sets

In this section, we describe Lax(B, Par) as a category of relational variable sets on a small category B (in the sense of [9]).

Recall that a relational variable set or Rel-set is a lax functor X: B [figure] Rel. Thus, a Rel-set X consists of a set X_{b}, for every object b, and a relation X_{β}: X_{b}−↦X_{b′}, for every morphism β: b [figure] b′, satisfying Δ_{X_{b}} ⊆ X_{id_{b}}, for every object b, and X_{β′} ∘ X_{β} ⊆ X_{β′β}, for every composable pair. Writing x →_{β} x′ for (x, x′) ∈ X_{β}, these conditions become

(R1) x →_{id_{b}} x, for all x ∈ X_{b}.

(R2) x →_{β} x′, x′ →_{β′} x′′ ⟹ x →_{β′β} x′′.

A morphism f: X [figure] Y of Rel-sets consists of a function f_{b}: X_{b} [figure] Y_{b}, for every object b such that

[figure: X_{b′}; Y_{b′}; f_{b′}; X_{b}; X_{b′}; X_{β}; X_{b}; Y_{b}; f_{b}; Y_{b}; Y_{b′}; Y_{β}; ⊆; −; −]

for every morphism β: b [figure] b′, or equivalently, x →_{β} x′ implies f_{b}x →_{β} f_{b′}x′. Then Lax(B, Rel) denotes the category of Rel-sets and morphisms.

A lax functor X: B [figure] Par consists of a set X_{b}, for every object b, and a partial map X_{β}: X_{b} ⇀ X_{b′}, for every morphism β: b [figure] b′, such that id_{X_{b}} ≤ X_{id_{b}}, for object b, and X_{β′} ∘ X_{β} ≤ X_{β′β}, for every composable pair. Since a relation X_{β}: X_{b}−↦X_{b′} is a partial map if and only if X_{β} ∘X_{β}^{∘} ⊆ Δ_{X_{b′}}, it follows that a Rel-set X is a lax functor X: B [figure] Par if and only if it satisfies

(P3) x →_{β} x′_{1}, x →_{β} x′_{2} ⟹ x′_{1} = x′_{2}

Thus, Lax(B, Par) is the full subcategory of Lax(B, Rel) consisting of those Rel-sets which satisfy (P3).

3. Lax Functors and Subcategories of Cat/B

In [9], we showed that the well-known equivalence between Lax(B, Span) and Cat/B restricts to one between Lax(B, Rel) and the full subcategory Cat_{f}/B of Cat/B consisting of faithful functors over B. In particular, a faithful functor p: X [figure] B corresponds to a Rel-set, also denoted by X, and defined as follows. For each object b, X_{b} is the fiber of X over b, i.e., the set of objects x such that px = b. Given β: b [figure] b′, the relation X_{β} is defined by x →_{β} x′, if there is a morphism α: x [figure] x′ such that pα = β. Moreover, the product of X and Y in Lax(B, Rel) is given by (X × Y)_{b} = X_{b} × Y_{b} and

(x, y) →_{β} (x′, y′) ⟺ x →_{β} y and x′ →_{β} y′

Identifying Par with the subcategory of Rel consisting of morphisms R: X−↦Y with R ∘ R^{∘} ⊆ Δ_{Y}, it is not difficult to show that Lax(B, Par) is equivalent to the full subcategory Cat_{pf}/B of Cat/B consisting of faithful functors p: X [figure] B such that given

[figure: X; B; p; b; b′; β; x; x′_{1}; α_{1}; x; x′_{2}; α_{2}]

if p(α_{1}) = p(α_{2}) = β, then α_{1} = α_{2}, and Lax(B, Par) has finite products which agree with those of Lax(B, Rel).

4. Exponentiability in Categories of Lax Functors

A Rel-set X is exponentiable in Lax(B, Rel) if and only if X preserves composition, i.e., for every composable pair, the containment X_{β′} ∘ X_{β} ⊆ X_{β′β} is an equality if and only if the corresponding faithful functor p: X [figure] B has the weak factorization lifting condition (WFL)

[figure: X; B; p; px; b′; β; px; px′′; pα′′; px′′; b′; β′; x; x′; α; x; x′′; α′′; x′′; x′; α′]

i.e., given α′′ and a factorization pα′′ = β′β, there exists a factorization α′′ = α′α such that pα = β and pα′ = β′ [9]. Moreover, X: B [figure] Span is exponentiable in Lax(B, Span) if and only if the corresponding functor p: X [figure] B satisfies the Giraud-Conduché condition, i.e., WFL plus a connectivity condition on the objects over b′ through which α′′ factors [5, 4].

To establish a characterization of exponentiable objects in Lax(B, Par), we use its equivalence with Cat_{pf}/B as well as the description, given in 2.1, of X: B [figure] Par as a Rel-set satisfying (P3).

A functor p: X [figure] B will be called a partial fibration if it satisfies the lifting condition

[figure: X; B; p; b; px′; β; x; x′; α]

i.e, given x′ and β, there exists α such that pα = β. It is easy to show that a faithful functor is a partial fibration if and only if the associated lax functor X: B [figure] Rel satisfies Δ_{X_{b′}} ⊆ X_{β} ∘ X_{β}^{∘}, i.e., X_{β} is onto.

4.1. Theorem. The following are equivalent for a lax functor X: B [figure] Par with corresponding functor p: X [figure] B.

(a) X is exponentiable in Lax(B, Par).

(b) X is a functor and X_{β}: X_{b} ⇀ X_{b′} is onto, for all β: b [figure] b′.

(c) p is exponentiable in Cat_{pf}/B.

(d) p is a partial fibration satisfying the weak factorization lifting condition WFL.

Proof. We know (a) and (c) are equivalent, since Lax(B, Par) ≃ Cat_{pf}/B. The equivalence of (b) and (d) follows from the remarks above, the definition of WFL, and the fact that X_{id_{b}} = id_{X_{b}} in Lax(B, Par), for all b, since x_{1} →_{id_{b}} x_{2} implies x_{1} = x_{2} by (P3). Thus, it suffices to show that (b) ⇒ (a) and (c) ⇒ (d).

For (b) ⇒ (a), suppose X is a functor and X_{β} is onto, for all β: b [figure] b′. Then X is exponentiable in Lax(B, Rel). Thus, given Y: B [figure] Par, it suffices to show that the exponential Rel-set Y^{X} is an object of Lax(B, Par), i.e., satisfies (P3), where Y^{X} is defined as follows [9]. Let (Y^{X})_{b} denote the set of functions σ: X_{b} [figure] Y_{b}, and define σ →_{β} σ′ if σx →_{β} σ′x′, for all x →_{β} x′ in X.

To see that Y^{X} satisfies (P3), suppose σ →_{β} σ′_{1}, σ →_{β} σ′_{2}, and x′ ∈ X_{b′}. Then x →_{β} x′, for some x ∈ X_{b}, since X_{β} is onto, and so σx →_{β} σ′_{1}x′ and σx →_{β} σ′_{2}x′. Thus, σ′_{1}x′ = σ′_{2}x′, since Y satisfies (P3), and it follows that σ′_{1} = σ′_{2}. Therefore, X is exponentiable in Lax(B, Par).

For (c) ⇒ (d), suppose p is exponentiable in Cat_{pf}/B. Then the elements σ of the fiber (Y^{X})_{b} can be identified with the functions X_{b} [figure] Y_{b}, since

[figure: 1; B; b; 1; Y^{X}; σ; Y^{X}; B; q^{p}; 1 ×_{B} X; B; b×p; 1 ×_{B} X; Y; Y; B; q; X_{b}; B; b; X_{b}; Y; Y; B; q; ⟷; ⟷]

Moreover, every morphism σ [figure] σ′ over β satisfies σx [figure] σ′x′, for all x [figure] x′ over β, since the counit is the evaluation functor ε: Y^{X} ×_{B} X [figure] Y, under this identification.

To see that p satisfies WFL, suppose α′′: x [figure] x′′ in X and pα′′ = β′β, where β: px [figure] b′ and β′: b′ [figure] px′′. Then the composite β′β gives rise to a pushout in Cat_{pf}/B of the form

[figure: 2; 3; 1; 2; 1; 1; 2; 0; 2; 3; 3; B; 2; B; β; 2; B; β′]

where 2 and 3 are the categories 0 [figure] 1 and 0 [figure] 1 [figure] 2, respectively. Since − × p preserves pushouts (as it has a right adjoint), it follows that the corresponding diagram

[figure: 2 ×_{B} X; 3 ×_{B} X; 1 ×_{B} X; 2 ×_{B} X; 1 ×_{B} X; 2 ×_{B} X; 2 ×_{B} X; 3 ×_{B} X; 3 ×_{B} X; B; 2 ×_{B} X; B; 2 ×_{B} X; B]

is a pushout in Cat_{pf}/B. The pushout P [figure] B of this diagram can be constructed as follows. Let X_{β} and X_{β′} denote the subcategories of X obtained by identifying p × β and p × β′ with their images in X. Then the objects of P are the union of those of X_{β} and X_{β′}, and the morphisms are those of X_{β} and X_{β′} together with pairs (α, α′): x [figure] x′′ such that α: x [figure] x′ in X_{β} and α′: x′ [figure] x′′ in X_{β′}, subject to an appropriate equivalence relation. Since α′′: x [figure] x′′ corresponds to a morphism of 3 ×_{B} X, and hence one of P over β′β, the desired factorization of α′′ follows.

It remains to show that p is a partial fibration. Suppose x′ is in X and β: b [figure] px′ in B. Let Y denote the category

[figure: y_{1}; y′_{1}; γ; y′_{2}]

with q: Y [figure] B given by qγ = β and qy′_{2} = px′. Let σ ∈ (Y^{X})_{b} denote the constant y_{1}-valued map, σ′_{1} ∈ (Y^{X})_{px′} the constant y′_{1}-valued map, and σ′_{2} ∈ (Y^{X})_{px′} the function

σ′_{2}x̂′ = \{ \begin{matrix}y′_{1} & if x̂′ ∈ Image(X_{β}) \\ y′_{2} & otherwise \end{matrix}

Thus, for i = 1, 2, we have x̂ [figure: β] x̂′ implies σx̂ [figure: β] σ′_{i}x̂′, and so σ [figure: β] σ′_{i}, and we get a diagram

[figure: Y^{X}; B; b; px′; β; σ; σ′_{1}; σ; σ′_{2}]

Since Y^{X} [figure] B satisfies (P3), it follows that σ_{1} = σ_{2}. Thus, X_{b′} = Image(X_{β}), and so there exists α: x [figure] x′ such that pα = β, to complete the proof.

4.2. Corollary. The inclusion Lax(B, Par) [figure] Lax(B, Rel) preserves exponentiability and exponentials.

Proof. Since the exponentials Y^{X} defined in the proof of (b)⇒(a) agree with those of Lax(B, Rel) given in [9] when X satisfies WFL, the desired result follows.

5. Pseudo(B, Span) and UFL/B

Since every pseudo functor X: B [figure] Span is exponentiable in Lax(B, Span), one might conjecture that Pseudo(B, Span) is cartesian closed. As noted in the introduction, this is not the case when B is a commutative square [7] since

Pseudo(B, Span) ≃ UFL/B

where the latter is the full subcategory of Cat/B consisting of functors satisfying the unique factorization lifting property UFL, i.e., the condition WFL given in Section 4 plus uniqueness of the lifted factorization. However, UFL/B is a topos which is coreflective in Cat/B, if B satisfies a condition called the interval glueing condition (IG) in [3]. The proof in [3] makes extensive use of (IG), and one in [7] exhibits UFL/B as a topos of sheaves, using a condition equivalent to (IG). In the following, we show that UFL/B is a topos, assuming only that it is coreflective in Cat/B. Although this appears to be a more general theorem than that of [3] and [7], we will see that coreflectivity of UFL/B in Cat/B is, in fact, equivalent to (IG), thus proving the converse of the result in [3].

5.1. Lemma. Suppose Y is a category with finite products and X [figure] Y is a product preserving inclusion of a coreflective subcategory. If X is an object of X which is exponentiable in Y, then X is exponentiable in X.

Proof. Given Y ∈ X, then Ŷ^{X} is the exponential in X, where denotes the coreflection, since X(W × X, Y) ≅ Y(W × X, Y) ≅ Y(W, Y^{X}) ≅ X(W, Ŷ^{X}).

5.2. Theorem. If UFL/B is a coreflective subcategory of Cat/B, then UFL/B is a topos.

Proof. A straightforward calculation shows that the inclusion UFL/B [figure] Cat/B preserves products, and so UFL/B is cartesian closed by Lemma 5.1. To see that it is a topos, let Ω denote the UFL subobject classifier in Cat [3]

[figure: ·; ·; ·; ·; ·]

and consider Ω × B [figure]B via the projection. Then Sub_{UFL/B}(X) ≅ Sub_{UFL}(X) ≅ Cat(X, Ω) ≅ Cat/B(X, Ω × B) ≅ UFL/B(X, Ω̂ × B), for all X [figure] B in UFL/B.

5.3. Corollary. If Pseudo(B, Span) is a coreflective subcategory of Lax(B, Span), then Pseudo(B, Span) is a topos.

Proof. Since Pseudo(B, Span) ≃ UFL/B, the desired result follows.

Given β: b [figure] b′ in B, consider the category [[β]] over B whose objects are factorizations

[figure: b; ·; β_{1}; b; b′; β; b′; ·; β_{2}]

morphisms are commutative diagrams

[figure: b; ·; β̄_{1}; ·; b; β_{1}; ·; ·; γ; b′; ·; β̄_{2}; ·; b′; β_{2}; ·; ·]

and projection to B takes the factorization β = β_{2}β_{1} to the codomain of β_{1}, or equivalently, the domain of β_{2}. Then we say B satisfies IG if the induced diagram

[figure: [[β]]; [[β′β]]; [[id_{b′}]]; [[β]]; [[id_{b′}]]; [[β′]]; [[β′]]; [[β′β]]; (∗)]

is a pushout in Cat, for all b [figure: β] b′ [figure: β′] b′′.

5.4. Lemma. The diagram (*) is a pushout in UFL/B, for all b [figure: β] b′ [figure: β′] b′′.

Proof. Suppose p: X [figure] B is a UFL and we are given a commutative diagram

[figure: [[β]]; [[β′β]]; [[id_{b′}]]; [[β]]; [[id_{b′}]]; [[β′]]; [[β′]]; [[β′β]]; X; f; X; f′]

over B. Applying f and f′ to the diagrams

[figure: b; b′; β; b; b; id_{b}; b; b′; β; b′; b′; id_{b′}; b; b′; β; b; b′; b′; b′′; β′; b′; b′; id_{b′}; b′; b′′; β′; b′′; b′′; id_{b′′}; b′; b′′; β′; b′; b′′]

gives morphisms α and α′ of X over β and β′, respectively, and these morphisms are composable by the commutativity of the diagram. Thus, we get a morphism α′α over β′β

[figure: X; B; p; b; b′; β; b; b′′; β′β; b′′; b′; β′; x; x′; α; x; x′′; α′α; x′′; x′; α′]

To define g: [[β′β]] [figure] X over B, suppose β′β = β_{2}β_{1} is an object of [[β′β]], and take g(β_{2}β_{1}) to be the codomain of α_{1}, where α′α = α_{2}α_{1} is the unique lifting of the factorization β′β = β_{2}β_{1}. Given a morphism

[figure: b; ·; β̄_{1}; ·; b; β_{1}; ·; ·; δ; b′′; ·; β̄_{2}; ·; b′′; β_{2}; ·; ·]

of [[β′β]], let α′α = ᾱ_{2}ᾱ_{1} be the unique lifting of β′β = β̄_{2}β̄_{1} and ᾱ_{1} = γ_{2}γ_{1} be the unique lifting of β̄_{1} = δβ_{1}. Thus, we get a diagram

[figure: x; ·; ᾱ_{1}; ·; x; γ_{1}; ·; ·; γ_{2}; x′′; ·; ᾱ_{2}; ·; x′′; ᾱ_{2}γ_{2}; ·; ·]

Then α_{1} = γ_{1} and α_{2} = ᾱ_{2}γ_{2}, by uniqueness of the factorization α′α = α_{2}α_{1}, and we can take γ_{2} to be the morphism g(δ): g(β_{2}β_{1}) [figure] g(β̄_{2}β̄_{1}). To establish the uniqueness of g, one shows that for any other such morphism ḡ the commutativity of the triangles implies that ḡ(β′β) = α′α, and so g = ḡ, by uniqueness of factorizations of α′α over β′β.

5.5. Theorem. UFL/B is coreflective in Cat/B if and only if B satisfies IG.

Proof. Suppose UFL/B is coreflective in Cat/B and b [figure: β] b′ [figure: β′] b′′. Then (*) is a pushout in UFL/B by Lemma 5.4, and hence, in Cat/B, since the inclusion preserves pushouts being a left adjoint. Thus, (*) is a pushout in Cat, and it follows that B satisfies IG, as desired. The converse holds by Proposition 3.2 and (the proof of) Lemma 4.3 of [3].

Applying the equivalence Pseudo(B, Span) ≃ UFL/B, gives:

5.6. Corollary. Pseudo(B, Span) is coreflective in Lax(B, Span) if and only if B satisfies IG.

Although IG works well in the proof of Theorem 5.5, the equivalent condition, called CFI in [2], is a good source of examples. This condition consists of two parts, namely, cancellation: given a diagram

[figure: ·; ·; f; ·; ·; g; ·; ·; h; ·; ·; k]

in B such that gf = hf and kg = kh, then g = h, and fill in: given a commutative square

[figure: c; d; k; a; c; h; a; b; f; b; d; g]

in B, there exists a morphism b [figure] c or c [figure] b making the diagram commute. Thus, Theorem 5.5 does not apply to the following two simple examples. A commutative square B does not satisfy the fill-in property, and cancellation fails in the category B with one object and a single non-identity idempotent morphism. Johnstone [7] showed that UFL/B (and hence, Pseudo(B, Span)) is not cartesian closed in the former case and the following example does so in the latter.

5.7. Example. Let B denote the category

[figure: b; β]

with one non-identity idempotent morphism β. Then the discrete category X = {0} over B is not exponentiable, since the following shows that Y^{X} does not exist when Y = {y_{1}, y_{2}} is the discrete category with two objects. One can show that Y^{X} = {σ_{1}, σ_{2}}, where σ_{i} is the constant y_{i}-valued map, and there is a (unique) morphism σ_{i} [figure] σ_{j} over β, for all i, j, since 0 has no endomorphisms over β. Thus, we have a diagram

[figure: σ_{1}; σ_{2}; σ_{1}; σ_{2}]

over β, contradicting the uniqueness of the lifting of the factorization β = β^{2}. Thus, UFL/B, and hence, Pseudo(B, Span), is not cartesian closed.

6. Pseudo(B, Rel)

As in the case of Span, every object of Pseudo(B, Rel) is exponentiable in Lax(B, Rel), and so one might conjecture that Pseudo(B, Rel) is cartesian closed. However, we will see that, unlike Pseudo(B, Span), it is not often a topos, since every topos is balanced, i.e., every morphism which is both a monomorphism and an epimorphism is necessarily an isomorphism [6].

6.1. Example. Let B be any category with no non-trivial retractions. If |B| denotes the discrete category with the same objects as B, then the Rel-set corresponding to the inclusion i: |B| [figure] B is a pseudo functor. Consider the diagram

[figure: |B|; B; i; B; X; f; B; X; g; B; B; id_{B}; |B|; B; X; B; p]

Now, i is an epimorphism, since fi = gi implies f = g, whenever p is faithful. Since i is clearly a monomorphism which is not an isomorphism in Cat_{f}/B, it follows that Pseudo(B, Rel) is not a topos.

6.2. Theorem. If Pseudo(B, Rel) is a coreflective subcategory of Lax(B, Rel), then Pseudo(B, Rel) is cartesian closed.

Proof. Since the inclusion Pseudo(B, Rel) [figure] Lax(B, Rel) preserves products, we can apply Lemma 5.1 to obtain the desired result.

Unfortunately, it is not possible to show that coreflectivity is equivalent to B satisfying condition IG, as it is in the case of Span, though we will see that IG is sufficient for a certain class of categories. In fact, IG is not necessary as only one of the non-cartesian closed examples carries over from Section 5. In particular, since every subobject of 1 in Pseudo(B, Rel) corresponds to a UFL subobject in Cat/B, Johnstone’s example [7] applies, and so Pseudo(B, Rel) is not cartesian closed when B is a commutative square. However, the following corollary shows this is not the case for Example 5.7.

6.3. Corollary. If B is the category

[figure: b; β]

with one non-identity idempotent morphism β, then Pseudo(B, Rel) is coreflective in Lax(B, Rel), and hence, is cartesian closed.

Proof. Let I_{b} = \{\frac{a}{2^{n}} | n ≥ 1, 0 ≤ a ≤ 2^{n}\} with

\frac{a}{2^{n}} →_{β} \frac{a′}{2^{n′}} ⟺ \frac{a}{2^{n}} < \frac{a′}{2^{n′}}

and let M denote the pseudo functor corresponding to the category over B with morphisms over β given by

[figure: 0; m; m; m; 1]

Then, given a pseudo functor X: B [figure] Rel, one can show that x →_{β} x′ in X if and only if there is a morphism f: I [figure] X or f: M [figure] X such that f(0) = x and f(1) = x′. If X is a lax functor, we call this property of an arrow x →_{β} x′, the pseudo functor property. Note that this property is hereditary, in the sense that, if x →_{β} x′ satisfies the property, then so do the other morphisms in the image of corresponding f.

Given a lax functor X: B [figure] Rel, let X̂ denote the Rel-set with the same elements as X and the following relations. Let X̂_{id_{b}} = ΔX̂_{b} and X̂_{β} denote the set of (x, x′) ∈ X_{β} satisfying the pseudo functor property. Then it is not difficult to show that

Lax(B, Rel) [figure: ]Pseudo(B, Rel)

is right adjoint to the inclusion, giving the necessary coreflection to apply Theorem 6.2, and it follows that Pseudo(B, Rel) is cartesian closed.

To apply Theorem 6.2 when B satisfies IG, we first construct a cartesian closed subcategory Cat_{f}/B, and then establish conditions on B making this category equivalent to Pseudo(B, Rel), using the following lemma.

6.4. Lemma. Suppose B is a category satisfying IG and the only isomorphisms are the identity morphisms. Then [[β]] is a totally ordered set, for every morphism β: b [figure] b′.

Proof. Suppose

[figure: b; ū; β̄; u; b; β; u; ū; b′; ū; β̄′; u; b′; β′; u; ū]

are objects of [[β]]. Then, since B satisfies the fill-in property, there is a morphism u [figure] ū or ū [figure] u of the corresponding factorizations in [[β]], and not more than one, since B has no non-identity isomorphisms and satisfies the cancellation property. Thus, [[β]] is totally ordered.

6.5. Corollary. Suppose B satisfies IG, has no non-identity isomorphisms, and [[β]] is finite, for all β in B. Then Pseudo(B, Rel) is a coreflective cartesian closed subcategory of Lax(B, Rel).

Proof. We will show that Pseudo(B, Rel) is equivalent to a cartesian closed coreflective subcategory C of Cat_{f}/B.

Given a faithful functor p: X [figure] B, let X̂ denote the subcategory of X with the same objects and those morphisms α: x [figure] x′ over β for which there is a commutative diagram

[figure: [[β]]; B; [[β]]; X; f_{α}; X; B; p]

such that f_{α}(b [figure: id_{b}]b [figure: β] b′) = x and f_{α}(b [figure: β] b′ [figure: id_{b′}]b′) = x′. Note that X̂ is closed under composition, since IG says that

[figure: [[β]]; [[β′β]]; [[id_{b′}]]; [[β]]; [[id_{b′}]]; [[β′]]; [[β′]]; [[β′β]]; (∗)]

is a pushout in Cat, for every composable pair. Thus, we get a commutative diagram

[figure: X̂; B; p̂; X̂; X; i_{X}; X; B; p]

in Cat_{f}/B. Let C denotes the full subcategory of Cat_{f}/B consisting of p: X [figure] B such that X̂ = X.

To see that C is coreflective in Cat_{f}/B, it suffices to show that ˆ X̂ = X̂, for all p: X [figure] B

in Cat_{f}/B. To do so we will show that every α: x [figure] x′ of X̂ is in ˆ X̂ by showing that the image of f_{α}: [[β]] [figure] X over β is contained in X̂. Given a morphism

[figure: b; ū; β̄_{1}; u; b; β_{1}; u; ū; γ; b′; ū; β̄_{2}; u; b′; β_{2}; u; ū]

of [[β]], there is a functor i: [[γ]] [figure] [[β]] given by precomposition with β_{1} and postcomposition

with β̄_{2}, and using [[γ]] [figure: i] [[β]] [figure: f_{α}]X, it is not difficult to show that f_{α}(γ) ∈ X̂.

Now, every object of C is exponentiable in Cat_{f}/B, i.e., p̂ satisfies WFL, since given α′′: x [figure] x′′ in X̂ such that pα′′ = β′β, the morphism f_{α′′}: [[β′β]] [figure] X induces a factorization of α′′ via the diagram (*). Since the inclusion preserves products and every object of C is exponentiable in Cat_{f}/B being a WFL, applying Lemma 5.1, we see that C is cartesian closed.

It remains to show that Pseudo(B, Rel) is equivalent to C, i.e., the objects of C are precisely the faithful WFL with discrete fibers. We already know that p̂ satisfies the first two conditions, and the fibers of p̂ are discrete, since [[id_{b}]] has one element (as the cancellation property implies that every element corresponds to an isomorphism). Thus it suffices to show that every faithful WFL p: X [figure] B with discrete fibers is in C.

Suppose α: x [figure] x′ is in X and pα = β. To show α is in X̂, we will define f_{α}: [[β]] [figure] X

over B such that f_{α}(b [figure: id_{b}]b [figure: β] b′) = x and f_{α}(b [figure: β] b′ [figure: id_{b′}]b′) = x′. Applying Lemma 6.4, we

see that [[β]] is totally ordered. Since [[β]] is finite, it sits over b [figure: β_{1}] u_{1} [figure: γ_{1}]… [figure: γ_{n−1}]u_{n} [figure: β′_{n}]b′ in B, and we have commutative diagrams

[figure: b; u_{i}; u_{i}; b′; b; b; id_{b}; b; u_{i}; β_{i}; b; b′; β; b; u_{i}; β_{i}; b; b′; β; u_{i}; b′; β′_{i}; u_{i}; b′; β′_{i}; b′; b′; id_{b′}; b; u_{i+1}; β_{i+1}; u_{i}; b; β_{i}; u_{i}; u_{i+1}; γ_{i}; b′; u_{i+1}; β′_{i+1}; u_{i}; b′; β′_{i}; u_{i}; u_{i+1}]

Since α: x [figure] x′ and pα = β = β′_{1}β_{1}, using the fact that p is a WFL, we get a factorization

x [figure: α_{0}]x_{1} [figure: α′_{1}]x′ of α over β = β′_{1}β_{1}. Similarly, since pα′_{1} = β′_{1} = β′_{2}γ_{1}, we get a factorization

x [figure: α_{0}] x_{1} [figure: α_{1}] x_{2} [figure: α′_{2}] x′ of α over β = β′_{2}γ_{2}β_{1}. Continuing, we get x [figure: α_{0}] x_{1} [figure: α_{1}]… [figure: α_{n−1}]x_{n} [figure: α_{n}] x′ of α over β = β′_{n}γ_{n−1} … γ_{1}β_{1}, and hence, the desired morphism f_{α}: [[β]] [figure] X over B.

Note that if B and B′ are any equivalent categories, one can show that Pseudo(B, Rel) and Pseudo(B′, Rel) are equivalent as well, but the same is not the case for the corresponding categories of lax functors. Thus, it turns out that to show that Pseudo(B, Rel) is cartesian closed (but not necessarily coreflective in Lax(B, Rel)), we need only assume that B has no non-trivial automorphisms rather than isomorphisms.

6.6. Corollary. If B satisfies IG, has no non-trivial automorphisms, and [[β]] is finite, for all β in B, then Pseudo(B, Rel) is cartesian closed.

Proof. Since B is equivalent to a skeletal category satisfying the hypotheses of Corollary 6.5, the desired result follows.

References

[1] J. Benabou, Introduction to bicategories, Springer Lecture Notes in Math. 47 (1967), 1–77.

[2] M. C. Bunge and M. P. Fiore, Unique factorization lifting and categories of processes, Math. Str. Comp. Sci. 10 (2000) 137–163.

LAX PRESHEAVES AND EXPONENTIABILITY  301

[3] M. C. Bunge and S. B. Niefield, Exponentiability and single universes, J. Pure Appl. Alg. 148 (2000), 217–250.

[4] F. Conduché, Au sujet de l’existence d’adjoints à droite aux foncteurs “image réciproque” dans la catégorie des catégories, C. R. Acad. Sci. Paris 275 (1972), A891–894.

[5] J. Giraud, Méthode de la déscente, Bull. Math. Soc. France, Mem. 2 (1964).

[6] P. T. Johnstone, Topos Theory, Academic Press, 1977.

[7] P. T. Johnstone, A note on discrete Conduché fibrations, Theory Appl. Categ. 5 (1999), 1–11.

[8] F. Lamarche, A new kind of fibration, talk at Peripatetic Seminar on Sheaves and Logic, Utrecht, October 1996.

[9] S. B. Niefield, Change of base for relational variable sets, Theory Appl. Categ. 12 (2004), 248–261.

[10] J. G. Stell, Granularity in change over time, in: Duckham, M., Goodchild, M., and Worboys, M. Foundations of Geographic Information Science, Taylor and Francis (2003) 95–115.

[11] R. Street, Powerful functors, expository note (2001).

Union College Department of Mathematics Schenectady, NY 12308

Email: niefiels@union.edu

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/24/12/24-12.{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, Cuill Inc.: valeria@cuill.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Tom Leinster, University of Glasgow, T.Leinster@maths.gla.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.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