3.5: Bonus- An introduction to limits and colimits

What do products of sets, the results of Π -operations on database instances, and meets ! in a preorder all have in common? The answer, as we shall see, is that they are all examples of limits. Similarly, disjoint unions of sets, the results of Σ -operations on ! database instances, and joins in a preorder are all colimits. Let’s begin with limits. Recall that Π! takes a database instance I: C → Set and turns it into a set Π!(I).

More generally, a limit turns a functor F : C → D into an object of D.

Terminal objects and products

Terminal objects and products are each a sort of limit. Let’s discuss them in turn.

Terminal objects. The most basic limit is a terminal object.

Definition: 3.79.

Let C be a category. Then an object Z in C is a terminal object if, for each object C of C, there exists a unique morphism !: C → Z.

Since this unique morphism exists for all objects in C, we say that terminal objects have a universal property.

Example 3.80.

In Set, any set with exactly one element is a terminal object. Why? Consider some such set {•}. Then for any other set C we need to check that there is exactly one function !: C → {•}. This unique function is the one that does the only thing that can be done: it maps each element c \(\in\) C to the element • \(\in\) {•}.

Exercise 3.81.

Let (P, ≤) be a preorder, let z \(\in\) P be an element, and let P be the corresponding category (see Section 3.2.3). Show that z is a terminal object in P if and only if it is a top element in P: that is, if and only if for all c \(\in\) P we have c ≤ z. ♦

Exercise 3.82.

Name a terminal object in the category Cat. (Hint: recall Exercise 3.76.) ♦

Exercise \(\PageIndex{1}\)

Not every category has a terminal object. Find one that doesn’t. ♦

Proposition 3.84.

All terminal objects in a category C are isomorphic.

Proof. This is a simple, but powerful standard argument. Suppose Z and Z′ are both terminal objects in some category C. Then there exist (unique) maps a : Z → Z′ and b : Z′ → Z. Composing these, we get a map a ; b : Z → Z. Now since Z is terminal, this map Z → Z must be unique. But \(id_{Z}\) is also such a map. So we must have a ; b = \(id_{Z}\). Similarly, we find that b ; a = \(id_{Z'}\). Thus a is an isomorphism, with inverse b. □

Remark 3.85 (“The limit” vs. “a limit”). Not only are all terminal objects isomorphic, there is a unique isomorphism between any two. We hence say “terminal objects are unique up to unique isomorphism.” To a category theorist, this is very nearly the same thing as saying “all terminal objects are equal.” Thus we often abuse terminology and talk of ‘the’ terminal object, rather than “a” terminal object. We will do the same for any sort of limit or colimit, e.g. speak of “the product” of two sets, rather than “a product.” We saw a similar phenomenon in Definition 1.81.

Products. Products are slightly more complicated to formalize than terminal objects, but they are familiar in practice.

Definition: 3.86.

Let C be a category, and let X, Y be objects in C. A product of X and Y is an object, denoted X × Y, together with morphisms \(p_{X}\) : X × Y → X and \(p_{Y}\) : X × Y → Y such that for all objects C together with morphisms f : C → X and g : C → Y, there exists a unique morphism C → X × Y, denoted ⟨f , g⟩, for which the following diagram commutes:

We will try to bring this down to earth in Example 3.87. Before we do, note that X × Y is an object equipped with morphisms to X and Y. Roughly speaking, it is like “the best object-equipped with morphisms to X and Y” in all of C, in the sense that any other object-equipped with morphisms to X and Y maps to it uniquely. This is called a universal property. It’s customary to use a dotted line to indicate the unique morphism that exists because of some universal property.

Example 3.87.

In Set, a product of two sets X and Y is their usual cartesian product

X × Y := {(x, y) | x \(\in\) X, y \(\in\) Y},

which comes with two projections pX : X × Y → X and pY : X × Y → Y, given by \(_{pX}\)(x, y) := x and \(_{pY}\)(x, y) := y.

Given any set C with functions f : C → X and g :C → Y, the unique map from C to X × Y such that the required diagram commutes is given by

⟨f ,g⟩(c) := (f (c), g(c)).

Here is a picture of the product \(\underline{6}\) × \(\underline{4}\) of sets \(\underline{6}\) and \(\underline{4}\).

Exercise 3.88.

Let (P, ≤) be a preorder, let x, y \(\in\) P be elements, and let P be the corresponding category. Show that the product x × y in P agrees with their meet x \(\wedge\) y in P. ♦

Example 3.89.

Given two categories C and D, their product C × D may be given as follows. The objects of this category are pairs (c, d), where c is an object of C and d is an object of D. Similarly, morphisms (c, d) → (c′, d′) are pairs (f , g) where f : c → c′ is a morphism in C and g : d → d′ is a morphism in D. Composition of morphisms is simply given by composing each entry in the pair separately, so (f,g) ; (f′,g′) = (f ; f′,g' ; g′).

Exercise 3.90.

1. What are the identity morphisms in a product category C × D?
2. Why is composition in a product category associative?
3. What is the product category 1 × 2?
4. What is the product category P × Q when P and Q are preorders and P and Q are the corresponding categories? ♦

These two constructions, terminal objects and products, are subsumed by the notion of limit.

Limits

We’ll get a little abstract. Consider the definition of product. This says that given any pair of maps \(X \leftarrow C \stackrel{g}{\rightarrow} Y\), there exists a unique map C → X × Y such that certain diagrams commute. This has the flavor of being terminal—there is a unique map to X × Y—but it seems a bit more complicated. How are the two ideas related?

It turns out that products are terminal objects, but of a different category, which we’ll call Cone(X, Y), the category of cones over X and Y in C. We will see in Exercise 3.91 that \(X \stackrel{p_{X}}{\longleftarrow} X \times Y \stackrel{p_{Y}}{\longrightarrow} Y\) is a terminal object in Cone(X, Y). An object of Cone(X, Y) is simply a pair of maps \(X \stackrel{f}{\longleftarrow} X \times Y \stackrel{g}{\longrightarrow} Y\). A morphism from \(X \stackrel{f}{\longleftarrow} X \times Y \stackrel{g}{\longrightarrow} Y\) to \(X \stackrel{f'}{\longleftarrow} X \times Y \stackrel{g'}{\longrightarrow} Y\) in Cone(X,Y)isamorphisma:C→C inCsuchthat the following diagram commutes:

Exercise 3.91.

Check that a product \(X \stackrel{p_{X}}{\longleftarrow} X \times Y \stackrel{p_{Y}}{\longrightarrow} Y\) is exaclty the same as a terminal object in Cone(X,Y). ♦

We’re now ready for the abstract definition. Don’t worry if the details are unclear; the main point is that it is possible to unify terminal objects, maximal elements, and meets, products of sets, preorders, and categories, and many other familiar friends under the scope of a single definition. In fact, they’re all just terminal objects in different categories. Recall from Definition 3.51 that formally speaking, a diagram in C is just a functor D : J → C. Here J is called the indexing category of the diagram D.

Definition: 3.92.

Let D : J → C be a diagram. A cone (C, c∗) over D consists of

(i) an object C \(\in\) C;

(ii) for each object j \(\in\) J, a morphism \(c_{j}\) : C → D(j).

To be a cone, these must satisfy the following property:

(a) for each f : j → k in J, we have \(c_{k}\) = \(c_{j}\); D(f).

A morphism of cones (C, c∗) → (C′, c∗′) is a morphism a : C → C′ in C such that for all j \(\in\) J we have \(c_{j}\) = a ; \(c'_{j}\). Cones over D, and their morphisms, form a category Cone(D). The limit of D, denoted lim(D), is the terminal object in the category Cone(D). Say it is the cone lim(D) = (C, c∗); we refer to C as the limit object and the map \(c_{j}\) for any j \(\in\) J as the \(j^{th}\) projection map.

For visualization purposes, if J is the free category on the graph

with five objects and five non-identity morphisms, then we may draw a diagram D : J → C inside C as on the left below, and a cone on it as on the right:

Here, any two parallel paths that start at C are considered the same. Note that both these diagrams depict a collection of objects and morphisms inside the category C.

Example 3.93.

Terminal objects are limits where the indexing category is empty, J = Ø.

Example \(\PageIndex{1}\)

Products are limits where the indexing category consists of two objects v,w and no arrows,

Finite limits in Set

Recall that this discussion was inspired by wanting to understand Π-operations, and in particular Π!. We can now see that a database instance I : C → Set is a diagram in Set. The functor Π! takes the limit of this diagram. In this subsection we give a formula describing the result. This captures all finite limits in Set.

In database theory, we work with categories C that are presented by a finite graph plus equations. We won’t explain the details, but it’s in fact enough just to work with the graph part: as far as limits are concerned, the equations in C don’t matter. For consistency with the rest of this section, let’s denote the database schema by J instead of C.

Theorm 3.95.

Let J be a category presented by the finite graph (V, A , s, t) together with some equations, and let D: J → Set be a set-valued functor. Write V = {v1,...,vn}. The set

\(\begin{aligned} &\lim _{g} D:=\left\{\left(d_{1}, \ldots, d_{n}\right) \mid d_{i} \in D\left(v_{i}\right) \text { for all } 1 \leq i \leq n\right. \text { and }\\
&\text { for all } a: v_{i} \rightarrow v_{j} \in A, \text { we have } \left.D(a)\left(d_{i}\right)=d_{j}\right\}
\end{aligned}\)

together with the projection maps \(p_{i}\) : (\(lim_{J}\) D) → D(vi) given by \(p_{i}\)(d1, . . . , dn) := di, is a limit of D.

Example 3.96.

If J is the empty graph \(\square\), then n = 0: there are no vertices. There is ex- actly one empty tuple ( ), which vacuously satisfies the properties, so we’ve constructed the limit as the singleton set {( )} consisting of just the empty tuple. Thus the limit of the empty diagram, i.e. the terminal object in Set is the singleton set. See Remark 3.85.

Exercise 3.97.

Show that the limit formula in Theorem 3.95 works for products. See Example 3.94. ♦

Exercise 3.98.

If D: 1 → Set is a functor, what is the limit of D? Compute it using Theorem 3.95, and check your answer against Definition 3.92. ♦

Pullbacks. In particular, the condition that the limit of D : J → Set selects tuples (d1,...,dn) such that D(a)(\(d_{i}\)) = dj for each morphism a: i → j in J allows us to use limits to select data that satisfies certain equations or constraints. This is what allows us to express queries in terms of limits. Here is an example.

Example 3.99.

If J is presented by the cospan graph \(\stackrel{x}{\bullet} \stackrel{f}{\longrightarrow} \stackrel{a}{\bullet} \stackrel{g}{\longleftarrow} y\), then its limit is known as a pullback. Given the diagram \(X \stackrel{f}{\rightarrow} A \stackrel{g}{\leftarrow} Y\), the pull back is the cone shown on the left below:

The fact that the diagram commutes means that the diagonal arrow ca is in some sense superfluous, so one generally denotes pullbacks by dropping the diagonal arrow, naming the cone point X ×\(_{A}\) Y, and adding the \(\text { I }\) symbol, as shown to the right above. Here is a picture to help us unpack the definition in Set. We take X = \(\underline{6}\), Y = \(\underline{4}\), and A to be the set of colors {red, blue, black}.

The functions f : \(\underline{6}\) → A and g : \(\underline{4}\) → A are expressed in the coloring of the dots: for example, g(2) = g(4) = red, while f (5) = black. The pullback selects pairs (i, j) \(\in\) \(\underline{6}\) × \(\underline{4}\) such that f (i) and g(j) have the same color.

Remark 3.100. As mentioned following Definition 3.68, this definition of pullback is not to be confused with the pullback of a set-valued functor along a functor; they are for now best thought of as different concepts which accidentally have the same name. Due to the power of the primordial ooze, however, the pullback along a functor is a special case of pullback as the limit of a cospan: it can be understood as the pullback of a certain cospan in Cat. To unpack this, however, requires the notions of category of elements and discrete opfibration; ask your friendly neighborhood category theorist.

brief note on colimits

Just like upper bounds have a dual concept—namely that of lower bounds—so limits have a dual concept: colimits. To expose the reader to this concept, we provide a succinct definition of these using opposite categories and opposite functors. The point, however, is just exposure; we will return to explore colimits in detail in Chapter 6.

Exercise 3.101.

Recall from Example 3.27 that every category C has an opposite Cop. Let F : C → D be a functor. How should we define its opposite, F \(^{op}\) : C\(^{op}\) → D\(^{op}\)? That is, how should F \(^{op}\) act on objects, and how should it act on morphisms? ♦

Definition: 3.102.

Given a category C we say that a cocone in C is a cone in C\(^{op}\). Given a diagram D: J → C, we may take the limit of the functor D\(^{op}\): J\(^{op}\) → C\(^{op}\).

This is a cone in C\(^{op}\), and so by definition a cocone in C. The colimit of D is this cocone.

Definition 3.102 is like a compressed file: useful for transmitting quickly, but com- pletely useless for working with, unless you can successfully unpack it. We will unpack it later in Chapter 6 when we discuss electric circuits.