4.19 Filtered colimits
Colimits are easier to compute or describe when they are over a filtered diagram. Here is the definition.
Definition 4.19.1. We say that a diagram $M : \mathcal{I} \to \mathcal{C}$ is directed, or filtered if the following conditions hold:
the category $\mathcal{I}$ has at least one object,
for every pair of objects $x, y$ of $\mathcal{I}$ there exist an object $z$ and morphisms $x \to z$, $y \to z$, and
for every pair of objects $x, y$ of $\mathcal{I}$ and every pair of morphisms $a, b : x \to y$ of $\mathcal{I}$ there exists a morphism $c : y \to z$ of $\mathcal{I}$ such that $M(c \circ a) = M(c \circ b)$ as morphisms in $\mathcal{C}$.
We say that an index category $\mathcal{I}$ is directed, or filtered if $\text{id} : \mathcal{I} \to \mathcal{I}$ is filtered (in other words you erase the $M$ in part (3) above).
We observe that any diagram with filtered index category is filtered, and this is how filtered colimits usually come about. In fact, if $M : \mathcal{I} \to \mathcal{C}$ is a filtered diagram, then we can factor $M$ as $\mathcal{I} \to \mathcal{I}' \to \mathcal{C}$ where $\mathcal{I}'$ is a filtered index category1 such that $\mathop{\mathrm{colim}}\nolimits _\mathcal {I} M$ exists if and only if $\mathop{\mathrm{colim}}\nolimits _{\mathcal{I}'} M'$ exists in which case the colimits are canonically isomorphic.
Suppose that $M : \mathcal{I} \to \textit{Sets}$ is a filtered diagram. In this case we may describe the equivalence relation in the formula
\[ \mathop{\mathrm{colim}}\nolimits _\mathcal {I} M = (\coprod \nolimits _{i\in I} M_ i)/\sim \]
simply as follows
\[ m_ i \sim m_{i'} \Leftrightarrow \exists i'', \phi : i \to i'', \phi ': i' \to i'', M(\phi )(m_ i) = M(\phi ')(m_{i'}). \]
In other words, two elements are equal in the colimit if and only if they “eventually become equal”.
Lemma 4.19.2. Let $\mathcal{I}$ and $\mathcal{J}$ be index categories. Assume that $\mathcal{I}$ is filtered and $\mathcal{J}$ is finite. Let $M : \mathcal{I} \times \mathcal{J} \to \textit{Sets}$, $(i, j) \mapsto M_{i, j}$ be a diagram of diagrams of sets. In this case
\[ \mathop{\mathrm{colim}}\nolimits _ i \mathop{\mathrm{lim}}\nolimits _ j M_{i, j} = \mathop{\mathrm{lim}}\nolimits _ j \mathop{\mathrm{colim}}\nolimits _ i M_{i, j}. \]
In particular, colimits over $\mathcal{I}$ commute with finite products, fibre products, and equalizers of sets.
Proof.
Omitted. In fact, it is a fun exercise to prove that a category is filtered if and only if colimits over the category commute with finite limits (into the category of sets).
$\square$
We give a counter example to the lemma in the case where $\mathcal{J}$ is infinite. Namely, let $\mathcal{I}$ consist of $\mathbf{N} = \{ 1, 2, 3, \ldots \} $ with a unique morphism $i \to i'$ whenever $i \leq i'$. Let $\mathcal{J}$ be the discrete category $\mathbf{N} = \{ 1, 2, 3, \ldots \} $ (only morphisms are identities). Let $M_{i, j} = \{ 1, 2, \ldots , i\} $ with obvious inclusion maps $M_{i, j} \to M_{i', j}$ when $i \leq i'$. In this case $\mathop{\mathrm{colim}}\nolimits _ i M_{i, j} = \mathbf{N}$ and hence
\[ \mathop{\mathrm{lim}}\nolimits _ j \mathop{\mathrm{colim}}\nolimits _ i M_{i, j} = \prod \nolimits _ j \mathbf{N} = \mathbf{N}^\mathbf {N} \]
On the other hand $\mathop{\mathrm{lim}}\nolimits _ j M_{i, j} = \prod \nolimits _ j M_{i, j}$ and hence
\[ \mathop{\mathrm{colim}}\nolimits _ i \mathop{\mathrm{lim}}\nolimits _ j M_{i, j} = \bigcup \nolimits _ i \{ 1, 2, \ldots , i\} ^{\mathbf{N}} \]
which is smaller than the other limit.
Lemma 4.19.3. Let $\mathcal{I}$ be a category. Let $\mathcal{J}$ be a full subcategory. Assume that $\mathcal{I}$ is filtered. Assume also that for any object $i$ of $\mathcal{I}$, there exists a morphism $i \to j$ to some object $j$ of $\mathcal{J}$. Then $\mathcal{J}$ is filtered and cofinal in $\mathcal{I}$.
Proof.
Omitted. Pleasant exercise of the notions involved.
$\square$
It turns out we sometimes need a more finegrained control over the possible conditions one can impose on index categories. Thus we add some lemmas on the possible things one can require.
Lemma 4.19.4. Let $\mathcal{I}$ be an index category, i.e., a category. Assume that for every pair of objects $x, y$ of $\mathcal{I}$ there exist an object $z$ and morphisms $x \to z$ and $y \to z$. Then
If $M$ and $N$ are diagrams of sets over $\mathcal{I}$, then $\mathop{\mathrm{colim}}\nolimits (M_ i \times N_ i) \to \mathop{\mathrm{colim}}\nolimits M_ i \times \mathop{\mathrm{colim}}\nolimits N_ i$ is surjective,
in general colimits of diagrams of sets over $\mathcal{I}$ do not commute with finite nonempty products.
Proof.
Proof of (1). Let $(\overline{m}, \overline{n})$ be an element of $\mathop{\mathrm{colim}}\nolimits M_ i \times \mathop{\mathrm{colim}}\nolimits N_ i$. Then we can find $m \in M_ x$ and $n \in N_ y$ for some $x, y \in \mathop{\mathrm{Ob}}\nolimits (\mathcal{I})$ such that $m$ maps to $\overline{m}$ and $n$ maps to $\overline{n}$. See Section 4.15. Choose $a : x \to z$ and $b : y \to z$ in $\mathcal{I}$. Then $(M(a)(m), N(b)(n))$ is an element of $(M \times N)_ z$ whose image in $\mathop{\mathrm{colim}}\nolimits (M_ i \times N_ i)$ maps to $(\overline{m}, \overline{n})$ as desired.
Proof of (2). Let $G$ be a non-trivial group and let $\mathcal{I}$ be the one-object category with endomorphism monoid $G$. Then $\mathcal{I}$ trivially satisfies the condition stated in the lemma. Now let $G$ act on itself by translation and view the $G$-set $G$ as a set-valued $\mathcal{I}$-diagram. Then
\[ \mathop{\mathrm{colim}}\nolimits _\mathcal {I} G \times \mathop{\mathrm{colim}}\nolimits _\mathcal {I} G \cong G/G \times G/G \]
is not isomorphic to
\[ \mathop{\mathrm{colim}}\nolimits _\mathcal {I} (G \times G) \cong (G \times G)/G \]
This example indicates that you cannot just drop the additional condition Lemma 4.19.2 even if you only care about finite products.
$\square$
Lemma 4.19.5. Let $\mathcal{I}$ be an index category, i.e., a category. Assume that for every pair of objects $x, y$ of $\mathcal{I}$ there exist an object $z$ and morphisms $x \to z$ and $y \to z$. Let $M : \mathcal{I} \to \textit{Ab}$ be a diagram of abelian groups over $\mathcal{I}$. Then the colimit of $M$ in the category of sets surjects onto the colimit of $M$ in the category of abelian groups.
Proof.
Recall that the colimit in the category of sets is the quotient of the disjoint union $\coprod M_ i$ by relation, see Section 4.15. Similarly, the colimit in the category of abelian groups is a quotient of the direct sum $\bigoplus M_ i$. The assumption of the lemma means that given $i, j \in \mathop{\mathrm{Ob}}\nolimits (\mathcal{I})$ and $m \in M_ i$ and $n \in M_ j$, then we can find an object $k$ and morphisms $a : i \to k$ and $b : j \to k$. Thus $m + n$ is represented in the colimit by the element $M(a)(m) + M(b)(n)$ of $M_ k$. Thus the $\coprod M_ i$ surjects onto the colimit.
$\square$
Lemma 4.19.6. Let $\mathcal{I}$ be an index category, i.e., a category. Assume that for every solid diagram
\[ \xymatrix{ x \ar[d] \ar[r] & y \ar@{..>}[d] \\ z \ar@{..>}[r] & w } \]
in $\mathcal{I}$ there exist an object $w$ and dotted arrows making the diagram commute. Then $\mathcal{I}$ is either empty or a nonempty disjoint union of connected categories having the same property.
Proof.
If $\mathcal{I}$ is the empty category, then the lemma is true. Otherwise, we define a relation on objects of $\mathcal{I}$ by saying that $x \sim y$ if there exist a $z$ and morphisms $x \to z$ and $y \to z$. This is an equivalence relation by the assumption of the lemma. Hence $\mathop{\mathrm{Ob}}\nolimits (\mathcal{I})$ is a disjoint union of equivalence classes. Let $\mathcal{I}_ j$ be the full subcategories corresponding to these equivalence classes. Then $\mathcal{I} = \coprod \mathcal{I}_ j$ with $\mathcal{I}_ j$ nonempty as desired.
$\square$
Lemma 4.19.7. Let $\mathcal{I}$ be an index category, i.e., a category. Assume that for every solid diagram
\[ \xymatrix{ x \ar[d] \ar[r] & y \ar@{..>}[d] \\ z \ar@{..>}[r] & w } \]
in $\mathcal{I}$ there exist an object $w$ and dotted arrows making the diagram commute. Then
an injective morphism $M \to N$ of diagrams of sets over $\mathcal{I}$ gives rise to an injective map $\mathop{\mathrm{colim}}\nolimits M_ i \to \mathop{\mathrm{colim}}\nolimits N_ i$ of sets,
in general the same is not the case for diagrams of abelian groups and their colimits.
Proof.
If $\mathcal{I}$ is the empty category, then the lemma is true. Thus we may assume $\mathcal{I}$ is nonempty. In this case we can write $\mathcal{I} = \coprod \mathcal{I}_ j$ where each $\mathcal{I}_ j$ is nonempty and satisfies the same property, see Lemma 4.19.6. Since $\mathop{\mathrm{colim}}\nolimits _\mathcal {I} M = \coprod _ j \mathop{\mathrm{colim}}\nolimits _{\mathcal{I}_ j} M|_{\mathcal{I}_ j}$ this reduces the proof of (1) to the connected case.
Assume $\mathcal{I}$ is connected and $M \to N$ is injective, i.e., all the maps $M_ i \to N_ i$ are injective. We identify $M_ i$ with the image of $M_ i \to N_ i$, i.e., we will think of $M_ i$ as a subset of $N_ i$. We will use the description of the colimits given in Section 4.15 without further mention. Let $s, s' \in \mathop{\mathrm{colim}}\nolimits M_ i$ map to the same element of $\mathop{\mathrm{colim}}\nolimits N_ i$. Say $s$ comes from an element $m$ of $M_ i$ and $s'$ comes from an element $m'$ of $M_{i'}$. Then we can find a sequence $i = i_0, i_1, \ldots , i_ n = i'$ of objects of $\mathcal{I}$ and morphisms
\[ \xymatrix{ & i_1 \ar[ld] \ar[rd] & & i_3 \ar[ld] & & i_{2n-1} \ar[rd] & \\ i = i_0 & & i_2 & & \ldots & & i_{2n} = i' } \]
and elements $n_{i_ j} \in N_{i_ j}$ mapping to each other under the maps $N_{i_{2k-1}} \to N_{i_{2k-2}}$ and $N_{i_{2k-1}} \to N_{i_{2k}}$ induced from the maps in $\mathcal{I}$ above with $n_{i_0} = m$ and $n_{i_{2n}} = m'$. We will prove by induction on $n$ that this implies $s = s'$. The base case $n = 0$ is trivial. Assume $n \geq 1$. Using the assumption on $\mathcal{I}$ we find a commutative diagram
\[ \xymatrix{ & i_1 \ar[ld] \ar[rd] \\ i_0 \ar[rd] & & i_2 \ar[ld] \\ & w } \]
We conclude that $m$ and $n_{i_2}$ map to the same element of $N_ w$ because both are the image of the element $n_{i_1}$. In particular, this element is an element $m'' \in M_ w$ which gives rise to the same element as $s$ in $\mathop{\mathrm{colim}}\nolimits M_ i$. Then we find the chain
\[ \xymatrix{ & i_3 \ar[ld] \ar[rd] & & i_5 \ar[ld] & & i_{2n-1} \ar[rd] & \\ w & & i_4 & & \ldots & & i_{2n} = i' } \]
and the elements $n_{i_ j}$ for $j \geq 3$ which has a smaller length than the chain we started with. This proves the induction step and the proof of (1) is complete.
Let $G$ be a group and let $\mathcal{I}$ be the one-object category with endomorphism monoid $G$. Then $\mathcal{I}$ satisfies the condition stated in the lemma because given $g_1, g_2 \in G$ we can find $h_1, h_2 \in G$ with $h_1 g_1 = h_2 g_2$. An diagram $M$ over $\mathcal{I}$ in $\textit{Ab}$ is the same thing as an abelian group $M$ with $G$-action and $\mathop{\mathrm{colim}}\nolimits _\mathcal {I} M$ is the coinvariants $M_ G$ of $M$. Take $G$ the group of order $2$ acting trivially on $M = \mathbf{Z}/2\mathbf{Z}$ mapping into the first summand of $N = \mathbf{Z}/2\mathbf{Z} \times \mathbf{Z}/2\mathbf{Z}$ where the nontrivial element of $G$ acts by $(x, y) \mapsto (x + y, y)$. Then $M_ G \to N_ G$ is zero.
$\square$
Lemma 4.19.8. Let $\mathcal{I}$ be an index category, i.e., a category. Assume
for every pair of morphisms $a : w \to x$ and $b : w \to y$ in $\mathcal{I}$ there exist an object $z$ and morphisms $c : x \to z$ and $d : y \to z$ such that $c \circ a = d \circ b$, and
for every pair of morphisms $a, b : x \to y$ there exists a morphism $c : y \to z$ such that $c \circ a = c \circ b$.
Then $\mathcal{I}$ is a (possibly empty) union of disjoint filtered index categories $\mathcal{I}_ j$.
Proof.
If $\mathcal{I}$ is the empty category, then the lemma is true. Otherwise, we define a relation on objects of $\mathcal{I}$ by saying that $x \sim y$ if there exist a $z$ and morphisms $x \to z$ and $y \to z$. This is an equivalence relation by the first assumption of the lemma. Hence $\mathop{\mathrm{Ob}}\nolimits (\mathcal{I})$ is a disjoint union of equivalence classes. Let $\mathcal{I}_ j$ be the full subcategories corresponding to these equivalence classes. The rest is clear from the definitions.
$\square$
Lemma 4.19.9. Let $\mathcal{I}$ be an index category satisfying the hypotheses of Lemma 4.19.8 above. Then colimits over $\mathcal{I}$ commute with fibre products and equalizers in sets (and more generally with finite connected limits).
Proof.
By Lemma 4.19.8 we may write $\mathcal{I} = \coprod \mathcal{I}_ j$ with each $\mathcal{I}_ j$ filtered. By Lemma 4.19.2 we see that colimits of $\mathcal{I}_ j$ commute with equalizers and fibre products. Thus it suffices to show that equalizers and fibre products commute with coproducts in the category of sets (including empty coproducts). In other words, given a set $J$ and sets $A_ j, B_ j, C_ j$ and set maps $A_ j \to B_ j$, $C_ j \to B_ j$ for $j \in J$ we have to show that
\[ (\coprod \nolimits _{j \in J} A_ j) \times _{(\coprod \nolimits _{j \in J} B_ j)} (\coprod \nolimits _{j \in J} C_ j) = \coprod \nolimits _{j \in J} A_ j \times _{B_ j} C_ j \]
and given $a_ j, a'_ j : A_ j \to B_ j$ that
\[ \text{Equalizer}( \coprod \nolimits _{j \in J} a_ j, \coprod \nolimits _{j \in J} a'_ j) = \coprod \nolimits _{j \in J} \text{Equalizer}(a_ j, a'_ j) \]
This is true even if $J = \emptyset $. Details omitted.
$\square$
Comments (5)
Comment #2260 by Dario Weißmann on
Comment #2261 by Johan on
Comment #2263 by Dario Weißmann on
Comment #9570 by Liam Nutley on
Comment #9830 by Elías Guisado on