Sunday, January 12, 2014

Categorical Limits and Colimits

Many types of universal constructions that appear in a wide variety of mathematical contexts can be realized as categorical limits and colimits. To define a limit we first need the notion of a cone of a diagram. A diagram of type $J$ in a category $\mathcal C$ is a simply a functor $F \colon J \to \mathcal C$. We imagine $J$ as an indexing for the objects and morphisms in $\mathcal C$ under consideration. When $J$ is a finite category it can be visualized as a directed graph.

A cone of $F$ is a pair $(N, \Psi)$ where $N$ is an object of $\mathcal C$ and $\Psi$ is a collection of $\mathcal C$-morphisms $\Psi_X \colon N \to F(X) $ (one for each object $X$ in $J$) such that $\Psi_Y = F(f) \circ \Psi_X$ for every $J$-morphism $f \colon X \to Y$. Given two cones $(N, \Psi)$ and $(M, \Phi)$ we call a $\mathcal C$-morphism $u \colon N \to M$ a cone morphism from $(N, \Psi)$ to $(M, \Phi)$ provided that $u$ respects the cone property, which is to say that for every object $X$ in $J$ the morphism $\Psi_X$ factors through $u$, i.e., $\Psi_X = \Phi_X \circ u$. We will write $u \colon (N, \Psi) \to (M, \Phi)$ to denote that $u$ is a cone morphism.
A limit cone of the diagram $F$ is a cone $(L, \Phi)$ of $F$ such that for every other cone $(N, \Psi)$ of $F$ there exists a unique cone morphism $u \colon (N, \Psi) \to (L, \Phi)$. In this sense a limit $L$ is a universal cone. A co-cone and colimit are the corresponding dual notions, so in particular a co-cone is a cone of a diagram of type $J$ in the opposite category $\mathcal C^{op}$.

One observation to make is that a limit of $F$ is unique up to canonical cone isomorphism. For this reason we typically speak of \emph{the} limit of $F$. What this means is that if $(L, \Phi)$ and $(L', \Phi')$ are limits of $F$, then there exists a unique cone isomorphism between them. To see this, first note that the identity morphism $\text{id}_L \colon L \to L$ is actually a cone morphism $\text{id}_L \colon (L, \Phi) \to (L, \Phi)$. By the uniqueness property of limits, this is the only such cone morphism. Moreover, since $L$ and $L'$ are both limits, there exist unique cone morphisms $u \colon (L', \Phi') \to (L, \Phi)$ and $u' \colon (L, \Phi) \to (L', \Phi')$. If we can show that $u \circ u' \colon L \to L$ and $u' \circ u \colon L' \to L'$ are cone morphisms, then it must follow that $u \circ u' = \text{id}_L$ and $u' \circ u = \text{id}_{L'}$, which proves that $u$ is in fact a unique cone isomorphism. To this end, observe that for any object $X$ in $J$ it follows that $\Phi'_X = \Phi_X \circ u$ and $\Phi_X = \Phi'_X \circ u'$, so $\Phi_X = \Phi'_X \circ u'= (\Phi_X \circ u) \circ u' = \Phi_X \circ (u \circ u')$ and similarly $\Phi'_X = \Phi'_X \circ (u' \circ u)$. So $u \circ u'$ and $u' \circ u$ are cone morphisms, as desired.

The product and co-product of objects in a category $\mathcal C$ are special cases of limits and co-limits. When $J$ consists precisely of two distinct objects $X$ and $Y$ with no non-identity morphisms, and $F \colon J \to \mathcal C$ is a functor, the product of $F(X)$ and $F(Y)$ is the limit $(F(X) \times F(Y), \pi)$ of $F$ and the co-product of these two objects is the co-limit $(F(X) \amalg F(Y), \iota)$.

For a specific example products and co-products consider the category $\mathcal C$ of sets and let $J$ be as above. If $F \colon J \to \mathcal C$ is any diagram, we claim that the Cartesian product $F(X) \times F(Y)$ together with the projection maps is the limit of $F$. To see this, first set $A:=F(X)$ and $B:=F(Y)$ and let $\pi_A$ and $\pi_B$ denote the respective projections from $A \times B$. We must show that if $N$ is any other set with maps $f \colon N \to A$ and $g \colon N \to B$, then there exists a unique map $u \colon N \to A \times B$ such that $f = \pi_A \circ u$ and $g = \pi_B \circ u$. First, the map $f \times g \colon N \to A \times B$ taking an element $x \in N$ to the tuple $(f(x), g(x))$ clearly satisfies $\pi_A \circ (f \times g) = f$ and $\pi_B \circ (f \times g) = g$, so $f \times g$ is a cone morphism. Now suppose $u \colon (N, \{ f, g \}) \to (A \times B, \pi)$ is a cone morphism. Then $\pi_A \circ u = f$ and $\pi_B \circ u = g$. If $u(x)=(a,b)$ for an element $x \in N$, then $a = (\pi_A \circ u) (x)= f(x)$ and $b = (\pi_B \circ u) (x) = g(x)$, so $uh(x)= f \times g (x)$. This proves that $u = f \times g$, so $f \times g$ is the unique cone morphism from $N$ to $A \times B$.

Next we claim that the disjoint union $A \amalg B$ together with the injections $\iota_A \colon A \to A \amalg B$ and $\iota_B \colon B \to A \amalg B$ is the co-product of $A$ and $B$. To see this, we must show that if $N$ is any other set and there are maps $f \colon A \to N$ and $g \colon B \to N$, then $f$ factors uniquely through $\iota_A$ and $g$ factors uniquely through $\iota_B$. More specifically this means we must show there is a unique map $u \colon A \amalg B \to N$ such that $f = u \circ \iota_A$ and $g = u \circ \iota_B$. Define a map $f \amalg g \colon A \amalg B \to N$ by $(f \amalg g) (x) = f(x)$ if $x \in A$ and $(f \amalg g) (x) = g(x)$ if $x \in B$. If $u \colon (A \amalg B, \iota) \to (N, \{ f, g \} )$ is a cone morphism, then $f(a) = (u \circ \iota_A) (a)$ for all $a \in A$ and $g(b) = (u \circ \iota_B) (b)$ for all $b \in B$. So in particular, if $a \in A$ (viewed as a subset of $A \amalg B$) we have $u(a) = f(a) = (f \amalg g) (a)$ and if $b \in B$ (viewed as a subset of $A \amalg B$) then $u(b) = g(b) = (f \amalg g) (b)$, so $u = f \amalg g$. This proves that $f \amalg g$ is a unique cone morphism, as desired.