Chapter 6

Fundamental Considerations of Categories

This chapter focuses mainly on limits and colimits in a given category C. It also discusses other important and interesting categorical constructions, such as the simple notion of opposite categories and the Grothendieck construction, which gives something like the histogram of a set-valued functor. As usual, the work relies as often as possible on a grounding in databases.

This chapter is in some sense parallel to Chapter 3, Fundamental Considerations in Set. When attention is restricted to C=Set, the discussion of limits and colimits in this chapter subsumes the earlier work (which focused on certain finite limits and colimits). Also, this chapter ends with a section called Arithmetic of Categories, Section 6.2.5, which is tightly parallel with Section 3.4.3. This shows that in terms of grade school arithmetic expressions like

A×(B+C)=?(C×A)+(B×A),

the behavior of categories is predictable: the rules for categories are well aligned with those of sets, which are well aligned with those of natural numbers.

6.1   Limits and colimits

Limits and colimits are universal constructions, meaning they represent certain ideals of behavior in a category. When it comes to sets that map to A and B, the A × B grid is ideal—it projects on to both A and B as straightforwardly as possible. When it comes to sets that can interpret the elements of both A and B, the disjoint union AB is ideal—it includes both A and B without confusion or superfluity. These are limits and colimits in Set. Limits and colimits exist in other categories as well.

Limits in a preorder are meets; colimits in a preorder are joins. Limits and colimits also exist for database instances and monoid actions, allowing us to discuss, for example, the product or union of different finite state machines. Limits and colimits exist for topological spaces, giving rise to products and unions as well as to quotients.

Limits and colimits do not exist in every category. However, when C is complete with respect to limits (or colimits), these limits always seem to mean something valuable to human intuition. For example, when a subject had already been studied for a long time before category theory came to promenance, it often turned out that classically interesting constructions in the subject corresponded with limits and colimits in its categorification C. For example, products, unions, and quotients by equivalence relations are classical ideas in set theory that are naturally captured by limits and colimits in Set.

6.1.1   Products and coproducts in a category

Section 3.1 discussed products and coproducts in the category Set of sets. Now we discuss the same notions in an arbitrary category. For both products and coproducts, we begin with examples and then write the general concept.

6.1.1.1   Products

The product of two sets is a grid, which projects down onto each of the two sets. This is a good intuition for products in general.

Example 6.1.1.2. Given two preorders, X1(X1,1) and X2(X2,2), we can take their product and get a new preorder X1×X2. Both X1 and X2 have underlying sets (namely, X1 and X2), so we might hope that the underlying set of X1× X2 is the set X1 × X2 of ordered pairs, and this turns out to be true. We have a notion of less-than on X1, and we have a notion of less-than on X2; we need to construct a notion of less-than on X1× X2. So, given two ordered pairs (x1, x2) and (x1,x2), when should we say that (x1,x2)1,2(x1,x2) holds? A guess is that it holds iff both x11x1 and x22x2 hold, and this works:1

X1×X2(X1×X2,1,2).

Note that the projection functions X1 × X2X1 and X1 × X2X2 induce morphisms of preorders. That is, if (x1,x2)1,2(x1,x2), then in particular, x11x1 and x22x2. So we have preorder morphisms

art

Exercise 6.1.1.3.

Suppose you have a partial order S=(S,S) on songs (you prefer some songs over others, but sometimes you cannot compare). And suppose you have a partial order A=(A,A) on pieces of art. You are about to be given two pairs (s, a) and (s′, a′), each including a song and an art piece. Does the product partial order S×A provide a reasonable guess for your preferences on these pairs?

Exercise 6.1.1.4.

Consider the partial order ⩽ on ℕ given by standard less-than-or-equal-to, so 5 ⩽ 9, and let divides be the partial order from Example 4.4.3.2, where 6 divides 12. If we call the product order (X, ≤) ≔ (ℕ, ⩽) × (ℕ, divides), which of the following are true?

(2,4)(3,4)(2,4)(3,5)(2,4)(8,0)(2,4)(0,0)

Example 6.1.1.5. Given two graphs G1 = (V1, A1, src1, tgt1) and G2 = (V2, A2, src2, tgt2), we can take their product and get a new graph G1 × G2. The vertices are the grid of vertices V1 × V2, so each vertex in G1 × G2 is labeled by a pair of vertices, one from G1 and one from G2. When should an arrow connect (v1, v2) to (v1,v2)? Whenever we can find an arrow in G1 connecting v1 to v1 and we can find an arrow in G2 connecting v2 to v2. It turns out there is a simple formula for the set of arrows in G1 × G2, namely, A1 × A2.

Let’s write GG1 × G2 and say, G = (V, A, src, tgt). We said that V = V1 × V2 and A = A1 × A2. What should the source and target functions AV be? Given a function src1 : A1V1 and a function src2 : A2V2, the universal property for products in Set (Proposition 3.1.1.10 or, better, Example 3.1.1.15) provides a unique function

srcsrc1×src2:A1×A2V1×V2.

Namely, the source of arrow (a1, a2) will be the vertex (src1(a1), src2(a2)). Similarly, we have a ready-made choice of target function tgt = tgt1 × tgt2. We have now defined the product graph,

G=G1×G2=(V1×V2,A1×A2,src1×src2,tgt1×tgt2).

Here is a concrete example. Let I and J be drawn as follows:

art

The product I × J has, as expected, 3 * 4 = 12 vertices and 3 * 4 = 12 arrows:

art

Here is the most important thing to notice. Look at the Arrow table for I × J, and for each ordered pair, look only at the first entry in all three columns; you will see something that matches with the Arrow table for I. For example, in the I × J table, the first row’s first entries are f, v, w. Then do the same for the second entry in each column, and again you will see a match with the Arrow table for J. These matches are readily visible graph homomorphisms I × JI and I × JJ in Grph.

Exercise 6.1.1.6.

Let [1] denote the linear order graph of length 1,

art

and let P = Paths([1]) be its paths-graph, as in Example 5.1.2.25 (so P should have three arrows and two vertices). Draw the graph P × P.

Exercise 6.1.1.7.

Recall from Example 4.5.2.10 that a discrete dynamical system (DDS) is a set s together with a function f : ss. It is clear that if

art

is the loop schema, then a DDS is simply an instance (a functor) I : LoopSet. We have not yet discussed DDS products, but perhaps you can guess how they should work. For example, consider these instances I, J : LoopSet:

art

a. Make a guess and tabulate I × J. Then draw it.2

b. Recall the notion of natural transformations between functors (see Example 5.3.3.5), which in the case of functors LoopSet are the morphisms of instances. Do you see clearly that there is a morphism of instances I × JI and I × JJ? Check that if you look only at the left-hand coordinates in your I × J, you see something compatible with I.

In each case what is most important to recognize is that there are projection maps I × JI and I × JJ, and that the construction of I × J seems as straightforward as possible, subject to having these projections.

Definition 6.1.1.8. Let C be a category, and let X,YOb(C) be objects. A span on X and Y consists of three constituents (Z, p, q), where ZOb(C) is an object, and where p : ZX and q : ZY are morphisms in C.

art

A product of X and Y is a span Xπ1X×Yπ2Y, such that for any other span XpZqY there exists a unique morphism tp,q : ZX × Y such that the following diagram commutes:3

art

We often denote the morphism tp,q by 〈p, q〉: ZX × Y .

Remark 6.1.1.9. Definition 6.1.1.8 endows the product of two objects with a universal property. It says that a product of two objects X and Y maps to those two objects and serves as a gateway for all that do the same. “None shall map to X and Y except through me!” This grandiose property is held by products in all the various categories discussed so far. It is what is meant by “X × Y maps to both X and Y and does so as straightforwardly as possible.” The grid of dots obtained as the product of two sets has such a property (see Example 3.1.1.11).

Example 6.1.1.10. Example 6.1.1.2 discussed products of preorders. This example discusses products in an individual preorder. That is, by Proposition 5.2.1.13, there is a functor PrOCat that realizes each individual preorder as a category. If P=(P,) is a preorder, what are products in P? Given two objects a,bOb(P), we first consider {a, b} spans, i.e., azb. That is some z such that za and zb. The product is a span aa × bb, but such that every other spanning object z is less than or equal to a × b. In other words, a × b is as big as possible subject to the condition of being less than a and less than b. This is precisely their meet, ab (see Definition 4.4.2.1).

Example 6.1.1.11. Note that the product of two objects in a category C may not exist. Let’s return to preorders to see this phenomenon.

Consider the set ℝ2, and say that (x1, y1) ≤ (x2, y2) if there exists ≥ 1 such that x1 = x2 and y1 = y2; in other words, point p is less than point q if, in order to travel from q to the origin along a straight line, one must pass through p along the way.4 We have given a perfectly good partial order, but p ≔ (1, 0) and q ≔ (0, 1) do not have a product. Indeed, it would have to be a nonzero point that was on the same line through the origin as p and the same line through the origin as q, of which there are none.

Example 6.1.1.12. Note that there can be more than one product of two objects in a category C but that any two choices will be canonically isomorphic. Let’s return once more to preorders to see this phenomenon.

Consider the set ℝ2, and say that (x1, y1) ≤ (x2, y2) if x12+y12x22+y22, in other words, if the former is closer to the origin. For any point p = (x0, y0), let Cp={(x,y)2|x2+y2=x02+y02)}, and call it the orbit circle of p.

For any two points p, q, there will be lots of points that serve as products p × q: any point a on the smaller of their two orbit circles will suffice. Given any two points a, a′ on this smaller circle, we have a unique isomorphism aa′ because aa′ and a′ ≤ a.

Exercise 6.1.1.13.

Consider the preorder P of cards in a deck, shown in Example 4.4.1.3; it is not the whole story of cards in a deck, but take it to be so. Consider this preorder P as a category (by way of the functor PrOCat).

a. For each of the following pairs, what is their product in P (if it exists)?

a diamond×a hearta queen×a black carda card×a red carda face card×a black card

b. How would these answers differ if P were completed to the “whole story” partial order classifying cards in a deck?

Exercise 6.1.1.14.

Let X be a set, and consider it as a discrete category. Given two objects x, y ∈ Ob(X), under what conditions will there exist a product x × y in X?

Exercise 6.1.1.15.

Let f : ℝ → ℝ be a function like one that you would see in grade school (e.g., f(x) = x+7). A typical thing to do is to graph f as a curve running through the plane ℝ2 ≔ ℝ×ℝ. For example, f is graphed as a straight line with slope 1 and y-intercept 7. In general, the graph of f is a curve that be understood as a function F : ℝ → ℝ2.

a. For an arbitrary function f : ℝ → ℝ with graph F : ℝ → ℝ2 and an arbitrary r ∈ ℝ, what are the (x, y) coordinates of F (r) ∈ ℝ2?

b. Obtain F : ℝ → ℝ2 using the universal property given in Definition 6.1.1.8.

Exercise 6.1.1.16.

Consider the preorder (ℕ, divides), discussed in Example 4.4.3.2, where, e.g., 5 ≤ 15, but 5 ≰ 6. Consider it as a category, using the functor PrOCat.

a. What is the product of 9 and 12 in this category?

b. Is there a standard name for products in this category?

Example 6.1.1.17. Products do not have to exist in an arbitrary category, but they do exist in Cat, the category of categories. That is, given two categories C and D, there is a product category C×D. We have Ob(C×D)=Ob(C)×Ob(D), and for any two objects (c, d) and (c′, d′), we have

HomC×D((c,d),(c,d))=HomC(c,c)×HomC(d,d).

The composition formula is clear.

Let [1] ∈ Ob(Cat) denote the linear order category of length 1:

art

As a schema it has one arrow, but as a category it has three morphisms. So we expect [1]×[1] to have nine morphisms, and that is true. In fact, [1]×[1] looks like a commutative square:

art

We see only four morphisms here, but there are also four identities and one morphism (0, 0) → (1, 1) given by composition of either direction. It is a minor miracle that the categorical product somehow “knows” that this square should commute; however, this is not a mere preference but follows rigorously from the definitions we already gave of Cat and products.

6.1.1.18   Coproducts

The coproduct of two sets is their disjoint union, which includes nonoverlapping copies of each of the two sets. This is a good intuition for coproducts in general.

Example 6.1.1.19. Given two preorders, X1(X1,1) and X2(X2,2), we can take their coproduct and get a new preorder X1 X2. Both X1 and X2 have underlying sets (namely, X1 and X2), so we might hope that the underlying set of X1× X2 is the disjoint union X1X2, and that turns out to be true. We have a notion of less-than on X1 and a notion of less-than on X2.

Given an element xX1X2 and an element x′ ∈ X1X2, how can we use ≤1 and ≤2 to compare x1 and x2? The relation ≤1 only knows how to compare elements of X1, and the relation ≤2 only knows how to compare elements of X2. But x and x′ may come from different homes, e.g., xX1 and x′ ∈ X2, in which case neither ≤1 nor ≤2 gives any clue about which should be bigger.

So when should we say that x1⊔2 x′ holds? The obvious guess is to say that x is less than x′ iff both x and x′ are from the same home and the local ordering has xx′. To be precise, we say x1⊔2 x′ if and only if either one of the following conditions hold:

  • xX1 and x′ ∈ X1 and x1 x′, or
  • xX2 and x′ ∈ X2 and x2 x′.

With ≤1⊔2 so defined, one checks that it is not only a preorder but that it serves as a coproduct of X1 and X2,5

X1X2(X1X2,12).

Note that the inclusion functions X1X1X2 and X2X1X2 induce morphisms of preorders. That is, if x, x′ ∈ X1 are elements such that x1 x′ in X1, then the same will hold in X1 X2, and similarly for X2. So we have preorder morphisms

art

Exercise 6.1.1.20.

Suppose you have a partial order A(A,A) on apples (you prefer some apples to others, but sometimes you cannot compare). And suppose you have a partial order O(O,O) on oranges. You are about to be given two pieces of fruit from a basket of apples and oranges. Is the coproduct partial order AO a reasonable guess for your preferences, or does it seem biased?

Example 6.1.1.21. Given two graphs G1 = (V1, A1, src1, tgt1) and G2 = (V2, A2, src2, tgt2), we can take their coproduct and get a new graph G1G2. The vertices will be the disjoint union of vertices V1V2, so each vertex in G1G2 is labeled either by a vertex in G1 or by one in G2 (if any labels are shared, then something must be done to differentiate them). When should an arrow connect v to v′? Whenever both are from the same component (i.e., either v, v′ ∈ V1 or v, v′ ∈ V2) and we can find an arrow connecting them in that component. It turns out there is a simple formula for the set of arrows in G1G2, namely, A1A2.

Let’s write GG1G2 and say, G = (V, A, src, tgt). We now know that V = V1V2 and A = A1A2. What should the source and target functions AV be? Given a function src1 : A1V1 and a function src2 : A2V2, the universal property for coproducts in Set can be used to specify a unique function

srcsrc1src2:A1A2V1V2.

Namely, for any arrow aA, we know either aA1 or aA2 (and not both), so the source of a will be the vertex src1(a) if aA1 and src2(a) if aA2. Similarly, we have a ready-made choice of target function tgt = tgt1tgt2. We have now defined the coproduct graph.

Here is an example. Let I and J be as in Example 5.3.3.5:

art

The coproduct IJ has, as expected, 3 + 5 = 8 vertices and 3 + 4 = 7 arrows:

art

Here is the most important thing to notice. Look at the Arrow tables and notice that there is a way to send each row in I to a row in IJ such that all the foreign keys match, and similarly for J. This also works for the vertex tables. These matches are readily visible graph homomorphisms IIJ and JIJ in Grph.

Exercise 6.1.1.22.

Recall from Example 4.5.2.10 that a discrete dynamical system (DDS) is a set s together with a function f : ss; if

art

is the loop schema, then a DDS is simply an instance (a functor) I : LoopSet. We have not yet discussed DDS coproducts but perhaps you can guess how they should work. For example, consider these instances I, J : LoopSet:

art

Make a guess and tabulate IJ. Then draw it.

In each case (preorders, graphs, DDSs), what is most important to recognize is that there are inclusion maps IIJ and JIJ, and that the construction of IJ seems as straightforward as possible, subject to having these inclusions.

Definition 6.1.1.23. Let C be a category, and let X,YOb(C) be objects. A cospan on X and Y consists of three constituents (Z, i, j), where ZOb(C) is an object, and where i : XZ and j : YZ are morphisms in C.

art

A coproduct of X and Y is a cospan Xι1XYι2Y, such that for any other cospan XiZjY there exists a unique morphism si,j : XYZ such that the following diagram commutes:6

art

The morphism si,j is often denoted {ij :XYZ .

Remark 6.1.1.24. Definition 6.1.1.8 endows the coproduct of two objects with a universal property. It says that a coproduct of two objects X and Y receives maps from those two objects, and serves as a gateway for all that do the same. “None shall receive maps from X and Y except through me!” This grandiose property is held by all the coproducts discussed so far. It is what is meant by “XY receives maps from both X and Y and does so as straightforwardly as possible.” The disjoint union of dots obtained as the coproduct of two sets has such a property (see Example 3.1.2.5).

Example 6.1.1.25. By Proposition 5.2.1.13, there is a functor PrOCat that realizes every preorder as a category. If P=(P,) is a preorder, what are coproducts in P? Given two objects a,bOb(P), we first consider {a, b} cospans, i.e., azb. A cospan of a and b is any z such that az and bz. The coproduct will be such a cospan aabb, but such that every other cospanning object z is greater than or equal to ab. In other words, ab is as small as possible subject to the condition of being bigger than a and bigger than b. This is precisely their join, ab (see Definition 4.4.2.1).

Just as for products, the coproduct of two objects in a category C may not exist, or it may not be unique. The nonuniqueness is much less “bad” because given two candidate coproducts, they will be canonically isomorphic. They may not be equal, but they are isomorphic. But coproducts might not exist at all in certain categories.

Example 6.1.1.26. Consider the set ℝ2 and partial order from Example 6.1.1.11, where (x1, y1) ≤ (x2, y2) if there exists ≥ 1 such that x1 = x2 and y1 = y2. Again the points p ≔ (1, 0) and q ≔ (0, 1) do not have a coproduct. Indeed, it would have to be a nonzero point that was on the same line through the origin as p and the same line through the origin as q, of which there are none.

Exercise 6.1.1.27.

Consider the preorder P of cards in a deck, shown in Example 4.4.1.3; it is not the whole story of cards in a deck, but take it to be so. Consider this preorder P as a category (by way of the functor PrOCat).

a. For each of the following pairs, what is their coproduct in P (if it exists)?

a diamonda hearta queena black carda carda red carda face carda black card

b. How would these answers differ if P were completed to the “whole story” partial order classifying cards in a deck?

Exercise 6.1.1.28.

Let X be a set, and consider it as a discrete category. Given two objects x, y ∈ Ob(X), under what conditions will there exist a coproduct xy?

Exercise 6.1.1.29.

Consider the preorder (ℕ, divides), discussed in Example 4.4.3.2, where, e.g., 5 ≤ 15, but 5 ≰ 6.

a. What is the coproduct of 9 and 12 in that category?

b. Is there a standard name for coproducts in that category?

6.1.2   Diagrams in a category

Diagrams have illustrated the text throughout the book. What is the mathematical foundation of these illustrations? The answer is functors.

Definition 6.1.2.1 (Diagrams). Let C and I be categories. An I-shaped diagram in C is simply a functor d:IC. In this case I is called the indexing category for the diagram.7

Here are some rules for drawing diagrams as in Definition 6.1.2.1.

Rules of good practice 6.1.2.2. Suppose given an indexing category I and an I-shaped diagram X:IC. One draws this as follows:

(i) For each object in qI, draw a dot labeled by X(q); if several objects in I point to the same object in C, then several dots are labeled the same way.

(ii) For each morphism f : qq′ in I, draw an arrow between dots X(q) and X(q′), and label it X(f) in C. Again, if several morphisms in I are sent to the same morphism in C, then several arrows are labeled the same way.

(iii) One can abridge this process by not drawing every morphism in I, as long as every morphism in I is represented by a unique path in C, i.e., as long as the drawing is sufficiently unambiguous as a depiction of X:IC.

(iv) One may choose to draw a dash box around the finished diagram X to indicate that it is referencing an ambient category C.

Example 6.1.2.3. Consider the commutative diagram in Set:

art

This is the drawing of a functor d : [1] × [1] → Set (see Example 6.1.1.17). With notation for the objects and morphisms of [1] × [1], as shown in diagram (6.1), we have d(0, 0) = d(0, 1) = d(1, 0) = ℕ and d(1, 1) = ℤ (for some reason) and d(id0, f): ℕ → ℕ given by nn + 1, and so on. The fact that d is a functor means it must respect composition formulas, which implies that diagram (6.2) commutes. We call [1] × [1] the commutative square indexing category. 8

Example 6.1.2.4. Recall from Section 2.2 that not all diagrams commute; one must specify that a given diagram commutes if one wishes to communicate this fact. But then, how is a noncommuting diagram to be understood as a functor?

Let G ∈ Ob(Grph) denote the following graph:

art

Recall the free category functor F : GrphCat (see Example 5.1.2.33). The free category F (G) ∈ Ob(Cat) on G looks almost like [1]×[1] in Example 6.1.2.3 except that since (0,0)[f, g] is a different path in G than is (0,0)[h, i], they become different morphisms in F(G). A functor F(G) → Set might be drawn the same way that (6.2) is, but it would be a diagram that would not be said to commute.

Exercise 6.1.2.5.

Consider [2], the linear order category of length 2.

a. Is [2] the appropriate indexing category for commutative triangles?

b. If not, what is? If so, what might lead someone to be skeptical, and why would the skeptic be wrong?

Example 6.1.2.6. Recall that an equalizer in Set is a diagram of sets that looks like this:

art

where g1f = g2f. What is the indexing category for such a diagram? It is the schema (6.3) with the PED E[f, g1] ≃ E[f, g2]. That is, in some sense one sees the indexing category, but the PED needs to be declared.

Exercise 6.1.2.7.

Let C be a category, AOb(C) an object, and f : AA a morphism in C. Consider the following two diagrams in C:

art

a. Should these two diagrams have the same indexing category?

b. Write the indexing category for both.

c. If they have the same indexing category, what is causing or allowing the pictures to appear different?

d. If they do not have the same indexing category, what coincidence makes the two pictures have so much in common?

Definition 6.1.2.8. Let I ∈ Ob(Cat) be a category. The left cone on I, denoted I, is the category defined as follows. On objects we put Ob(I) = {LCI} ⊔ Ob(I), and we call the new object LCI the cone point of I. On morphisms we add a single new morphism sb : LCIb for every object b ∈ Ob(I); more precisely,

HomI(a,b)={HomI(a,b)if a,bOb(I),{sb}if a=LCI,bOb(I),{idLCI}if a=b=LCIif aOb(I),b=LCI.

The composition formula is in some sense obvious. To compose two morphisms both in I, compose as dictated by I; if one has LCI as source, then there will be a unique choice of composite.

There is an obvious inclusion of categories,

II.(6.4)

Remark 6.1.2.9. Note that the specification of I given in Definition 6.1.2.8 works just as well if I is considered a schema and we are constructing a schema I: add the new object LCI and the new arrows sb : LCIb for each b ∈ Ob(I), and for every morphism f : bb′ in I, add a PED [sb]LCI [sb,f]LCI . We generally do not distinguish between categories and schemas, since they are equivalent, by Theorem 5.4.2.3.

Example 6.1.2.10. For a natural number n ∈ ℕ, define the n-leaf star schema, denoted Starn, to be the category (or schema; see Remark 6.1.2.9) n, where n is the discrete category on n objects. The following illustrate the categories Star0, Star1, Star2, and Star3:

art

Exercise 6.1.2.11.

Let C00¯ denote the empty category, and for any natural number n ∈ ℕ, let Cn+1=(Cn). Draw C4.

Exercise 6.1.2.12.

Let C be the graph-indexing schema as in (5.8). What is C, and how does it compare to the indexing category for equalizers, (6.3)?

Solution 6.1.2.12.

They are the same,

art

where the latter is understood to include the PED E[f, g1] = E[f, g2].

Definition 6.1.2.13. Let I ∈ Ob(Cat) be a category. The right cone on I, denoted I, is the category defined as follows. On objects we put Ob(I) = Ob(I) ⊔ {RCI}, and we call the new object RCI the cone point of I. On morphisms we add a single new morphism tb : bRCI for every object b ∈ Ob(I); more precisely,

HomI(a,b)={HomI(a,b)if a,bOb(I),{tb}if aOb(I),b=RCI,{idRCI}if a=b=RCI,if a=RCI,bOb(I).

The composition formula is in some sense obvious. To compose two morphisms both in I, compose as dictated by I; if one has RCI as target, then there will be a unique choice of composite.

There is an obvious inclusion of categories II.

Exercise 6.1.2.14.

Let C be the category (2), where 2 is the discrete category on two objects. Then C is somehow square-shaped, but what category is it exactly? Is C the commutative square indexing category [1] × [1] (see Example 6.1.2.3), is it the noncommutative square indexing category F (G) (see Example 6.1.2.4), or is it something else?

Exercise 6.1.2.15.

Let I = 2, let C be an arbitrary category, and let D=Fun(I,C).

a. Using Rules 6.1.2.2, draw an object d ∈ Ob(D).

b. How might you draw a morphism f : dd′ in D?

Solution 6.1.2.15.

a. We have I = Star2, as in Example 6.1.2.10. We can draw an object d:IC as a span,

d1id0jd2.

b. We could draw f : dd′ as

art

6.1.3   Limits and colimits in a category

Let C be a category, let I be an indexing category (which means that I is a category that we use as the indexing category for a diagram), and let D:IC be an I-shaped diagram (which means a functor). It is in relation to this setup that we can discuss the limit or colimit. In general, the limit of a diagram D:IC is a I shaped diagram, lim D:IC. In the case of products we have I = 2, and the limit looks like a span, the shape of I (see Exercise 6.1.2.15). For general I, D we may have many I-shaped diagrams; which of them is the limit of D? Answer: The one with the universal gateway property; see Remark 6.1.1.9.

6.1.3.1   Universal objects

Definition 6.1.3.2. Let C be a category. An object aOb(C) is called initial if, for all objects cOb(C), there exists a unique morphism ac, i.e., |HomC(a,c)|=1. An object zOb(C) is called terminal if, for all objects cOb(C), there is exists a unique morphism cz, i.e., |HomC(c,z)|=1.

Example 6.1.3.3. For any category I, the left cone I has a unique initial object, and the right cone I has a unique terminal object; in both cases it is the cone point. See Definitions 6.1.2.8 and 6.1.2.13.

Example 6.1.3.4. The initial object in Set is the set a for which there is always one way to map from a to anything else. Given c ∈ Ob(Set), there is exactly one function Ø → c, because there are no choices to be made, so the empty set Ø is the initial object in Set.

The terminal object in Set is the set z for which there is always one way to map to z from anything else. Given c ∈ Ob(Set), there is exactly one function c → {☺}, where {☺} is any set with one element, because there are no choices to be made: everything in c must be sent to the single element in {☺}. There are lots of terminal objects in Set, and they are all isomorphic to 1.

Example 6.1.3.5. The initial object in Grph is the graph a for which there is always one way to map from a to anything else. Given c ∈ Ob(Grph), there is exactly one graph homomorphism Ø → c, where Ø ∈ Ob(Grph) is the empty graph; so Ø is the initial object.

The terminal object in Grph is more interesting. It is

art

the graph with one vertex and one arrow. In fact, there are infinitely many terminal objects in Grph, but all of them are isomorphic to Loop, meaning one can change the names of the vertex (s) and the arrow (f) and get another terminal object.

Exercise 6.1.3.6.

Let X be a set, let ℙ(X) be the set of subsets of X (see Definition 3.4.4.9). We can regard ℙ(X) as a preorder under inclusion of subsets (see, for example, Section 4.4.2). And we can regard preorders as categories using a functor PrOCat (see Proposition 5.2.1.13).

a. What is the initial object in ℙ(X)?

b. What is the terminal object in ℙ(X)?

Example 6.1.3.7. The initial object in the category Mon of monoids is the trivial monoid, 1. Indeed, for any monoid M, a morphism of monoids 1M is a functor between one-object categories and these are determined by where they send morphisms. Since 1 has only the identity morphism and functors must preserve identities, there is no choice involved in finding a monoid morphism 1M.

Similarly, the terminal object in Mon is also the trivial monoid, 1. For any monoid M, a morphism of monoids M1 sends everything to the identity; there is no choice.

Exercise 6.1.3.8.

a. What is the initial object in Grp, the category of groups?

b. What is the terminal object in Grp?

Example 6.1.3.9. Recall the preorder Prop of logical propositions from Section 5.2.4.1. The initial object is a proposition that implies all others. It turns out that “FALSE” is such a proposition. The proposition “FALSE” is like “1 ≠ 1”; in logical formalism it can be shown that if “FALSE” is true, then everything is true.

The terminal object in Prop is a proposition that is implied by all others. It turns out that “TRUE” is such a proposition. In logical formalism, everything implies that “TRUE” is true.

Example 6.1.3.10. The discrete category 2 has no initial object and no terminal object. The reason is that it has two objects 1, 2, but no maps from one to the other, so Hom2(1, 2) = Hom2(2, 1) = Ø.

Exercise 6.1.3.11.

Recall the divides preorder (see Example 4.4.3.2), where 5 divides 15.

a. Considering this preorder as a category, does it have an initial object?

b. Does it have a terminal object?

Exercise 6.1.3.12.

Let M = (List({a, b}), [ ], ++) denote the free monoid on the set {a, b} (see Definition 4.1.1.15) considered as a category via the functor MonCat (see Theorem 5.2.1.3).

a. Does M have an initial object?

b. Does M have a terminal object?

c. Which monoids M, considered as one-object categories, have initial (resp. terminal) objects?

Exercise 6.1.3.13.

Let S be a set, and consider the indiscrete category KS ∈ Ob(Cat) on objects S (see Example 5.3.4.3).

a. For what S does KS have an initial object?

b. For what S does KS have a terminal object?

An object in a category is sometimes called universal if it is either initial or terminal, but we rarely use that term in practice, preferring to be specific about whether the object is initial or terminal. The word final is synonymous with the word terminal, but we will use the latter.

Universal properties refer to either initial or terminal objects in a specially-designed category. Colimits end up having an initial sort of universal property, and limits end up having a terminal sort of universal property. See Section 6.1.3.16.

Warning 6.1.3.14. A category C may have more than one initial object; similarly a category C may have more than one terminal object. As shown in Example 6.1.3.4, any set with one element, e.g., {*} or {☺} or {43}, is a terminal object in Set. Each of these terminal sets has the same number of elements, i.e., there exists an isomorphism between them, but they are not exactly the same set.

In fact, Proposition 6.1.3.15 shows that in any category C, any two terminal objects in C are isomorphic (similarly, any two initial objects in C are isomorphic). While there are many isomorphisms in Set between {1, 2, 3} and {a, b, c}, there is only one isomorphism between {*} and {☺}. This is always the case for universal objects: there is a unique isomorphism between any two terminal (resp. initial) objects in any category.

As a result, we often speak of the initial object in C or the terminal object in C, as though there were only one. “It is unique up to unique isomorphism” is put forward as the justification for using the rather than a. This is not too misleading, because just as a person today does not contain exactly the same atoms as that person yesterday, the difference is unimportant.

This book uses either the definite or the indefinite article, as is convenient, when speaking about initial or terminal objects. For example, Example 6.1.3.4 discussed the initial object in Set and the terminal object in Set. This usage is common throughout mathematical literature.

Proposition 6.1.3.15. Let C be a category, and let a1,a2Ob(C) both be initial objects. Then there is a unique isomorphism f:a1a2. (Similarly, for any two terminal objects in C, there is a unique isomorphism between them.)

Proof. Suppose a1 and a2 are initial. Since a1 is initial, there is a unique morphism f : a1a2; there is also a unique morphism a1a1, which must be ida1. Since a2 is initial, there is a unique morphism g : a2a1; there is also a unique morphism a2a2, which must be ida2. So gf = ida1 and fg = ida2, which means that f is the desired (unique) isomorphism.

The proof for terminal objects is appropriately dual.

6.1.3.16   Examples of limits

We are moving toward defining limits and colimits in full generality. We have assembled most of the pieces we will need: indexing categories, their left and right cones, and the notion of initial and terminal objects. Relying on the now familiar notion of products, we put these pieces in place and motivate one more construction, the slice category over a diagram.

Let C be a category, and let X,YOb(C) be objects. Definition 6.1.1.8 defines a product of X and Y to be a span Xπ1X×Yπ2Y such that for every other span XpZqY, there exists a unique morphism ZX × Y making the triangles commute. It turns out that we can enunciate this in the language of universal objects by saying that the span Xπ1X×Yπ2Y is itself a terminal object in the category of {X, Y} spans. Phrasing the definition of products in this way is generalizable to defining arbitrary limits.

Construction 6.1.3.17 (Products). Let C be a category, and let X1, X2 be objects. We can consider this setup as a diagram X:2¯C, where X(1) = X1 and X(2) = X2. Consider the category 2 = Star2 (see Example 6.1.2.10), the inclusion i : 22 (see (6.4)), and the category of functors Fun(2¯,C ). The objects in Fun(2¯,C ) are spans in C, and the morphisms are natural transformations between them (see Exercise 6.1.2.15).

Given a functor S:2¯C, we can compose with i : 22 to get a functor 2¯C. We want that to be X. That is, to get the product of X1 and X2, we are looking among those S:2¯C for which the following diagram commutes:

art

We are ready to define the category of {X1, X2} spans.

Define the category of X spans in C, denoted C/X, to be the category whose objects and morphisms are as follows:

Ob(C/X)={S:2¯C|Si=X}HomC/X(S,S)={α:SS|αi=idX}.(6.5)

The product of X1 and X2 was defined in Definition 6.1.1.8; we can now recast X1 × X2 as the terminal object in C/X.

An object in C/X can be pictured as a diagram in C of the following form:

X1pZqX2

In other words, the objects of C/X are spans. A morphism in C/X from object X1pZqX2 to object X1 p Z qX2 consists of a morphism : ZZ′, such that p′ ○ = p and q′ ○ = q. So the set of such morphisms in C/X are all the ’s that make both squares commute in the right-hand diagram:

art

Each object in C/X is a span on X1 and X2, and each morphism in C/X is a morphism of cone points in C making everything commute. The terminal object in C/X is the product of X1 and X2 (see Definition 6.1.1.8).

It may be strange to have a category in which the objects are spans in another category. But once one admits this possibility, the notion of morphism between spans becomes totally sensible.

Example 6.1.3.18. Consider the following arbitrary six-object category C, in which the three diagrams that can commute do so:

art

Let X:2¯C be given by X(1) = X1 and X(2) = X2. Then the category of X spans might be drawn

art

6.1.3.19   Definition of limit

A product of two objects X, Y ∈ Ob() is a special case of a limit, namely, one in which the indexing category is 2. To handle arbitrary limits, we replace 2 with an arbitrary indexing category I, and use the following definition to generalize the category of spans, defined in (6.5).

Definition 6.1.3.20. Let C be a category, let I be a category. Let I be the left cone on I, and let i : II be the inclusion. Suppose that X:IC is an I-shaped diagram in C. The slice category of C over X, denoted C/X, is the category whose objects and morphisms are as follows:

Ob(C/X)={S:IC|Si=X}; HomC/X(S,S)={α:SS|αi=idX}.

A limit of X, denoted limI X or lim X, is a terminal object in C/X.

Remark 6.1.3.21. Perhaps the following diagram will be helpful for understanding limits. Given a functor X:IC, what is its limit? The solid-arrow part of the figure is the data we start with, i.e., the category C, the indexing category I, and the diagram X:IC, as well as the part we automatically add, the cone I with the inclusion IiI. The category C/X is found in the dotted arrow part: its objects are the dotted arrows S:IC that make the following triangle commute, and its morphisms are the natural transformations α : SS′x between them:

art

The limit of X is the initial object in this category.

Pullbacks The relevant indexing category for pullbacks is the cospan, I = 2, drawn as on the left:

art

A I-shaped diagram in C is a functor X:IC, which might be drawn as on the right (e.g., X0Ob(C)).

An object S in the slice category C/X is a commutative diagram S : IC over X, which looks like the left-hand box:

art

A morphism in C/X is drawn as in the right-hand box. A terminal object in C/X is precisely the gateway we want, i.e., the limit of X is the pullback X0×X2X1 (see Remark 6.1.1.9).

Remark 6.1.3.22. Let C be a category, and suppose given a functor X:IC. Its limit is a certain functor lim X:IC. The category I looks basically the same as I, except it has an extra cone point LCI mapping to everything in I (see Definition 6.1.2.8). The functor lim X can be applied to this object in I to get an object in C, and it is this object that people often refer to as the limit of X. We call it the limit set of X.

For example, if I = 2 then a functor X:2¯C consists of two objects in C, say X1 and X2. The left cone 2 is the span category, so the limit of X is a span, in particular it is the product span X1X1 × X2X2. But people often speak of the product as if it was just X1 × X2, the cone point of the span.

Exercise 6.1.3.23.

Let GrIn be the graph-indexing category (see (5.8)).

a. What is GrIn?

b. Let G : GrInSet be the graph from Example 4.3.1.2. Give an example of an object in Set/G.

Exercise 6.1.3.24.

Let C be a category, and let I = 0 be the empty category. There is a unique functor X:0¯C.

a. What is the slice category C/X?

b. What is a limit of X?

Solution 6.1.3.24.

a. The left cone of 0 is the terminal category 0 = 1, and since every diagram

art

commutes, we have an isomorphism Fun(1¯,C)C/X. But by (??), we have an isomorphism CFun(1¯,C), so in fact C/XC.

b. A limit of X is defined to be a terminal object in C/X, which is a terminal object in C, if it exists. In other words, terminal objects in a category give us a canonical example of limits. This was hinted at in Exercise 3.2.3.5.

Example 6.1.3.25. In the course of doing math, random-looking diagrams sometimes come up, for which one wants to take the limit. We have now constructed the limit for any shape diagram. For example, if we wanted to take the product of more than two, say, n, objects, we could use the diagram shape I = n. A functor X : nSet is n sets X1, X2, … , Xn, and their limit is a functor lim X : nSet,

art

which, of course, is the product, XLCn¯=X1×X2××Xn.

Example 6.1.3.26. We have now defined limits in any category, so we have defined limits in Cat. Let [1] denote the category depicted

0e1

and let C be an arbitrary category. Naming two categories is the same thing as naming a functor X : 2Cat; consider the functor X(1) = [1], X(2)=C. The limit of X is a product of categories (see Example 6.1.1.17); it is denoted [1]×C. It turns out that [1]×C looks like a C-shaped prism. It consists of two panes, front and back, say, each having the precise shape as C (same objects, same arrows, same composition) as well as morphisms from the front pane to the back pane making all front-to-back squares commute. For example, if C was the category generated by the left-hand schema , then C×[1] would be the category generated by the right-hand schema:

art

It turns out that a natural transformation α : FG between functors F,G:CD is the same thing as a functor C×[1]D such that the front pane is sent via F and the back pane is sent via G. The components are captured by the front-to-back morphisms, and the naturality is captured by the commutativity of the front-to-back squares in C×[1].

Exercise 6.1.3.27.

Recall that Section 3.4.6.5 described relative sets. In fact, Definition 3.4.6.6 basically defines a category of relative sets over any fixed set B. Let B : 1Set be the functor representing the object B ∈ Ob(Set).

a. What is the relationship between the slice category Set/B, as defined in Definition 6.1.3.20, and the category of relative sets over B?

b. What is the limit of the functor B : 1Set?

Theorem 6.1.3.28. Let I be a category and let F : ISet be a functor. Then its limit set limI F ∈ Ob(Set) exists and one can find its elements as follows. An element of the set limI F is given by choosing an element of xiF (i) for each object i ∈ Ob(I) such that, for each f : iione has F(f)(xi) = xi.

Proof. See [29].

Exercise 6.1.3.29.

Let I be the category given by the following schema:

art

Let X : ISet be given on objects by X(a) ≔ 2, X(b) ≔ 1, X(c) ≔ 3, X(d) = 2, and given (in sequence notation) on morphisms by X(f) = (1, 1), X(g) = (1, 1, 1), X(h) = (1, 2, 1). What is the limit limI X.

6.1.3.30   Definition of colimit

The definition of colimits is appropriately dual to the definition of limits. Instead of looking at left cones, we look at right cones; instead of being interested in terminal objects, we are interested in initial objects.

Definition 6.1.3.31. Let C be a category, let I be a category; let I be the right cone on I, and let i : II be the inclusion. Suppose that X:IC is an I-shaped diagram in C. The coslice category of C over X, denoted CX/, is the category whose objects and morphisms are as follows:

Ob(CX/)={S:IC|Si=X};HomCX/(S,S)={α:SS|αi=idX}.

A colimit of X, denoted colimI X or colim X, is an initial object in CX/.

Remark 6.1.3.32. Perhaps the following diagram will be helpful for understanding colimits. Given a functor X:IC, what is its colimit? The solid-arrow part of the figure is the data we start with, i.e., the category C, the indexing category I, and the diagram X:IC, as well as the part we automatically add, the cone I with the inclusion IiI. The category CX/ is found in the dotted arrow part: its objects are the dotted arrows S:IC that make the following triangle commute, and its morphisms are the natural transformations α : SS′ between them:

art

The colimit of X is the initial object in this category.

Pushouts The relevant indexing category for pushouts is the span, I = 2 drawn as on the left:

art

An I-shaped diagram in C is a functor X:IC, which might be drawn as on the right (e.g., X0Ob(C)).

An object S in the coslice category CX/ is a commutative diagram S:IC over X, which looks like the left-hand box:

art

A morphism in CX/ is drawn as in right-hand box. An initial object in CX/ is precisely the gateway we want, i.e., the colimit of X is the pushout, X1X0X2.

Exercise 6.1.3.33.

Let GrIn be the graph-indexing category (see (5.8)).

a. What is GrIn?

b. Let G : GrInSet be the graph from Example 4.3.1.2. Give an example of an object in SetG/.

Exercise 6.1.3.34.

Let C be a category, and let I = 0 be the empty category. There is a unique functor X:0¯C.

a. What is the coslice category CX/?

b. What is a colimit of X (assuming it exists)?

Solution 6.1.3.34.

a. The right cone of 0 is the terminal category 01, and since every diagram

art

commutes, we have an isomorphism Fun(1¯,C)CX/. But by (??), we have an isomorphism CFun(1¯,C), so in fact CCX/.

b. A colimit of X is defined to be an initial object in CX/, which is an initial object in C, if it exists. In other words, initial objects in a category give us a canonical example of colimits. This was hinted at in Exercise 3.3.3.4.

Theorem 6.1.3.35. Let I be a category and let F : ISet be a functor. Then its colimit set colimI F ∈ Ob(Set) exists and one can find its elements as follows. An element of the set colimI F is given by choosing any i ∈ Ob(I) and any element of xiF(i), and then considering two such elements equivalent if there exists f : iisuch that X(f)(xi) = xi.

Proof. See [29].

Exercise 6.1.3.36.

Let I be the category given by the following schema:

art

Let X : ISet be given on objects by X(a) ≔ 2, X(b) ≔ 2, X(c) ≔ 4, X(d) = 3, and given (in sequence notation) on morphisms by X(f) = (1, 2), X(g) = (1, 2, 1), X(h) = (1, 2, 4). What is the colimit colimI X.

Remark 6.1.3.37. Definition 6.1.3.31 defined what it means to be a colimit in any category; however, in any particular category, some colimits may not exist. It is like defining the quotient of any two natural numbers r, s ∈ ℕ by r ÷ s = q if and only if qs=r. We have defined what it means to be a quotient, but that doesn’t mean the quotient of any two numbers exists, e.g. if r = 7 and s = 2.

The same goes for limits. A category C in which every diagram is guaranteed to have a limit is called complete. A category C in which every diagram is guaranteed to have a colimit is called cocomplete.

Example 6.1.3.38 (Cone as colimit). It turns out that Cat is cocomplete, meaning every diagram in C has a colimit. We give an example of a colimit in Cat.

Let C be a category, and recall from Example 6.1.3.26 the category C×[1]. The inclusion of the front pane is a functor i0:CC×[1]. (Similarly, the inclusion of the back pane is a functor i1:CC×[1].) Finally, let t:C1¯ be the unique functor to the terminal category (see Exercise 5.1.2.40). We now have a diagram in Cat of the form

art

The colimit (i.e., the pushout) of this diagram in Cat slurps down the entire front pane of C×[1] to a point, and the resulting category is isomorphic to C. The diagrams in (6.7) illustrate this phenomenon.

art

The category C is shown in the upper left-hand corner of (6.7). The left cone C on C is obtained as a pushout in Cat. We first make a prism C×[1] and then identify the front pane with a point. (Similarly, the pushout of an analogous diagram for i1 would give C.)

Example 6.1.3.39. Consider the category Top of topological spaces. The (unfilled) circle is a topological space, which people often denote by S1 (for one-dimensional sphere). Topologically, it is equivalent to an oval, as shown in Figure 6.1. The filled-in circle, also called a two-dimensional disk, is denoted D2. The inclusion of the circle into the disk, as its boundary, is continuous, so we have a morphism in Top of the form i : S1D2. The terminal object in Top is the one-point space ●, so there is a unique morphism t : S1 → ●.

The pushout of the diagram D2iS1t is isomorphic to the two-dimensional sphere (the exterior of a tennis ball), S2. The reason is that we have slurped the entire bounding circle of D2 to a point, which becomes, say, the south pole, and the interior area of D2 becomes the surface area of the sphere. Mathematically, the category of topological spaces has the right morphisms to ensure that this intuitive picture is correct.

art
Figure 6.1 A pushout of topological spaces. A circle S1 is both included as the boundary of a disk D2 and sent to a single point ●. The resulting pushout is a 2-dimensional sphere S2, formed by sewing the boundary circle of a disk all together into a single point.

Application 6.1.3.40. Consider the symmetric graph Gn consisting of a chain of n vertices,

art

Think of this as modeling a subway line. There are n-many graph homomorphisms G1Gn given by the various vertices. One can create transit maps using colimits. For example, the colimit of the left-hand diagram is the symmetric graph drawn at the right:

art

6.2   Other notions in Cat

This section discusses some additional notions about categories. Section 6.2.1 explains a kind of duality for categories, in which arrows are flipped. Reversing the order in a preorder is an example of this duality, as is the similarity between the definitions of limit and colimit. Section 6.2.2 discusses the Grothendieck construction, which in some sense makes a histogram for a set-valued functor, and shows that this idea is useful for transforming databases into the kind of format (RDF) used in scraping data off web pages. Some ways of creating new categories from old are explained in Sections 6.2.3 and 6.2.4. Finally, Section 6.2.5 shows that precisely the same arithmetic statements that held for sets (see Section 3.4.3) hold for categories.

6.2.1   Opposite categories

In the early days of category theory, and still today, people would sometimes discuss two different kinds of functors between categories: covariant functors and contravariant functors. Covariant functors are what this book calls functors. The reader may have come across the idea of contravariance when considering Exercise 5.2.3.2,9 which showed that a continuous mapping of topological spaces f : XY does not induce a morphism of orders on their open sets Open(X) → Open(Y); that is not required by the notion of continuity. Instead, a morphism of topological spaces f : XY induces a morphism of orders Open(Y) → Open(X), going backward. So we do not have a functor TopPrO in this way, but it is quite close. It used to be said that Open is a contravariant functor TopPrO.

As important and common as contravariance is, one finds that keeping track of which functors were covariant and which were contravariant is a big hassle. Luckily, there is a simple work-around, which simplifies everything: the notion of opposite categories.

Definition 6.2.1.1. Let C be a category. The opposite category of C, denoted Cop, has the same objects as C, i.e., Ob(Cop)=Ob(C), and for any two objects c, c′, one defines

HomCop(c,c)HomC(c,c).

Example 6.2.1.2. If n ∈ ℕ is a natural number and n the corresponding discrete category, then nop = n. Recall the span category I = 2 from Definition 6.1.1.8. Its opposite is the cospan category Iop = 2, from Definition 6.1.1.23.

Exercise 6.2.1.3.

Let C be the category from Example 6.1.3.18. Draw Cop.

Proposition 6.2.1.4. Let C and D be categories. One has (Cop)op=C. Also one has a canonical isomorphism Fun(C,D)Fun(Cop,Dop). This implies that a functor CopD can be identified with a functor CDop.

Proof. This follows straightforwardly from the definitions.

Exercise 6.2.1.5.

If C is a category and cOb(C) is an initial object, does this imply that c is a terminal object in Cop?

Exercise 6.2.1.6.

In Exercises 5.2.3.2, 5.2.4.3, and 5.2.4.4 there were questions about whether a certain function Ob(C)Ob(D) extended to a functor CD.

a. Does the function Open: Ob(Top) → Ob(PrO) extend to a functor Open: TopopPrO?

b. Does the function L : Ob(J) → Ob(Prop) extend to a functor L : JopProp?

c. Does the function R : Ob(J) → Ob(Set) extend to a functor R : JopSet?

Example 6.2.1.7 (Simplicial sets). Recall from Example 5.3.4.4 the category Δ of linear orders [n]. For example, [1] is the linear order 0 ⩽ 1, and [2] is the linear order 0 ⩽ 1 ⩽ 2. Both [1] and [2] are objects of Δ. There are 6 morphisms from [1] to [2], which could be denoted

HomΔ([1],[2])={(0,0),(0,1),(0,2),(1,1),(1,2),(2,2)}.

The category Δop turns out to be quite useful in algebraic topology. It is the indexing category for a combinatorial approach to the homotopy theory of spaces. That is, we can represent something like the category of spaces and continuous maps using the functor category Fun(Δop, Set), which is called the category of simplicial sets.

This may seem very complicated compared to simplicial complexes (see Section 3.4.4.3). But simplicial sets have excellent formal properties that simplicial complexes do not. We do not go further with this here, but through the work of Dan Kan, André Joyal, Jacob Lurie, and many others, simplicial sets have allowed category theory to pierce deeply into the realm of topology, and vice versa.

6.2.2   Grothendieck construction

Let C be a database schema (or category), and let J:CSet be an instance. We have been drawing this in table form, but there is another standard way of laying out the data in J, called the resource descriptive framework, or RDF. Developed for the World Wide Web, RDF is a useful format when one does not have a schema in hand. For example, when scraping information off a website, one does not know which schema will be best. In these cases information is stored in RDF triples, which are of the form

Subject,Predicate,Object.

For example, one might see something like

art

This might be an RDF interpretation of the sentence “On January 14, 2013, Barack Obama told congress to raise the debt ceiling.”

Category-theoretically, it is quite simple to convert a database instance J:CSet into an RDF triple store. To do so, we use the Grothendieck construction, also known as the category of elements.

Definition 6.2.2.1. Let C be a category, and let J:CSet be a functor. The category of elements of J, denoted CJ, is defined as follows:

       Ob(CJ){(C,x)|COb(C),xJ(C)};HomCJ((C,x),(C,x)){f:CC|J(f)(x)=x}.

There is a natural functor πJ:CJC. It sends each object (C,x)Ob(CJ) to the object COb(C). And it sends each morphism f : (C, x) → (C′, x′) to the morphism f : CC′. We call πJ the projection functor.

Example 6.2.2.2. Let A be a set, and consider it as a discrete category. We saw in Exercise 5.3.3.4 that a functor S : ASet is the same thing as an A-indexed set, as discussed in Section 3.4.6.9. We follow Definition 3.4.6.11 and, for each aA, write SaS(a).

What is the category of elements of a functor S : ASet? The objects of ∫A S are pairs (a, s), where aA and sS(a). Since A has nothing but identity morphisms, ∫A S has nothing but identity morphisms, i.e., it is the discrete category on a set. In fact, that set is the disjoint union

AS=aASa.

The functor πS: ∫A SA sends each element in Sa to the element aA.

One can see this as a kind of histogram. For example, let A = {BOS, NYC, LA, DC}, and let S : ASet assign

SBOS={Abby, Bob, Casandra},SNYC=,SLA={John, Jim},SDC={Abby, Carla}.

Then the category of elements of S would look like the (discrete) category at the top:

art

We also see that the category of elements construction has converted an A-indexed set into a relative set over A, as in Definition 3.4.6.6.

The preceding example does not show how the Grothendieck construction transforms a database instance into an RDF triple store. The reason is that the database schema was A, a discrete category that specifies no connections between data (it simply collects the data into bins). So let’s examine a more interesting database schema and instance. This is taken from Spivak [39].

Application 6.2.2.3. Consider the following schema, first encountered in Example 4.5.2.1:

art

And consider the instance J:CSet, which we first encountered in (4.12) and (4.14):

art

The category of elements of J:CSet looks like this:

art

In Diagram (6.11) of CJ, ten arrows were omitted for ease of readability, for example, arrow 102 first Bertrand was omitted.

How do we see the category of elements CJ as an RDF triple store? For each arrow in CJ, we take the triple consisting of the source vertex, the arrow name, and the target vertex. So the triple store would include triples such as 〈101 worksIn q10〉 and 〈q10 name Production〉. Note that if C were an olog, we could read off these triples (and concatenations of them) as English sentences. For example, the preceding two triples could be Englished as follows:

Employee 101 works in Department q10, which has as name Production.

Exercise 6.2.2.4.

Devise a schema C for which you can imagine an instance I:CSet such that the category of elements ∫(I) is the triple store in (6.8).

Slogan 6.2.2.5.

The Grothendieck construction takes structured, tabulated data and flattens it by throwing it all into one big space. The projection functor is then tasked with remembering which box each datum originally came from.

Exercise 6.2.2.6.

Recall from Section 4.1.2.10 that a finite state machine is a free monoid (List(Σ), [ ], ++) acting on a set X. Recall also that we can consider a monoid as a category M with one object, and we can consider a monoid action as a set-valued functor F: MSet (see Section 5.2.1.1). In the case of Figure 4.2 the monoid is List(a, b), which can be drawn as the schema

art

and the functor F:MSet is recorded in an action table in Example 4.1.3.1. What is MF? How does it relate to Figure 4.2?

6.2.3   Full subcategory

Definition 6.2.3.1. Let C be a category, and let XOb(C) be a set of objects in C. The full subcategory of C spanned by X is the category, denoted COb=X, with objects Ob(COb=X)X and with morphisms HOMCOb=X(x,x)HOMC(x,x).

Example 6.2.3.2. The following are examples of full subcategories. For example, the category Fin of finite sets is the full subcategory of Set spanned by the finite sets.

  • If X = {s ∈ Ob(Set) | s is finite}, then Fin = SetOb=X.
  • If X = {P ∈ Ob(PrO) | P is a finite linear order)}, then FLin = PrOOb=X.
  • If X = {[n] ∈ FLin | n ∈ ℕ} (see Example 5.3.4.4), then Δ = FLinOb=X.
  • If X = {M ∈ Ob(Mon) | M is a group}, then Grp = MonOb=X.
  • If X={COb(Cat)|C has one object}, then Mon = CatOb=X.
  • If X = {n ∈ Ob(Fin) | n ∈ ℕ}, then there is an equivalence of categories FinFinOb=X.
  • If X = {(V, A, src, tgt) ∈ Ob(Grph) | A = ∅}, then SetGrphOb=X.
  • If X={CCat|C is discrete}, then SetCatOb=X.

Remark 6.2.3.3. A subcategory CD is (up to isomorphism) just a functor i:CD that happens to be injective on objects and arrows. The subcategory is full if and only if i is a full functor in the sense of Definition 5.3.4.8.

Example 6.2.3.4. Let C be a category, let XOb(C) be a set of objects, and let COb=X denote the full subcategory of C spanned by X. We can realize this as a fiber product of categories. Indeed, recall that for any set, we can form the indiscrete category on that set (see Example 5.3.4.3). In fact, we have a functor Ind: SetCat. Thus the function XOb(C) can be converted into a functor between indiscrete categories Ind(X)Ind(Ob(C)). There is also a unique functor CInd(Ob(C)) sending each object to itself. Then the full subcategory of C spanned by X is the fiber product of categories,

art

Exercise 6.2.3.5.

Recall the sets 0, 1, 2 ∈ Ob(Set) from Notation 2.1.2.21. Including all identities and all compositions, how many morphisms are there in the full subcategory SetOb={0,1,2}?

6.2.4   Comma categories

Category theory includes a highly developed and interoperable catalogue of materials (categories such as [n], GrIn, PrO, etc.) and production techniques for making new categories from old. One such was the full subcategory idea in the previous section—given any category and any subset of objects, one can form a new category to restrict attention to the subset. Another is the comma category construction.

Definition 6.2.4.1. Let AFCGB be a cospan of categories. The comma category of C morphisms from F to G, denoted (FCG) or simply (FG), is the category with objects

Ob(FG)={(a,b,f)|aOb(A),bOb(B),f:F(a)G(b) in C},

and for any two objects (a, b, f) and (a′, b′, f′) the set Hom(FG) ((a, b, f), (a′, b′, f′)) of morphisms (a, b, f) → (a′, b′, f′) is

{(q,r)|q:aa in A, r:bb in B, such that fF(q)=G(r)f}.

In diagram form,

art

There is a canonical functor (FG)A, called left projecton, sending (a, b, f) to a, and a canonical functor (FG)B, called right projection, sending (a, b, f) to b.

A cospan AFCGB is reversible, i.e., we can flip it to obtain BGCFA. However, note that (FG) is different than (i.e., almost never equivalent to) (GF).

Slogan 6.2.4.2.

When two categories A, ℬ can be interpreted in a common setting C, the comma category integrates them by recording how to move from A to B inside C.

Example 6.2.4.3. Let C be a category and I:CSet a functor. This example shows that the comma category construction captures the notion of taking the category of elements CI (see Definition 6.2.2.1).

Consider the set 1, the category Disc(1), and the functor F : Disc(1) → Set sending the unique object to the set 1. We use the cospan Disc(1¯)FSetIC. There is an isomorphism of categories

CI(FI).

Indeed, an object in (FI) is a triple (a, b, f), where a ∈ Ob(Disc(1)), bOb(C), and f : F(a) → I(b) is a morphism in Set. There is only one object in Disc(1), so this reduces to a pair (b, f), where bOb(C) and f : {☺} → I(b). The set of functions {☺} → I(b) is isomorphic to I(b) (see Exercise 2.1.2.20). So we have reduced Ob(FI) to the set of pairs (b, x), where bOb(C) and xI(b); this is Ob(CI). Because there is only one function 11, a morphism (b, x) → (b′, x′) in (FI) boils down to a morphism r : bb′ such that the diagram

art

commutes. But such diagrams are in one-to-one correspondence with the diagrams defining morphisms in CI.

Exercise 6.2.4.4.

Let C be a category, and let c,cOb(C) be objects represented by the functors c,c:1¯C. Consider the cospan 1¯cCc1¯. What is the comma category (cc′)?

Exercise 6.2.4.5.

Let C and D be categories, and let !:C1¯ and !:D!¯ be the unique functors to the terminal category. What is the comma category for C!1¯!D?

Exercise 6.2.4.6.

Let C be a category.

a. If cC is an initial object, what is the comma category for the cospan 1¯cCidCC?

b. If dC is a terminal object, what is the comma category for the cospan CidCCdC?

6.2.5   Arithmetic of categories

Section 3.4.3 summarized some of the properties of products, coproducts, and exponentials for sets, showing that they lined up precisely with familiar arithmetic properties of natural numbers. We can do the same for categories.

In the following proposition, we denote the coproduct of two categories A and B by the notation A+B rather than AB. We also denote the functor category Fun(A,B) by BA. Finally, we use 0 and 1 to refer to the discrete category on 0 objects and on 1 object respectively.

Proposition 6.2.5.1. The following isomorphisms exist for any small categories A,B,and C.

  • A+0¯A.
  • A+BB+A.
  • (A+B)+CA+(B+C).
  • A×0¯0¯.
  • A×1¯A.
  • A×BB×A.
  • (A×B)×CA×(B×C).
  • A×(B+C)(A×B)+(A×C).
  • A0¯1¯.
  • A1¯A.
  • 0¯A0¯, if A0¯.
  • 1¯A1¯.
  • AB+CAB×AC.
  • (AB)CAB×C.
  • (A×B)CAC×BC.

Proof. These are standard results; see Mac Lane [29].

__________________

1Given R1X1 × X1, R2X2 × X2, take R1 × R2 ⊆ (X1 × X2) × (X1 × X2).

2The result is not necessarily inspiring, but at least computing it is straightforward.

3The names X × Y and π1, π2 are not mathematically important; they are pedagogically useful.

4Note that (0, 0) is not related to anything else.

5Given R1X1 × X1, R2X2 × X2, take

R1R2(X1×X1)(X2×X2)(X1×X1)(X2×X2)(X2×X1)(X2×X2)(X1X1)×(X1X2).

6The names XY and ı1, ı2 are not mathematically important; they are pedagogically useful.

7The indexing category I is usually assumed to be small in the sense of Remark 5.1.1.2, meaning that its collection of objects is a set.

8What is here denoted F (G) might be called the noncommutative square indexing category.

9Similarly, see Exercise 5.2.4.4.