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:

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:

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:

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:

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:

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):

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

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.

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)$.

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.

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$ 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.

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$.

A Brief Introduction to Categories, Part 7: General Limits and Colimits

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, unless stated otherwise.

Introduction

Previously, we have studied particular examples of limits and colimits. This time, we will go into the general theory. Using the close relation between limits and representable functors and the previous results on universal elements and representability, we are able to provide different perspectives on limits.

Limits as Universal Cones

Definition C7.1 Let $I$ be a small category, let $\mathcal C$ be any category, then the diagonal functor $\Delta:\mathcal C \to [I,\mathcal C]$ is defined as follows:

• For any object $x \in \mathcal C$, $\Delta(x):I \to \mathcal C$ is the constant functor with values in $x$, i.e. the functor which sends every object of $I$ to $x$ and every morphism in $I$ to $\mathrm{id}_x$
• For any morphism $f: x \to y$ in $\mathcal C$, we define $\Delta(f):\Delta(x) \Rightarrow \Delta(y)$ to be the natural transformation that has for any object $i \in I$, the component $\Delta(f)_i=f:\Delta(x)(i)=x \to \Delta(y)(i)=y$

Definition C7.2 Let $I$ be a small category, let $\mathcal C$ be any category and let $F:I \to \mathcal C$ be a functor. Then a cone over $F$ consists of an object $x \in \mathcal C$ -called apex- and a natural transformation $\eta: \Delta(x) \Rightarrow F$. The naturality condition can be stated by saying that the following diagram commutes for any morphism $f:i \to j$ in $I$:

Given two cones $\eta:\Delta(x) \Rightarrow F$ and $\varepsilon:\Delta(y) \Rightarrow F$, a morphism of cones is a morphism $f:x \to y$ such that $\varepsilon \circ \Delta(f) = \eta$. Morphisms of cones can be composed and so we obtain a category of cones over $F$, denoted by $\mathrm{Cone}(F)$.

Definition C7.3 A limit $\displaystyle \varprojlim_{i \in I}F(i)$ is a terminal object in the category of cones $\mathrm{Cone}(F)$.

If the limit $\varprojlim_{i \in I}F(i)$ is given by a cone consisting of an object $x \in \mathcal C$ and a natural transformation $\eta:\Delta(x) \Rightarrow F$, then we call $x$ the limit object (or just limit, by abuse of language) and the components of $\eta$ the structure morphisms.

Remark Being a terminal object, a limit is unique up to unique isomorphism of cones.

Example C7.4 Let $I$ be a discrete category, then a functor $I \to \mathcal C$ is nothing but a family of objects $(X_i)_{i \in I}$. In this case, a limit is just a product of the objects $(X_i)_{i \in I}$. As a special case, a limit over the empty functor $\varnothing \to \mathcal C$ is a terminal object.

Example C7.5 Let $I$ be a set and consider the following category $J$, having two objects $a,b$ and for every $i \in I$, a morphism $i:a \to b$ (and of course the identities for $a$ and $b$). There’s a unique way to define composition to turn this into a category. Then having a functor $F:J \to \mathcal C$ is equivalent to having a family of morphisms $(f_i)_{i \in I}:X \to Y$ in $\mathcal C$ with common source and target. In this case, a limit over $F$ is equivalently an equalizer for the family of morphisms $f_i$.

Example C7.6 Let $I$ be the category with three objects $a,b,c$ and as morphisms (aside from the identities) a unique morphism $a \to c$ and a unique morphism $b \to c$. Then a functor $I \to \mathcal C$ is equivalently a triple of objects $X,Y,Z$ and two morphisms $f:X \to Z$ and $g:Y \to Z$. As one might guess, a limit over such a functor is equivalently a pullback $X \times_Z Y$.

Example C7.7 Consider $(\mathbb N, \leq)$ with the usual ordering as a category $I$ (this is in particular a preorder). Suppose that we have a descending sequence of sets $U_1 \supset U_2 \supset \dots$. Then we can define a contravariant functor $F:I^{op} \to \mathbf{Set}$ given by $F(i)=U_i$ on objects and for two natural numbers $n,m$ with $n \leq m$, i.e. a morphism $f:m \to n$ in $I^{op}$ we let $F(f)$ to be subset inclusion $U_m \hookrightarrow U_n$. Then the limit of the functor $F$ is the intersection $\bigcap_{i=1}^n U_i$, with structure morphisms being the inclusions $\bigcap_{i=1}^n U_i \hookrightarrow U_j$. Indeed, for a collection of maps from an object $X$,$(f_i)_{i \in I}:X \to U_i$ such that for $i \leq j$, we have that $f_i$ and $f_j$ agree, we see that all the $f_i$ are equal. Hence the image is contained in $\bigcap_{i=1}^n U_i$ and there’s a unique map $f:X \to \bigcap_{i=1}^n U_i$ that makes the necessary triangles commute. Thus we have found a terminal object in the category of cones over $F$.

Definition C7.8 Given a functor $F: I \to \mathcal C$ from a small category $I$ to a category $\mathcal C$, then $F$ can also be considered as a functor $F^{op}:I^{op} \to \mathcal C^{op}$, then a cocone over $F$ is defined as a cone over $F^{op}$. A colimit is defined as an initial object in the category of cocones. Explicitly, a cocone is an object $x \in \mathcal C$ with a natural transformation $\eta:F\Rightarrow \Delta(x)$. The colimit is denoted by $\varinjlim F$.

Remark A limit in $\mathcal C^{op}$ is a colimit in $\mathcal C$ and vice versa.

Limits as Adjoints to the Diagonal Functor

Let $I$ be a small category, let $\mathcal C$ be any category, then consider the following functor $\mathcal C^{op} \to \mathbf{Set}, x \mapsto \mathrm{Hom}_{[I,\mathcal C]}(\Delta(x),F)$, denoted by $\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F)$.
Suppose that this functor is representable, then take a representation $\eta:\mathrm{Hom}_{\mathcal C}(-,L) \cong \mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F)$. Then $L$ is a limit object of $F$ and $\eta_L(\mathrm{id}_L):\Delta(L) \Rightarrow F$ are the structure morphisms, i.e. $(L,\eta_L)$ is a terminal object in the category of cones. This is just a special case of general theorems we have proved on representable functors in virtue of the following observation:

Remark The category of cones $\mathrm{Cone}(F)$ is the opposite category of the category of elements for the functor $\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F):\mathcal C^{op} \to \mathbf{Set}$, i.e. $\mathrm{Cone}(F)=\int(\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F))^{op}$

Proof An object in $\int(\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F))^{op}$ is an object $x \in \mathcal C$ together with an element $\eta \in \mathrm{Hom}_{[I,\mathcal C]}(\Delta(x),F)$, i.e. a cone. A morphism $(x,\eta) \to (y,\varepsilon)$ consists of a morphism $(y,\varepsilon) \to (x,\eta)$ in the category of elements $\int(\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F))$, i.e. a morphism $y \to x$ in $\mathcal{C}^{op}$, i.e. a morphism $f:x \to y$ in $\mathcal{C}$ such that $\mathrm{Hom}_{[I,\mathcal C]}(\Delta(f),F))(\varepsilon)=\eta$, which means that $\Delta(f) \circ \varepsilon = \eta$. This is precisely the notion of a morphism of cones.

Now we can apply lemma C5.15 and lemma C5.3, that is, the fact that initial objects in the category of elements for a functor and representations of that functor both correspond to universal elements to conclude the following:

Lemma C7.10 $\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F)$ is representable if and only if the limit of $F$ in $\mathcal C$ exists and representations of that functor correspond to limit objects together with structure morphisms satisfying the universal property with respect to $\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F)$.

General Limits from Products and Equalizers

General limits can be quite complicated. But apart from some specific examples, we don’t know yet what limits look like in familiar categories such as $\mathbf{Set}$ or if they even exist. We have already seen how pullbacks can be constructed from products and equalizers. (Cf. lemma C6.23) The following construction describes a vast generalization:

Theorem C7.11 Let $F:I \to \mathcal{C}$ be a functor from a small category $I$ to a category $\mathcal C$ that has all products and binary equalizers. Then $\varprojlim F$ exists and can be constructed as follows: Take the product $P:=\prod_{i \in I} F(i)$ with structure maps $\pi_i:P \to F(i)$. Now for every morphism $f:i \to j$ in $I$, we have a morphism $F(f) \circ \pi_i:P \to F(j)$, so that by the universal property of the product, there is a unique morphism $\alpha:P \to P$ such that $\pi_j \circ \alpha= F(f) \circ p_i$ for all morphisms $f:i \to j$ in $I$. Then the equalizer $L:=\mathrm{Eq}(\mathrm{id}_{P},\alpha)$ is the limit together with structure morphisms $f_i:L \to F(i)$ given by $f_i:=\pi_i \circ \iota$, where $\iota:L \to P$ is the structure morphism of the equalizer.

Proof We first check that the collection of $f_i$ makes $L$ into a cone. Let $f:i \to j$ be a morphism in $I$. Then we have
$F(f) \circ f_i = F(f) \pi_i \circ \iota = \pi_j \circ \alpha \circ \iota = \pi_j \circ \mathrm{id}_P \circ \iota = f_j$, showing that the $f_i$ form the components of a natural transformation $\Delta(L) \Rightarrow F$, that is we have a cone over $F$. Let $(x,\eta)$ be a cone over $F$, then for all $i \in I$, we have a morphism $\eta_i:x \to F(i)$. So by the universal property of the product, we get a unique morphism $h:x \to P$ such that $\pi_i \circ h = \eta_i$ for all $i$. Consider the morphism $\alpha \circ h:x \to P$. We have for any morphism $f:i \to j$ in $I$
$\pi_j \circ \alpha \circ h =F(f) \circ \pi_i \circ h =F(f) \circ \eta_i = \eta_j$
(where we used naturality of $\eta$). So that by uniqueness of $h$, we get that $h = \alpha \circ h$. Thus by the universal property of the equalizer $L=Eq(h,\mathrm{id}_P)$, we get that a unique morphism $h':x \to L$ such that $\iota \circ h'= h$.
To see that $h'$ is a morphism of cones, note that $f_i \circ h'=\pi_i \circ \iota \circ h' = \pi_i \circ h=\eta_i$. To see that $h'$ is unique, let $w':x \to L$ be another morphism of cones, then $w:=\iota \circ w'$ satisfies
$\alpha \circ w = \alpha \circ \iota \circ w' = \iota \circ w' = w$
Furthermore, we have $\pi_i \circ w = \pi_i \circ \iota \circ w'= f_i \circ w'=\eta_i$, so that by uniqueness of $h$, we get $w=h$, i.e. $\iota \circ w' = \iota \circ h'$. By the uniqueness part of the universal property of the equalizer, we get that $w'=h'$.

This theorem not only gives us a criterion for the existence of all limits in a category from just some specific ones, but it also tells us what they look like, given that we understand products and equalizers:

Example C7.12 Consider the category of sets $\mathbf{Set}$, then limits can be constructed as follows: $F:I \to \mathbf{Set}$ be a functor from a small category $I$, then the limit of $F$ is given by $\varprojlim F = \{(x_i)_{i \in I} \in \prod_{i \in I}F(i) \mid \forall (f:i \to j) \in I, F(f)(x_i)=x_j\}$

Exercise C7.13 Using previously estabished contructions of coproducts and coequalizers in $\mathbf{Set}$, describe general colimits in $\mathbf{Set}$.

Limits as Representations of the Limit Functor

We have already seen that for a functor $F: I \to \mathcal C$ from a small category $I$ to any category $\mathcal C$, the existence of a limit is equivalent to the representability of the functor $\mathrm{Hom}_{[I,\mathcal C]}(\Delta(-),F)$. In this section we shall derive another description of this functor that relates limits in arbitrary categories to limits in $\mathbf{Set}$.

Definition C7.14 Let $I$ be a small category, $\mathcal C$ be any category and $F:I \to \mathcal C$ be a functor. Then the functor $\displaystyle \varprojlim_{i \in I}\mathrm{Hom}_{\mathcal C}(-,F(i)): \mathcal C^{op} \to \mathbf{Set}$ is defined as follows: for an object $x \in \mathcal C$, we can consider the functor $I \to \mathbf{Set}$, $i \mapsto \mathrm{Hom}_{\mathcal C}(x,F(i))$ (i.e. we compose $F$ with the covariant Hom-functor corresponding to $x$). Since limits in $\mathbf{Set}$ exist, we can take the limit $\displaystyle \varprojlim_{i \in I} \mathrm{Hom}_{\mathcal C}(x,F(i))$. This is the value of the functor $\displaystyle \varprojlim_{i \in I}\mathrm{Hom}_{\mathcal C}(-,F(i))$ at $x$(Exercise: Check that this is indeed a functor, i.e. that it acts in a compatible way on morphisms)

Remark This is actually the limit in the functor category. One can check that limits in functor categories may be computed “pointwise”.

Lemma C7.15 There’s a natural isomorphism of functors $\mathrm{Hom}_{[I, \mathcal C]}(\Delta(-),F) \cong \varprojlim_{i \in I}\mathrm{Hom}_{\mathcal C}(-,F(i))$: Both functors send an object $x$ to the set of cones with $x$ as an apex.

Proof By definition, an element of $\mathrm{Hom}_{[I,\mathcal C]}(\Delta(x),F)$ is a cone with $x$ is an apex. For $\varprojlim_{i \in I}\mathrm{Hom}_{\mathcal C}(-,F(i))$, we can use the description of example C7.12: $\varprojlim_{i \in I} \mathrm{Hom}_{\mathcal C}(x,F(i))$  $= \{(f_i)_{i \in I} \in \prod_{i \in I}\mathrm{Hom}(x,F(i)) \mid \forall (g:i \to j \in I): F(g) \circ f_i = f_j\}$
Clearly this set consists of all natural transforations $\Delta(x) \Rightarrow F$. Naturality is easily checked: Indeed, using the now established identifications on objects with the functor sending an object $x$ to the set of cones with $x$ as an apex, both functors send a morphism $f:x \to y$ to the map from the set of cones over $F$ with $y$ as an apex to the set of cones over $F$ with $y$ as an apex that takes a cone $\eta:\Delta(y) \Rightarrow F$ to the cone with $x$ as an apex with the natural transformation whose components are $\eta_i \circ f:x=\Delta(x)(i) \to F(i)$ for each $i \in I$.

Corollary C7.16 A limit of a functor $F:I \to \mathcal C$ from a small category to $\mathcal C$ exists if and only if the limit functor $\varprojlim_{i \in I}\mathrm{Hom}_{\mathcal C}(-,F(i))$ is representable.

Corollary C7.17 Covariant Hom-functors are “continuous” in the following sense: if a limit over a functor $F:I \to \mathcal C$ exists, where $I$ is a small category and $\mathcal C$ is any category, then $\mathrm{Hom}_{\mathcal C}(x,\varprojlim_{i \in I} F(i)) \cong \varprojlim_{i \in I} \mathrm{Hom}_{\mathcal C}(x,F(i))$

Corollary C7.18 Dualizing the previous corollary, contravariant Hom-functor send colimits to limits.

A Brief Introduction to Categories, Part 6: Some Examples of Limits and Colimits

This post is part of a series on category theory. See Overview of Blog Posts for a list of all posts. All categories in this post are assumed to be locally small (the morphisms between two objects form a set), unless stated otherwise.

Introduction

Last time, we studied universal properties and representable functors. A particular class of universal properties and representable functors is given by (co)limits. This class generalizes many known and frequently appearing constructions and is of great importance both for the study of categories themselves and for applications of category theory. Using the notion of limits, we will be able to state and prove a useful criterion for when a functor is representable in a future post. For motivation, we will start be studying particular examples of limits and colimits in familiar categories before giving the general definition in the future. As we shall see in future posts, all general limits and colimits can be constructed from these examples.

Terminal and Initial Objects

We have already defined initial objects in definition C5.12, but for completeness’s sake, we shall repeat the definition here.

Definition C6.1 Let $\mathcal C$ be a category. Then an object $T$ is called terminal if for any object $x$, there is a unique morphism $x \to T$.

Definition C6.2 Let $\mathcal C$ be a category. Then an object $I$ is called initial if for any object $x$, there is a unique morphism $I \to x$.

Remark From the definitions, it is clear that an initial object is just a terminal object in the opposite category and vice versa.

Remark By lemma C5.13, intial objects (and hence terminal objects, see above) are unique up to unique isomorphisms.

Example C6.3 In the category of sets, the empty set $\varnothing$ is the unique initial object. Indeed, for any set $X$, there is a unique map $\varnothing \to X$, namely the empty map. Every one-point set $\{*\}$ is a terminal object, as for any set $X$, there is a unique map $X \to \{*\}$ that sends everything to $*$. Similarly, in the category $\mathbf{Top}$ of topological spaces, the empty space is an initial object and the one-point space is a terminal object. In the category of small categories $\mathbf{Cat}$, the empty category is an initial object and the category with one object and one morphism (the identity of the one object), i.e. a one-object discrete category, is the terminal object.

Example C6.4 In the category of groups, abelian groups, or modules over a ring $R$, the trivial group (or zero module module) is both an initial and a terminal object.

Example C6.5 In the category of rings, the zero ring $0$ is a terminal object and the ring of integers $\mathbb{Z}$ is an initial object. More generally, let $R$ be a commutative ring and consider the category of $R$-algebras. Then $R$ is an initial object and the zero ring $0$ is a terminal object. This generalizes the last example, as rings are equivalently $\mathbb{Z}$-algebras.

Example C6.6 Let $(A,\leq)$ be a preordered set, considered as a category (cf. example C1.5). Then an initial object is an element $a \in A$, such that $a \leq x$ for all $x \in A$, i.e. a least element. Dually, a terminal object is a greatest element.

Example C6.7 The category of fields does not have an initial object or a terminal object. The reason is that if two fields have different characteristic, there is no field homomorphism between them. If we fix the characteristic to be $0$ or a prime number $p$, then the category of fields of that characteristic has the prime field of that characteristic, i.e. $\mathbb{F}_p$ or $\mathbb{Q}$ as an initial object, but it still has no terminal object, as all field homomorphisms are injective and there are fields of arbitrarily large cardinality.

Remark In the terminology of universal properties and representable functors, an initial object in $\mathcal C$ represents the constant functor $\mathcal C \to \mathbf{Set}$ that sends every object to the terminal object in $\mathbf{Set}$, namely a one-point set. The identity of the initial object is a universal element for this constant functor. Dually, a terminal object represents the constant functor that sends everything to a one-point set, considered as a contravariant functor, i.e. a functor $\mathcal C^{op} \to \mathbf{Set}$. The identity of the terminal object is a universal element.

Products and Coproducts

Definition C6.8 Let $I$ be a set and let $(X_i)_{i \in I}$ be a collection of objects in a category $\mathcal C$. Then a product is given by the following data:

• An object in $\mathcal C$, denoted by $\prod_{i \in I}X_i$
• A collection of morphisms, for any $j \in I$, a morphism $\pi_j: \prod_{i \in I}X_i \to X_j$, called structure morphisms or canonical projections.

With the following universal property:

• For any object $Y$ in $\mathcal C$ and a collection of morphisms $f_i:Y \to X_i$, there exists a unique morphism $f:Y \to \prod_{i \in I}X_i$ such that $\pi_i \circ f = f_i$ for all $i$.

The property can be visualized via a commutative diagram, here shown in the case of binary products:

Remark C6.9 Let $I=\varnothing$ be the empty set. Then a product $\prod_{\varnothing}$ is exactly a terminal object.

Example C6.10 Consider the category of sets $\mathbf{Set}$. For a family of sets $(X_i)_{i \in I}$, one can construct the Cartesian product $\prod_{i \in I}X_i$ and let $\pi_j:\prod_{i \in I}X_i \to X_j$ be the projection onto the $j$-th coordinate. This clearly satisfies the universal property for a product, as for any set $Y$ and maps $f_i:Y \to X_i$, the obvious definition $f:Y \to \prod_{i \in I}X_i, y \mapsto (f_i(y))_{i \in I}$ yields the unique map $Y \to \prod_{i \in I}X_i$ such that $\pi_i \circ f=f_i$ for all $i$. If we have the category of semigroups, of monoids,  of groups, of abelian groups, of rings, of $R$-modules or of $R$-algebras etc. with their respective homomorphisms as morphisms, then equipping the cartesian product with coordinate-wise operations yields the product in that category. (Note that as the operation in the product is defined coordinate-wise, the projections are homomorphisms of the respective type of algebraic structure.)
In the category of topological spaces $\mathbf{Top}$, one takes the Cartesian product and equips it with the product topology to obtain the categorical product.

Example C6.11 Let $(A,\leq)$ be a preordered set. Then the product of a family of objects, if if it exists, is the infimum. The universal property of the product turns into the universal property of the infimum: $\forall x \in X:(\forall i \in I: x \leq a_i \Leftrightarrow x \leq \inf_{i \in I}a_i)$. For example, if $A$ is an integral domain and we define $a \leq b$ if and only if $a$ divides $b$, then the product will be the greatest common divisor of a family of objects, if it exists.

Example C6.12 Consider the category of small categories $\mathbf{Cat}$. Then for a family of categories $(\mathcal C_i)_{i \in I}$, there’s the product category $\mathcal C=\prod_{i \in I} \mathcal C_i$ together with projection functors $\pi_i:\mathcal C \to \mathcal C_i$ for all $i$. The objects are given by $\mathrm{Obj}(\mathcal C)=\prod_{i \in I}\mathrm{Obj}(\mathcal C_i)$ and the morphisms are given by $\mathrm{Hom}_{\mathcal C}((A_i)_{i \in I},(B_i)_{i \in I})=\prod_{i \in I}\mathrm{Hom}_{\mathcal C_i}(A_i,B_i)$ with composition defined component-wise. We have already seen the special case for binary products in definition C3.7.

Remark Let $\mathcal C$ be a category and let $(X_i)_{i \in I}$ be a family of objects indexed by a set $I$. Then if the product $(X:=\prod_{i \in I}X_i,\pi_i)$, exists, we have a bijection for any object $Y$,$\mathrm{Hom}_{\mathcal C}(Y,X) \to \prod_{i \in I} \mathrm{Hom}_{\mathcal C}(Y,X_i)$, given by $f \mapsto \pi_i \circ f$, where the $\pi_i$ are the structure morphisms of the product. One checks that this is natural in $Y$. This means that the functor $\mathcal{C}^{op} \to \mathbf{Set}, Y \mapsto \prod_{i \in I} \mathrm{Hom}_{\mathcal C}(Y,X_i)$ is represented by $X$ and that the family of structure morphisms $(\pi_i)_{i \in I} \in \prod_{i \in I}\mathrm{Hom}_{\mathcal C}(X,X_i)$ is a universal element. Thus we have shown that the “universal property” of the product is indeed a universal property in the formal sense defined in the last entry.
Conversely, given a representation of the functor $\prod_{i \in I}\mathrm{Hom}_{\mathcal C}(-,X_i)$, the representing object is a product of the $X_i$ and the universal element is the family of structure morphisms.
Being representing object of a functor, a product is uniquely determined up to unique isomorphism in the following sense: If $X$ and $X'$ are products for the family $(X_i)_{i \in I}$ with structure morphisms $\pi_i:X \to X_i$ and $\pi_i':X' \o X_i$, then there exists a unique isomorphism $f:X \to X'$ such that $\pi_i' \circ f= \pi_i$ for all $i$.

As with any notion defined for a category, we can dualize the concept of a product.

Definition C6.13 Let $\mathcal C$ be a category, let $I$ be a set and let $(X_i)_{i \in I}$ be a family of objects in $\mathcal C$. Then a coproduct of $(X_i)_{i \in I}$ is a product of $(X_i)_{i \in I}$ in $\mathcal C^{op}$. The coproduct is denoted by $\coprod_{i \in I}X_i$, the structure morphisms $\iota_j:X_j \to \coprod_{i \in I}X_i$ are also called canonical inclusions.

Exercise Write out the universal property of coproducts as in definition C6.8.

Remark Dualizing a previous remark, a coproduct over an empty set is equivalently an inital object.

Example C6.14 Consider the category of sets $\mathbf{Set}$. The coproduct of a familiy of sets $(X_i)_{i \in I}$ is given by the disjoint union $\bigsqcup_{i \in I} X_i$ and the structure morphisms are given by the inclusions $\iota_j:X_j \to \bigsqcup_{i \in I} X_i$. The universal property of the coproduct says that having a map defined on a disjoint union $\bigsqcup_{i \in I}X_i \to Y$ is equivalent to having a map $X_i \to Y$ for each $i$. The correspondence is given by composing with inclusion, i.e. restricting to each component of the disjoint union.
In the category of topological spaces, we can also take the disjoint union with the finest topology that makes all inclusions continuous.
Similarly, in the category of small categories, one can take the disjoint union of objects and the disjoint union of morphisms to get coproducts. (E.g. any discrete category is a disjoint union of copies of the terminal category. The category of fields is a disjoint union of the categories of fields of a fixed characteristic $c$, where $c$ varies over all primes and $0$.)

Example C6.15 Let $R$ be a ring and consider the category of left $R$-modules $R\textrm{-}\mathrm{Mod}$. For a family of left $R$-modules $(M_i)_{i \in I}$, the direct sum $\bigoplus_{i \in I}M_i$ (i.e. the submodule of the product consisting of all tuples in which all but finitely many entries are $0$) is the coproduct with the structure morphisms $\iota_j:M_j \to \bigoplus_{i \in I}M_i$ given by the inclusion in the j-th coordinate. Note that for a finite family, product and coproduct agree, although the structure morphisms are different.

Example C6.16 Consider the categeory of groups $\mathbf{Grp}$. Here the coproduct is given by the so-called free product. For simplicity, let us define the free product in terms of presentations (as it satisfies a universal property, it is unique up to unique isomorphism and hence doesn’t depend on the presentation.) If $(G_i)_{i \in I}$ is a family of groups with presentations $G_i=\langle S_i \mid R_i\rangle$, then the free product has a presentation $\large{*}_{i \in I} G_i=\langle \bigsqcup_{i \in I} S_i \mid \bigsqcup_{i \in I} R_i\rangle$ and the structure morphisms are induced by the inclusion of generators $S_j \to \bigsqcup_{i \in I} S_i$. (cf. example C5.5 for the universal property of presentations.)

Example C6.17 Dualizing example C6.11, if we consider a preordered set $(A,\leq)$ as a category, then the coproduct of a family of objects is given by the supremum, if it exists. For the divisibility relation in an integral domain, this is the least common multiple.

Remark Just like with products, coproducts can be understood in terms of representable functors (they are just products in the opposite category, after all). Explicitly, for a family of objects $(X_i)$ in a category $\mathcal C$, we can form the product of Hom-functors $\prod_{i \in I}(X_i,-):\mathcal C \to \mathbf{Set}$. A representation of this functor is equivalently a coproduct, with the universal element being the family of structure morphisms. (cf. the corresponding remark for products.)

Equalizers and Coequalizers

Definition C6.17 Let $\mathcal{C}$ be a category, let $X,Y$ be objects and let $(f_i)_{i \in I}:X \to Y$ be a family of morphisms. Then an equalizer $\mathrm{Eq}((f_i)_{i \in I})$ consists of the following data:

• An object $E=\mathrm{Eq}((f_i)_{i \in I})$ in $\mathcal{C}$
• A morphism $\iota:E \to X$, called structure morphism or -by abuse of terminology- also the equalizer of the $f_i$, which satisfies $\forall i,j \in I: f_i \circ \iota=f_j \circ \iota$.

Such that the following universal property holds:

• For any object $Z$ and every morphism $f:Z \to X$ such that $\forall i,j \in f_i \circ f=f_j \circ f$, there is a unique morphism $f':Z \to E$ such that $\iota \circ f'=f$

The universal property can be visualized via a commutative diagram, here shown in the case of binary equalizers:

Remark Equalizers are terminal objects in a suitable chosen category: in the situation of definition C6.17, define the following category $\mathcal D$:

• Objects are pairs $(A,f)$ where $A$ is an object in $\mathcal C$ and $f:A \to X$ is a morphism such that $\forall i,j \in I: f_i \circ f= f_j \circ f$.
• Morphisms $(A,f) \to (B,g)$ are morphisms $h:A \to B$ in $\mathcal C$ such that $g \circ h = f$
• Composition is inherited from $\mathcal C$

Then one may restate the definition of an equalizer by saying that an object $(E, \iota) \in \mathcal D$ is a terminal object if and only if $E$ is an equalizer with structure morphism $\iota$. This implies that an equalizer is unique up to unique isomorphism in the following sense: If $\iota:E \to X$ and $\iota':E' \to X$ are both equalizers of the same family of morphisms $X \to Y$, then there exists a unique isomorphism $f:E \to E'$ such that $\iota' \circ f=\iota$.

Example C6.18 Consider the category of sets $\mathbf{Set}$. Then an equalizer of a family of maps $f_i:X \to Y$ can be realized as the largest subset of $X$ on which they agree: If we let $E$ be the subset of $X$ consisting of all $x$ such that $\forall i,j: f_i(x)=f_j(x)$ and take $\iota:E \to X$ to be the subset inclusion, then any map $f:Z \to X$ such that $\forall i,j \in I: f_i \circ f = f_j \circ f$ has its image contained in $E$. Hence it factorizes uniquely through the subset inclusion $\iota$, showing that $\iota:E \to X$ satisfies the universal property. If all sets involved are semigroups, monoids, groups, rings or $R$-modules etc. and the maps are homomorphisms of the respective type, then $E$ will be a subsemigroup, submonoid, subgroup, subring or submodule, respectively and by the same argument, $\iota:E \to X$ satisfies the universal property of the equalizer.
Suppose a group $G$ acts on a set $X$, then we can consider the action as a collection of maps $X \to X$. In this case, one checks that the set $E$ is given by the set of invariants $X^G=\{x \in X \mid \forall g \in G:gx=x\}$.

One can think the equalizer as measuring “how equal” a collection of morphisms are.

Definition C6.19 A coequalizer in a category $\mathcal{C}$ is an equalizer in the opposite category $\mathcal{C}^{op}$.

Exercise Write out the universal property for coequalizers.

Example C6.20 Consider the category of sets $\mathbf{Set}$, then a coequalizer of a family of morphisms $f_i:X \to Y$, $i \in I$ can be constructed as follows: Consider the equivalence relation $\sim$ on $Y$ generated by $f_i(x) \sim f_j(x)$ for all $x \in X$ and $i,j \in I$. (Given a relation on a set, the intersection of all equivalence relations containing it is again an equivalence relation, called the equivalence relation generated by it.) Then the quotient map $Y \to Y/\sim$ is a coequalizer. If a group $G$ acts on a set $X$, then if we consider the coequalizer of the family of maps by which $G$ acts, this is the quotient space $X/G$. If we use the quotient topology, the same construction works in the category of topological spaces.

Example C6.21 If we work in the category of $R$-modules and we have a family of $R$-linear maps $(f_i)_{i \in I}:M \to N$, then one can take the quotient of $N$ by the submodule generated by the set $f_i(m)-f_j(m)$ where $i,j$ vary over $I$ and $m$ varies over $M$. The quotient module with the quotient map is then a coequalizer in the category of $R$-modules.

If one thinks of an equalizer as a universal solution to the problem of making maps equal from the left (i.e. by precomposing with a map), then dually a coequalizer is a universal solution to the problem of making maps equal from the right (i.e. by postcomposing with a map).

Pullbacks and Pushouts

Definition C6.22 Let $\mathcal C$ be a category, let $X,Y,Z$ be objects and let $f:X \to Z$ and $g:Y \to Z$ be morphisms. Then a pullback consists of the following data:

• An object $X \times_Z Y$
• Morphisms $\pi_1:X \times_Z Y \to X, \pi_2:X \times_Z Y \to Y$

Such that the following universal property holds:

• $f \circ \pi_1 = g \circ \pi_2$
• For every object $W$ and morphisms $f':W \to X$ and $g':W \to Y$ such that $f \circ f'= g \circ g'$, there exists a unique morphism $u:W \to X \times_Z Y$ such that $\pi_1 \circ u = f'$ and $\pi_2 \circ u = g'$

The universal property can be visualized by the following commutative diagram:

Exercise Generalize this definition to the case of a family of objects $(X_i)_{i \in I}$ and a family of morphisms $(f_i)_{i \in I}:X_i \to Z$.

One can think of pullbacks as a “mix” of products and equalizers. For products, we had multiple objects but no morphisms between them as a given datum, whereas for equalizers, we had multiple morphisms, but all with the same source and target. For pullbacks, we have different objects and morphisms from those objects to a common target. The following lemmata make the relation of pullbacks to equalizers and products precise.

Lemma C6.23 In the situation of definition C6.22, suppose that the product $X \times Y$ exists and suppose that for the structure morphisms of the product $\pi_1:X \times Y \to X$ and $\pi_2:X \times Y \to Y$, the equalizer $P=Eq(f \circ \pi_1,g \circ \pi_2)$ exists with structure morphism $\iota: P \to X \times Y$. Then this equalizer is a pullback with structure morphisms $\pi_1 \circ \iota: P \to X$ and $\pi_2 \circ \iota: P \to Y$.

Proof We verify the universal property. We have $f \circ \pi_1 \circ \iota=g \circ \pi_2 \circ \iota$ from the definition of an equalizer. Let $W$ be an object and let $f':W \to X$ and $g':W \to Y$ be morphisms such that $f \circ f'=g \circ g'$. Then by the universal property of the product, there is a unique morphism $f' \times g':W \to X \times Y$ such that $\pi_1 \circ (f' \times g')=f$ and $\pi_2 \circ (f' \times g') =g'$. Then we get that $(f \circ \pi_1) \circ (f' \times g') = f \circ f'=g \circ g' = (g \circ \pi_2) \circ (f' \times g')$, so that by the universal property of the equalizer, there is a unique map $u:W \to Eq(f \circ \pi_1,g \circ \pi_2)$ with the required property.

Lemma C6.24 Suppose that a category $\mathcal C$ has a terminal object $1$. Then, if for two objects $X,Y$, the pullback $X \times_1 Y$ (along the unique morphisms $X \to 1, Y \to 1$), exists, it is a product of $X$ and $Y$.

Lemma C6.25 Suppose that in a category $\mathcal C$, the product $Y \times Y$ for an object $Y$ exists. Let $f,g:X \to Y$ be two morphisms from another object $X$ and let $\Delta_Y:Y\to Y \times Y$ be the unique morphism such that $\pi_1 \circ \Delta_Y= \mathrm{id}_Y$ and $\pi_2 \circ \Delta_Y = \mathrm{id}_Y$. Furthermore, let $f \times g:X \to Y \times Y$ be the unique morphism such that $\pi_1 \circ (f \times g) = f$ and $\pi_2 \circ (f \times g)=g$. Then if the pullback $Y \times_{Y \times Y} X$ exists, it is an equalizer $Eq(f,g)$ with structure morphism defined via the projection $Y \times_{Y \times Y} X \to X$.

Exercise Prove the preceeding two lemmata. (This is a nice exercise in getting used to working with universal properties.)

Exercise If a pullback exists, it is unique up to unique isomorphism in a certain sense. Specify what that means and prove it. (There are a couple of different ways to see this, one can define a category such that a pullback is a terminal object (as we did for equalizers), one can define a functor such that a pullback is a representation of that functor (as we did for products), or one can work with the universal property directly.)

Example C6.26 Lemma C6.23 tells us what pullbacks look like, given that we know products and equalizers. For example, in the category of sets, a pullback of two maps $f:X \to Z$ and $g:Y \to Z$ can be realized as a subset of the product $X \times_Z Y := \{(x,y) \in X \times Y \mid f(x)=g(y)\}$. The same construction works for semigroups, monoids, groups, rings etc.

As you might expect, we can dualize this notion, giving rise to the notion of pushouts.

Definition C6.27 A pushout in a category $\mathcal C$ is a pullback in the opposite category $\mathcal{C}^{op}$

Example C6.28 Consider the category of commutative rings. Given commutative rings $A,R,B$ and ring homomorphisms $f:R \to A$, $g:R \to B$, we can consider both $A$ and $B$ as $R$-modules via $f$ and $g$, respectively, so we can consider the tensor product $A \otimes_R B$. Via the definition $(a \otimes b) \cdot (a' \otimes b')=(aa' \otimes bb')$ on elementary tensors, one obtains a multiplication (using the universal property of tensor products to see that it is well-defined) that turns $A \otimes_R B$ into a commutative ring. The structure morphisms are given by $A \to A \otimes_R B, a \mapsto a \otimes 1$ and $B \to A \otimes_R B, b \mapsto 1 \otimes b$. Using the dualized version of lemma C6.24, we see that the coproduct of two commutative rings $A$ and $B$ is given by $A \otimes_{\mathbb Z} B$.

This concludes this post on examples of limits and colimits, next time we will look into the general definition.

A Brief Introduction to Categories, Part 5: Universal Properties and Representable Functors

This post is part of a series on category theory. See Overview of Blog Posts for all posts.

Introduction

Many objects or contstructions can be characterized by a so-called universal property that describes either the morphisms to them or the morphisms from them. By the virtue of the Yoneda lemma, we can forget about any concrete representation of the object and can only work with its universal property. One can think of a universal property as a “universal” solution to a problem in the sense that it is uniquely related to all other solutions. For example, consider the problem of finding a commutative ring $R$ and two elements $a,b \in R$ such that $a^2=b^3$. The universal solution to this problem is given by the elements $x$ and $y$ in $\mathbb{Z}[x,y]/(x^2-y^3)$; this solution is universal in the sense that for every other commutative ring $R$ and elements $a,b \in R$ such that $a^2=b^3$, there’s a unique ring homomorphism $f: \mathbb{Z}[x,y]/(x^2-y^3) \to R$ such that $f(x)=a$ and $f(y)=b$. The general definition is a straightforward abstraction from this example. Universal properties are closely related to representable functors and this relation is established by the Yoneda lemma. Understanding objects in terms of universal properties is the epitome of categorial thinking.

Representability and Universal Elements

Throughout this section, let $\mathcal C$ be a locally small category and let $F:\mathcal C \to \mathbf{Set}$ be a functor.

Definition C5.1 $F$ is called representable if there is natural isomorphism $\alpha:\mathrm{Hom}_{\mathcal C}(A,-) \to F$ for some object $A \in \mathcal C$. We say that $F$ is represented by $A$ and call $A$ a representing object. The pair $(A,\alpha)$ is called a representation of $F$.

Definition C5.2 For an object $A \in \mathcal C$, we say that an element $u \in F(A)$ is universal if the following property holds: For any object $B \in \mathcal C$ and $v \in F(B)$, there’s a unique morphism $f:A \to B$ with $v=F(f)(u)$. In this case, this property is called the universal property of $(A,u)$.

Lemma C5.3 For an object $A \in \mathcal C$, the representations $\alpha: \mathrm{Hom}_{\mathcal C}(A,-) \to F$ are in bijection to universal elements of the form $(A,u)$ via $\alpha \mapsto \alpha_A(\mathrm{id}_A)$

Proof Via the Yoneda lemma, we know that natural transformations $\alpha:\mathrm{Hom}_{\mathcal C}(A,-) \to F$ correspond to elements in $F(A)$ via $\alpha \mapsto \alpha_A(\mathrm{id}_A)$. We need to check that $\alpha$ is an isomorphism if and only if $\alpha_A(\mathrm{id}_A) \in F(A)$ is an universal element. For every object $B$, we have $\alpha_B:\mathrm{Hom}_{\mathcal C}(A,B) \xrightarrow{\sim} F(B)$, but by naturality of $\alpha$, we have for any morphism $f: A \to B$, $\alpha_B(f)=\alpha_B(f \circ \mathrm{id}_A)=F(f)(\alpha_A(\mathrm{id}_A))$ (cf. the proof of the Yoneda lemma). Thus $\alpha$ is a natural isomorphism if and only if for every object $B$, the map $\mathrm{Hom}_{\mathcal C}(A,B) \to F(B), f \mapsto F(f)(\alpha_A(\mathrm{id}_A))$ is a bijection, which is just a restatement of saying that $\alpha_A(\mathrm{id}_A) \in F(A)$ is a universal element.

Example C5.4 Let $A$ be a commutative ring and consider the forgetful functor $V$ from the category of commutative $A$-algebras $A\textrm{-}\mathbf{CAlg}$ to the category of sets $\mathbf{Set}$, that sends an $A$-algebra to its underlying set. Then $V$ is the represented by the polynomial ring $A[x]$. Concretely, we have a natural isomorphism $\alpha:\mathrm{Hom}_{A\textrm{-}\mathbf{CAlg}}(A[x],B) \to V(B), f \mapsto f(x)$. $x \in V(A[x])$ is the corresponding universal element. This holds, because any $A$-algebra homomorphism $f:A[x] \to B$ is given by evaluation at a uniquely determined element, namely $f(x)$.

Example C5.5 Let $G$ be a group with a presentation $G=\langle S \mid R \rangle$ with $S$ being the set of generators and $R$ the set of relations. Then for if we have for a group $H$ for every generator $s \in S$ an element $h_s \in H$ such that the relations in $R$ are satisfied by those corresponding elements, this uniquely determines a group homomorphism $G \to H$. Consequently, for the functor $F$ sending a group $H$ to the families of elements in $H$ indexed by $S$ such that the corresponding relations are satisfied, we see that the family $(s)_{s \in S}$ in $F(G)$ is an universal element and $F$ is represented by $G$.

Example C5.6 Let $R$ be a ring and $r \in R$, then consider the functor $R\textrm{-}\mathbf{Mod} \to \mathbf{Set}$, i.e. from the category of left $R$-modules with $R$-linear maps to the category of sets that sends a module $M$ to the set $M[a]:= \{m \in M \mid am=0\}$. Then this functor is represented by $R/Ra$ and $\overline{1} \in R/Ra$ is a universal element.

Example C5.7 Let $\mathrm{Mor}:\mathbf{Cat} \to \mathbf{Set}$ be the functor from the category of small categories to the category of sets that sends a small category $\mathcal C$  to the set of all morphisms in $\mathcal C$. Then $\mathrm{Mor}$ is represented by the arrow category from definition C3.6. The unique morphism $\iota:0 \to 1$ in the arrow category is a universal element.

Example C5.8 Let $\mathcal C$ be a small category, let $A \in \mathcal C$ be an object and consider the functor from the functor category $[\mathcal{C},\mathbf{Set}]$ to $\mathbf{Set}$ sending a functor $F$ to $F(A)$ and a natural transformation $\eta: F \Rightarrow G$ to $\eta_A:F(A) \to G(A)$. Then the Yoneda lemma in this context can be stated by saying that this functor is representable by $\mathrm{Hom}_{\mathcal C}(A,-)$ and the identity $\mathrm{id}_A \in \mathrm{Hom}_{\mathcal C}(A,A)$ is a universal element.

Example C5.9 Let $G$ be a group, not necessarily abelian. Then consider the functor from the category of all abelian groups to the category of sets $\mathbf{Ab} \to \mathbf{Set}$ given by taking all group homomorphism to an abelian group: $A \to \mathrm{Hom}_{\mathbf{Grp}}(G,A)$ (this is a hom-functor from a larger category restricted to a subcategory). Then this functor is representable by the abelianization $G^{ab}=G/[G,G]$ with the quotient map $G \to G^{ab}$ as a universal element in $\mathrm{Hom}_{\mathbf{Grp}}(G,G^{ab})$: This is the universal property of the abelianization: Every map from $G$ to an abelian group factorizes over the quotient map $G \to G^{ab}$.

Example C5.10 To give an example of a contravariant representable functor, consider the functor $\mathrm{Ouv}:\mathbf{Top}^{op} \to \mathbf{Set}$ from the opposite category of topological spaces to the category of sets that sends a topological space to the set consisting of all of its open subsets. A continuous map $f:X \to Y$ is sent to the map $\mathrm{Ouv}(Y) \to \mathrm{Ouv}(X), U \mapsto f^{-1}(U)$. This functor is represented by the Sierpinski space $S$ whose points are $\{0,1\}$ with the topology that has as open sets $\{\varnothing,\{1\},\{0,1\}\}$. (For all algebraic geometers: this arises as the spectrum of a discrete valuation ring.) The open subset $\{1\} \in \mathrm{Ouv}(S)$ is a universal element. This reason this holds is that for any map $f:X \to S$, we always have $f^{-1}(\varnothing)=\varnothing$ and $f^{-1}(S)=X$, so the only interesting part of being continuous is requiring that $f^{-1}(\{1\})$ is open. Since $S$ has only two points, knowing $f^{-1}(\{1\})$ completely determines $f$. Putting these things together, we get that the map $\mathrm{Hom}_{\mathbf{Top}}(X,S) \to \mathrm{Ouv}(X), f \mapsto f^{-1}(\{1\})$ is a bijection, proving the claim.

Example C5.11 Not every functor is representable. As a boring example, one can take the constant functor $\mathcal C \to \mathbf{Set}$ that sends every object to the empty set. (Exercise: why will this never be representable, provided that $\mathcal C$ is non-empty?) For a more interesting example, consider the functor from the category of all groups to the category of sets that sends a group to the set of all of its torsion elements, i.e. elements of finite order. $[\mathrm{tors}]: \mathbf{Grp} \to \mathbf{Set},G \mapsto G[\mathrm{tors}]$. (This defines a functor because group homomorphisms send torsion elements to torsion elements.) Suppose that $[\mathrm{tors}]$ is represented by a group $G$ and let $g \in G[\mathrm{tors}]$ be a universal element. Then for every $n \in \mathbb{N}$, we have an element $\overline{1} \in \mathbb{Z}/n\mathbb{Z}[\mathrm{tors}]$. By universality of $g$, there is a group homomorphism $G \to \mathbb{Z}/n\mathbb{Z}$ that sends $g$ to $\overline{1} \in \mathbb{Z}/n\mathbb{Z}$. But this implies that $n$ divides the order of $g$. As $n$ was arbitrary, this is impossible, as the order of $g$ is finite.

Universal Elements as Initial Objects

One can ask for a characterization for representability of a functor that doesn’t refer to a representing $A$. In this section, we shall introduce the notion of an initial object to obtain such a criterion, although the criterion will be a mere reformulation of the definition. This reformulation will be put to use in the future to prove a more useful criterion, for which we lack the tools at the moment. We shall return to the notion of initial objects later when we generalize them vastly to colimits.

Definition C5.12 Let $\{*\}$ be a one-point set. An object $x$ in a category $\mathcal C$ is called initial if it represents the constant functor $\mathcal C \to \mathbf{Set}$, given by sending each object in $\mathcal C$ to $\{*\}$ and every morphism to $\mathrm{id}_{\{*\}}$.

Unfolding the definition, this means that for an object $x$ is initial if for any object $y$, there is exactly one morphism $x \to y.$

We prove an elementary, but useful property of initial objects:

Lemma C5.13 If a category $\mathcal C$ has an initial object, it is unique up to unique isomorphism.

Proof Let $x$ and $y$ be initial objects in $\mathcal C$, then there are unique morphisms $f:x \to y$ and $g:y \to x$. Then both $\mathrm{id}_x$ and $g \circ f$ are morphisms $x \to x$, so they must agree, thus $g \circ f=\mathrm{id}_x$. By symmetry, $f \circ g = \mathrm{id}_y$ proving that $f$ and $g$ are mutually inverse isomorphisms. $f:x \to y$ is necessarily unique as $x$ is initial.

Definition C5.14 Let $F:\mathcal C \to \mathbf{Set}$ be a functor where $\mathcal C$ is a locally small category. Define the category of elements $\int F$ as follows:

• Objects are pairs $(A,a)$ consisting of an element $A \in \mathcal C$ and an element $a \in F(A)$.
• Morphisms $(A,a) \to (B,b)$ are morphisms $f:A \to B$ in $\mathcal C$ such that that $F(f)(a)=b$.

Lemma C5.15 $(A,a)$ satisfies the universal property for $F$ if and only if $(A,a)$ is an initial object in $\int F$.

Proof Immediate from the definitions.

Corollary C5.16  Object characterized by a universal property are unique up to unique isomorphism in the following sense: if $(X,u)$ and $(Y,v)$ both satisfy the universal property for a functor $F$, then there exists a unique isomorphism $f:X \to Y$ such that $F(f)(u)=v$.

Proof By lemma C5.15, both $(X,u)$ and $(Y,v)$ are initial objects in $\int F$. Now apply lemma C5.13.

This concludes this post on representability and universal properties. Next time, we will see an important class of examples for those concepts, given by (co)limits.

A Brief Introduction to Categories, Part 4: The Yoneda Lemma

This post is part of a series on category theory, see Overview of Blog Posts for all blog posts.

Introduction

Using the notion of natural transformations introduced previously, we are able to state and prove the (in)famous and all-important Yoneda lemma, which is not only applied throughout category theory, but can yield satisfying conceptual proofs in many distinct areas. This result single-handedly justifies the “behavioristic” or “relative” viewpoint internal to category theory that lies in not bothering with concrete qualities of the objects one is interested in and studying them via their relations to other objects, for it implies in a certain technical sense that an object is uniquely determined by how it relates to other objects. This allows us to think of objects in terms of functors.

Functor Categories

Let $\mathcal{C}$ and $\mathcal{D}$ be categories, then we can consider the class of functors $\mathcal C \to \mathcal D$. For two such functors, we can consider natural transformations between them, which we can compose in an associative way. For any functor, there’s the identity natural transformation. So this turns the collection of functors $\mathcal C \to \mathcal D$ into a category, right?
Not quite, at least with our definitions. The subtle problem is that there is no reason to expect that the natural transformations between two functors form a set, there might be “too many”. To remedy this deficiency, we shall amend the definition of a category. Henceforth, what is defined in definition C1.1 shall be called a “locally small category” and a not necessarily locally small or “large” category has the same definition, except that the morphisms between two objects are allowed to be proper classes. With this amendment, we can make the following definition:

Definition C4.1 Let $\mathcal C$ and $\mathcal D$ be categories. Then the functor category, denoted by $[\mathcal C,\mathcal D]$ has as its objects all functors $F: \mathcal C \to \mathcal D$ and as morphisms natural transformations, with composition of natural transformations defined pointwise.

Exercise C4.2 If $\mathcal C$ is a small category (the objects form a set and it is locally small) and $\mathcal D$ is a locally small category, then the functor category $[\mathcal C,\mathcal D]$ is locally small.

Example C4.3 As we have already seen, the functor category $[G,\mathbf{Set}]$ for a group $G$ considered as a one-object category is the category of $G$-sets with equivariant maps as morphisms. (cf. example C2.4 and example C3.3)

Example C4.4 Similarly, for a field $k$ and a group $G$, the functor category $[G,k\mathrm{-Vect}]$ is the category of representations of $G$ over $k$. (cf. example C2.5 and example C3.4)

The Yoneda Lemma

We now come to the promised infamous lemma:

Theorem C4.5 (Yoneda lemma) Let $\mathcal C$ be a locally small category, let $x$ be an object in $\mathcal C$ and let $F: \mathcal C \to \mathbf{Set}$ be a functor, then the map $\varphi^{x,F}:\mathrm{Hom}_{[\mathcal C,\mathbf{Set}]}(\mathrm{Hom}_{\mathcal C}(x,-),F) \to F(x), \eta \mapsto \eta_{x}(\mathrm{id}_x)$ is a bijection that is natural in $x$ and in $F$.

Proof construct an inverse map $\theta_{x,F}$ as follows: let $c \in F(x)$, then set $\theta^{x,F}(c)$ to be the following natural transformation: for any object $y \in \mathcal C$ and any morphism $f:x \to y$, let $\theta^{x,F}(c)_y(f)=F(f)(c)$, we need to check that this is indeed a natural transformation from $\mathrm{Hom}_{\mathcal C}(x,-)$ to $F$. Let $z$ be a third object and let $g:y \to z$ be a morphism in $\mathcal C$. Then we need to verify that the following diagram commutes:

To show this, let $f \in \mathrm{Hom}_{\mathcal C}(x,y)$, then $\theta^{x,F}(c)_z(g \circ f)=F(g \circ f)(c)=F(g)(F(f)(c))=F(g)(\theta^{x,F}(c)_y(f))$ showing that the diagram commutes. Hence $\theta^{x,F}$ is a natural transformation.

We now need to show that $\theta^{x,F}$ is the inverse of $\varphi^{x,F}$. Let $\eta: \mathrm{Hom}_{\mathcal C}(x,-) \Rightarrow F$ be a natural transformation, then we need to show that $\theta^{x,F}(\varphi^{x,F}(\eta))=\eta$, which we can check this component-wise. Let $y \in \mathcal C$ be an object and let $f:x \to y$ be a morphism, then we have $\theta^{x,F}(\varphi^{x,F}(\eta))_y(f)=\theta^{x,F}(\eta_x(\mathrm{id}_x))_y(f)=F(f)(\eta_x(\mathrm{id}_x))$ by naturality of $\eta$ this equals $\eta_y(f)$, see the diagram below, applied to the identity on $x$:

This proves one direction, for the other direction, we have for $c \in F(x)$, $\varphi^{x,F}(\theta^{x,F}(c))=\theta^{x,F}(c)_x(\mathrm{id}_x)=F(\mathrm{id}_x)(c)=c$. This shows that $\varphi$ and $\theta$ are mutually inverse bijections. Naturality in $x$ and $F$ are easy computations.

There is also a contravariant version of the Yoneda lemma:

Corollary C4.6 Let $\mathcal C$ be a locally small category and let $F:\mathcal C^{op} \to \mathbf{Set}$ be a functor, i.e. a contravariant functor on $C$, then for any object $x \in \mathcal C$, the map $\mathrm{Hom}_{[\mathcal{C}^{op},\mathbf{Set}]}(\mathrm{Hom}_{\mathcal C}(-,x),F) \to F(x), \eta \mapsto \eta_x(\mathrm{id}_x)$ is a natural bijection.

Proof Apply the Yoneda lemma to the opposite category.

The most important case is when $F$ is another Hom-functor:

Corollary C4.7 Let $\mathcal C$ be a locally small category and let $x,y \in \mathcal C$ be objects. Then there is a natural isomorphism $\mathrm{Hom}_{[\mathcal{C}^{op},\mathbf{Set}]}(\mathrm{Hom}_{\mathcal C}(-,x),\mathrm{Hom}_{\mathcal C}(-,y)) \cong \mathrm{Hom}_{\mathcal C}(x,y)$ given by $\eta \mapsto \eta_x(\mathrm{id}_x)$.

Corollary C4.8 Let $\mathcal C$ be a locally small category. Then the functor $Y_{\mathcal C}: \mathcal C \to [\mathcal C^{op},\mathbf{Set}]$, called the Yoneda embedding, given by $Y(x)=\mathrm{Hom}_{\mathcal{C}}(-,x)$ is fully faithful.

Corollary C4.9 Let $\mathcal C$ be a locally small category, then if for two objects $x$ and $y$, the functors $\mathrm{Hom}_{\mathcal C}(-,x)$ and $\mathrm{Hom}_{\mathcal C}(-,y)$ are naturally isomorphic, then $x$ and $y$ are isomorphic up to a unique isomorphism inducing a given natural isomorphism between the functors.

Proof By corollary C4.8, the Yoneda embedding is fully faithful, hence it reflects being isomorphic by lemma C3.11. As the Yoneda embedding is faithful, we get uniqueness.

Corollary C4.10 Let $\mathcal C$ be a locally small category. If for two objects $x$ and $y$, the functors $\mathrm{Hom}_{\mathcal C}(x,-)$ and $\mathrm{Hom}_{\mathcal C}(y,-)$ are naturally isomorphic, then $x$ and $y$ are isomorphic up to a unique isomorphism inducing a given natural isomorphism between the functors.

Proof Apply corollary C4.9 to the opposite category and note that two objects are isomorphic if and ony if they are isomorphic in the opposite category.

Remark Using the Yoneda lemma, one can identify a locally small category $\mathcal C$ with the subcategory of the functor category $[\mathcal C^{op},\mathbf{Set}]$, containg as objects all Hom-functors and as morphisms natural transformations between them.

Let us ponder for a moment what a remarkable thing we have shown: The last two corollaries tell us that in order to study an object, it is sufficient to study all morphisms from that object or all morphisms into that object. To put it succinctly, the Yoneda lemma tells us that an object is determined by its relation to other objects. Studying the functor $\mathrm{Hom}_{\mathcal C}(x,-)$ or the functor $\mathrm{Hom}_{\mathcal C}(-,x)$ can be easier than studying an object itself, especially if the objects satisfy so-called universal properties, which are basically convenient descriptions of the functors from or to an object.

Example C4.11 Let $\mathbf{CRing}$ be the category of commutative rings, then if $R$ is a commutative ring and $I$ is an ideal, one has an isomorphism natural in $T$: $\mathrm{Hom}_{\mathbf{CRing}}(R/I,T) \cong \{f \in \mathrm{Hom}_{\mathbf{CRing}}(R,T) \mid f_{\mid I}=0\}$, given by pulling back along the projection $R \to R/I$. In this sense, the projection $\pi:R \to R/I$ is the universal morphism that restricts to $0$ on $I$: every other such morphism factorizes over it. This is the content of the homomorphism theorem. From a categorical perspective, the homomorphism theorem is the proper definition of a quotient modulo an ideal, whereas the construction with equivalence classes is mere coincidence. In a similar manner, for a multiplicatively closed subset $S \subset R$, the localization $S^{-1}R$ together with the canonical morphism $s:R \to S^{-1}R$ is the universal solution to the problem of finding a ring $T$ and a ring homomorphism $f:R \to T$ such that $f$ maps all elements of $S$ to units. Explicitly, one has a natural isomorphism $\mathrm{Hom}_{\mathbf{CRing}}(S^{-1}R,T) \cong \{f \in \mathrm{Hom}_{\mathbf{CRing}}(R,T) \mid f(S) \subset T^\times\}$.
If we look into the case that we have both an ideal $I$ and a multiplicatively closed subset $S$ in $R$, then we can ask for a universal morphism that sends both $I$ to $0$ and maps $S$ to units. Here we can see the Yoneda lemma in action, for we have natural isomorphisms $\mathrm{Hom}_{\mathbf{CRing}}(S^{-1}R/S^{-1}I,T) \cong \{f \in \mathrm{Hom}_{\mathbf{CRing}}(S^{-1}R,T) \mid f_{S^{-1}I} = 0 \} \cong \{f \in \mathrm{Hom}_{\mathbf{CRing}}(R,T) \mid f(S) \subset T^\times, f_{I}=0\} \cong \{f \in \mathrm{Hom}_{\mathbf{CRing}}(R/I,T) \mid f(\overline{S}) \subset T^\times\} \cong \mathrm{Hom}_{\mathbf{CRing}}(\overline{S}^{-1}R/I,T)$
which implies that $\overline{S}^{-1}R/I \cong S^{-1}R/S^{-1}I$ by the Yoneda lemma. This is a conceptually very satisfying proof, as we didn’t have to fiddle with equivalence classes or fractions, but we only used the abstract defining properties of localizations and quotients.

Exercise Use the Yoneda lemma to prove that if $R$ is a commutative ring and $I$ and $J$ are two ideals such that $I \subset J$, then $R/J \cong (R/I) / (R/J)$.

Exercise If $S$ and $T$ are two multiplicatively closed subsets of a commutative ring $R$ and $S \cdot T$ is the multiplicatively closed subset generated by $S$ and $T$, then show that $S^{-1}T^{-1}R \cong (S\cdot T)^{-1}R$ using the Yoneda lemma.

This concludes the post on the Yoneda lemma, which we shall see in many applications to come.

A Brief Introduction to Categories, Part 3: Natural Transformations and Equivalences

This post is a continuation of a mini-series on category theory, starting with this post. As before, knowing the background for every single example is not required for understanding the overall concepts.

Introduction

Previously, we have defined categories and the morphisms between them. In the case that one has two parallel functors $F,G:\mathcal C \to \mathcal D$, between two categories $\mathcal C$ and $\mathcal D$, it is frequently the case that for any object $x \in \mathrm{Obj}(\mathcal C)$, one has a morphism $F(x) \to G(x)$. In this situation, the notion of a natural transformation conceptualizes what it means for this collection of morphisms to vary “naturally” with the object $x$, leading to a concept essential to all of category theory. Using this concept, we can define a coarser notion of equivalences than the obvious one of isomorphic categories.

Natural Transformations

Definition C3.1 Let $\mathcal C$ and $\mathcal D$ be categories and let $F,G:\mathcal C \to \mathcal D$ be functors. Then a natural transformation $\eta:F \Rightarrow G$ consists of the following data:

• For every object $x \in \mathcal C$ a morphism in $\mathcal D$, $\eta_x:F(x) \to G(x)$ called the component of $\eta$ at $x$.

Such that the following condition holds:

• For every objects $x,y \in \mathcal C$ and every morphism $f:x \to y$, the following diagram commutes:
which means that $\eta_y \circ F(f)=G(f) \circ \eta_x$

One can think of the naturality condition as saying that $\eta$ “interpolates” between $F$ and $G$.

Definition C3.2 If all the components of a natural transformation $\eta:F \Rightarrow G$ are isomorphisms, $\eta$ is called a natural isomorphism and $F$ and $G$ are called naturally isomorphic.

Example C3.3 Let $G$ be a group and $X$ and $Y$ be $G$-sets, considered as functors $G \to \mathbf{Set}$. Then a natural transformation $X \Rightarrow Y$ has only one component, as $G$ has only one object, so it is given by a map of the underlying sets $f:X \to Y$ satisfying a naturality condition. This condition requires that we have for any $g \in G$ (i.e. for any morphism in $G$) $f \circ g = g \circ f$, (by abuse of notation, we write $g$ for its action on $X$ and $Y$), so that natural transformations correspond precisely to $G$-equivariant maps.

Example C3.4 Reasoning as in the last example, one concludes that if we have a group $G$ and a field $k$, then natural transformations between two representations, considered as functors $G \to k\mathrm{-Vect}$ correspond to morphisms of representations.

Example C3.5 Let $\mathbf{CRing}$ be the category of commutative and unital rings with ring homomorphisms and $\mathbf{Mon}$ be the category of monoids. Fix $n \in \mathbb N$. Let $F:\mathbf{CRing} \to \mathbf{Mon}$ be the functor that sends a commutative ring to the multiplicative monoid of the matrix ring: $F(R)=(M_n(R), \cdot)$. Every ring homomorphism $f: R\to S$ induces a monoid homomorphism $F(f): M_n(R) \to M_n(S)$ of multiplicative monoids by applying $f$ to every component (this is in fact a ring homomorphism of the matrix rings). Let $G:\mathbf{CRing} \to \mathbf{Mon}$ be the “forgetful” functor that forgets about addition and sends a commutative ring to its multiplicative monoid. Every ring homomorphism respects multiplication and the unit element, so that it induces a monoid homomorphism on the multiplicative monoids. The determinant is defined by a polynomial with coefficients in $\Bbb Z$. Hence it doesn’t matter if we apply the ring homomorphism $f:R \to S$ componentwise to a square matrix and then take the determinant or if we take the determinant first and then apply $f$ to the result. We hence get a commutative diagram:  stating that the determinant is natural in $R$.

Natural Transformations as Homotopies

(Image source: https://commons.wikimedia.org/wiki/File:HomotopySmall.gif)

Reminder/Definition Consider two topological spaces $X$ and $Y$ and let $f:X \to Y$ and $g:X \to Y$ be continuous maps, then a homotopy $H$ between $f$ and $g$ is a continuous map $H:[0,1] \times X \to Y$ such that $H(0,x)=f(x)$ for all $x \in X$ and $H(1,x)=g(x)$ for all $x \in X$. If there exists such a homotopy, $f$ and $g$ are called homotopic, denoted by $f \simeq g$.

One thinks of a homotopy as a continuous deformation or an interpolation of $f$ to $g$ and of the first parameter from $[0,1]$ as a time parameter, as in the picture above. The definition states that $H$ behaves on $\{0\} \times X \cong X$ like $f$ and on $\{1\} \times X \cong X$ like $g$. Continuity implies that it is a continuous deformation of $f$ to $g$.

If we think of categories as the objects of study in category theory and functors as the morphisms between them, then natural transformations interpolate between  morphisms between the objects. This situation might be reminiscent of the situation in topology: objects in topology are topological spaces, the morphisms between them are continuous functions and homotopies interpolate between continuous functions. We will see in this section that this analogy can be made even closer than this vague similarity by defining the analogue of products and the unit interval for categories.

Definition C3.6 The arrow category or interval category $I$ is the following category: we have two objects $\mathrm{Obj}(I)=\{0,1\}$ and three morphisms: the two identities and a unique morphism $\iota:0 \to 1$. One easily observes that there is only one possible way to define composition which makes this into a category.

This category plays a role for natural transformations analogous to the unit interval

Definition C3.7 Let $\mathcal C$ and $\mathcal D$ be categories, then the product category $\mathcal{C} \times \mathcal{D}$ consists of the following data:

• $\mathrm{Obj}(\mathcal C \times \mathcal D)=\mathrm{Obj}(\mathcal C) \times \mathrm{Obj}(\mathcal D)$
• For $X,X' \in \mathcal C$ and $Y,Y' \in \mathcal D$, we have $\mathrm{Hom}_{\mathcal C \times \mathcal D}((X,Y),(X',Y'))=\mathrm{Hom}_{\mathcal C}(X,X') \times \mathrm{Hom}_{\mathcal D}(Y,Y')$
• Composition is defined componentwise.

Using these definitions, we can define the analogue of a homotopy: let $\mathcal C$ and $\mathcal D$ be categories and let $F:\mathcal C \to \mathcal D$ and $G:\mathcal C \to \mathcal D$ be functors. Then a “categorical homotopy” from $F$ to $G$ is a functor $H:I \times \mathcal C \to \mathcal D$ such that $H(0,x)=F(x)$ for all $x \in \mathrm{Obj}(\mathcal C)$ and $H(1,x)=G(x)$ for all $x \in \mathrm{Obj}(\mathcal C)$ and for all morphisms $f:x \to x'$ in $\mathcal C$, we have $H(\mathrm{id}_0,f)=F(f)$ and $H(\mathrm{id}_1,f)=G(f)$. This means that on the subcategory $0 \times \mathcal C \cong \mathcal C$, $H$ behaves like $F$ and on the subcategory $1 \times \mathcal C$, $H$ behaves like $G$.

Proposition C3.8 Let $\mathcal C,\mathcal D$ be categories and let $\mathcal F,G:\mathcal C \to \mathcal D$ be functors, then natural transformations $\eta:F \Rightarrow G$ correspond to categorical homotopies $H:I \times \mathcal C \to \mathcal D$ from $F$ to $G$.

Proof Let $\eta:F \Rightarrow G$ be a natural transformation, then we define a categorical homotopy $H_\eta: I \times \mathcal C \to \mathcal D$ as follows:

• For all $x \in \mathrm{Obj}(\mathcal C)$, let for $H_\eta(0,x)=F(x)$ and $H_\eta(1,x)=G(x)$.
• For all morphisms $f:x \to y$ in $\mathcal C$, let $H_{\eta}( \mathrm{id}_0,f)=F(f)$ and let $H_{\eta}(\mathrm{id}_1,f)=G(f)$ and let $H_{\eta}(\iota,f)=G(f) \circ \eta_x=\eta_y \circ F(f)$ (the last equality holds by naturality of $\eta$.)

Let us check that this is indeed a functor. It clearly respects identities. The only non-obvious cases for compatibility with composition involve $\iota$ in the first component. We have for morphisms $f:x \to y$ and $g:y \to z$ in $\mathcal C$,
$H_{\eta}((\iota,g) \circ (\mathrm{id}_0,f))=H_{\eta}(\iota,g \circ f)= G(g \circ f) \circ \eta_x= G(g) \circ G(f) \circ \eta_x=(G(g) \circ \eta_y) \circ F(f)=H_{\eta}(\iota,g) \circ H_{\eta}(\mathrm{id}_0,f)$
In the other case we have
$H_{\eta}((\mathrm{id}_1,g) \circ (\iota,f)))=H_{\eta}(\iota,g \circ f)=\eta_z \circ F(g \circ f)=\eta_z \circ F(g) \circ F(f)= G(g) \circ (\eta_y \circ F(f))=H_{\eta}(\mathrm{id}_1,g) \circ H_{\eta}(\iota,f)$
Such that $H_{\eta}:I \times \mathcal C \to \mathcal D$ is indeed a functor. It is clear from the construction that $H_{\eta}$ is a categorical homotopy from $F$ to $G$, completing one half of the correspondence. For the other direction, let $H$ be a categorial homotopy from $F$ to $G$. To obtain a natural transformation, set $\eta_x=H(\iota,\mathrm{id}_x)$ for all $x \in \mathrm{Obj}(x)$. Naturality now follows from functoriality of $H$,
as for any morphism $f:x \to y$ in $\mathcal C$, we have:
$G(f) \circ \eta_x = H(\mathrm{id}_1,f) \circ H(\iota,\mathrm{id}_x)=H((\mathrm{id}_1,f) \circ (\iota,\mathrm{id}_x)) = H(\iota,f)=H((\iota,\mathrm{id}_y) \circ (\mathrm{id}_0,f)=H(\iota,\mathrm{id}_y) \circ H(\mathrm{id}_0,f)=\eta_y \circ F(f)$
Using the same computations, one checks that those two constructions are inverse to each other.

Equivalences of Categories and Related Properties

There’s an obvious notion of isomorphisms for categories: a functor $F:\mathcal C \to \mathcal D$ is an isomorphism if there is a functor $G:\mathcal D \to \mathrm C$ such that $G\circ F$ and $F \circ G$ are the identity functors on $\mathcal C$ and $\mathcal D$, respectively. For many purposes, however, this notion is too strict and a coarser notion is much more useful. We can let the analogy between natural transformations and homotopies guide us.

Reminder/Definition A continuous map $f:X \to Y$ between topological spaces $X$ and $Y$ is called a homotopy equivalence if there is a continuous map $g:Y \to X$ such that $g \circ f$ and $f \circ g$ are homotopic to the identities on $X$ and $Y$, respectively.

Example The $n$-dimensional sphere is homotopy equivalent to $\mathbb{R}^{n+1} \setminus \{0\}$.

This leads “naturally” to the following definition:

Definition C3.9 A functor $F:\mathcal C \to \mathcal D$ between two categories $\mathcal C$ and $\mathcal D$ is called an equivalence of categories if there is a functor $G:\mathcal D \to \mathcal C$ such that $G \circ F$ and $F \circ G$ are naturally isomorphic to the identity functor on $\mathcal C$ and on $\mathcal D$, respectively.

It is sometimes easier to verify some sufficient (and necessary) conditions for a functor to be an equivalence than to use the definition directly by constructing a functor in the other direction. We shall now define those properties, which are important in their own right.

Definitions C3.10 A functor $F:\mathcal C \to \mathcal D$ between two categories $\mathcal C$ and $\mathcal D$ is called

• faithful, if for all $x,y \in \mathrm{Obj}(\mathcal C)$, the induced map $\mathrm{Hom}_{\mathcal C}(x,y) \to \mathrm{Hom}_{\mathcal D}(F(x),F(y))$ is injective.
• full, if for all $x,y \in \mathrm{Obj}(\mathcal C)$, the induced map $\mathrm{Hom}_{\mathcal C}(x,y) \to \mathrm{Hom}_{\mathcal D}(F(x),F(y))$ is surjective.
• fully faithful, if for all $x,y \in \mathrm{Obj}(\mathcal C)$, the induced map $\mathrm{Hom}_{\mathcal C}(x,y) \to \mathrm{Hom}_{\mathcal D}(F(x),F(y))$ is bijective.

We state and prove a useful property of fully faithful functors:

Lemma C3.11 Let $F:\mathcal C \to \mathcal D$ be a fully faithful functor, then $F$ reflects isomorphisms in the following sense: if $x,y \in \mathrm{Obj}(\mathcal C)$ are two objects such that $F(x)$ and $F(y)$ are isomorphic in $\mathcal D$, then $x$ and $y$ are isomorphic in $\mathcal C$.

Proof Take an isomorphism $f':F(x) \to F(y)$ with inverse $g':F(y) \to F(x)$, then there are some $f:x \to y, g:y \to x$ such that $F(f)=f'$ and $F(g)=g'$ as the induced maps on $\mathrm{Hom}$-sets is surjective. We get $F(f \circ g)=F(f) \circ F(g)=f' \circ g'=\mathrm{id}_{F(y)}=F(\mathrm{id}_y)$, so $f \circ g = \mathrm{id}_y$ as $F$ is faithful. By symmetry, $g \circ f = \mathrm{id}_x$, so $f$ is an isomorphism with inverse $g$.

Lemma C3.12 A natural isomorphism of functors preserves fullness, faithfulness and full faithfulness

Proof Let $F,G: \mathcal C \to \mathcal D$ be functors and let $\eta:F \Rightarrow G$ be a natural isomorphism. One immediately sees that for any objects $x,y \in \mathrm{Obj}(\mathcal C)$ the map $\phi:\mathrm{Hom}_{\mathcal D}(F(x),F(y)) \to \mathrm{Hom}_{\mathcal D}(G(x),G(y)), \phi(h)=\eta_y \circ h \circ \eta_x^{-1}$ is a bijection with inverse given by $h \mapsto \eta_y^{-1} \circ h \circ \eta_x$.
By naturality, we have for any morphism $f:x \to y$ in $\mathcal C$ $G(f) \circ \eta_x = \eta_y \circ F(f)$, which implies that $G(f)= \eta_y \circ F(f) \circ \eta_x^{-1}=\phi(F(f))$ From this equation, we conclude that the maps induced by $F$ and $G$, respectively, on Hom-sets are related by the bijection $\phi$, hence one is injective, surjective or bijective if and only if the other one is.

Lemma C3.13 If $F:\mathcal C \to \mathcal D$ and $G:\mathcal D \to \mathcal E$ are functors such that $G \circ F$ is faithful, then $F$ is faithful. If $G \circ F$ is full, then $G$ is full. If $G$ is fully faithful, then $G \circ F$ is full/faithful/fully faithful if and only $F$ is.

Proof These assertions follow immediately from the corresponding elementary statements about injective, surjectiv and bijective maps. (E.g. if $g \circ f$ is surjective, then $g$ is surjective.)

Corollary C3.14 Any equivalence of categories is fully faithful.

Proof Let $F:\mathcal C \to \mathcal D$ be a functor and $G:\mathcal D \to \mathcal C$ be a functor such that $G \circ F$ is naturally isomorphic to the identity functor on $\mathcal C$ and $F \circ G$ is naturally isomorphic to the identity functor on $\mathcal D$. By using lemma C3.12, we can conclude that $G \circ F$ and $F \circ G$ are fully faithful, as the identity functor is evidently fully faithful. In virtue of lemma C3.13, this implies that $F$ is both full and faithful, hence fully faithful.

Definition C3.15 A functor $F:\mathcal C \to \mathcal D$ is called essentially surjective if for every object $x \in \mathrm{Obj}(\mathcal D)$, there is an object $y \in \mathrm{Obj}(\mathcal C)$ such that $F(y)$ is isomorphic to $x$.

Lemma C3.16 An equivalence of categories is essentially surjective.

Proof Let $F$ be a functor $\mathcal C \to \mathcal D$ and $G$ be a  functor $\mathcal D \to \mathcal C$ such that $F \circ G$ is naturally isomorphic via $\eta$ to the identity functor on $\mathcal D$. Then for any object $x \in \mathrm{Obj}(\mathcal D)$, we have an isomorphism $\eta_x:F(G(x)) \to x$, showing that $F$ is essentially surjective.

At this point, we have collected enough necessary properties of equivalences of categories to obtain a characterization that doesn’t rely on the existence of another functor, which consitutes the main result of this post.

Theorem C3.17 A functor is an equivalence of categories if and only if it is fully faithful and essentially surjective.

Proof Lemma C3.16 and corollary C3.14 furnish one half of the proof.
For the other half, let $F:\mathcal C \to \mathcal D$ be a fully faithful and essentially surjective functor. For any object $x \in \mathrm{Obj}(\mathcal D)$, choose an object $G(x) \in \mathrm{Obj}(C)$ such that $F(G(x))$ is isomorphic to $x$ (which is possible, as $F$ is essentially surjective.) Choose an isomorphism $\eta_x:x \to F(G(x))$. Let $f:x \to y$ be a morphism in $\mathcal D$. Then $\eta_y \circ f \circ \eta_x^{-1}$ is a morphism $F(G(x)) \to F(G(y))$. By full faithfulness of $f$, there is a unique morphism $G(f):G(x) \to G(y)$ such that $F(G(f))=\eta_y \circ f \circ \eta_x^{-1}$.
We need to check that these assignments make $G$ into a functor: let $f:x \to y$ and $g:y \to z$ be morphisms in $\mathcal D$, then from the definition of $G$, we obtain $F(G(g \circ f))=\eta_z \circ g \circ f \circ \eta_x^{-1}=(\eta_z \circ g \circ \eta_y^{-1}) \circ (\eta_y \circ f \circ \eta_x^{-1})=F(G(g)) \circ F(G(f))=F(G(g) \circ G(f)$, such that by faithfulness of $F$, $G(g \circ f)=G(g) \circ G(f)$. As for identities, we get for any object $x \in \mathrm{Obj}(\mathcal D)$, $F(G(\mathrm{id}_x))=\eta_x \circ \mathrm{id}_x \circ \eta_x^{-1}=\mathrm{id}_{F(G(x))}=F(\mathrm{id}_{G(x)})$ so that by faithfulness, $G(\mathrm{id}_x)=\mathrm{id}_{G(x)}$.
We now need to show that $G \circ F$ and $F \circ G$ are naturally isomorphic to the respective identities: The defining equation $F(G(f))=\eta_y \circ f \circ \eta_x^{-1}$ yields $F(G(f)) \circ \eta_x= \eta_y \circ f=\eta_y \circ \mathrm{Id}_{\mathcal D}(f)$ so that $\eta$ is a natural isomorphism from the identity functor on $\mathcal D$ to $F \circ G$.
$G(f)$.
To finish the proof, we have to show that $G \circ F$ is naturally isomorphic the identity functor on $\mathcal C$. Note that since $F \circ G$ is naturally isomorphic to the identity functor on $\mathcal D$ we get that $F(G(F(x)))$ is naturally isomorphic to $F$, because we have for any object $x \in \mathcal C$ an isomorphism $\eta_{F(x)}:F(x) \to F(G(F(x)))$ such that for any morphism $f:x \to y$ in $\mathcal C$, we have $F(f) \circ \eta_{F(x)}= \eta_{F(y)}\circ F(G(F(f)))$. Now as $F$ is fully faithful, there exist for each pair of objects $x,y \in \mathcal C$ a unique morphism $\vartheta_x: x \to G(F(x))$ such that $F(\vartheta)=\eta_{F(x)}$. To show that $\vartheta$ is natural, insert into $F(f) \circ \eta_{F(x)}= \eta_{F(y)}\circ F(G(F(f)))$ so that the definition of $\vartheta$, so that we get $F(f) \circ F(\theta_x)=F(\theta_y) \circ F(G(F(f)))$ which implies by functionariality $F(f \circ \theta_x)=F( \theta_y \circ \circ G(F(f)))$ so that by faithfulness, we get $f \circ \theta_x = \theta_y \circ G(F(f))$, which means precisely that $\theta$ is a natural transformation from the identity functor to $G \circ F$. As $F(\theta_x)$ is an isomorphism for each $x$ and $F$ is fully faithful, one concludes that $\theta_x$ is an isomorphism. (If $F$ is a fully faithful functor and $F(f)$ is an isomorphism, then $f$ is an isomorphism, cf. the proof of C3.11.) This shows that $G \circ F$ is naturally isomorphic to the identity functor on $\mathcal C$, which concludes the proof and also this post.

(Exercises and remarks for the stray logician or set theorist:
The above proof doesn’t work in ZFC, why? Give an example of an underlying set theory as a meta-theory such that the proof does indeed work.
Prove that the above proof does work in ZFC if one restricts the statement to small categories and that the statement for small categories is equivalent to choice over ZF.
In practice, set-theoretic issues are often ignored by those doing category theory, or one uses Tarski-Grothendieck set theory)

A Brief Introduction to Categories, Part 2: Functors

This post is a continuation of a previous post and part of a mini-series on category theory. As before, knowing the background of every single example is not necessary (nor sufficient) to grasp the general concept.

Introduction

Previously, we have defined and discussed categories. However, studying categories as isolated objects with no relation to other categories would be a fruitless toil. It would also not be in the spirit of category theory, which studies everything through its relationship to other things. Yet the necessity to bring together distinct instances of the objects one is studying is not specific to category theory: For example, it’s hard to imagine studying group theory without studying group homomorphisms.

It should by now be clear that we are in dire need of a notion allowing us to connect different categories and to express relationships between them. It seems natural to let the definition of a category guide us to the definition of things that relate them. This plan comes to fruition in the conception of functors. These should be thought of as (homo)morphisms of categories, mappings preserving the structure categories have, i.e. identities and composition, just like a monoid homomorphism preserves the neutral element and the monoid operation.

The ubiquity with which functors arise is remarkable, and after some experience in thinking categorically it will become second nature to ask whether a construction behaves “functorially”.

Functors

Definition C2.1 Let $\mathcal C$ and $\mathcal D$ be categories, then a (covariant) functor $F$ consists of the following data:

• A map $\mathrm{Obj}(\mathcal C) \to \mathrm{Obj}(\mathcal D), X \mapsto F(X)$
• For any pair of objects $X, Y \in \mathrm{Obj}(\mathcal C)$ a map $\mathrm{Hom}_{\mathcal C}(X,Y) \to \mathrm{Hom}_{\mathcal D}(F(X),F(Y)), f \mapsto F(f)$

such that the following conditions hold:

• For every object $X \in \mathrm{Obj}(\mathcal C)$ we have $F(\mathrm{id}_X)=\mathrm{id}_{F(X)}$
• For any three objects $X,Y,Z \in \mathrm{Obj}(\mathcal C)$ and morphisms $f:X \to Y, g:Y \to Z$ we have $F(g \circ f)= F(g) \circ F(f)$.

Let us ponder for a moment how this definition generalizes familiar concepts.

Example C2.2 Let $X$ and $Y$ be sets, then we can consider them as discrete categories (cf. C1.4), so that the elements of each set are the objects of the associated discrete category and the only morphisms are the identity morphisms. Then any map $f:X \to Y$ uniquely determines a functor $F$ between the associated discrete categories restricting to $f$ on the objects, as the only morphisms are identities and the definition of a functor requires sending identity morphisms to the corresponding identity morphisms in the target category. To summarize, functors between discrete categories correspond to maps between the underlying sets.

Example C2.3 Let $M$ and $N$ be monoids, considered as one-object categories. Then a functor $F:M \to N$ has to send the unique object of $M$ to the unique object of $N$. The action on morphisms is more interesting: from the definition of a functor, we see that a map of the underlying sets $f:M \to N$ determines a functor if and only if it preserves the monoid operation and the identity, i.e. if and only if it is a monoid homomorphisms. Thus for monoids (and hence for groups), we can regard homomorphisms as functors.

Example C2.4 Let $G$ be a group, considered as a one-object category and let us consider functors to the category of sets (cf. C1.2), $F:G \to \mathbf{Set}$. Since $G$ has one proxy object $x$, the value of $F(x)$ corresponds to a choice of a particular set $X$. As for the morphisms, we have for each $g \in G$ a map $F(g):X \to X$ such that $F(e)=\mathrm{id}_X$ and $F(gh)=F(g) \circ F(h)$. These are precisely the axioms for a group action on $X$, such that functors $G \to \mathbf{Set}$ correspond to sets with a (left) $G$-action, i.e. $G$-Sets.

Example C2.5 By reasoning as in the last example, one can show that if $K$ is a field and we consider the category $K\mathbf{-Vect}$ of vector spaces over $K$ with linear maps as morphisms, then functors $G \to K\mathbf{-Vect}$ correspond to representations of $G$ on vector spaces over $K$.

Now we shall look into examples of particular functors.

Example C2.6 There are a plethora of so-called “forgetful” functors. These arise when you “forget” part of the structure of an object. In this case, the target category consists of objects with less structure than the source category.
For example, we can forget about the multiplication in a ring and are left with an abelian group, this gives rise to a forgetful functor from the category of rings to the category of abelian groups. We can then proceed on our path to oblivion and forget that an abelian group is abelian, yielding a forgetful functor from abelian groups to groups. Finally, every group is a set, giving rise to yet another forgetful functor. It should be noted that it is important to consider also the morphisms for these forgetful functors to work: every ring homomorphism is a homomorphism of abelian groups on the additive groups, every homomorphism of abelian groups is a group homomorphism and every group homomorphism is a map of sets. Another chain of forgetful functors goes from smooth complex varieties to complex manifolds, from complex manifolds to smooth manifolds, from smooth manifolds to topological manifolds, from topological manifolds to topological spaces and from topological spaces to sets, ending another journey of obliviousness in the same destination.
Forgetful functors are often implicitly applied, especially if one is not doing category theory. And indeed, it should deserve no particular mention that for instance, any group is a set. It can be quite helpful, however, to explicitly state when you apply them, for example to clarify in which category two objects are isomorphic or if you want to apply concepts or theorems on functors to a forgetful functor.

Example C2.7 One could say that the first example of functoriality is encountered in an introductory calculus class, although that would be a bit of a stretch.
Let $\mathbf{Diff}_{*}$ be the category of pointed smooth manifolds, i.e. objects are pairs $(M,x)$ where $M$ is a smooth manifold and $x \in M$ and morphisms $(M,x) \to (N,y)$ are smooth maps $f:M \to N$ such that $f(x)=y$. Then there’s the tangent space functor $T_{-}: \mathbf{Diff}_* \to \mathbb{R}\mathbf{-Vect}$ to the category of $\mathbb{R}$-vector spaces with linear maps that sends a pair $(M,x)$ to the tanget space $T_x M$ of $M$ at $x$ and a morphism $f:(M,x) \to (N,y)$ to the differential $D_x(f):T_xM \to T_y N$. The fact that this behaves functorially is an abstract version of the chain rule: $D_x(g \circ f)=D_{f(x)}(g) \cdot D_x(f)$, justifying the assertion on functoriality in calculus above.

Example C2.8 Let $\mathbf{Ring}$ be the category of rings with ring homomorphisms as morphisms, then for any ring $A$, the units $A^\times$ form a group and ring homomorphisms preserve units so that a ring homomorphism $f: A \to B$ restricts to a group homomorphism $A^\times \to B^\times$. We obtain a functor from $\mathbf{Ring}$ to $\mathbf{Grp}$, the category of groups with group homomorphisms as morphisms.

Example C2.9 Let $A$ be an abelian group and $n \in \mathbb{N}$, then there’s a functor from the category $\mathbf{Top}$ of topological spaces to the category of abelian groups that sends a space $X$ to the singular homology group $H_n(X,A)$. The fact that this is a functor is even part of the Eilenberg-Steenrod axioms for homology theories.

Example C2.10 Let $\mathbf{Top}$ be the category of topological spaces with continuous maps and let $\mathcal C$ be the category of measurable spaces with measurable maps as morphisms. There’s a functor $\mathbf{Top} \to \mathcal C$ that equips a topological space with its Borel $\sigma$-algebra, turning it into a measurable space. Every continuous map is measurable with respect to the corresponding Borel $\sigma$-algebras, ensuring that this construction yields a functor.

Example C2.11 Not every constructions that seems in some sense “natural” can be turned into a functor. For example, we can associate to each group $G$ its center $Z(G)$ which is an abelian group. One could hope that this can be made into a functor. The problem is that central elements don’t necessarily get sent to central elements under a group homomorphism. Indeed, it is impossible to define any action on morphisms such that the assignment on objects $G \mapsto Z(G)$ becomes a functor, for the identity on the cyclic group on two elements $C_2$ factors through the inclusion $\iota$ of $C_2$ to $S_3$ as a transposition and the sign homomorphism $\sigma:S_3 \to C_2$. We have $\mathrm{id}_{C_2}=\sigma \circ \iota$. However, the center of $C_2$ is itself, whereas the center of $S_3$ is trivial. If there was any functor $F$ that restricts to $G \mapsto Z(G)$ on objects, then we would get $\mathrm{id}_{C_2}=F(\mathrm{id}_{C_2})=F(\sigma \circ \iota)=F(\sigma) \circ F(\iota)$ implying that the identity on $C_2$ factors over the trivial group, which is impossible.

Example C2.12 Let $C$ be a category and let $X \in \mathrm{Obj}(\mathcal C)$, then for any object $Y \in \mathrm{Obj}(\mathcal C)$, we have a set $\mathrm{Hom}_{\mathcal C}(X,Y)$ and for a morphism $f:Y \to Y'$, we can postcompose with $f$, yielding a map $f \circ -: \mathrm{Hom}_{\mathcal C}(X,Y) \to \mathrm{Hom}_{\mathcal C}(X,Y')$. By associativity of composition and the definition of the identity elements, this construction yields a functor $\mathcal C \to \mathbf{Set}$. These functors – affectionally called Hom-functors – are of paramount importance, as we shall see in future posts.

Example C2.13 We have said that functors can be thought of as morphisms between categories. This can be taken quite literally. To avoid Russel’s paradox and to ensure that our sets of morphisms will actually be sets, let’s restrict our attention to categories whose class of objects is actually a set, so-called “small” categories. There’s a (non-small!) category $\mathbf{Cat}$, in which the objects are small categories and morphisms are functors between small categories. Note that we have implicitly said that one can compose functors and that there’s an identity functor for each category.

Contravariance

All the previous examples of functors had one thing in common: they didn’t reverse the orientation of the arrows. Even so, there are other instances of functoriality. The following construction allows us to subsume those instances under the previous definition:

Definition C2.15 Let $\mathcal C$ be a category, then the opposite category $\mathcal C^{op}$ has the same objects. For $X,Y \in \mathrm{Obj}(\mathcal C^{op})$, we set $\mathrm{Hom}_{\mathcal C^{op}}(X,Y)=\mathrm{Hom}_{\mathcal C}(Y,X)$ composition is defined like the composition in $\mathcal C$ except in the opposite order.

Intuitively, we just reverse all the arrows.

Definition C2.16 Let $\mathcal C$ and $\mathcal D$ be categories, then a contravariant functor $F: \mathcal C \to \mathcal D$ is a covariant functor $\mathcal C^{op} \to \mathcal D$.

For clarification, regular functors (as in definition C2.1) are called covariant, but if “functor” is used without specification, they are always covariant by default.

From this definition, it follows that a contravariant functor reverses the direction of morphisms when it is applied. (Hence the picture in the beginning of this section)

Example C2.16 Consider the category of sets $\mathbf{Set}$. The assignment on objects $X \mapsto \mathcal{P}(X)$ can be made into a functor in two different ways, a covariant one and a contravariant one. For the covariant one, let $f:X \to Y$ be any map. Then we can define a map $\mathcal{P}(X) \to \mathcal{P}(Y)$ via $X \supset U \mapsto f(U)$, giving rise to the covariant powerset functor. For the contravariant one, we can define for a map $f:X \to Y$ a map $\mathcal{P}(Y) \to \mathcal{P}(X)$ via $Y \supset V \mapsto f^{-1}(V)$. In both cases the verification of the functorial properties is easy.

Example C2.17 Let $k$ be a field. Consider the category $\mathcal C$ of finite separable extensions of $k$ with $k$-linear field homomorphisms as morphisms. We can define a contravariant functor $F$ from $\mathcal C$ to $\mathbf{Grp}$, the category of groups with group homomorphisms as morphisms, in the following manner: For an object $L \in \mathrm{Obj}(\mathcal C)$, set $F(L)=L^\times$ and for a (necessarily injective) morphism $f:L \to M$, define $F(f)$ to be the field norm $N_{M/L}:M^\times \to L^\times$. The transitivity formula for norms in towers translates into functoriality of this construction: For a tower of extensions $L \subset M \subset N$ we have $N_{N/M} \circ N_{M/L}=N_{N/L}$.
A similar construction works for the field trace.

Example C2.18 Consider the category of compact Hausdorff spaces with continuous maps as morphisms. For any compact Hausdorff space $X$, the continuous functions $X \to \mathbb{C}$ form a C*-algebra with pointwise operations (i.e. addition, multiplication, scalar multiplication and conjugation), denoted by $C(X)$. If $X$ and $Y$ are compact Hausdorff spaces and $f:X \to Y$ is a continuous map, then we can define a homomorphism of C*-algebras by pulling back continuous functions along $f$: for a continuous function $g: Y \to \mathbb C$, $g \circ f$ is a continuous function $X \to \mathbb C$. We obtain a contravariant functor from the category of compact Hausdorff spaces to the category of commutative unital C*-algebras.

Example C2.19 As in the examples C2.4 and C2.5, if $G$ is a group, considered as a one-object category and we let $\mathcal C$ be the category of sets or the category of $k$-vector spaces for a field $k$, then contravariant functors correspond to right $G$-sets or right representations on vector spaces over $k$, respectively.

Example C2.20 The construction from C2.12 has a contravariant sibling. Let $\mathcal C$ be any category and $x \in \mathrm{Obj}(\mathcal C)$. Then we have for any object $y$ in $\mathcal C$, a set $\mathrm{Hom}_{\mathcal C}(y,x)$ and for a morphism $f:y \to y'$, we get a map $\mathrm{Hom}_{\mathcal C}(y',x) \to \mathrm{Hom}_{\mathcal C}(y,x), g \mapsto g \circ f$. This construction is a functor, called the contravariant Hom functor.

A Brief Introduction to Categories, Part 1: Categories

The purpose of this post is to establish some basic language of categories. This can be read independently of the ongoing series on representation theory, although concepts and results from this post will be used in the representation theory series. So with respect to the representation theory series, one can think of this post (and the follow-up posts) as the analog of an appendix.

The notions of category theory can be encountered in many different mathematical contexts. To illustrate the concepts, a range of examples will be given, but I will go quickly over standard examples – For common examples in greater detail and multitude, see the references below. It is not necessary to know the background of every single example to grasp the concepts.

To readers who wish to read a more detailed introduction, I recommend Tom Leinster’s “Basic Category Theory”  (available as a free pdf, but also published in book form) or in case you know German Martin Brandenburg’s “Einführung in die Kategorientheorie”. If you simply cannot get enough, Francis Bourceux’ three-volume Handbook of Categorical Algebra is the right place to get lost in the realm of categories and functors.

The views expressed on category theory are naturally (no pun intended) my own highly subjective ones and others may differ, especially those with a categorical disapproval of categorical things.

Introduction

The meta-mathematical notions of category theory provide a unifying framework for a lot of different mathematical theories. (Merely having a framework, however, can’t always replace delving into the specifics of the particular objects that one is interested in.) We can not only translate statements into categorical language, but we can also use categorical language to make things precise that might otherwise be vague, e.g. what it means for two different kinds of mathematical structures to be “equivalent” or what it means for a map to be “natural”.

THe basic objects of category theory are categories. One should think of a category as a big directed graph in which objects are represented by nodes and morphisms are represented by arrows and where we have a special operation called composition that takes two consecutive arrows and produces a third arrow representing going along one arrow first and then along the other one.
Compared with set theory, which can be called “materialistic”, in the sense that it is about what objects actually are made out of, category theory can be considered “behavioristic”, in the sense that it’s more about how objects behave, i.e. relate to each other. Relations between objects are conceptualized by the arrows also known as morphisms. But for morphisms, just like for the objects themselves, it’s more about how they relate each other and less about what they actually represent. The relations between morphisms are given by composition.
From a linguistic point of view, category theory is purely syntax, whereas semantics come into play only in the interpretation of particular examples.

Thinking categorically, we can economize on routine verifications by doing them in the utmost generality. More importantly, category theory can expose formal similarities between seemingly disconnected phenomena. These analogies might only become apparent through the high level of abstraction category-theoretic concepts provide, allowing one to transfer intuition, techniques and concepts in ways not available otherwise, at least not as easily or as precisely-defined.

Peter Freyd wrote once that “Perhaps the purpose of categorical algebra is to show that which is trivial is trivially trivial.”
Peter May commented: “I prefer an update of that quote: ‘ Perhaps the purpose of categorical algebra is to show that which is formal is formally formal’. It is by now abundantly clear that mathematics can be formal without being trivial.”

Now then! After this informal introduction, let us delve into the formal details of why that which is formal is formally formal.

Categories

Definition C1.1 A category $\mathcal{C}$ consists of the following data:

• A class of objects $\mathrm{Obj}(\mathcal{C})$
• For every pair of objects $X,Y \in \mathrm{Obj}(\mathcal{C})$, a set of morphisms $\mathrm{Hom}_{\mathcal{C}}(X,Y)$
• For every triple of objects $X,Y,Z \in \mathrm{Obj}(\mathcal{C})$, a map $\mathrm{Hom}_{\mathcal{C}}(Y,Z) \times \mathrm{Hom}_{\mathcal{C}}(X,Y) \to \mathrm{Hom}_{\mathcal{C}}(X,Z)$ called composition and denoted by $(f,g) \mapsto f \circ g$

Such that the following conditions hold:

• For any object $X \in \mathrm{Obj}(\mathcal{C})$, there exists an identity $\mathrm{id}_X \in \mathrm{Hom}_{\mathcal C}(X,X)$ such that for all objects $Y,Z \in \mathrm{Obj}(\mathcal{C})$ and all morphisms $f \in \mathrm{Hom}_{\mathcal{C}}(Y,X), g \in \mathrm{Hom}_{\mathcal{C}}(X,Z)$ we have $\mathrm{id}_X \circ f= f$ and $g \circ \mathrm{id}_X = g$
• Composition is associative, that means for all objects $X,Y,Z,W \in \mathrm{Obj}(\mathcal{C})$ and $f \in \mathrm{Hom}_{\mathcal{C}}(X,Y), g \in \mathrm{Hom}_{\mathcal{C}}(Y,Z), h \in \mathrm{Hom}_{\mathcal{C}}(Z,W)$, we have $h \circ (g \circ f) = (h \circ g) \circ f$
• $\mathrm{Hom}_{\mathcal{C}}(X,Y) \cap \mathrm{Hom}_{\mathcal{C}}(X',Y') = \varnothing$ unless $X=X'$ and $Y=Y'$

Remark The last condition is just a technical one that is not very interesting and is mostly omitted from verifications that things are categories. You can always replace the Hom-sets by disjoint copies by set-theoretic juggling, so it’s not much of an issue. The advantage of this convention is that source and target of a morphism are uniquely determined.

Example C1.2 We can form the category of sets $\mathbf{Set}$, where $\mathrm{Obj}(\mathbf{Set})$ is the class of all sets and for $X,Y \in \mathrm{Obj}(\mathbf{Set})$, $\mathrm{Hom}_{\mathbf{Set}}(X,Y)$ is the set of all maps from $X$ to $Y$ and the composition of morphisms is just the usual composition of maps. Many other examples (but not all of them) can be formed as “subcategories” of this example in the sense that the objects are sets with additional structure and morphisms are mappings which preserve that structure in some way, such as topological spaces and continuous maps or algebraic structures of a specific type and homomorphisms or smooth manifolds and smooth maps or complex manifolds and holomorphic maps or varieties over an algebraically closed fields and regular maps etc.

Example C1.3 There is another category with the class of all sets as objects, but with more morphisms. Recall that a mapping is a particular kind of relation. $\mathbf{Rel}$ is the category consisting of all sets as objects, and for two objects $X,Y \in \mathrm{Obj}(\mathbf{Rel})$, $\mathrm{Hom}_{\mathbf{Rel}}(X,Y)$ is the set of all relations from $X$ to $Y$, i.e. subsets $R \subset X \times Y$. Given three sets $X,Y,Z$ and relations $R \subset X \times Y, S \subset Y \times Z$, we can form the composite relation $S \circ R := \{(x,z) \in X \times Z \mid \exists y \in Y: ((x,y) \in R \land (y,z) \in S) \}$. (If $R$ and $S$ are functions, this reduces to regular function composition.) With this composition, $\mathbf{Rel}$ satisfies the axioms for a category.

Example C1.4 In the previous examples for categories, the objects were given by the class of all sets. But there’s also the possibility to fix a particular set $X$ and consider $X$ as a category $\mathcal{C}$ in the following way: $\mathrm{Obj}(\mathcal{C})=X$ and the only morphisms are the identity morphisms required by the definition of categories. Due to the striking similarity with discrete topological spaces (compare for instance the set of morphisms $\mathrm{Hom}_{\mathcal{C}}(x,y)=\varnothing$ if $x \neq y$ and $\mathrm{Hom}_{\mathcal{C}}(x,y)=\mathrm{id}_x$ if $x=y$ with the discrete metric), this construction is called the discrete category on the set $X$.

Example C1.5 Instead of only allowing for the minimum amount of morphisms, we can take a set $X$ and consider such categories with $X$ as their class of objects that have at most one morphism between two objects. In such a case, the only interesting information is whether there is a morphism between two objects or not. Consequently, such a category corresponds to a relation $R \subset X \times X$. But the requirements for compositions and identities force a relation to have some properties if it is supposed to define a category in this manner: the existence of identity morphisms in the supposed category is equivalent to the relation being reflexive and the existence of compositions translates to transivity. A reflexive and transitive relation is called “preorder”. For instance, all equivalence relations and all partial orderings are preorders. An example of a preorder that is neither can be formed by taking a ring, say, an integral domain $A$ such as $\mathbb{Z}$ and considering the divisibility relation on elements of $A$. Here the failure to be a partial order is due to the existence of non-trivial units and the failure to be an equivalence relation is to due the existence of non-invertible elements.

Definition C1.6 Speaking of invertible things, just like for an element in a ring, we can define when a morphism in a category is invertible. Let $f:X \to Y$ a morphism in a category. Then $f$ is called invertible, or an isomorphism, if there is a morphism $g:Y \to X$ such that $g \circ f = \mathrm{id}_X$ and $f \circ g = \mathrm{id}_Y$. If there is such a morphism, then $X$ and $Y$ are called isomorphic. Note that the notations $f: X \to Y$ and $g \circ f$, albeit reminiscent of the situation in the category $\mathbf{Set}$, don’t necessarily refer to mappings or function composition, but to the particular morphisms and composition in an arbitrary category.

Example C1.7 Other than restricting the size of morphisms as in example C1.5, one can also restrict the size of the class of objects. For this, let’s consider categories with only one object. In general, if we consider composition as a function on all morphisms of a category, it is only partially defined, since source and target need to match up correctly. But this doesn’t arise if we have only one object. Let $\mathcal C$ be a category with one object $x$ and let $\mathrm{Hom}_{\mathcal C}(x,x)=M$. Then composition is a (totally defined) mapping $M \times M \to M$, i.e. a binary operation.
The existence of the identity $\mathrm{id}_x:=e$ implies that $e$ is a unit with respect to this binary operation and the associativity of the composition implies that the binary operation is, well, associative. Thus composition $\circ:M \times M \to M$ makes $M$ into a monoid.
Conversely, given a monoid $M$, we can turn $M$ into a one-object category by taking a proxy object $x$ with no particular meaning, setting $\mathrm{Hom}(x,x)=M$ and defining the composition via the monoid operation. These constructions are inverse to each other, such that monoids correspond to one-object categories.
A particular frequently occuring and much beloved class of monoids consists of groups, i.e. monoids in which every element is invertible. By a pleasant convergence of terminology, an element in a monoid being invertible (in the classical sense) is the same as being an invertible morphism if we consider the monoid as a one-object category. Thus we can say that a monoid is a group if and only if every morphism is an isomorphism. This leads to the following notion:

Groupoids

Definition C1.8 A groupoid is a category such that every morphism is an isomorphism.

If we think of groups as encoding the symmetries of one object, then groupoids can capture the symmetries of a configuration with many objects.

Example C1.9 Let $R$ be a preorder on a set $X$, then we can form a category from these data as described in example C1.8. One can ask when one obtains groupoid in this way. It turns out that the corresponding category is a groupoid if and only if $R$ is symmetric, i.e. an equivalence relation.

Remark From this observation we can extract an intuition for general groupoids: a groupoid is like a set with an equivalence relation, except that two objects can be equivalent in more than one way and we’re keeping track of different ways of being equivalent. From this viewpoint a group, being a one-object groupoid, is like the various ways a particular object is equivalent to itself, following the narrative that groups encode the symmetries of an object.

Example C1.10 Let $G$ be a group acting on a set $X$, then one can form a groupoid encoding the group action as follows: Let $X // G$ be the category having elements from $X$ as its objects and for every $x \in X$ and $g \in G$, there’s a morphism $x \to gx$, such that $\mathrm{Hom}_{X // G}(x,y)$ is in bijection with $\{g \in G:gx=y\}$. This groupoid played an important role in a previous post.

Example C1.11 Let $\mathcal C$ be any category. Then there is a maximal subcategory that is a groupoid: simply take the subcategory of $\mathcal C$ with the same objects as $\mathcal C$ and all the isomorphisms of $\mathcal C$ as morphisms. This is called the core of the category $\mathcal C$ and it is a groupoid. If $\mathcal C$ has only one object, i.e. is a monoid, then the core of $\mathcal C$ is just the group of invertible elements, also known as units.
As an exercise, one can check that the categories $\mathbf{Set}$ and $\mathbf{Rel}$ (cf. C1.2 and C1.3) have the same core, i.e. any invertible relation is already a function and in fact a bijection.

Example C1.12 Let $X$ be a topological space. Then the fundamental groupoid $\Pi_1(X)$ has as its objects all elements of $X$. For $x,y \in X$, $\mathrm{Hom}_{\Pi_{\leq 1}(X)}(x,y)$ consists of all homotopy classes of paths from $x$ to $y$. Composition is given by concatenation of paths. $\Pi_{\leq 1}(X)$ contains important homotopy-theoretic information about $X$, such as the path-components and the fundamental group of each path-component. For more information on this very geometric construction and groupoids in algebraic topology, I heartily recommend Ronald Brown’s “Topology and Groupoids”.

This concludes the first part of the mini-series on introductory categories. Next time we’ll look into functors.

Tensor Products for Group Actions, Part 2

In this previous post, tensor products of $G$-sets were introduced and some basic properties were proved, this post is a continuation, so I’ll asume that you’re familiar with the contents of that post.

In this post, unless specified otherwise, $G,H,K,I$ will denote groups. Groups will sometimes be freely identified with the corresponding one-object category. Left $G$-sets will sometimes just be referred to as $G$-sets.

After some lemmas, we will begin this post by some easy consequences of the Hom-Tensor adjunction, which is the main result of the previous post.

Lemma The category $G\textrm{-}\mathbf{Set}$ is complete and cocomplete and the limits and colimits look like in the category of sets (i.e. the forgetful functor $G\textrm{-}\mathbf{Set} \to \mathbf{Set}$ is continuous and cocontinuous) with the “obvious” actions from $G$. Similarly for $\mathbf{Set}\textrm{-}G$.

Proof This is not too difficult to prove directly (you can reduce the existence of (co)limits to (co)products and (co)equalizers by general nonsense), but it also follows directly from the fact that $G\textrm{-}\mathbf{Set}$ is the functor category $[G, \mathbf{Set}]$. The reason is that if $\mathcal{C}$ and $\mathcal{D}$ are categories and $\mathcal{D}$ is (co)complete (and $\mathcal{C}$ is small to avoid any set-theoretic trouble), then the functor category $[\mathcal{C},\mathcal{D}]$ is also (co)complete and the (co)limits may be computed “pointwise”. In the case of $[G, \mathbf{Set}]$, $G$ has only one object, so the (co)limits look like they do in $\mathbf{Set}$.

Lemma If $X$ is a $(G,H)$-set, $Y$ is a $(H,K)$-set and $Z$ is a $(K,I)$-set, then we have a natural isomorphism of $(G,I)$-sets