Chapter 4. Adjunctions
FC03 — Riehl, Category Theory in Context.
This chapter contains 13 definitions, 6 theorems, 10 propositions, 8 lemmas, 10 corollaries, 20 examples, 2 constructions, 2 remarks, 1 notation and 4 other statements.
Nobody has checked this chapter against Lean yet, so the statements below say nothing about whether they are formalized.
Definition 4.1.1
An adjunction F:C→D ⊣ G:D→C is a natural family of bijections D(Fc,d) ≅ C(c,Gd), natural in c and d; F is the left adjoint, G the right adjoint, and corresponding morphisms are transposes.
Lemma 4.1.3
Consider a pair of functors \(F \colon \mathsf{C} \to \mathsf{D}\) and \(G \colon \mathsf{D} \to \mathsf{C}\) equipped with isomorphisms \(\mathsf{D}(Fc,d) \cong \mathsf{C}(c,Gd)\) for all \(c \in \mathsf{C}\) and \(d \in \mathsf{D}\). Naturality of this collection of isomorphisms is equivalent to the assertion that, for every \(f \colon c' \to c\) in \(\mathsf{C}\), every \(g \colon d \to d'\) in \(\mathsf{D}\) and every \(k \colon Fc \to d\) with transpose \(k^{\sharp} \colon c \to Gd\), \[ (g \cdot k \cdot Ff)^{\sharp} = Gg \cdot k^{\sharp} \cdot f, \] that is, the square (4.1.4) commutes in \(\mathsf{D}\) if and only if its transposed square commutes in \(\mathsf{C}\).
Notation 4.1.5
Write F ⊣ G (equivalently G ⊢ F) to assert that F:C→D is left adjoint to G:D→C.
Example 4.1.6
The forgetful functor U : Top Set admits both left and right adjoints. The left adjoint constructs a topological space from a set S in such a way that continuous maps from this space to another space T correspond naturally and bijectively to functions \(S \to U ( T )\) . The discrete topology on S has this universal property: writing \(D ( S )\) for this discrete space, any function \(S \to U ( T )\) defines a continuous map \(D ( S ) \to T\)
Definition/comparison
An adjunction between preorders is a monotone Galois connection: order-preserving F:A→B and G:B→A satisfy F(a)≤b iff a≤G(b).
Example 4.1.7
The inclusion of posets \(\mathbb { Z } \hookrightarrow \mathbb { R }\) , with the usual ordering , has both left and right adjoints, namely, the ceiling and floor functions. For any integer n and real number \(r , n \leq r \mathrm { i f }\) and only if \(n \leq \lfloor r \rfloor\) , where \(\lfloor r \rfloor\) denotes the greatest integer less than or equal to r. This function is order-preserving, defining a functor \(\lfloor - \rfloor \colon \mathbb { R } \to \mathbb { Z }\) that is right adjoint to the inclusion \(\mathbb { Z } \hookrightarrow \mathbb { R }\) . Dually, \(r \leq n\) if and only if \(\lceil r \rceil \leq n ,\) and this order-preserving function defines a functor \(\lceil - \rceil : \mathbb { R } \to \mathbb { Z }\) that is left adjoint to the inclusion.
Example 4.1.8
Consider a function \(f \colon A \to B\) between sets. The subsets of A and subsets of B form posets, PA and \(P B ,\) ordered by inclusion. The map f induces direct image and inverse image functors \(f _ { * } \colon P A \to P B\) and \(f ^ { - 1 } \colon P B \to P A\) The inverse image is right adjoint to the direct image: for \(A ^ { \prime } \subset A\) and \(B ^ { \prime } \subset B , f ( A ^ { \prime } ) \subset B ^ { \prime }\) if and only if \(A ^ { \prime } \subset f ^ { - 1 } ( B ^ { \prime } )\)
Example 4.1.9
A propositional function is a function \(P \colon X \Omega = { \bot , \top }\) , which we interpret as declaring, for each \(x \in X ,\) , whether \(P ( x )\) is true or false. The set \(\Omega ^ { X }\) is then the set of propositional functions on X. The set Ω is given the partial order \(\perp \le \top\) from which \(\Omega ^ { X }\) inherits a pointwise-defined order: \(P \leq Q\) if and only if \(P ( x ) \leq Q ( x )\) for all \(x \in X\) which is the case if and only if \(P\) implies \(Q .\)
Example 4.1.10
There is a large and very important family of “free forgetful” adjunctions \[ \mathsf {A} \xrightarrow [ U ]{\stackrel {{F}} {\perp}} \mathsf {S}, \] with the forgetful functor U defining the right adjoint and the free functor F defining the left adjoint. If one can construct a universal object of type A on an object of type S, and this construction defines a left adjoint to a forgetful functor \(U \colon \mathsf { A } \mathsf { S }\) , then the term “free” is used in place of “universal” to convey this particular relationship. The reason why left adjoints to forgetful functors are more common than right adjoints has to do with the handedness of the universal properties that one meets in practice. “Cofree” constructions, which define right adjoints to some forgetful functor, are somehow less common. The following forgetful functors admit left adjoints, defining “free” constructions.
Construction: For a ring map φ:R→S, restriction of scalars φ:ModS→ModR has left adjoint…
For a ring map φ:R→S, restriction of scalars φ*:Mod_S→Mod_R has left adjoint S⊗_R−, called extension of scalars.
Example 4.1.11
Example 4.1.10(xiii) can be generalized: Example 6.2.8 proves that for any complete and cocomplete category C and any group homomorphism φ: \(H \to G ,\) , the restriction functor \(\phi ^ { * } \colon { \mathsf { \bar { C } } } ^ { \mathsf { B } G } \to { \mathsf { \bar { C } } } ^ { \mathsf { B } H }\) admits both left and right adjoints. These are most commonly considered for subgroup inclusions \(H \subset G .\) , in which case the left adjoint is called induction and the right adjoint is called coinduction: Taking \(\mathsf { C } \ = \ \mathsf { V e c t _ { \mathbb { k } } }\) , the adjunction \(\mathrm { i n d } _ { H } ^ { G } \ \mathsf { \Pi } \mathsf { \Pi } \mathsf { I } \mathrm { e s } _ { H } ^ { G }\) between the category \(\mathsf { V e c t } _ { \parallel _ { \mathsf { k } } } ^ { \mathsf { B } H }\) of \(H -\) representations and the category of \(\mathsf { V e c t } _ { \Bbbk } ^ { \mathsf { B } \bar { G } }\) of \(G \mathrm { . }\) -rep resentations. This adjunction is known in the representation theory literature as Frobenius reciprocity.
Example 4.1.12
None of the functors \[ \text { Field } \xrightarrow {U} \text { Ring }, \quad \text { Field } \xrightarrow {U} \text { Ab }, \quad \text { Field } \xrightarrow {(-) ^ {\times}} \text { Ab }, \quad \text { Field } \xrightarrow {U} \text { Set } \] that forget algebraic structure on fields admit left or right adjoints. To see that no left adjoint is possible, note that there exist maps in the target categories from \(\mathbb { Z }\) to fields of any characteristic. As there are no field homomorphisms between fields of difering characteristic, it is not possible to define the value of a hypothetical left adjoint on \(\mathbb { Z } .\) . A similar argument can be used to show that no right adjoints to these functors exist.
Example 4.1.13
The forgetful functor U : Cat DirGraph admits a left adjoint \(F ,\) defining the free category on a directed graph. A directed graph G consists of a set V of vertices, a set \(E\) of edges, and two functions \(s , t \colon E \preceq V\) defining the source and target of each directed edge. The free category on G has V as its set of objects. The set of morphisms consists of identities for each vertex together with finite “paths” of edges. Composition is defined by concatenation of paths.
Example 4.1.14
Let \(\mathbb{n}+\mathbb{1}\) denote the ordinal category, freely generated by the directed graph \(0 \to 1 \to 2 \to \cdots \to n\). For each \(0 \leq i \leq n\) there is an injective functor \(d^{i} \colon \mathbb{n} \to \mathbb{n}+\mathbb{1}\), where \(i \in \mathbb{n}+\mathbb{1}\) is the unique object missing from the image. For each \(0 \leq i < n\) there is also a surjective functor \(s^{i} \colon \mathbb{n}+\mathbb{1} \to \mathbb{n}\), for which \(i \in \mathbb{n}\) is the unique object with two preimages. These functors define a sequence of \(2n+1\) adjoints \[ d^{0} \dashv s^{0} \dashv d^{1} \dashv s^{1} \dashv \cdots \dashv s^{n-1} \dashv d^{n}, \] proving that arbitrarily long finite sequences of adjoint functors exist.
Example 4.1.15
The inclusion \(\mathsf{Groupoid} \hookrightarrow \mathsf{Cat}\) admits both a left and a right adjoint. The right adjoint carries a category to its maximal subgroupoid, considered in Lemma 1.1.13: since functors preserve isomorphisms, the image of a functor \(\mathsf{G} \to \mathsf{C}\) whose domain is a groupoid factors uniquely through the maximal subgroupoid of \(\mathsf{C}\). The left adjoint formally inverts the morphisms of a category, constructing the corresponding category of fractions. The category of fractions for \(\mathsf{C}\) is a quotient of the free category on the directed graph obtained by gluing the directed graph underlying \(\mathsf{C}\) to the directed graph underlying \(\mathsf{C}^{\mathrm{op}}\) along the common discrete subcategory \(\mathrm{ob}\,\mathsf{C}\). Its objects are the objects of \(\mathsf{C}\) and its morphisms are finite zig-zags of morphisms of \(\mathsf{C}\), subject to relations that, for instance, equate the zig-zags \[ a \xrightarrow{\ f\ } b \xleftarrow{\ f\ } a \qquad\text{and}\qquad b \xleftarrow{\ f\ } a \xrightarrow{\ f\ } b \] with the identities on \(a\) and on \(b\).
Lemma 4.2.2
Given an adjunction \(F \to G ,\) , there is a natural transformation η : \(1 _ { \mathsf { C } } \Rightarrow G F ,\) called the unit of the adjunction, whose component \(\eta _ { c } \colon c \to G F c\) at c is defined to be the transpose of the identity morphism \(1 _ { F c }\)
Lemma 4.2.3
Given an adjunction \(F \to G ,\) , there is a natural transformation \(\epsilon \colon F G \Rightarrow 1 _ { \mathsf { D } } ,\) called the counit of the adjunction, whose component $_ { d } F G d $ d at d is defined to be the transpose of the identity morphism \(1 _ { G d } .\)
Example 4.2.4
The left adjoint F to the forgetful functor \(U \colon { \mathsf { G r o u p } } \to { \mathsf { S e t } }\) defines the free group on a set S . Elements of the group \(F ( S )\) are finite “words” whose “letters” are elements s of S and formal “inverses” \(s ^ { - 1 }\) , modulo some evident relations. The empty word serves as the identity element and multiplication is by concatenation; the relations, in particular, identify \(s s ^ { - 1 }\) and \(s ^ { - 1 } s\) with the empty word.
Construction/terminology
For an adjunction, components of the unit and counit are the universal elements representing the adjunction hom-set bijections.
Definition 4.2.5
An adjunction may equivalently be specified by F:C→D, G:D→C, a unit η:1_C⇒GF and counit ε:FG⇒1_D satisfying the triangle identities Gε·ηG=1_G and εF·Fη=1_F.
Proposition 4.2.6
Given a pair of functors \(F \colon \mathsf { C } \mathsf { D } \colon G ,\) , there exists a natural isomorphism \(\mathsf { D } ( F c , d ) \cong \mathsf { C } ( c , G d )\) if and only if there exists a pair of natural transformations \(\eta \colon 1 _ { \mathsf { C } } \Rightarrow G F\) and \(\epsilon \colon F G \Rightarrow { \mathrm { 1 } } _ { \mathsf { D } }\) satisfying the triangle identities.
Remark 4.2.7
Proposition 4.2.6 reveals that the data of a fully-specified adjunction can be presented in two equivalent forms: a pair of functors \(F \colon \mathsf{C} \to \mathsf{D}\), \(G \colon \mathsf{D} \to \mathsf{C}\) together with either (i) a natural family of isomorphisms \(\mathsf{D}(Fc,d) \cong \mathsf{C}(c,Gd)\) for all \(c \in \mathsf{C}\), \(d \in \mathsf{D}\), or, equivalently, (ii) natural transformations \(\eta \colon 1_{\mathsf{C}} \Rightarrow GF\) and \(\epsilon \colon FG \Rightarrow 1_{\mathsf{D}}\) satisfying \(G\epsilon \cdot \eta G = 1_{G}\) and \(\epsilon F \cdot F\eta = 1_{F}\). Either of the unit and the counit alone suffices: (i) and (ii) are each equivalent to (iii) a natural transformation \(\eta \colon 1_{\mathsf{C}} \Rightarrow GF\) for which \[ \mathsf{D}(Fc,d) \xrightarrow{\ G\ } \mathsf{C}(GFc,Gd) \xrightarrow{\ (\eta_{c})^{*}\ } \mathsf{C}(c,Gd) \] is an isomorphism for all \(c \in \mathsf{C}\), \(d \in \mathsf{D}\), and dually to (iv) a natural transformation \(\epsilon \colon FG \Rightarrow 1_{\mathsf{D}}\) for which \[ \mathsf{C}(c,Gd) \xrightarrow{\ F\ } \mathsf{D}(Fc,FGd) \xrightarrow{\ (\epsilon_{d})_{*}\ } \mathsf{D}(Fc,d) \] is an isomorphism for all \(c \in \mathsf{C}\), \(d \in \mathsf{D}\).
Corollary 4.2.8
If \(\mathsf{A}\) and \(\mathsf{B}\) are posets and \(F \colon \mathsf{A} \to \mathsf{B}\), \(G \colon \mathsf{B} \to \mathsf{A}\) form a Galois connection, with \(F \dashv G\), then \(F\) and \(G\) satisfy the fixed point formulae \[ FGF = F \qquad\text{and}\qquad GFG = G. \]
Definition 4.3.1
A pair of contravariant functors \(F \colon { \mathsf { C } } ^ { \mathrm { o p } } \to \mathsf { D }\) and \(G \colon { \mathsf { D } } ^ { \mathrm { o p } } \ \to \ { \mathsf { C } }\) are mutually left adjoint if there exists a natural isomorphism \[ \mathsf{D}(Fc,d) \cong \mathsf{C}(Gd,c), \] or mutually right adjoint if there exists a natural isomorphism \[ \mathsf{D}(d,Fc) \cong \mathsf{C}(c,Gd). \]
Example 4.3.2
For a fixed natural number n and algebraically closed field k, consider the sets of elements in the polynomial ring \(\mathbb { k } [ x _ { 1 } , \ldots , x _ { n } ]\) and in the vector space \(\mathbb { k } ^ { n }\) . There are contravariant functors \[ P(\Bbbk[x_{1},\dots,x_{n}])^{\mathrm{op}} \xrightarrow{\ V\ } P(\Bbbk^{n}) \qquad\text{and}\qquad P(\Bbbk^{n})^{\mathrm{op}} \xrightarrow{\ I\ } P(\Bbbk[x_{1},\dots,x_{n}]), \] carrying a set of polynomials to its vanishing locus and a set of points to the ideal of polynomials vanishing on it; they are mutually right adjoint.
Example 4.3.3
Let \(\mathrm{Axiom}_{\sigma}\) be a set of axioms, that is, sentences in a fixed first-order language whose signature \(\sigma\) specifies function, constant and relation symbols, and let \(\mathrm{Struct}_{\sigma}\) be a set of \(\sigma\)-structures, that is, sets with interpretations of those symbols. For instance, the language of the natural numbers has a constant symbol \(0\), a binary function symbol \(+\) and a binary relation symbol \(\leq\); a structure for it is any set with a specified constant, binary function and binary relation. Axioms include sentences such as \[ \forall x,y,z,\ ((x \leq y) \wedge (y \leq z)) \rightarrow (x \leq z) \qquad\text{or}\qquad \forall x,\ x + 0 = x, \] asserting transitivity of \(\leq\) and that \(0\) is a unit for \(+\). Writing \(M \models A\) when every axiom of \(A\) holds in every structure of \(M\) gives contravariant functors between the posets \(P(\mathrm{Axiom}_{\sigma})\) and \(P(\mathrm{Struct}_{\sigma})\), ordered by inclusion, which form a Galois connection.
Named comparison
Sets of axioms and classes of structures form the Galois connection between syntax and semantics via satisfaction.
Proposition 4.3.4
Consider a functor \(F \colon \mathsf { A } \mathsf { B }\) so that for each \(b \in \mathsf { B }\) there exists an object Gb A together with an isomorphism \[ \mathsf{B}(Fa,b) \cong \mathsf{A}(a,Gb), \quad\text{natural in } a \in \mathsf{A}. \tag{4.3.5} \] Then there is a unique way to extend the assignment \(b \mapsto Gb\) to a functor \(G \colon \mathsf{B} \to \mathsf{A}\) so that the isomorphisms (4.3.5) are also natural in \(b\), and \(F \dashv G\).
Proposition 4.3.6
Suppose that \(F \colon \mathsf { A } \times \mathsf { B } \to \mathsf { C }\) is a bifunctor so that for each object a A, the induced functor \(F ( a , \mathrm { - } ) \colon { \mathsf { B } } \to { \mathsf { C } }\) admits a right adjoint \(G _ { a } \colon { \mathsf { C } } \to { \mathsf { B } }\) . Then: (i) These right adjoints assemble into a unique bifunctor \(G \colon \mathsf { A } ^ { \mathrm { o p } } \times \mathsf { C } \to \mathsf { B }\) , defined so that \(G ( a , c ) = G _ { a } ( c )\) and so that the isomorphisms \[ \mathsf {C} (F (a, b), c) \cong \mathsf {B} (b, G (a, c)) \] are natural in all three variables.
Definition 4.3.7
A triple of bifunctors \[ \mathsf{A} \times \mathsf{B} \xrightarrow{\ F\ } \mathsf{C}, \qquad \mathsf{A}^{\mathrm{op}} \times \mathsf{C} \xrightarrow{\ G\ } \mathsf{B}, \qquad \mathsf{B}^{\mathrm{op}} \times \mathsf{C} \xrightarrow{\ H\ } \mathsf{A} \] equipped with a natural isomorphism \[ \mathsf{C}(F(a,b),c) \cong \mathsf{B}(b,G(a,c)) \cong \mathsf{A}(a,H(b,c)) \] defines a two-variable adjunction.
Definition: For a two-variable adjunction associated to a monoidal product, the…
For a two-variable adjunction associated to a monoidal product, the pointwise right adjoints are the left and right closures; when isomorphic, the monoidal product is called closed.
Example 4.3.8
The product bifunctor \(\times \colon \mathsf{Set} \times \mathsf{Set} \to \mathsf{Set}\) is closed: the operation called currying in computer science defines a family of natural isomorphisms \[ \{A \times B \xrightarrow{\ f\ } C\} \cong \{A \xrightarrow{\ f\ } C^{B}\} \cong \{B \xrightarrow{\ f\ } C^{A}\}, \] so the product and exponential bifunctors form a two-variable adjunction.
Definition 4.3.9
A cartesian closed category is a category C with finite products in which the product bifunctor \[ \times \colon \mathsf{C} \times \mathsf{C} \to \mathsf{C} \] is closed.
Example 4.3.10
The category \(\mathsf{Top}\) is not cartesian closed, but Steenrod’s convenient category of spaces is: the product on a yet-to-be-defined subcategory \(\mathsf{cgHaus}\) should be the categorical product of Definition 3.1.9, which is not preserved by the full inclusion \(\mathsf{cgHaus} \hookrightarrow \mathsf{Haus}\). Objects of \(\mathsf{cgHaus}\) are the compactly generated Hausdorff spaces: Hausdorff \(X\) such that any \(A \subset X\) meeting every compact \(K \subset X\) in a closed subset is itself closed. The inclusion \(\mathsf{cgHaus} \hookrightarrow \mathsf{Haus}\) has a right adjoint \(k \colon \mathsf{Haus} \to \mathsf{cgHaus}\), \(k\)-ification, which refines the topology of \(X\) by adding as closed those \(A \subset X\) whose intersections with all compact \(K\) are closed; by the dual of Proposition 4.5.15 its presence makes \(\mathsf{cgHaus}\) complete and cocomplete. The product on \(\mathsf{cgHaus}\) is the \(k\)-ification of the product on \(\mathsf{Haus}\), and the pointwise right adjoint is \(\operatorname{Map}(X,Y)\): the set of continuous maps \(X \to Y\) with the \(k\)-ification of the compact-open topology.
Example 4.3.11
Consider the hom bifunctor \(\operatorname{Hom} \colon \mathsf{Ab}^{\mathrm{op}} \times \mathsf{Ab} \to \mathsf{Ab}\), where \(\operatorname{Hom}(A,B)\) is the group of homomorphisms \(A \to B\) with addition defined pointwise in \(B\). Fixing the contravariant variable, there is an adjunction \(A \otimes_{\mathbb{Z}} - \dashv \operatorname{Hom}(A,-)\) on \(\mathsf{Ab}\), with \[ \mathsf{Ab}(A \otimes_{\mathbb{Z}} B, C) \cong \mathsf{Ab}(B, \operatorname{Hom}(A,C)), \tag{4.3.12} \] defining the tensor product. Proposition 4.3.4 extends this data to a functor \(A \otimes_{\mathbb{Z}} - \colon \mathsf{Ab} \to \mathsf{Ab}\) and Proposition 4.3.6(i) to the bifunctor \(\otimes_{\mathbb{Z}} \colon \mathsf{Ab} \times \mathsf{Ab} \to \mathsf{Ab}\), in such a way that the tensor product and the hom define a two-variable adjunction.
Example 4.3.14
Temporarily, let Top denote not the ordinary category of topological spaces but the cartesian closed category of spaces defined in Example 4.3.10. In this context, the two-variable adjunction specializes to define an adjunction: \[ \text { Top } \xrightarrow [ \text { Map } (S ^ {1} , -) ]{S ^ {1} \times -} \text { Top } \] where \(S ^ { 1 } \in\) Top is the unit circle. The space \(\mathbf { M a p } ( S ^ { 1 } , X )\) is the free loop space on X; points in \(\mathbf { M a p } ( S ^ { 1 } , X )\) are loops in the space X. The slice category of Top under the singleton space defines a convenient category Top of based topological spaces. By Exercise \(4 . 3 . \mathrm { i v ( i i ) }\) , Top admits a two-variable adjunction \[ \wedge \colon \mathsf{Top}_{*} \times \mathsf{Top}_{*} \to \mathsf{Top}_{*}, \qquad \mathsf{Top}_{*}^{\mathrm{op}} \times \mathsf{Top}_{*} \to \mathsf{Top}_{*}, \] the smash product together with the based mapping space.
Named construction
On based spaces, the closed monoidal product appearing in the two-variable adjunction is the smash product.
Proposition 4.4.1
If \(F\) and \(F'\) are both left adjoint to \(G\), then \(F \cong F'\), and moreover there is a unique natural isomorphism \(\theta \colon F \cong F'\) commuting with the units and counits of the two adjunctions. Explicitly, \[ \theta := F \xrightarrow{\ F\eta'\ } FGF' \xrightarrow{\ \epsilon F'\ } F', \qquad \theta^{-1} = F' \xrightarrow{\ F'\eta\ } F'GF \xrightarrow{\ \epsilon' F\ } F, \] where \(\theta\) is the transpose of \(\eta' \colon 1_{\mathsf{C}} \Rightarrow GF'\) under the adjunction \(F \dashv G\).
Proposition 4.4.4
Given adjunctions \(F \to G\) and \(F ^ { \prime } \to G ^ { \prime }\) \[ \mathsf {C} \xrightarrow [ G ]{\underset {\perp} {F}} \mathsf {D} \xrightarrow [ G ^ {\prime} ]{\underset {\perp} {F ^ {\prime}}} \mathsf {E} \qquad \rightsquigarrow \qquad \mathsf {C} \xrightarrow [ G G ^ {\prime} ]{\underset {\perp} {F ^ {\prime} F}} \mathsf {E} \] the composite \(F ^ { \prime } F\) is left adjoint to the composite \(G G ^ { \prime }\) Proof 1. There are natural isomorphisms \[ \mathsf{E}(F'Fc, e) \cong \mathsf{D}(Fc, G'e) \cong \mathsf{C}(c, GG'e), \] the first defined using \(F' \dashv G'\) and the second using \(F \dashv G\).
Proposition 4.4.5
Any equivalence \[ \mathsf {C} \xrightarrow [ G ]{F} \mathsf {D} \qquad \eta \colon 1 _ {\mathsf {C}} \cong G F, \quad \epsilon \colon F G \cong 1 _ {\mathsf {D}} \] can be promoted to an adjoint equivalence, in which the natural isomorphisms satisfy the triangle identities, by replacing either one of the originally specified natural isomorphisms by a new unit or counit. Note that the symmetry in the definition implies that an equivalence of categories \(F \colon { \mathsf { C } } \to { \mathsf { D } }\) may be regarded as either a left or right adjoint; indeed, any chosen equivalence inverse \(G \colon \mathsf { D } \to \mathsf { C }\) is both left and right adjoint to \(F\)
Proposition 4.4.6
Given an adjunction \(F \dashv G \colon \mathsf{C} \rightleftarrows \mathsf{D}\), post-composition with \(F\) and \(G\) defines a pair of adjoint functors \[ F_{*} \dashv G_{*} \colon \mathsf{C}^{\mathsf{J}} \rightleftarrows \mathsf{D}^{\mathsf{J}} \] for any small category \(\mathsf{J}\), and pre-composition with \(F\) and \(G\) also defines an adjunction \[ G^{*} \dashv F^{*} \colon \mathsf{E}^{\mathsf{C}} \rightleftarrows \mathsf{E}^{\mathsf{D}} \] for any locally small category \(\mathsf{E}\).
Remark 4.4.7
The “syntactic” proofs of Propositions 4.4.1, 4.4.4, 4.4.5, and 4.4.6 (the last of these left to Exercise 4.4.ii) apply immediately to adjunctions defined internally to any 2-category, in place of Cat. This suggests a reason to prefer these proofs to the alternate “Yoneda-style” arguments, which apply only to Cat. However, using analogous arguments to those made in §3.4, these “Yoneda-style” arguments can be bootstrapped from Cat to a general 2-category. As (co)limits in a general category are defined representably in terms of limits in Set, so too—again by the Yoneda lemma—are adjunctions and equivalences in a 2-category are defined representably in terms of adjunctions and equivalences in Cat. This line of reasoning supports the category theorist’s joke that “all theorems are Yoneda.”
Proposition 4.5.1
A category C admits all limits of diagrams indexed by a small category J if and only if the constant diagram functor \(\Delta \colon { \mathsf { C } } \to { \mathsf { C } } ^ { \mathsf { J } }\) admits a right adjoint, and admits all colimits of J-indexed diagrams if and only if ∆ admits a left adjoint: When these adjoints exist, they define the limit and colimit functors introduced in Proposition 3.6.1. Recall that the axiom of choice is needed to define the action of the limit or colimit functor on objects.
Theorem 4.5.2
Right adjoints preserve limits.
Theorem 4.5.3
Left adjoints preserve colimits. Corollaries are ubiquitous. For instance:
Corollary 4.5.4
For any function \(f \colon A \ \to \ B ,\) the inverse image \(f ^ { - 1 } \colon P B \to P A\) , a function between the power sets of A and B, preserves both unions and intersections, while the direct image \(f _ { * } \colon P A \to P B\) only preserves unions.
Corollary 4.5.5
For any vector spaces \(U , V , W ,\) \[ U \otimes (V \oplus W) \cong (U \otimes V) \oplus (U \otimes W). \]
Corollary 4.5.6
For any sets \(A\), \(B\), \(C\) there are natural isomorphisms \[ A \times (B+C) \cong (A \times B) + (A \times C), \qquad (B \times C)^{A} \cong B^{A} \times C^{A}, \qquad A^{B+C} \cong A^{B} \times A^{C}. \] Consequently, for any cardinals \(\alpha\), \(\beta\), \(\gamma\), cardinal arithmetic satisfies the laws \[ \alpha \times (\beta + \gamma) = (\alpha \times \beta) + (\alpha \times \gamma), \qquad (\beta \times \gamma)^{\alpha} = \beta^{\alpha} \times \gamma^{\alpha}, \qquad \alpha^{\beta+\gamma} = \alpha^{\beta} \times \alpha^{\gamma}. \]
Corollary 4.5.7
The free group on the set X Y is the free product of the free groups on the sets X and Y.
Corollary 4.5.8
For any R-S bimodule M, the tensor product M \(\otimes _ { S } - i s \ r i g h t \ e x a c t\)
Definition 4.5.9
A functor is right exact if it preserves finite colimits and left exact if it preserves finite limits.
Proposition 4.5.10
A functor \(F \colon \mathsf{A} \to \mathsf{B}\) between abelian categories is left exact if and only if it preserves direct sums and kernels. For such functors, if \[ 0 \to A \to A' \to A'' \] is exact in \(\mathsf{A}\), then \[ 0 \to FA \to FA' \to FA'' \] is exact in \(\mathsf{B}\).
Corollary 4.5.11
For any adjoint functors between abelian categories, the left adjoint is right exact and the right adjoint is left exact. Moreover, both functors are additive.9
Definition 4.5.12
A reflective subcategory of a category C is a full subcategory D so that the inclusion admits a left adjoint, called the reflector or localization: \[ \mathsf {D} \xleftarrow [ ]{\underset {\perp} {\overset {L} {\longrightarrow}}} \mathsf {C} . \] Where possible, we identify the full subcategory D with its image in \(\complement ,\) declining in particular to introduce notation for the inclusion functor. With this convention in mind, the components of the unit have the form \(c \to L c ;\) the mnemonic is that “an object looks at its reflection.” The following lemma implies that the components of the counit \(L d \cong d\) are isomorphisms. Via the counit, any object in a reflective subcategory \(\mathsf { D } \hookrightarrow \mathsf { C }\) is naturally isomorphic to its reflection back into that subcategory.
Lemma 4.5.13
Consider an adjunction \[ \mathsf {C} \xrightarrow [ \begin{array}{c} \perp \ G \end{array} ]{\stackrel {{F}} {\longrightarrow}} \mathsf {D} \] with counit ǫ : \(F G \Rightarrow 1 _ { \mathsf { D } }\) . Then: (i) G is faithful if and only if each component of ǫ is an epimorphism.
Example 4.5.14
The following define reflective subcategories: (i) Compact Hausdorf spaces define a reflective subcategory cHaus \(\hookrightarrow\) Top of the category of all topological spaces. The reflector is the functor \(\beta \colon\) Top cHaus sending a space to its Stone–Čech compactification, which is constructed in Example 4.6.12. The universal property of the unit says that any continuous function \(X K\) from a space X to a compact Hausdorf space K extends uniquely to the Stone–Čech compactification: (ii) Abelian groups define a reflective subcategory \(\mathsf { A b } \hookrightarrow\) Group of the category of groups. The reflector carries a group G to its abelianization, the quotient \(G / [ G , G ]\) by the commutator subgroup, the normal subgroup generated by elements \(g h g ^ { - 1 } h ^ { - 1 }\) The quotient maps \(G \to G / [ G , G ]\) define the components of the unit. For any abelian group A, there is an isomorphism \(A \cong A / [ A , A ] ;\)
Named comparison
Examples of reflective subcategories: Ab↪Group with reflector G↦G/[G,G], CRing↪Ring via commutativization, and torsion-free abelian groups ↪ Ab via A↦A/TA.
Proposition 4.5.15
\(I f \mathsf { D } \hookrightarrow \mathsf { C }\) is a reflective subcategory, then: (i) The inclusion \(\mathsf { D } \hookrightarrow \mathsf { C }\) creates all limits that C admits. (ii) D has all colimits that C admits, formed by applying the reflector to the colimit in C. By Theorems 4.5.2 and 4.5.3, if D has limits or colimits, they must be constructed in the way described in Proposition 4.5.15: limits are preserved by the inclusion \(\mathsf { D } \hookrightarrow \mathsf { C }\) and colimits of diagrams in D, regarded as diagrams in C, are preserved by \(L \colon { \mathsf { C } } \to { \mathsf { D } }\) . The real content of this result is that these (co)limits necessarily exist in D. A special case of this completes some unfinished business from §3.5:
Corollary 4.5.16
Cat is complete and cocomplete.
Lemma 4.6.1
A functor U : \(\mathsf { A } \to \mathsf { S }\) admits a left adjoint if and only if for each \(s \in \mathsf { S }\) the comma category \(\mathbf { s } \downarrow U\) has an initial object.
Terminology
A limit-preserving functor is called continuous; a colimit-preserving functor is called cocontinuous.
Lemma 4.6.2
For any functor \(U \colon \mathsf { A } \mathsf { S }\) and object \(s \in \mathsf { S } ,\) the associated forgetful functor Π : \(s \downarrow U \to { \mathsf { A } }\) strictly creates the limit of any diagram whose limit exists in A and is preserved by U. In particular, if A is complete and U is continuous, then \(s \downarrow U\) is complete.
Theorem 4.6.3
Let \(U \colon \mathsf { A } \mathsf { S }\) be a continuous functor whose domain is locally small and complete. Suppose that U satisfies the following solution set condition: For every \(s \in \mathsf { S }\) there exists a set of morphisms \(\Phi _ { s } = { f _ { i } \colon s U a _ { i } }\) so that any $f s $ Ua factors through some \(f _ { i } \in \Phi _ { s }\) along a morphism \(a _ { i } \to a\) in A. Then U admits a left adjoint. The solution set condition says exactly that \({ f _ { i } \colon s U a _ { i } }\) is a set of jointly weakly initial objects in the category \(s \downarrow U\)
Definition 4.6.4
- An object c in a category C is weakly initial if for every \(x \in \mathsf { C }\) there exists a morphism \(c \to x\) (but possibly more than one). (ii) A collection of objects \(\Phi = { c _ { i } }\) in a category C is jointly weakly initial if for every \(x \in \mathsf { C }\) there exists some \(c _ { i } \in \Phi\) for which there exists a morphism \(c _ { i } \to x .\) In the presence of certain limits, an initial object can be built from a jointly weakly initial set of objects:
Lemma 4.6.5
If C is complete, locally small, and has a jointly weakly initial set of objects Φ, then C has an initial object.
Example 4.6.6
For example, consider the functor U : Group Set and a set S . The following construction of the free group on S can be found in [Lan02, §I.12]. Let Φ′ be the set of representatives for isomorphism classes of groups that can be generated by a set of elements of cardinality at most S . Let Φ be the set of functions \(S \to U G\) , with \(G \in \Phi ^ { \prime } .\) whose image generates the group G. This is a jointly weakly initial set of objects in the comma category \(S \downarrow U\) and a solution set for \(U \colon { \mathsf { G r o u p } } \to { \mathsf { S e t } }\)
Definition 4.6.7
A separating set or separator for a category C is a set Φ of objects that can distinguish between distinct parallel morphisms in the following sense: given \(f , g \colon x \preceq y\) , if \(f \neq g\) then there exists some \(h \colon c \to x\) with \(c \in \Phi\) so that \(f h \neq g h\) . A coseparating set in C is a separating set in \({ \mathsf { C } } ^ { \mathrm { { o p } } }\)
Definition 4.6.8
A subobject of an object \(c \in \mathsf { C }\) is a monomorphism \(c ^ { \prime } \mapsto c\) with codomain \(c .\) Isomorphic subobjects, that is, subobjects \(c ^ { \prime } \mapsto c \gets c ^ { \prime \prime }\) with a commuting isomorphism \(c ^ { \prime } \cong c ^ { \prime \prime }\) , are typically identified.
Theorem 4.6.10
Let \(U \colon \mathsf { A } \mathsf { S }\) be a continuous functor whose domain is complete and whose domain and codomain are locally small. Furthermore, if A has a small coseparating set and every collection of subobjects of a fixed object in A admits an intersection, then U admits a left adjoint.
Lemma 4.6.11
Suppose C is locally small, complete, has a small coseparating set \(\Phi ,\) and has the property that every collection of subobjects has an intersection. Then C has an initial object.
Example 4.6.12
The Special Adjoint Functor Theorem is an abstraction of the construction of the Stone–Čech compactification \(\beta \colon\) Top cHaus, which defines a left adjoint to the inclusion cHaus ֒ Top. The unit interval \(I = [ 0 , 1 ] \in \mathbb { R }\) is a coseparating object in cHaus. To see this, note that if \(f \neq g \colon X \Rightarrow Y .\) , there must be some \(x \in X\) with \(f ( x ) \neq g ( x )\) . Then Urysohn’s lemma can be used to define a continuous function h : \(Y I\) with \(h f ( x ) = 0\) and \(h g ( x ) = 1\) , so that in particular \(h f \neq h g\) . Given a topological space X, Theorem 4.6.10 constructs an initial object in X cHaus in the following manner. A coseparating family in \(X \downarrow\) cHaus is given by the set of all maps \(X I .\) By Proposition 3.3.8, the product of these maps, considered as objects in \(X \downarrow\) cHaus, is the canonical map \[ X \xrightarrow{\ \hat{\eta}\ } \prod_{\operatorname{Hom}(X,I)} I. \]
Corollary 4.6.13
Suppose C is locally small, complete, has a small coseparating set, and has the property that every collection of subobjects of a fixed object has an intersection. Then C is also cocomplete.
Corollary 4.6.14
Suppose C is locally small, complete, has a small coseparating set, and has the property that every collection of subobjects of a fixed object has an intersection. Then any continuous functor \(F \colon \mathsf { C } \to\) Set is representable.
Theorem 4.6.15
Let \(F \colon \mathsf { C } \to\) Set be a continuous functor and suppose that C is complete and locally small. If F satisfies the solution set condition: There exists a set Φ of objects of C so that for any \(c \in \mathsf { C }\) and any element \(x \in F c ,\) there exists an \(s \in \Phi ,\) , an element \(y \in F s ,\) , and a morphism f : \(s c\) so that \(F f ( y ) = x\) then F is representable.
Definition 4.6.16
Let κ be a regular cardinal.12 A locally small category C is locally κ-presentable if it is cocomplete and if it has a set of objects S so that: (i) Every object in C can be written as a colimit of a diagram valued in the subcategory spanned by the objects in S . (ii) For each object \(s \in S\) , the functor \({ \mathsf { C } } ( s , - ) \colon { \mathsf { C } } \to\) Set preserves κ-filtered colimits. A functor between locally κ-presentable categories is accessible if it preserves κ-filtered colimits. For example, a large variety of categories whose objects are sets equipped with some sort of “algebraic” structure are locally finitely presentable (meaning locally ω-presentable); see Definition 5.5.5. A locally κ-presentable category is also locally λ-presentable for any \(\lambda > \kappa .\) Between locally presentable categories, meaning categories that are locally κ-presentable for some \(\kappa ,\) the adjoint functor theorem takes a part icularly appealing form, theorem 4.6.17: a functor between locally presentable categories admits a right adjoint if and only if it is cocontinuous, and a left adjoint if and only if it is continuous and accessible.
Theorem 4.6.17
A functor F : C D between locally presentable categories (i) admits a right adjoint if and only if it is cocontinuous. (ii) admits a left adjoint if and only if it is continuous and accessible.