A Brief Introduction to Categories, Part 8: Adjunctions I

This post is part of a series on category theory, see Overview of Blog Posts for a list of all posts. As always, knowing the background of every single example is not required to understand the general concept. All categories are assumed to be locally small.

Introduction

In this post, we shall study another fundamental notion of category theory that arises with remarkable ubiquity: adjoint functors. Given a functor, one can think of an adjoint as a very weak form of an inverse. There are close connections to representable functors, limits and equivalences. Knowing the basics about adjunctions of functors can be quite useful as they enjoy a non-empty set of nice properties. For illustrative purposes, we shall start by studying the special case of adjunctions between partially ordered sets, which are called Galois connections.

Galois Connections

Definition C8.1 Let (A,\leq) and (B,\leq) be partially ordered sets (i.e. each comes equipped with a reflexive,transitive and antisymmetric relation), then a map f:A \to B is called

  • isotone, if for all a,a' \in A we have a \leq a' \Rightarrow f(a) \leq f(a').
  • antitone, if for all a,a' \in A we have a,\leq a' \Rightarrow f(a') \leq f(a).

Remark If one considers (A,\leq) and (B,\leq) as categories (note that every partially ordered set is in particular preordered, so cf. example C1.5), then isotone maps correspond to covariant functors and antitone maps correspond to contravariant functors.

Definition C8.2 Let (A,\leq) and (B,\leq) be partially ordered sets, then a covariant (or contravariant, respectively) Galois connection from A to B consists of the following data:

  • An isotone (or antitone, respectively) map F:A \to B
  • An isotone (or antitone, respectively) map G:B \to A

Such that the following condition holds:

  • For all a \in A and b \in B, we have F(a) \leq b \Leftrightarrow a \leq F(b)

We write F \dashv G

Example C8.3 Let f:X \to Y be a map. Then the power sets \mathcal{P}(X) and \mathcal{P}(Y) are partially ordered by inclusion, and we have isotone maps f_*:\mathcal{P}(X) \to \mathcal{P}(Y), U \mapsto f(U) and f^*:\mathcal{P}(X) \to \mathcal{P}(Y) \to \mathcal{P}(X), V \mapsto f^{-1}(V) and it holds that f(U) \subset V \Leftrightarrow U \subset f^{-1}(V) for all U \in \mathcal{P}(X),V \in \mathcal{P}(Y), so this is an example of a Galois connection.

Example C8.4 Let G be a group and let H be a normal subgroup. Then consider the partially ordered sets of all subgroups of G and G/H, respectively. Let \pi:G \to G/H be the canonical projection map. Then one can define maps \pi_*:\mathrm{Subgrp}(G) \to \mathrm{Subgrp}(G/H), U \mapsto \pi(U) and \pi^*:\mathrm{Subgrp}(G/H) \to \mathrm{Subgrp}(G), V \mapsto \pi^{-1}(V). As in the last example, we have \pi_* \dashv \pi^*, so this is an example of a Galois connection.

Example C8.5 Let R and S be commutative rings and let f:R \to S be a ring homomorphism. Then we can consider the sets of all ideals of R and S, respectively, denoted by I(R) and I(S). I(R) and I(S) are partially ordered by inclusion and we have isotone maps I(R) \to I(S), I \mapsto S \cdot f(I):=I^{e} (the ideal generated by f(I)) I(S) \to I(R), J \mapsto f^{-1}(J):=J^{c}, called extension and contraction. One has that I^{e} \subset J \Leftrightarrow I \subset J^{c} for all I \in I(R), J \in I(S), so this yields another example of a Galois connection.

Example C8.6 The eponymous example of a Galois connection comes from Galois theory. Let L/K be any field extension. Then one can consider G=\mathrm{Aut}_K(L) and the set of all subgroups of G, denoted by \mathrm{Subgrp}(G) and the set of all intermediate fields L \backslash \mathbf{Fld}/K, both partially ordered by inclusion. Then one has antitone maps \mathrm{Subgrp}(G) \to L \backslash \mathbf{Fld}/K, H \mapsto L^H := \{l \in L \mid \forall h \in H:h(l)=l \} and L\backslash \mathbf{Fld}/K \to \mathrm{Subgrp}(G), E \mapsto \mathrm{Aut}_E(L):=\{g \in G \mid \forall e \in E:g(e)=e \}. One checks that H \subset \mathrm{Aut}_E(L) \Leftrightarrow L^H \subset E, so that this is a contravariant Galois connection.

Example C8.7 Now for a geometric example. Let k be an algebraically closed field. Then the set of subsets \mathcal{P}(k^n) is partially ordered by inclusion. On the other hand, consider the set of all ideals in k[x_1, \dots,x_n], I(k[x_1, \dots, x_n]), partially ordered by inclusion. then we have antitone maps I:\mathcal{P}(k^n) \to I(k[x_1,\dots,x_n]), X \mapsto I(X):=\{f \in k[x_1, \dots,x_n] \mid \forall x \in X: f(x)=0\} and V:I(k[x_1,\dots,x_n]) \to \mathcal{P}(k^n), J \mapsto V(J):=\{x \in X \mid \forall f \in J:f(x)=0\}. We have that J \subset I(X) \Leftrightarrow V(J) \subset X. The sets V(J) are sets that “cut out” via polynomial equations. The example is geometric in the sense that many common geometric subsets of say \Bbb R^n (although this is not algebraically closed) can be defined via polynomial equations, such as circles, lines, parabolas, hyperbolas, conics etc.

To see that the notion of Galois connections is useful, let’s prove something.

Lemma C8.8 Let A and B be partially ordered sets and F:A \to B, G:B \to A be isotone maps that form a Galois connection, i.e. F \dashv G. Then we have FGF(X)=F(X) for all X \in A and GFG(Y)=G(Y) for all Y \in B.

Proof We have F(X) \leq F(X) and hence X \leq GF(X) as F \dashv G. Applying F using isotonicity, we obtain F(X) \leq FGF(X). On the other hand, we get that GF(X) \leq GF(X) and hence FGF(X) \leq F(X) as F \dashv G. Thus by antisymmetry, we obtain FGF(X)=F(X). The other statement is proved analogously.

Corollary C8.9 Let A and B be partially ordered sets and F:A \to B, G:B \to A be antitone maps that form a contravariant Galois connection, i.e. F \dashv G. Then FGF(X) = F(X) for all X \in A and GFG(Y)=G(Y) for all Y \in B.

Proof Replace A and B by the opposite category to obtain a covariant Galois connection, now apply the previous result.

Definition C8.10 Let A and B be partially ordered sets and F:A \to B, G:B \to A be either two isotone or two antitone maps that form a Galois connection. Then call X \in A closed if and only if X=G(Y) for some Y \in X. Similarly, call Y \in B closed if and only if Y=F(X) for some X \in A.

Corollary C8.11 Let A and B be partially ordered sets and F:A \to B, G:B \to A be either two isotone or two antitone maps that form a Galois connection, i.e. F \dashv G. Then the maps F and G induce a bijection between the closed elements of A and the closed elements of B. Furthermore, X \in A is closed if and only if GF(X)=X and Y \in B is closed if and only if FG(Y)=Y.

Proof Clear from lemma C8.8 and C8.9 by the equations FGF(X)=F(X) and GFG(Y)=G(Y).

Definition C8.12 Let A and B be partially ordered sets and F:A \to B, G:B \to A be either two isotone or two antitone maps that form a Galois connection, i.e. F \dashv G. Then the maps A \to A, X \mapsto GF(X) and B \to B, Y \mapsto FG(Y) are called closure operators.

Remark To motivate the terminology, note that GF(X) is the smallest closed element of A containing X.

Example C8.13 Let G be a group and N be a normal subgroup and consider the Galois connection from example C8.4. As the projection \pi:G \to G/N is surjective, we have \pi_* \pi^*(U)=U for any subgroup U of G/N, so every subgroup of G/N is closed. On the other hand, it’s easy to see that for a subgroup V of G, we have V=\pi^*\pi_*(V) if and only if N \subset V, in general \pi^* \pi_*(V) is the subgroup generated by N and V. It follows that \pi_* and \pi^* induce order-preserving bijections between subgroups of G/N and subgroups of G containing N by corollary 8.11, which recovers a well-known fact from group theory.

Example C8.14 Let L/K be a field extension, then applying corollary 8.11 to the Galois connection from example C8.6, we obtain an order-reversing bijection between intermediate extensions of the form L^{H} for some subgroup H \subset \mathrm{Aut}_K(L) and subgroups of \mathrm{Aut}_K(L) of the form \mathrm{Aut}_E(L) for some intermediate extension E. If L/K is algebraic and Galois, then one can show that every intermediate extension is closed, and that the closed subgroups are the subgroups which are closed in the topology which has a basis at the identity by \mathrm{Gal}(L/E) for all intermediate extensions E such that L/E has finite degree. The correspondence between intermediate extensions and closed subgroups is the main result of Galois theory. (In the finite case, the topology is discrete and hence every subgroup is closed.)

Example C8.15 Let k be an algebraically closed field and let n be a natural number. Then consider the Galois connection between subsets of k^n and ideals in k[x_1,\dots,x_n]. One can show that the subsets of k^n of the form V(J) for an ideal J \subset k[x_1,\dots,x_n] form the closed subsets of a topology on k^n, called the Zariski topology. Hilbert’s Nullstellensatz may be stated in the form I(V(J))=\mathrm{rad}(J) := \{f \in k[x_1,\dots,x_n] \mid \exists m \in \Bbb N, f^m \in J\}. An ideal J is called radical if \mathrm{rad}(J)=J. From the formalism of Galois connections, in particular corollary 8.16, we obtain an order-reversing bijection between subsets in k^n that are cut out by polynomials and radical ideals in k[x_1,\dots,x_n]. The difficult part here is computing the closure operator, the rest is a formality. This is an important bridge between algebra and geometry.

Adjunctions via Hom-Sets

Definition C8.16 Let \mathcal{C} and \mathcal{D} be categories and let F:\mathcal{C} \to \mathcal{D} and G:\mathcal{D} \to \mathcal{C} be functors. Then an adjunction of the pair (F,G) is given by a natural isomorphism of functors \mathcal{C}^{op} \times \mathcal{D} \to \mathbf{Set}, \mathrm{Hom}_{\mathcal D}(F(-),-) \cong \mathrm{Hom}_{\mathcal C}(-,G(-)). If an adjunction exists, F and G are called adjoint, denoted by F \dashv G. In this case, F is called left adjoint to G and G is called right adjoint to F.

Exercise Verify that the notion of an adjunction specializes to that of a Galois connection in the case of partially ordered sets.

Example C8.17 Consider the category of commutative rings \mathbf{CRing} and the full subcategory of reduced commutative rings \mathbf{CRing}_{\mathrm{red}}. We have a forgetful functor V:\mathbf{CRing}_{\mathrm{red}} \to \mathbf{CRing}. We also have a functor \mathbf{CRing} \to \mathbf{CRing}_{\mathrm{red}} that sends a ring A to the associated reduced ring A_{\mathrm{red}}:=A/\mathrm{nil}(A), the quotient by the nilradical. As every ring homomorphism f:A \to B from any commutative ring A to a reduced commutative ring B factors uniquely through A_{\mathrm{red}}, we obtain a natural bijection between ring homomorphisms f:A \to B and ring homomorphisms A_{\mathrm{red}} \to B, so that the functor A \mapsto A_{\mathrm{red}} is left adjoint to the forgetful functor V.

Example C8.18 Let R and S be rings and let M be a R,S-bimodule. Then we have a functor R\textrm{-}\mathrm{Mod} \to S\textrm{-}\mathrm{Mod} given by \mathrm{Hom}_R(M,-), this functor has a left adjoint given by the tensor product M \otimes_S-.

Example C8.19 Consider the category \mathbf{Cat} of small categories. We have a functor \mathrm{Obj}:\mathbf{Cat} \to \mathbf{Set} which sends a small category to its set of objects. Given a set X we can form the discrete category \mathrm{Disc}(X) on X (see example C1.4 for details). Now a functor \mathrm{Disc}(X) \to \mathcal{C} for some category \mathcal{C} is determined uniquely by a map X \to \mathrm{Obj}(C): As the only morphisms in \mathrm{Disc}(X) are identities, the action of a functor on morphisms is determined completely by the action on objects. Thus \mathrm{Disc} is left adjoint to \mathrm{Obj}.

Example C8.20 Let \mathcal{C} be the following category: objects are pairs (A,S), where A is a commutative ring and S \subset A is a multiplicatively closed subset and morphisms (A,S) \to (B,T) are ring homomorphisms f such that f(S) \subset T. Let \mathbf{CRing} be the category of commutative rings. We have a functor G:\mathbf{CRing} \to \mathcal{C} sending A to (A,A^\times). The universal property of localization may be stated by saying that this functor has a left adjoint given by (A,S) \mapsto S^{-1}A.

Example C8.21 Let \mathbb{K} be a complete normed field, such as \mathbb{R}, \mathbb{C} (or even \mathbb{Q}_p, \mathbb{C}((x)) etc.). Now consider the category of normed vector spaces over \mathbb{K} with bounded linear maps as morphisms, denoted by \mathbf{Norm}_{\mathbb{K}} and the full subcategory of complete normed spaces, i.e. Banach spaces over \mathbb{K}. We have a forgetful functor \mathbf{Ban}_{\mathbb{K}} \to \mathbf{Norm}_{\mathbb{K}}. We also have the completion functor \mathbf{Norm}_{\mathbb{K}} \to \mathbf{Ban}_{\mathbb{K}}. As bounded linear maps are uniformly continuous and every normed space is dense in its completion, we get that for a normed space V and a complete normed space W, every bounded linear map V \to W extends uniquely to a bounded linear map \widehat{V} \to W, where \widehat{V} denotes the completion of V. This shows that the completion functor is left adjoint to the forgetful functor \mathbf{Ban}_{\mathbb{K}} \to \mathbf{Norm}_{\mathbb{K}}.

An analogy with linear algebra

The terminology “adjunction” comes from an analogy with linear algebra. Let \mathcal C and \mathcal D be categories. Then these come equipped with their respective Hom-functors \mathcal{C}^{op} \times \mathcal{C} \to \mathbf{Set}, \mathcal{D}^{op} \times \mathcal{D} \to \mathbf{Set}. One can think of these Hom functor as being analogous to inner products. Then the Yoneda lemma tells us that these inner products are non-degenerate. In this analogy, for two functors F:\mathcal C \to \mathcal D and G:\mathcal D \to \mathcal C, having a natural isomorphism \mathrm{Hom}_{\mathcal D}(F(X),Y) \cong \mathrm{Hom}_{\mathcal C}(X,G(Y)) corresponds to having an equality \langle f(v),w \rangle_W = \langle v,g(w) \rangle_V for two inner product spaces V,W and linear maps f:V \to W, g:W \to V, which is what defines g to be the adjoint map to f.