Adjoint Functors

I struggled for some time with the concept of adjoint functors. Even before writing down the definition, I find their very type signature somewhat unusual. An adjoint pair $L\dashv R$ consists of two functors $L:C\to D$ and $R:D\to C$. They generalize isomorphisms between categories, in that the inverse to an invertible functor is both, its left and right adjoint. But unlike other generalizations, like left-inverses or right-inverses, they are unique (up to natural isomorphism), that means, if the adjoint pair $L\dashv R$ exists, then $R$ is uniquely recoverable from $L$ and vice versa. Also, from $L\dashv R$ we can’t say anything about left adjoints of $L$ or right adjoints of $R$, they might or might not exist, and they might or might not be equal to $R$ or $L$ respectively. So while it’s common to name the functors $L$ and $R$ when discussing a single adjoint pair, there is nothing inherent to $R$ making it a right adjoint, it could just as well be the left adjoint to another functor, and vice versa.

Before defining adjoint functors, we need to establish some concepts. First, can functors be meaningfully isomorphic? Do they live in a category themselves? Well, in the category $\ccat$, functors appear as morphisms between categories, but if we want to talk about functors being isomorphic to each other, we should instead consider a category where functors are objects and morphisms between them are something else. Here it makes sense to consider not arbitrary functors but start with the set $[C,D]$ of functors between fixed categories $C$ and $D$. How could we possibly draw an arrow from $F:C\to D$ to $G:C\to D$? For all $c\in C$, the objects $Fc$ and $Gc$ live in the same category $D$, so naturally we can look at morphisms between the two. A possible arrow from $F$ to $G$ is a family $\{\alpha_c\}_c$ of morphisms $\alpha_c:Fc\to Gc$. That alone would be enough to constitute a category structure on $[C,D]$, but like so often in category theory, we want certain freely constructed entities with matching types to be actually equal. Given a morphism $f:c\to d$ in $C$, we can construct the following square:

In other words, there are two canonical morphisms from $Fc$ to $Gd$ constructed just from the presence of $f$ without any further assumptions, so it would be natural to ask for equality between these two, or in other words, the square to commute. That is exactly the definition of a natural transformation between functors and it’s the standard categorical structure on $[C,D]$.

If all arrows in the category are unique, so hom-sets are empty or singletons, then we clearly don’t need to check for the naturality condition.

Further, a natural isomorphism is a just natural transformation with an inverse. If $\alpha$ has an inverse transformation $\beta$, in the sense of $\beta_c$ being a pointwise inverse to $\alpha_c$ for all $c\in C$, then $\beta$ is automatically natural:

Given objects $c,d\in C$, the hom-set of morphisms from $c$ to $d$, written $\hom_C(c,d)$. So $\hom_C(*,*)$ is a function from $C\times C$ to $\cset$, it takes a pair of objects and returns the hom-set between these objects, and we want to turn this into a functor. This works best if we choose $C^\op\times C$ rather than $C\times C$ as the domain of the functor, $C^\op$ has the same objects as $C$, but all arrows are reversed. A morphism $(a,b):(c,d)\to(c',d')$ in this category consists of $a:c\to c'$ in $C^\op$, that is $a:c'\to c$ in $C$, and $b:d\to d'$ in $D$. How would that be mapped under the functor $\hom_C(*,*)$, that is, how to construct a function from $\hom_C(c,d)$ to $\hom_C(c',d')$? Given a morphism $f:c\to d$, we can construct the composition $b\circ f\circ a:c'\to d'$. Abstracting over $f$, this yields a function $b\circ*\circ a:\hom_C(c,d)\to\hom_C(c',d')$, and one can check that it satisfies all requirements to turn $\hom_C(*,*)$ into a functor.

At this point, we have all the pieces in place to define adjoint functors. Given $L:C\to D$ and $R:D\to C$ as before, we can construct the functor compositions $\hom_D(L*,*):=\hom_D(*,*)\circ(L\times\id_D)$ and $\hom_C(*,R*):=\hom_C(*,*)\circ(\id_C\times G)$, both running from $C^\op\times D$ to $\cset$.

$L$ and $R$ form an adjoint pair $L\vdash R$, if and only if there is a natural isomorphism

For clarity, we can write out the square from before, to see what naturality exactly means here:

We said before that we don’t need to check for naturality if the hom-sets are empty or singletons. In the naturality square above, however, we need to distinguish between two levels of hom-sets, the hom-sets between elements in $C$ or $D$, which act as objects in $\cset$, and appear in the corners of the square, and the hom-sets between them. Interestingly, if two objects in $\cset$ are empty or singletons, then the set of functions between them is necessarily empty or a singleton as well. As a result, when verifying adjoint functors in a category where all hom-sets are empty or singletons, we don’t need to check for naturality explicitly. Furthermore, since we talk about isomorphism in $\cset$, in this special case it suffices to check that all $\hom_D(Lc,d)$ and $\hom_C(c,Rd)$ agree in their inhabitedness, that is, that they are either both empty or both singletons, as can be seen in the next example.

Adjoint functors are sometimes motivated as approximate inverses, which approximate the possibly non-existing inverse to a functor from above (left adjoint) or below (right adjoint), where above and below is kept vague here. An example illustrating this point is the embedding $\iota:\zz\to\rr$ of integers into real numbers. Here, we turn partially (or in this case, totally) ordered sets into categories by assuming exactly one unique arrow $x\to y$ whenever $x\preceq y$. For a non-integer number such as $\pi$, we can’t directly map it back into $\zz$, the closest maps we get are $\mathsf{ceil}:\rr\to\zz$, choosing the smallest integer greater or equal to the input, and $\mathsf{floor}:\rr\to\zz$, choosing the largest integer smaller or equal to the input. It turns out that these are exactly the left and right adjoints to $\iota$ respectively.

Since all arrows in poset categories are unique, as discussed before, checking the adjointness in the case of $\mathsf{ceil}$ simplifies to verifying that $\hom_\zz(\mathsf{ceil}(*),*)$ is inhabited if and only if $\hom_\rr(*,\iota(*))$ is. This condition boils down precisely to $\mathsf{ceil}(r)\le z\Leftrightarrow r\le\iota(z)=z$, which is equivalent to the definition of $\mathsf{ceil}$. Verifying that $\mathsf{floor}$ is the right adjoint works similarly.

Another, more typical, example of adjoints is the free group functor, which is the right adjoint to the forgetful functor $|*|:\mathsf{Grp}\to\cset$. Unfortunately, this one only has only one adjoint, so we can’t see the dual approximation from two sides.

The forgetful functor $|*|$ takes a group $G$ and maps it to the base set $|G|$, forgetting all the group structure. The question for a right adjoint then is, can we simulate all the arrows from base sets to other sets within the category of groups? Can we find for each set $X$ some group $Rx$ such that the set functions from $|G|$ to $X$ correspond exactly to the group morphisms from $G$ to $RX$? This concept is called the free group $F_X$ on $X$, its elements are all the words over the alphabet $\{x,x^{-1}:x\in X\}$ with no occurences of pairs of inverses like $xx^{-1}$ or $x^{-1}x$, and the multiplication is just concatenation of words with deletion of possibly newly created pairs of inverses afterwards. The neutral element is the empty word. This group has the special property that for every group $G$ and any set function $f:|G|\to X$ there is a unique group homomorphism $\hat f:G\to F_X$ extending $f$.

For a deeper understanding, let’s briefly revisit invertible functions in $\cset$, it can serve as a blueprint for invertible functors and how adjoints generalize them. A bijection (isomorphism) $f:X\to Y$ can be defined as an injective and surjective function, or as the existence of $g:Y\to X$ such that $fg=\id_Y$ and $gf=\id_X$. However, there is a third perspective: both functions $f$ and $g$ can be seen as representing the same information, just encoded in different ways. Every function $f:X\to Y$ can be represented by its graph $\mathsf{graph}(f)$, defined as the set of pairs ${(x,f(x)):x \in X}$. Conversely, every function $g:Y\to X$ can be represented by its graph in reverse order, which I’ll denote by $\mathsf{graph}^T(g)$, consisting of the pairs ${(g(y),y):y\in Y}$. Thus, we have an embedding $\mathsf{graph}:X^Y\to\mathcal{P}(X \times Y)$ and another embedding $\mathsf{graph}^T:Y^X\to\mathcal{P}(X\times Y)$. Within this framework, a function $f:X\to Y$ is invertible precisely when its graph lies in the intersection of these two embeddings. We will see that there is a similar framework for categories, aiding with the understanding of adjoint functors. But before we can explore this further, we need to build up some machinery.

A so-called presheaf on $C$ is just a functor $S:C^\op\to\cset$, and the category of presheaves, denoted $\psh(C)$, is defined as $[C^\op,\cset]$. We can construct a functor from $C$ to $\psh(C)$ by assigning an object $c\in C$ to the presheaf $\hom_C(*,c)$ which maps objects $c'\in C$ to the set $\hom_C(c',c)$. A morphism $f:c\to d$ acts then on these hom-sets via post-composition. We’ll shortly see that this is actually an embedding, and it’s called the Yoneda embedding functor $y_C:C\to\psh(C)$. Conversly, a presheaf $S$ on $C$ is called representable if it is isomorphic to $y_C(c)$ for some $c\in C$.

The Yoneda Lemma, which we won’t prove here, states that for every presheaf $S$ on $C$ and every object $c'\in C$, there is a natural bijection between the sets $S(c')$ and $\hom_{\psh(C)}(y_C(c'),S)$, or more precisely, a natural isomorphism between the functors $S$ and $\hom_{\psh(C)}(y_C(*), S)$ from $C^\op$ to $\cset$. This is quite a lot to digest, but for us, the important case is where $S$ equals the presheaf $y_C(c)$. Here it says that for every $c'\in C$, there is a natural bijection between the set the set $y_C(c')$, that is, the morphisms from $c'$ to $c$, and the set of natural transformations from $y_C(c')$ to $y_C(c)$. This tells us that $y_C$ is indeed an embedding, that is, a functor injective on objects and bijective on hom-sets. Another way of looking at it’s that the full subcategory of $\psh(C)$ spanned by the objects $y_C(c)$ is isomorphic to $C$.

The category of presheaves over $C$ is in some sense the completion of $C$, automatically satisfying nice properties like completeness and cocompleteness, even when $C$ does not. However, while sometimes compared to the completion of a metric space, the analogy is not perfect. First, there’s no idempotence: $\psh(\psh(C))$ typically doesn’t resemble $\psh(C)$, you can repeatedly create new structure by taking presheafs from presheafs. Second, unlike the situation with metric spaces and continuous functions, two functors from $\psh(C)$ to $\psh(D)$ that agree on $C$ don’t need to be equal or even isomorphic. Third, there’s a directional subtlety absent from the metric setting. The opposite category $C^\op$ encodes the same data underlying data with arrows reversed, yet $\psh(C^\op)$ can differ significantly from $\psh(C)$. This provides two different “completions” from the same starting point, a phenomenon with no analogue for metric spaces.

In set theory, currying refers to the process of transforming a function $f:X\times Y\to Z$ into a function $\hat f:X\to Z^Y$, defined by $\hat f(x)(y):=f(x,y)$. This establishes a bijection between $Z^{X\times Y}$ and $(Z^Y)^X$. The same concept carries over to category theory, where we have an isomorphism between $[C \times D, E]$ and $[C, [D, E]]$. At the level of objects, this correspondence is entirely analogous to the set-theoretic case, and at the level of morphisms, it extends naturally. By swapping $C$ and $D$ (clearly, $C\times D$ is isomorphic to $D\times C$), one obtains another isomorphism between $[C\times D, E]$ and $[D, [C, E]]$.

Recall that for adjoint pairs $L\vdash R$, the functors $\hom_D(L*,*)$ and $\hom_C(*,R*)$ must be isomorphic in $[C^\op\times D,\cset]$, which is also called the category of profunctors from $D$ to $C$, written $\prof(D,C)$. By currying, this category is isomorphic both to $[C^\op,[D,\cset]]$ and $[D,[C^\op,\cset]]$, or written in terms of presheafs, $[C^\op,\psh(D^\op)]$ and $[D,\psh(C)]$.

We can extend the codomain of any $L:C\to D$ to $\psh(D)$ via post-composition with $y_D$. This operation yields an embedding of $[C,D]$ into $[C,\psh(D)]$, and, by uncurrying, also into $\prof(C,D)$. Similarly, we can post-compose any $R:D\to C$ with $y_C$, this yields an object in $[D,\psh(C)]$, but this does uncurry to $\prof(D,C)$ and not $\prof(C,D)$, so we need a different approach. Taking the opposite functor $R^\op:D^\op\to C^\op$, which contains precisely the same data as $R$, post-composing it with $y_{C^\op}$ yields an object in $[D^\op,\psh(C^\op)]$, which nicely uncurries to $\prof(C,D)$. We could of course also use $\prof(D,C)$ as common ambient category, by taking the opposite of $L$ instead of $R$, in the end it’s just a matter of taste.

This reveals an interesting perspective. The profunctor category $\prof(D,C)$ acts as an ambient category for both, $[C,D]$ and $[D,C]$, analogous to how $\mathcal{P}(X\times Y)$ acts as an ambient set for $X^Y$ and $Y^X$. For a functor $L':C\to\psh(D)$, there is always a corresponding functor $R':D^\op\to\psh(C^\op)$, due to the isomorphism $[C,\psh(D)]\cong[D^\op,\psh(C^\op)]$, and vice versa. So also every $L:C\to D$ has a corresponding “pseudo-adjoint” (not a standard term) $R':D^\op\to\psh(C^\op)$, by using $L':=y_C\circ L$, but if it doesn’t map $D^\op$ neatly into the essential image of $y_{D^\op}$, that is the extension of the image by isomorphic objects (presheafs), then $L$ has no right adjoint, and vice versa for $R:D\to C$.

In other words, to find a right adjoint to $L$, it suffices that for each object $d\in D$, the presheaf $\hom_D(L*,d)$ is representable in $C$. This presheaf is precisely the value of $d$ under the pseudo-adjoint $R'$ constructed above. If $R'd$ happens to lie in the essential image of the Yoneda embeding $y_C$, then there exists an object $Rd\in C$ with

This might seem odd at first because it appears to require naturality only in $C$, whereas the definition of adjoint functors demands combined naturality in both $C$ and $D$. The reason for this discrepancy is that we have not fixed any action on morphisms for $R$, we only verified the existence of an adjoint by checking locally for representability. The morphisms come straight from the pseudo-adjoint $R'$, by fullness of the Yoneda embedding, if the presheafs $\hom_D(L*,d)$ are representable in $C$, then any natural transformations between these presheafs, so especially the images of morphisms $g:d\to d'$ in $D$ under $R'$, are automatically representable as well, that means, there is a unique morphism in $C$ corresponding to the natural transformations $y_D(g)$.

So to summarize, in order to verify adjointness of a given pair of functors, hom-set bijections must be established and naturality checked in both variables. But to verify the existence of an adjoint to a given functor, it suffices to check locally, for each object, whether the corresponding Yoneda embedding is representable.