The Adjoint Functor Theorem in Everyday Life

Posted on March 13, 2022
Word count: 1677

Here’s a mathematical situation that comes up a lot more often than is reasonable. Suppose we have some mathematical object $G$, generally defined as some structure on a set: a group, a ring, a topological space. These all have natural categorical structures, so we can - in a uniform way - talk about their subobjects:

• A subgroup $X$ of $G$ is a subset of $G$1 closed under the group operations: If $x, y \in X$ then you must also have $xy \in X$, the unit $1$ is in $X$, and if $x \in X$ then so is $x^{-1}$. Alternatively — this is the categorical phrasing — a subgroup $X$ of $G$ is a group $X$ equipped with an injective2 group homomorphism $f : X \hookrightarrow G$. Injective means “reflecting equality”: If $f(x) = f(y)$ then we must have $x = y$.
• A subring $X$ of $R$ is a subset of $U(R)$ closed under the ring operations; Alternatively, it’s a ring $X$ equipped with an injective ring homomorphism $X \hookrightarrow R$.

For now, let us focus on groups. Fix a group $G$: It has an underlying set of elements $U(G)$ (keep in mind that the “underlying set” operation is really a faithful functor). Of course, not every subset of $U(G)$ is going to be a subgroup of $G$ — consider the case where $G = (\mathbb{Z},+)$ and the subset we have at hand is e.g. $\{ 1, 2, 3 \}$. But — suppose that we do have a subset, and we’re really keen on seeing it grow up to be an honest-to-god subgroup. Are we out of luck? Is there any hope for us?

Generating subgroups

As it turns out — yes! Suppose that we have two subgroups $X$, $Y$ of $G$: one can (and you probably should) check that their intersection $X \cap Y$ is also a subgroup of $G$. I’m going to phrase this with a lot more abstract nonsense though: There is a canonical way of regarding “arbitrary objects with maps into a fixed object” as a category: A slice category, in this case the slice $\mathrm{Grp}/G$ (it’s read “groups over $G$”). The specific case we’re interested in is referred to as $\mathrm{Sub}(G)$ (the “poset of subobjects”) — it’s the full subcategory of $\mathrm{Grp}/G$ on the monic maps.

Suppose that we have subgroups $(X, \iota_1)$ and $(Y, \iota_2)$, which, by definition, are groups equipped with maps into $G$. Their intersection, if it exists, is an object $X \times Y$ together with maps $(X \times Y) \to X$ and $(X \times Y) \to Y$, universal among such “cones” (see the diagram below): It’s a product of $X$ and $Y$ in the category $\mathrm{Grp}/G$. Some abstract nonsense (by which I mean category theory) tells us that the product of $(X, \iota_1)$ and $(Y, \iota_2)$ in $\mathrm{Grp}/G$ is given by the pullback $X \times_G Y$ in $\mathrm{Grp}$, equipped with the canonical projections and choice of map into $G$.

Of course, there’s also the normal, set-theoretic, boring intersection of subgroups $X$ and $Y$. I’ll (cheekily) leave it as an exercise to the reader to show that, given material subsets $X$ and $Y$ of $G$, the underlying set of the pullback group $X \times_G Y$ (where the injections are canonical) is isomorphic to the intersection $X \cap Y$. The abstract nonsense perspective here is to emphasise thinking of the subgroups of a given group as forming their own little category.

Now, suppose that we have just some random subset $X$ of the underlying set of $G$, which — keeping with the abstract nonsense — we will consider as a set $X$ equipped with an injection $i : X \hookrightarrow U(G)$. We can now ask our question with slightly more precision: Is there any object $X'$ of $\mathrm{Sub}(G)$ which we can map $X$ into? Note that this question is still slightly misphrased: $X$ and whatever $X'$ might be are in different categories!

Fortunately, our functor $U : \mathrm{Grp} \to \mathrm{Sets}$ extends smoothly to a functor $\mathrm{Sub}(G) \to \mathrm{Sub}(U(G))$, patching up the last paragraph and letting us ask the question “is there any hope for us?” in a precise way:

Question. Given an object $X$ of $\mathrm{Sub}(U(G))$, are there any interesting objects $X' \in \mathrm{Sub}(G)$ with cool maps $X \to U(X')$?

Note the emphasis on interesting and cool: $\mathrm{Sub}(G)$ has a terminal object (it’s $G$ itself, equipped with the identity map), so there are plenty of boring answers to the question: any subset of $G$ embeds into the “greatest subgroup” — $G$ itself! Note that we still haven’t answered the question either way: we’ve just rephrased it into the language of category theory. This means that we can now attack it with abstract nonsense!

The nonsense

We’ll start by generalising our question away from the specific situation of subgroups and subsets: If we have any functor $R : \mathcal{D} \to \mathcal{C}$, is there a way of assigning objects $X' \in \mathcal{D}$ to objects $X \in \mathcal{C}$, such that there are interesting maps $X \to R(X')$? First, I’ll note that the objects $X'$ equipped with maps $X \to R(X')$ form their own category, which is referred to as $X \swarrow R$ (the maps in that category are a surprise tool that will help us later). But let’s ping back to the group example — hell, let’s consider a concrete example, for a big change, and yes, right after I said we’d attack it with abstract nonsense — to figure out what interesting maps might mean.

Suppose we set $G = (\mathbb{Z},+)$, and our subset is $X = \{2, 4\}$. Consider the trivial solution, where we set $X' \subseteq \mathbb{Z}$ (all the inclusions in this paragraph are omitted — they’re canonical). A better solution is to consider just the evens: $X' = \{ 2n : n \in \mathbb{Z} \}$. But how exactly is it better? Well - it’s smaller! Literally! It is, in fact, the smallest such solution, in that if you have a subgroup $S$ which includes $X$, then it includes every even integer. Categorifying, we say that any other solution $X \to S$ factors uniquely as $X \to X' \to S$.

Now, conveniently, we can introduce the maps in $X \swarrow R$: A map $(A, f) \to (B, g)$ is a map $h : A \to B$ for which the diagram below commutes. A factoring of $g$ as $f$ followed by $R(h)$.

Finally - finally! - we can express what it means to “solve $R$” in an “interesting” way: we have an object $X'$, together with a map $\eta : X \to R(X')$, map such that $(X', \eta)$ is an initial object in the comma category $X \swarrow R$ — which is precisely the data of a left adjoint functor $L : \mathcal{C} \to \mathcal{D}$ to our functor $R$.

Generating sub-thingies

Here’s a list of constructions, including the solution to the “subgroup problem” we’ve been pondering. Note that all the constructions below are done “relative to” a bigger structure, because (for instance) it makes no sense to consider subgroups without having a bigger group to embed them in!

• The subgroup $F(S)$ generated by a subset $S$ is the intersection of all subgroups of $G$ containing $S$;

• The normal subgroup generated $F(S)$ generated by a subgroup $G$ is the intersection of all normal subgroups of $G$ containing $S$;

• The closure $\overline{S}$ of a subset $S$ (of a topological space $X$) is the intersection of all closed subsets of $X$ containing $S$;

• The interior $\mathrm{int}(S)$ of a subset $S$ (of a topological space $X$) is the union of all open subsets contained in $S$;

That last one is sneaky: it’s dual to all of the others (it’s happening in an opposite category). Let’s focus on the first three; the interior case is, well, dual. In all of them, we’re constructing an object — the smallest object satisfying some property — by taking the intersection of all objects satisfying that property. We already know that intersections correspond to products (the “empty intersection”, i.e. the maximal subset, is a terminal object): this generalises to $n$-ary intersections corresponding to limits. This construction is entirely formulaic! Does this generalise?

Yes! All of the constructions above are instances of the general adjoint functor theorem: For a functor $R : \mathcal{D} \to \mathcal{C}$, if:

• $\mathcal{D}$ is a small, complete preorder; and
• $R$ preserves all limits (meets) in $\mathcal{D}$, then

Then $R$ admits a left adjoint $L$, with $L$ mapping $x$ to the limit of — pardon the strong wording — the whole-ass category $x \swarrow R$, which exists by our assumption that $D$ is complete. I will warn you that, since $\mathcal{D}$ has limits the size of its class of arrows, it must3 be a preorder. Please note that, since — and I quote:

this generalises to $n$-ary intersections corresponding to limits.

The construction of the left adjoint in the AFT is given in the same way as our bullet list before, taking the intersection of all the candidates! And the case with duals? That’s using the AFT to construct a right adjoint: formally dual to the situation above. Let me spell out an example in a tiny bit more detail:

Fix a group $G$; Consider the full subcategory of $\mathrm{Grp}/G$ on the normal monomorphisms, i.e. the poset of normal subgroups of G — let’s call it $\mathrm{Norm}(G)$. $\mathrm{Norm}(G)$ is small because, e.g., $\mathrm{Grp}$ is locally presentable: standard-issue abstract nonsense. This category admits a functor $U : \mathrm{Norm}(G) \to \mathrm{Sub}(U(G))$, to the poset of subsets of the underlying set of $G$. $\mathrm{Norm}(G)$ is also a preorder: it admits a fully faithful functor into the poset of subobjects of G.

Moreover, since $\mathrm{Grp}$ has limits, and normal monomorphisms are closed under arbitrary intersections, we can conclude that $\mathrm{Norm}(G)$ is complete; Since intersections of subgroups are taken to intersections of sets by $U$, the AFT tells us it has a left adjoint $F$: The “free normal subgroup” on a subset of $G$. Moreover, $F(X)$ is computed by taking the limit of all normal subobjects which include $X$, as promised.

Conclusion

Okay, but then what? Well, then nothing. I just wanted to write about something that clicked for me — I knew about the AFT and “big intersection” constructions both, but not that they’re the same thing! This blew my mind when I learned about it, and I hope that it’s helped make at least one of these concepts seem less arbitrary.

Also: I hope you noticed some of those links! Yeah, I’ve been gone for a while. I’ve been working on the 1Lab: a formalised, cross-linked, explorable reference resource for univalent mathematics. I’m going back to playing with cubes now — take care!

1. Formally speaking, it’s a subset of the underlying set of $G$, generally written $U(G)$.↩︎

2. A stickler for details could point out that the right notion of “injectivity” in an arbitrary category is being a monomorphism rather than reflecting equality. However, both $\mathrm{Grp}$ and $\mathrm{Ring}$ admit a faithful functor into $\mathrm{Sets}$, and faithful functors reflect monos; It suffices to check that the underlying function of the homomorphism is injective.↩︎

3. Assuming excluded middle, or in any Grothendieck topos↩︎