An adjoint characterization of the category of sets

Robert Rosebrugh^{∗}

Department of Mathematics and Computer Science

Mount Allison University Sackville, N. B. E0A 3C0 Canada

R. J. Wood^{∗}

Department of Mathematics, Statistics and Computing Science Dalhousie University

Halifax, N. S. B3H 3J5 Canada

Abstract

If a category B with Yoneda embedding Y : B ⟶ CAT(B^{op}, set) has an adjoint string, U ⊣ V ⊣ W ⊣ X ⊣ Y, then B is equivalent to set.

∗The authors gratefully acknowledge financial support from NSERC Canada. Diagrams typeset using M. Barr’s diagram macros.

1 Introduction

The statement of the Abstract was implicitly conjectured in [9]. Here we establish the conjecture. We will see that it suffices to assume that B has an adjoint string V ⊣ W ⊣ X ⊣ Y with V pullback preserving.

A word on foundations and our notation is necessary. We write set for the category of small sets and assume that there is a Grothendieck topos, SET, of sets which contains the set of arrows of set as an object. The 2-category of category objects in SET, which we write CAT, is cartesian closed and set is an object of CAT. Thus, for C a category in CAT, CAT(C^{op}, set) is also an object of CAT and we abbreviate it by MC, (it was written PC in [8].) Substitution gives a 2-functor M : CAT^{coop} ⟶ CAT where CAT^{coop} is the dual which reverses both arrows of CAT (functors) and 2-cells (natural transformations.) A category B in CAT is said to be locally small if it has a hom functor B^{op} × B ⟶ set, or equivalently a Yoneda embedding Y = Y_{B} : B ⟶ MB. We say that a category A is small if the set of arrows of A is an object of set. All categories under consideration, other than SET and CAT, are objects of CAT.

A functor F : A ⟶ B is said to be Kan if MF : MB ⟶ MA has a left adjoint, denoted ∃F. If A is small and B is locally small then F is Kan, [8], but neither condition is necessary: if, say, we have L ⊣ F then ML ⊣ MF and ∃F ≅ ML. Smallness of A and local smallness of B also ensures that MF has a right adjoint, which we denote by ∀F. In particular, for small A the Yoneda embedding Y_{A} : A ⟶ MA yields ∃(Y_{A}) ⊣ M(Y_{A}) ⊣ ∀(Y_{A}) : MA ⟶ MMA and it is shown in [8] that ∀(Y_{A}) is isomorphic to Y_{MA}. We can apply these considerations to A = 0, the empty category, which is the initial object of CAT. The unique functor 0 ⟶ M0 = 1 is necessarily Y_{0} and gives rise to ∃(Y_{0}) ⊣ M(Y_{0}) ⊣ Y_{1} : 1 ⟶ M1. But M1 is isomorphic to set and 1 is terminal in CAT so the adjoint string is more conveniently labelled 0 ⊣ ! ⊣ 1 : 1 ⟶ set. A further application of the result quoted from [8] gives an adjoint string of the kind mentioned in the Abstract, namely

∃0 ⊣ M0 ⊣ M! ⊣ M1 ⊣ Y_{set} : set ⟶ Mset.

We recall from [8] or [9] that a locally small category B is said to be total (abbreviating totally cocomplete) if Y : B ⟶ MB has a left adjoint, X. Considerable motivation for the terminology is given in either reference. Examples include categories of algebras, categories of spaces and categories of sheaves on a Grothendieck site. The reader is advised to keep in mind the situation when B is an ordered set and Y is replaced by its counterpart ↓ in the 2-category, ord, of ordered sets, order-preserving functions and transformations. There ↓: B ⟶ DB sends an element b to the down-closed subset of B consisting of all x such that x ≤ b. (DB is the lattice of all down-closed subsets of B ordered by inclusion.) This functor has a left adjoint, namely supremum, ⋁, precisely when B is (co)complete. It is helpful to think of X above as a generalization of ⋁ . Continuing the analogy, we recall from [1] that ⋁ has a left adjoint precisely when B is (constructively) completely distributive. With this in mind we say that a total category is totally distributive when it has an adjoint string, W ⊣ X ⊣ Y : B ⟶ MB. The considerations in the previous paragraph show that MA is totally distributive for small A.

In the ord case a left adjoint for ⋁ classifies the ≪, or “totally below”, relation defined by b ≪ b′ if and only if, for any D in DB, b′ ≤ ⋁ D implies b ∈ D. A similar interpretation is possible for W. Its transpose, B^{op} × B ⟶ set, is in some respects like another hom functor. At least it makes good sense to think of its values as sets of “arrows”, a priori distinct from the arrows of B. A left adjoint, V, for W expresses a universal property with respect to the new arrows and if this colimit-like functor itself has a left adjoint then ordinary limits also distribute over these colimit-like universals.

The point of the heuristics of the preceding paragraph is that the adjoint strings we are considering are manifestations of “exactness”. Given a suitably complete and cocomplete category B it seems possible, ab initio, that B be more distributive than set. The Theorem of this paper shows that this is not the case. Exactness of a locally small category is strictly bounded by the exactness of set. Note further that while total categories B can fail to be cototal (that is, B^{op} can fail to be total), totally distributive categories are always cototal. This and a detailed study of the heuristics above will appear in a separate forthcoming paper.

2 The adjoint characterization

Let B be a totally distributive category with adjoint string W ⊣ X ⊣ Y : B ⟶ MB. We write α, β : X ⊣ Y to indicate that α is the unit and β is the counit for the adjunction. Since Y is fully faithful, β is an isomorphism and X is cofully faithful i. e. CAT(X, C) is fully faithful for all C. We write γ, δ : W ⊣ X for the other adjunction. Cofully faithfulness of X implies that the unit, γ, is an isomorphism and so W is fully faithful. We define σ : W ⟶ Y to be the unique natural transformation satisfying Xσ·γ = β^{−1}. Equivalently, σ is the unique solution of β·Xσ = γ^{−1}. We write I : E ⟶ B for the inverter of σ : W ⟶ Y : B ⟶ MB, i. e. E is the full subcategory of B determined by those B for which σ_{B} is an isomorphism. I is the resulting inclusion. For any functor F : C ⟶ D with D(F C, D) in set for all C, D and for any G : K ⟶ D, we follow Street and Walters, [8], in writing D(F, G) : K ⟶ MC for the functor whose value at K in K is D(F −, GK). If D is locally small, D(F, G) is the composite

K ⟶^{G} D ⟶^{Y} MD ⟶^{MF} MC.

Further, still assuming that D is locally small, and for any H : K ⟶ MD, the Yoneda Lemma gives MD(Y F, H) ≅ MF · H even though MD need not be locally small.

Lemma 1 A category B is equivalent to one of the form MA with A small if and only if B is totally distributive and the inverter I, as above, is dense and Kan.

Proof. (only if) We have already remarked that MA is totally distributive for small A. Here E is the Cauchy completion of A. (Since this part of the Lemma is not central to our present concerns we leave the proof of this claim as an exercise for the reader. In the ord case it is discussed in [5].) It is easy to see that I is dense and Kan.

(if) Given B and I as above, consider the composite

B ⟶^{Y} MB ⟶^{MI} ME = B(I, 1_{B}).

Since Y and MI have left adjoints, namely X and ∃I respectively, so does B(I, 1). We denote the left adjoint by I ⋆ – , since its value at Γ in ME, I ⋆ Γ, is the colimit of I weighted by Γ [8]. The unit for I ⋆ – ⊣ B(I, 1) is an isomorphism since I is dense. The following isomorphisms are justified by (in order): definition of I ⋆ – , W ⊣ X, σ is inverted by I, the Yoneda lemma and fully faithfulness of ∃I (which follows from fully faithfulness of I).

B(I, I ⋆ Γ) ≅ B(I, (X ·∃I)(Γ)) ≅ MB(W I, ∃I(Γ)) ≅ MB(Y I, ∃I(Γ)) ≅ (MI ·∃I)(Γ) ≅ Γ.

Thus B(I, 1) : B ⟶ ME is an equivalence. Since both E and now ME are locally small it follows from [7] (see also [2]) that E is small as required.

If C and D are total then a functor F : C ⟶ D preserves all colimits if and only if it has a right adjoint. If, moreover, F is Kan then preservation of all colimits is equivalent to invertibility of the canonical natural transformation X_{D}∃F ⟶ F X_{C} as shown in the left hand diagram below.

[figure: C; D; F; MC; MD; ∃F; X_{C}; X_{D}; C; MD; F; MC; MMD; ∃F; X_{C}; MY_{D}; ≅; ≅]

Again, the reader is advised to think of “X” as a general counterpart of the supremum arrow for a complete ordered set. Now replace D in the immediately preceding discussion by MD, where D is an arbitrary locally small category. According to our definition of total category and again invoking [7] (or [2]) MD is total if and only if D is small. But we do have MY_{D} assuming only that D is locally small. If F is both Kan and a left adjoint then a canonical isomorphism as in the right hand diagram is produced by a modification of the calculations which establish that the canonical arrow in the left hand diagram is an isomorphism. Of course we implicitly noted in the Introduction that if D is small then MY_{D} ≅ X_{MD}. The point is that for D locally small, MD has the requisite weighted colimits and they are provided by MY_{D}.

Let B be a totally distributive category with V ⊣ W. Then W : B ⟶ MB is both Kan and a left adjoint. The considerations of the previous paragraph show that W X ≅ MY ·∃W. Since W is fully faithful, XW ≅ 1_{B} and we have MY·∃W·W ≅ W. (This is a formulation for totally distributive categories of the “Interpolation Lemma” for constructively completely distributive lattices as in [5].) Now a calculation shows that the natural isomorphism above, MY · ∃W · W ⟶^{≅} W, admits description by both

[figure: MY ·∃W ·W; MY ·∃Y ·W; MY ·∃σ·W; ≅ W; and; MY ·∃W ·W; MY ·∃W ·Y; MY ·∃W ·σ; ≅ W ·X ·Y ≅ W,]

where both the first and last un-named isomorphisms express the fully faithfulness of Y and the second un-named isomorphism is an instance of MY ·∃W ≅ W X. These descriptions show that the profunctor B \overline{}B determined by W : B ⟶ MB carries an idempotent comonad structure, with counit determined by σ : W ⟶ Y. It is convenient to define T = V Y : B ⟶ B. Then

MY ·∃W ·σ ≅ MY ·MV ·σ ≅ M(V Y)·σ ≅ MT ·σ

which shows that MT coinverts σ. By Lemma 4.3 of [4], T inverts σ.

Lemma 2 A category B is equivalent to one of the form MA with A a small, complete ordered set if and only if B is totally distributive with V ⊣ W.

Proof. (only if) A small, complete ordered set, A, is a total category. Indeed, by definition ↓_{A} : A ⟶ DA has a left adjoint. So does the inclusion DA ⟶ MA and its composite with ↓_{A} is Y : A ⟶ MA, which therefore has a left adjoint. It follows that MA has the required adjoint string.

(if) We saw above that T = V Y inverts σ : W ⟶ Y. We denote the inverter I : E ⟶ B as above, so there exists a unique functor H : B ⟶ E such that IH = T. We show H ⊣ I by showing that E(H, 1) ≅ B(1, I). Now

B(1, I) ≅ Y I ≅ W I ≅ MB(Y, W I) ≅ B(V Y, I) ≅ B(T, I) ≅ B(IH, I) ≅ E(H, 1)

where we have the last isomorphism because I is fully faithful. From H ⊣ I we have I Kan (with ∃I ≅ MH). To see that I is dense consider

I ⋆ – ·B(I, 1) ≅ X ·∃I ·MI ·Y ≅ X ·MH ·MI ·Y = X ·M(IH)·Y
= X ·M(T)·Y ≅ X ·B(T, 1) = X ·B(V Y, 1)
≅ X ·MB(Y, W) ≅ X ·W ≅ 1_{B}.

By (the proof of) Lemma 1, B is equivalent to ME and the equivalence B(I, 1) identifies I and Y_{E}. Thus H ⊣ I shows that E is total (directly, although that was already clear above since a full reflective subcategory of a total is total) and hence complete in the usual sense. But from Lemma 1 we also have E small so, by [3], E is an ordered set.

Theorem 3 A category B is equivalent to set if and only if B is totally distributive with V ⊣ W and V preserves pullbacks.

Proof. (only if) This follows from the Introduction. For if we have U ⊣ V then certainly V preserves pullbacks.

(if) Now T = V Y preserves pullbacks. It follows from the construction of H in Lemma 2 that H preserves pullbacks so E is “lex total”, meaning that the defining left adjoint for totality is left exact. (It necessarily preserves the terminal object.) By [6], E is a Grothendieck topos (for since E is small the size requirement in [6] is trivially satisfied). But since, by Lemma 2, E is also an ordered set it must therefore be 1. Indeed, we have true = false : 1 ⟶ Ω in E.

Corollary 4 The category set is characterized by U ⊣ V ⊣ W ⊣ X ⊣ Y.

References

[1] B. Fawcett and R. J. Wood. Constructive complete distributivity I. Math.

Proc. Cam. Phil. Soc., 107:81–89, 1990.

[2] F. Foltz. Légitimité des catégories de préfaisceaux. Diagrammes, 1:1–5, 1979.

[3] P.J. Freyd. Abelian Categories. Harper and Row, 1964.

[4] R. Paré, R. Rosebrugh, and R.J. Wood. Idempotents in bicategories.

Bulletin of the Australian Math. Soc., 39:421–434, 1989.

[5] R. Rosebrugh and R. J. Wood. Constructive complete distributivity IV.

to appear, 1992.

[6] R. Street. Notions of topos. Bulletin of the Australian Math Society, 23:199–208, 1981.

[7] R. Street. Unpublished manuscript. 1979.

[8] R. Street and R. F. C. Walters. Yoneda structures on 2-categories. Journal of Algebra, 50:350–379, 1978.

[9] R. J. Wood. Some remarks on total categories. Journal of Algebra, 75:538–545, 1982.