A Brief Introduction to Categories, Part 9: Adjunctions II

This post is part of a series on category theory, see Overview of Blog Posts for all posts. All categories are assumed to be locally small.

Introduction

In this post, we shall establish different perspectives on the previously established concept of adjoint functors, along with more examples and properties. We shall use the same idea that underlies the Yoneda lemma to characterize an adjunction using special natural transformations called unit and counit.

To get a class of examples for adjunction, we shall study free objects in concrete categories. (Where “concrete” is a technical term. But don’t worry, the concept of concrete categories will be made concrete in examples of concrete concrete categories.).
Through them, we shall see how a natural generalization of the concept of a basis from linear algebra leads to adjunctions.

By following this approach, we will also see that there is a close connection between adjoint functors and representability.

Unit and Counit

An adjunction between two functors is given by a natural isomorphism between two functors involving Hom-functors. We know from the Yoneda lemma and in particular from its proof that a natural transformation from a Hom functor is determined by its action on identities. In the same spirit, all the information of an adjunction is contained in the action on certain identity morphisms.

Let \mathcal{C} and \mathcal{D} be categories and let F:\mathcal{C} \to \mathcal{D},G:\mathcal{D} \to \mathcal{C} be functors. Suppose we are given an adjunction, i.e. a natural isomorphism H: \mathrm{Hom}_{\mathcal D}(F(-),-) \cong \mathrm{Hom}_{\mathcal C}(-,G(-)). Then for each X \in \mathcal{C} and each Y \in \mathcal{D}, we have a bijection H_{X,Y}:\mathrm{Hom}_{\mathcal D}(F(X),Y) \cong \mathrm{Hom}_{\mathcal C}(X,G(Y)). If we fix X and set Y=F(X), then we obtain an element H_{X,F(X)}(\mathrm{id}_F(X)):=\eta_X \in \mathrm{Hom}_{\mathcal C}(X,G(F(X))). Similarly, we can fix Y and set X=G(Y) and obtain an element H_{G(Y),Y}^{-1}(\mathrm{id}_{G(Y)}):=\varepsilon_Y \in \mathrm{Hom}_{\mathcal D}(F(G(Y)),Y).

Definition C9.1 In the above discussion, \eta_X is called the unit of the adjunction (at X) and \varepsilon_Y is called the counit of the adjunction.

Lemma C9.2 The collection of morphisms \eta_X:X \to GF(X) is natural in X.

Proof Let f:X \to X' be a morphism in C, then we must show that the following diagram commutes:

unitnaturality

i.e. GF(f) \circ \eta_X=\eta_{X'} \circ f.
Via naturality of H_{X,Y} in the second argument, we obtain a commutative diagram:

unitnaturality2

Applying this to the identity \mathrm{id}_{F(X)} yields the equation H_{X,F(X')}(F(f) \circ \mathrm{id}_{F(X)})=GF(f) \circ H_{X,F(X)}(\mathrm{id}_{F(X)}, i.e. H_{X,F(X')}(F(f))=GF(f) \circ \eta_X.
Naturality of H_{X,Y} in the first argument yields another commutative diagram:

unitnaturality3

Applying this to the identity \mathrm{id}_{F(X')} leads to the equation H_{X',F(X')}(\mathrm{id}_{F(X')}) \circ f=H_{X,F(X')}(\mathrm{id}_{F(X')} \circ F(f)), i.e. \eta_{X'} \circ f=H_{X,F(X')}(F(f)).
We have thus shown that GF(f) \circ \eta_X=\eta_{X'} \circ f, as both sides equal H_{X,F(X')}(F(f)).

This lemma shows that the unit of an adjunction defines a natural transformation, which we denote by \eta.

A very similar proof leads to the following lemma:

Lemma 9.3 Given the established context, the collection of morphisms \varepsilon_Y: FG(Y) \to Y is natural in Y.

So far, we have established how an adjunction F \dashv G gives rise to two natural transformations \eta:\mathrm{id}_{\mathcal{C}} \Rightarrow GF and \varepsilon:FG \Rightarrow \mathrm{id}_{\mathcal{D}}. Following the Yoneda philosophy as described in the beginning of this section, our goal is to show that this pair of natural transformations already encapsulates the whole adjunction. To this end, we will prove properties which will turn out to give a necessary and sufficient condition for a pair of such natural transformations to come from an adjunction.

Lemma C9.4 We have for every X \in \mathcal{C}, \mathrm{id}_{F(X)}=\varepsilon_{F(X)} \circ F(\eta_X)

Proof Naturality of H_{X,Y} in the first argument respect to \eta_X:GF(X) \to X yields the commutative diagram:

unitcouniteq

Applying this to \varepsilon_{F(X)} \in \mathrm{Hom}_{\mathcal{D}}(FGF(X),F(X)), we get H_{X,F(X)}(\varepsilon_{F(X)} \circ F(\eta_X))=H_{GF(X),F(X)}(\varepsilon_{F(X)}) \circ \eta_X=\mathrm{id}_{GF(X)} \circ \eta_X =\eta_X=H_{X,F(X)}(\mathrm{id}_{F(X)}), so that we obtain by the injectivity of H_{X,F(X)} the desired equality \mathrm{id}_{F(X)}=\varepsilon_{F(X)} \circ F(\eta_X).

Lemma C9.5 We have for every Y \in \mathcal{D}, \mathrm{id}_{G(Y)}=G(\varepsilon_Y) \circ \eta_{G(Y)}.

Proof Applying naturality of H_{X,Y} in the second argument with respect to \varepsilon_Y:FG(Y) \to Y yields the following commutative diagram:

unitcouniteq2

Applying this to \mathrm{id}_{FG(Y)}, we obtain G(\varepsilon_Y) \circ H_{G(Y),FG(Y)}(\mathrm{id}_{FG(Y)}) = H_{G(Y),Y}(\varepsilon_Y \circ \mathrm{id}_{FG(Y)}), i.e. G(\varepsilon_Y) \circ \eta_{G(Y)}=\mathrm{id}_{G(Y)}.

Lemma C9.6 Given a pair of functors F:\mathcal{C} \to \mathcal{D},G:\mathcal{D} \to \mathcal{C} and a pair of natural transformations \eta:\mathrm{Id}_{\mathcal{C}} \Rightarrow GF, \varepsilon:FG \Rightarrow \mathrm{Id}_{\mathcal{D}} such that for all X \in \mathcal{C} and Y \in \mathcal{D}, we have \mathrm{id}_{F(X)}=\varepsilon_{F(X)} \circ F(\eta_X) and \mathrm{id}_{G(Y)}=G(\varepsilon_Y) \circ \eta_{G(Y)}, the map H_{X,Y}:\mathrm{Hom}_{\mathcal{D}}(F(X),Y) \to \mathrm{Hom}_{\mathcal{C}}(X,G(Y)),f \mapsto G(f) \circ \eta_X is a natural isomorphism with inverse W_{X,Y}:g \mapsto \varepsilon_Y \circ F(g).

Proof Naturality of H_{X,Y} follows from the naturality of \eta. For any X \in \mathcal{C},Y \in \mathcal{D} and f \in \mathrm{Hom}_{\mathcal{D}}(F(X),Y), we obtain W_{X,Y}(H_{X,Y}(f))=W_{X,Y}(G(f) \circ \eta_X)=\varepsilon_Y \circ F(G(f) \circ \eta_X))=\varepsilon_Y \circ FG(f) \circ F(\eta_X). By naturality of \varepsilon with respect to f, we have \varepsilon_Y \circ FG(f)=f \circ \varepsilon_{F(X)}. By assumption \varepsilon_{F(X)} \circ F(\eta_X)=\mathrm{id}_{F(X)}. Combining these, we see that \varepsilon_Y \circ FG(f) \circ F(\eta_X)=f. For g:X \to G(Y), we have H_{X,Y}(W_{X,Y}(g))=g, which can be shown by analogous reasoning from the naturality of \eta with respect to g and the condition \mathrm{id}_{G(Y)}=G(\varepsilon_Y) \circ \eta_{G(Y)}.

Putting everything together, we have shown:

Theorem C9.7 Given two categories \mathcal C and \mathcal D and functors F:\mathcal C \to \mathcal D, G:\mathcal D \to \mathcal C, the datum of an adjunction between F and G is equivalent to giving two natural transformations \eta:\mathrm{Id}_{\mathcal{C}} \Rightarrow GF, \varepsilon:FG \Rightarrow \mathrm{Id}_{\mathcal{D}} satisfying the so-called unit-counit equations: for all X \in \mathcal{C} and Y \in \mathcal{D}, we have \mathrm{id}_{F(X)}=\varepsilon_{F(X)} \circ F(\eta_X) and \mathrm{id}_{G(Y)}=G(\varepsilon_Y) \circ \eta_{G(Y)}.

Free Objects

We shall now return from the general to the concrete (quite literally):

Definition C9.8 A concrete category is a pair (\mathcal C,V) where \mathcal C is a category and V:\mathcal C \to \mathbf{Set} is a faithful functor.

Using the faithful functor V, which we think of as a “forgetful” functor, we can think of objects in the category \mathcal C as sets and of morphisms as maps. A lot of common examples of categories have a canonical choice for a faithful functor V.

Example C9.9 The category of sets \mathbf{Set} is concrete with V the identity functor.

Examples C9.10 The categories of semigroups, monoids, groups, abelian groups, rings, commutative rings, fields, modules over a fixed base ring etc. with the respective homomorphisms as morphisms are all concrete categories where V is the forgetful functor to \mathbf{Set}

Examples C9.11 The category of topological spaces with continuous maps is a concrete category, so is the category of smooh manifolds with smooth maps, and so is the category of complex-analytic manifolds with holomorphic maps.

Example C9.12 Let M be a monoid, considered as a one-object category. Then the idea from the proof of Cayley’s theorem from group theory allows us to realize M as a concrete category: to define the functor V, send the unique object of M to the set underlying set of M (i.e. the set of all morphisms in M) and define V(f) to be left multiplication with f.

Example C9.13 Generalizing the last example, every small category \mathcal{C} admits the structure of a concrete category in a canonical way: consider the functor V:\mathcal{C} \to \mathbf{Set} that sends an object X to the set of all morphisms to X and a morphism f:X \to Y to the map V(X) \to V(Y) given by post-composing with f.  Then V is a faithful functor, which makes \mathcal{C} a concrete category.

Example C9.14 The category of all small categories \mathbf{Cat} is a concrete category. We can define a functor \mathrm{Mor}:\mathbf{Cat} \to \mathbf{Set}, by sending a small category \mathcal C to the set of all morphisms in \mathcal C and sending a functor between small categories to the induced map on the sets of morphisms. (Note that the action on the objects can be recovered from the action on morphisms by looking at the images of the identities). On the other hand,the functor \mathrm{Obj}:\mathbf{Cat} \to \mathbf{Set} that sends a small category to the set of its objects is not faithful, so it does not make \mathbf{Cat} into a concrete category.

Remark Not every category admits the structure of a concrete category. For example, Freyd showed that the category \mathbf{hTop} which has as objects topological spaces and as morphisms homotopy class of morphisms is not concretizable.

Consider the notion of a basis from linear algebra. We let V be the forgetful functor from the category of vector spaces over k for a fixed field k to the category of sets. Let X be a vector space and let B \subset V(X) be a subset. To phrase the notion of a basis in terms of morphisms, one can say that B is a basis for X if and only for every morphism of sets f:B \to V(W) to another vector space Y, we have a unique morphism of vector spaces g:X \to Y such that V(g)|_{B}=f.
This is just a formal way of saying that a subset of a vector space is a basis if and only if one can uniquely define linear maps to other vector spaces by the values of the basis vectors.

Having phrased the notion of a basis in this way, we can immediately abstract from the special case of vector spaces to arbitrary concrete categories.

Definition C9.14 Let (\mathcal C,V) be a concrete category. Then for an object X \in \mathcal{C}, we say that a map b:B \to V(X) is a basis for X if we have the following universal property: For any object Y \in \mathcal{C} and for any map f:B \to V(Y), there is a unique morphism g:X \to Y such that V(g) \circ b =f. We say that an object is free if it admits a basis.

Intuitively, a basis b:B \to V(X) for an object X is like a subset (as we may think of objects in a concrete category as sets by the virtue of the faithful functor that is part of the datum) except that we don’t require injectivitiy, which “generates” the object in the sense that any morphism from X to another object is determined by its restriction to B and which does so “indepedently” or “freely” that there are no “dependencies” between the elements of B in X that would restrict how we can define morphisms based on where the elements in B are sent.

Example C9.15 We already saw that bases in the sense of linear algebra are a special case of the abstract notion. The same holds for modules over a ring, although in general not every module is free.

Exercise C9.16 Consider the concrete category of topological spaces \mathbf{Top} with the forgetful functor to \mathbf{Set}, then a topological space is a free object if and only if the topology is discrete, and in this case the only possible basis is the whole space.

One can easily relate the property of a basis with representable functors:

Lemma C9.17 Let (\mathcal C,V) be a concrete category and let X be a set. Then there exists a free object in \mathcal C with basis X if and only if the functor \mathcal C \to \mathbf{Set}, M \mapsto \mathrm{Hom}_{\mathbf{Set}}(X,V(M)) is representable. In this case, a representing object corresponds to a free object and the universal element corresponds to the basis.

Proof This follows directly from lemma C5.3 in A Brief Introduction to Categories, Part 5: Universal Properties and Representable Functors.

One can observe that for modules over a ring R, a module is free if and only if it is isomorphic to a direct sum of copies of R and for topological spaces, a space is discrete if and only if it is homeomorphic to a disjoint union of singletons. The following lemma generalizes these obvservations.

Lemma C9.18 Let (C,V) be a concrete category. Suppose that V is representable by some object x. Then an object is free if and only if it isomorphic to a coproduct of copies of x.

Proof Let I be any index set and consider the coproduct \displaystyle \bigsqcup_{I} x We have natural isomorphisms \mathrm{Hom}_{\mathcal C}(\bigsqcup_{I} x,Y) \cong \prod_{I} \mathrm{Hom}_{\mathcal{C}}(x,Y) \cong \prod_{I} V(Y) \cong \mathrm{Hom}_{\mathbf{Set}}(I,V(Y)). We conclude by lemma C9.17 that \bigsqcup_{I} x is free with basis I.
Suppose that X \in \mathcal C is free with basis B \to V(X). Then by lemma C9.17 we have a natural isomorphism \mathrm{Hom}_{\mathcal C}(X,Y) \cong \mathrm{Hom}_{\mathbf{Set}}(B,V(Y)). By the computation from the other direction, the latter Hom set is naturally isomorphic to \mathrm{Hom}_{\mathcal C}(\bigsqcup_{B} x,Y). We conclude that X \cong \bigsqcup_{B} x by the Yoneda lemma.

Example C9.19 Consider the category of small categories \mathbf{Cat} with the concrete category structure given by the functor \mathrm{Mor} that sends a small category \mathcal C to the set of all morphisms in \mathcal C. \mathrm{Mor} is represented by the arrow category (cf. C3.6 and C5.7). Thus lemma C9.18 implies that a small category is free if and only if it is a disjoint union of copies of the arrow category. This means that for a set X, the free category generated by X is given by having for each x \in X, two objects s_x,t_x and a unique morphism x:s_x \to t_x (apart from the required identities).
Here’s a representation of the free category on three arrows (the identities are not depicted):

freecategory

At this point, I should justify why we talk about free objects in a post about adjunctions. We will generalize the situation first.

Adjunctions via Universal Morphisms

Definition C9.20 Let \mathcal C,\mathcal D be categories and let G:\mathcal D \to \mathcal C be a functor. Then we say that for an object X \in \mathcal C, there exists a local left adjoint at X if there is an object Y \in \mathcal D and a morphism u:X \to G(Y) with the following universal property: For every object Z \in \mathcal D and every morphism f:X \to G(Z) there is a unique morphism \tilde{f}:Y \to Z such that G(\tilde{f}) \circ u  =  f.

Local left adjoints are like bases. Clearly we have a free object in a concrete category (\mathcal C,V) with basis B, if and only if V has a local left adjoint at B.

The reason for name “local left adjoint” is the following theorem:

Theorem C9.21 Let \mathcal C,\mathcal D be categories and let G:\mathcal D \to \mathcal C be a functor. Then G has a left adjoint if and only if for every object X \in \mathcal C, G has local left adjoint at X.

Proof Suppose that G has a left adjoint F:\mathcal C \to \mathcal D. Let X \in \mathcal C be an object. Then we have the unit \eta_X:X \to GF(X), so we can set Y=F(X), u=\eta_X. Let Z \in \mathcal D be an object. As we have seen in lemma C9.6, the map \mathrm{Hom}_{\mathcal D}(F(X),Z) \to \mathrm{Hom}_{\mathcal C}(X,G(Z)), \tilde{f} \mapsto G(\tilde{f}) \circ \eta_X is a bijection, which means precisely that for every morphism f:X \to G(Z) there is a unique morphism \tilde{f}:F(X)=Y \to G(Z) such that G(\tilde{f}) \circ \eta_X=f.
Suppose that for every object X \in \mathcal C, G has local left adjoint at X. Call the local left adjoint of G at X F(X). We need to extend the assignment X \mapsto F(X) to a functor. Let f:X \to Y be a morphism in \mathcal C. We have morphisms u_x:X \to GF(X) and u_Y:Y \to GF(Y) satisfying the respective universal properties. Thus we have u_Y \circ f:X \to GF(Y) which gives us a unique morphism F(f):F(X) \to F(Y) such that GF(f) \circ u_X = u_Y \circ f.
We now have to check functoriality: let X,Y,Z \in \mathcal C and suppose we are given morphisms f:X \to Y and g:Y \to Z. By construction of F(f) and F(g), we have GF(f) \circ u_X = u_Y \circ f and GF(g) \circ u_Y = u_Z \circ g. We thus obtain u_Z \circ g \circ f=GF(g) \circ u_Y \circ f =GF(g) \circ GF(f) \circ u_X. But F(g \circ f) also satisfies GF(g \circ f) \circ u_X = u_Z \circ g \circ f and so by uniqueness, we obtain F(g \circ f)=F(g) \circ F(f). The fact that F preserves identities follows by a similar argument: both h=F(\mathrm{id}_X) and h=\mathrm{id}_{F(X)} satisfy the equation G(h) \circ u_X = \mathrm{id}_X \circ u_X=u_X.
We now have to check that F is left adjoint to G.
Since F(X) is a local left adjoint to G for any X, we have for any morphism g:F(X) \to Y a unique morphism \tilde{f}:X \to G(Y) such that G(\tilde{f}) \circ u_X = f. This implies that the map H_{X,Y}:\mathrm{Hom}_{\mathcal D}(F(X),Y) \to \mathrm{Hom}_{\mathcal D}(X,G(Y)), g \mapsto G(g) \circ u_X is a bijection.

adjunction

In equations, for any h:F(X) \to Y, we need to check that
H_{X',Y'}(g \circ h \circ F(f)) = G(g) \circ H_{X,Y}(h) \circ f, that is
G(g \circ h \circ F(f)) \circ u_{X'}=G(g) \circ G(h) \circ u_X \circ f. But this follows from the functoriality of G and the fact that GF(f) \circ u_{X'} = u_X \circ f, which was already mentioned in the construction of F(f).

Adjunctions via Representability

Due to the close connections between representability and universal properties that were established by lemma C5.3 in A Brief Introduction to Categories, Part 5: Universal Properties and Representable Functors, we can immediately conclude from theorem C5.21:

Corollary C9.22 A functor G:\mathcal D \to \mathcal C has a local left adjoint at X \in \mathcal C if and only if the functor D \to \mathbf{Set}, Y \mapsto \mathrm{Hom}_{\mathcal C}(X,G(Y)) is representable.

Example C9.23 Let \mathcal C be a category and let I be a small category, thought of as an index category. Then the diagonal functor \Delta:\mathcal C \to [I,\mathcal C], which sends an object X \in \mathcal C to the constant functor with value X has a local left adjoint at an object F \in [I,\mathcal C] if and only if the colimit over F exists in C.

Proof Apply the dualized version of lemma C7.10 in A Brief Introduction to Categories, Part 7: General Limits and Colimits.

Combining theorem C9.21 and corollary C9.22, we obtain:

Corollary C9.24 A functor G:\mathcal D \to \mathcal C has a left adjoint if and only if for every X \in \mathcal C, the functor \mathcal D \to \mathbf{Set},  Y \mapsto \mathrm{Hom}_{\mathcal C}(X,G(Y)) is representable.

Dualizing, we obtain:

Corollary C9.25 A functor F:\mathcal C \to \mathcal D has a right adjoint if and only if for each Y \in \mathcal D, the functor C^{op} \to \mathbf{Set}, X \mapsto \mathrm{Hom}_{\mathcal D}(F(X),Y) is representable.

Example C9.26 Let \mathcal C be a category and let I be a small category, thought of as an index category. Then the diagonal functor \Delta:\mathcal C \to [I,\mathcal C], which sends an object X \in \mathcal C to the constant functor with value X has a left adjoint if and only if for all functors F:I \to \mathcal C, the colimit \varinjlim F exists in \mathcal C.  Dually, this functor has a right adjoint if and only if the limits for all F \in [I,\mathcal C] exist.

Thus one can think of adjoint functors as a parametrized version of representable functors, providing yet another view on this important concept. We can also turn this around and see that representable functors are special case of adjoint functors. To see this, we use the characterization of representability via the existence of initial objects in a certain category.

Lemma C9.27 Let \mathcal C be a category. Then \mathcal C has an initial object if and only if the terminal functor \mathcal C \to * has a left adjoint. Here * is the category with one object and one morphism. If G is a left adjoint, then G evaluted at the unique object of * is an initial object.

Proof Exercise. (There’s not much to check)

Corollary C9.28 A functor F:\mathcal D \to \mathbf{Set} is representable if and only if the terminal functor \int F \to * has a left adjoint. Here \int F is the category of elements, as defined here in definition C5.14. In this case, the value of a left adjoint at the unique object of * is a pair (X,u), where X \in \mathcal D is a representing object and u \in F(X) is a universal element.

This follows directly from lemma C9.24 and lemma C5.15 in A Brief Introduction to Categories, Part 5: Universal Properties and Representable Functors.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s