A Brief Introduction to Categories, Part 8: Adjunctions I

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

Introduction

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

Galois Connections

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

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

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

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

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

Such that the following condition holds:

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

We write F \dashv G

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Adjunctions via Hom-Sets

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

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

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

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

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

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

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

An analogy with linear algebra

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

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:

cone

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

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:

equalizer

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

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

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:

yoneda2

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:
    cd 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: det stating that the determinant is natural in R.

Natural Transformations as Homotopies

HomotopySmall

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 Y \cong Y 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 anyhing via 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.

Example C2.14 Let \mathbf{Cat} be the category from the previous example. Fix a commutative ring R. For any small category \mathcal C, let R[\mathcal C] be the free R-module with a basis given by the set of all morphisms in \mathcal C. (Note for the set-theoretically careful: since the objects form a set and the morphisms between two fixed objects form a set, the set of all morphisms is a union of sets indexed by a set (twice), which is thus again a set)
This means that elements of R[\mathcal C] are formal linear combinations of morphisms in \mathcal C. For two morphisms f,g in \mathcal C, considered as basis elements of R[\mathcal C], define their product to be f \circ g, if f and g can be composed or 0 otherwise. This extends bilinearly to a mapping R[\mathcal C] \times R[\mathcal C] \to R[\mathcal C] that makes R[\mathcal C] into an associative, generally non-commutative and non-unital R-algebra. If F: \mathcal C \to \mathcal D is a functor of small categories, then F extends linearly to a homomorphism of R-algebras R[\mathcal C] \to R[\mathcal D].
Thus we obtain a functor from the category of small categories to the category of associative R-algebras. If G is a group, considered as a one-object category (cf. example C1.7), then R[G] coincides with the group algebra associated to R and G (for more details on how this is useful for representation theory, see this post).
The same construction also works if R is not commutative, yielding a non-unital ring, but then it wouldn’t make sense to call the result an R-algebra.

Contravariance

contra

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.