The Unapologetic Mathematician

Mathematics for the interested outsider

Today I return to the discussion of universals, limits, representability, and related topics. The last piece of this puzzle is the notion of an adjunction. I’ll give a definition and examples today and work out properties later.

An adjunction between categories $\mathcal{C}$ and $\mathcal{D}$ consists of a pair of functors $F:\mathcal{C}\rightarrow\mathcal{D}$ and $G:\mathcal{D}\rightarrow\mathcal{C}$ and a natural isomorphism $\Phi_{X,Y}:\hom_\mathcal{D}(F(X),Y)\rightarrow\hom_\mathcal{C}(X,G(Y))$. Notice that the functors on either side of $\Phi$ go from $\mathcal{C}^\mathrm{op}\times\mathcal{D}$ to $\mathbf{Set}$, so each component $\Phi_{X,Y}$ is a bijection of sets. We say that $F$ is “left adjoint” to $G$, and conversely that $G$ is “right adjoint” to $F$, and we write $F\dashv G$.

Now, we have been seeing these things all along our trip so far, but without mentioning them as such. For instance, we have all the “free” constructions:

and maybe more that I’ve mentioned, but don’t recall.

These all have a very similar form in their definitions. For instance, the free monoid $M(S)$ on a set $S$ is characterized by the following universal property: every function $f$ from $S$ into the underlying set of a monoid $N$ extends uniquely to a monoid homomorphism $\bar{f}:M(S)\rightarrow N$. If we write the underlying set of $N$ as $U(N)$, we easily see that $U:\mathbf{Mon}\rightarrow\mathbf{Set}$ is a functor. The condition then is that every element of the hom-set $\hom_\mathbf{Set}(S,U(N))$ corresponds to exactly one element of the hom-set $\hom_\mathbf{Mon}(M(S),N)$, and every monoid homomorphism restricts to a function on $S$. That is, for every set $S$ and monoid $N$ we have an isomorphism of sets $\hom_\mathbf{Mon}(M(S),N)\cong\hom_\mathbf{Set}(S,U(N))$.

Now, given a function from a set $S_1$ to a set $S_2$ we can consider $S_2$ to be a subset of the free monoid on itself, giving a function $f:S_1\rightarrow U(M(S_2))$. This extends to a unique monoid homomorphism $M(f):M(S_1)\rightarrow M(S_2)$. This construction preserves identities and compositions, making $M$ into a functor from $\mathbf{Set}$ to $\mathbf{Mon}$.

If we have a function $f:S_1\rightarrow S_2$ and a monoid homomorphism $m:N_1\rightarrow N_2$ then we can build functions $\hom_\mathbf{Mon}(M(f),m):\hom_\mathbf{Mon}(M(S_2),N_1)\rightarrow\hom_\mathbf{Mon}(M(S_1),N_2)$ and $\hom_\mathbf{Set}(f,U(m)):\hom_\mathbf{Set}(S_2,U(N_1))\rightarrow\hom_\mathbf{Set}(S_1,U(N_2))$. The isomorphisms $\hom_\mathbf{Mon}(M(S_2),N_1)\cong\hom_\mathbf{Set}(S_2,U(N_1))$ and $\hom_\mathbf{Mon}(M(S_1),N_2)\cong\hom_\mathbf{Set}(S_1,U(N_2))$ commute with these arrows, so they form the components of a natural isomorphism between the two functors. This proves that the free monoid functor $M:\mathbf{Set}\rightarrow\mathbf{Mon}$ is a left adjoint to the forgetful functor $U:\mathbf{Mon}\rightarrow\mathbf{Set}$.

All the other examples listed above go exactly the same way, giving left adjoints to all the forgetful functors.

As a slightly different example, we have a forgetful functor $U:\mathbf{Ab}\rightarrow\mathbf{Grp}$ that takes an abelian group and “forgets” that it’s abelian, leaving just a group. Conversely, we can take any group $G$ and take the quotient by its commutator subgroup $\left[G,G\right]$ to get an abelian group. This satisfies the property that for any group homomorphism $f:G\rightarrow U(A)$ from $G$ to an abelian group $A$ (considered as just a group) there is a unique homomorphism of abelian groups $\bar{f}:G/[G,G]\rightarrow A$. Thus it turns out that “abelianization” of a group is left adjoint to the forgetful functor from abelian groups to groups.

There are more explicit examples we’ve seen, but I’ll leave them to illustrate some particular properties of adjoints. Take note, though, that not all adjunctions involve forgetful functors like these examples have.

An adjunction between two categories can be seen as a weaker version of an equivalence. An equivalence given by functors $F:\mathcal{C}\rightarrow\mathcal{D}$ and $G:\mathcal{D}\rightarrow\mathcal{C}$ tells us that both $F$ and $G$ are fully faithful, so $\hom_\mathcal{C}(C',C)\cong\hom_\mathcal{D}(F(C'),F(C))$. Now let’s put $C'=G(D)$ to find that $\hom_\mathcal{C}(G(D),C)\cong\hom_\mathcal{D}(F(G(D)),F(C))\cong\hom_\mathcal{D}(D,F(C))$, where the last isomorphism uses the natural isomorphism $F\circ G\rightarrow1_\mathcal{D}$. So every equivalence is an adjunction.

July 16, 2007 Posted by | Category theory | 16 Comments