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.

A Brief Introduction to Categories, Part 1: Categories

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

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

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

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

Introduction

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

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

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

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

Categories

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

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

Such that the following conditions hold:

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

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

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

 

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

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

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

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

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

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

Groupoids

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

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

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

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

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

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

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

 

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