# The Stacks Project

## Tag 04AX

### 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:

1. the category $\mathcal{I}$ has at least one object,
2. for every pair of objects $x, y$ of $\mathcal{I}$ there exists an object $z$ and morphisms $x \to z$, $y \to z$, and
3. 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{\rm colim}\nolimits_\mathcal{I} M$ exists if and only if $\mathop{\rm 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{\rm 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{\rm colim}\nolimits_i \mathop{\rm lim}\nolimits_j M_{i, j} = \mathop{\rm lim}\nolimits_j \mathop{\rm 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}$ consist of 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{\rm colim}\nolimits_i M_{i, j} = \mathbf{N}$ and hence $$\mathop{\rm lim}\nolimits_j \mathop{\rm colim}\nolimits_i M_{i, j} = \prod\nolimits_j \mathbf{N} = \mathbf{N}^\mathbf{N}$$ On the other hand $\mathop{\rm lim}\nolimits_j M_{i, j} = \prod\nolimits_j M_{i, j}$ and hence $$\mathop{\rm colim}\nolimits_i \mathop{\rm 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 exists an object $z$ and morphisms $x \to z$ and $y \to z$. Then

1. If $M$ and $N$ are diagrams of sets over $\mathcal{I}$, then $\mathop{\rm colim}\nolimits (M_i \times N_i) \to \mathop{\rm colim}\nolimits M_i \times \mathop{\rm colim}\nolimits N_i$ is surjective,
2. 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{\rm colim}\nolimits M_i \times \mathop{\rm colim}\nolimits N_i$. Then we can find $m \in M_x$ and $n \in N_y$ for some $x, y \in \mathop{\rm Ob}\nolimits(\mathcal{I})$ such that $m$ mapsto $\overline{m}$ and $n$ mapsto $\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{\rm 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{\rm colim}\nolimits_\mathcal{I} G \times \mathop{\rm colim}\nolimits_\mathcal{I} G \cong G/G \times G/G$$ is not isomorphic to $$\mathop{\rm 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 exists 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{\rm 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 exists 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 exists a $z$ and morphisms $x \to z$ and $y \to z$. This is an equivalence relation by the assumption of the lemma. Hence $\mathop{\rm 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 exists an object $w$ and dotted arrows making the diagram commute. Then

1. an injective morphism $M \to N$ of diagrams of sets over $\mathcal{I}$ gives rise to an injective map $\mathop{\rm colim}\nolimits M_i \to \mathop{\rm colim}\nolimits N_i$ of sets,
2. 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{\rm colim}\nolimits_\mathcal{I} M = \coprod_j \mathop{\rm 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{\rm colim}\nolimits M_i$ map to the same element of $\mathop{\rm 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{\rm 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{\rm 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

1. for every pair of morphisms $a : w \to x$ and $b : w \to y$ in $\mathcal{I}$ there exists an object $z$ and morphisms $c : x \to z$ and $d : y \to z$ such that $c \circ a = d \circ b$, and
2. 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 exists 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{\rm 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 fibred 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$

1. Namely, let $\mathcal{I}'$ have the same objects as $\mathcal{I}$ but where $\mathop{\rm Mor}\nolimits_{\mathcal{I}'}(x, y)$ is the quotient of $\mathop{\rm Mor}\nolimits_\mathcal{I}(x, y)$ by the equivalence relation which identifies $a, b : x \to y$ if $M(a) = M(b)$.

The code snippet corresponding to this tag is a part of the file categories.tex and is located in lines 1964–2354 (see updates for more information).

\section{Filtered colimits}
\label{section-directed-colimits}

\noindent
Colimits are easier to compute or describe when they
are over a filtered diagram. Here is the definition.

\begin{definition}
\label{definition-directed}
We say that a diagram $M : \mathcal{I} \to \mathcal{C}$ is {\it directed},
or {\it filtered} if the following conditions hold:
\begin{enumerate}
\item the category $\mathcal{I}$ has at least one object,
\item for every pair of objects $x, y$ of $\mathcal{I}$
there exists an object $z$ and morphisms $x \to z$,
$y \to z$, and
\item 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}$.
\end{enumerate}
We say that an index category $\mathcal{I}$ is {\it directed}, or
{\it filtered} if $\text{id} : \mathcal{I} \to \mathcal{I}$ is filtered
(in other words you erase the $M$ in part (3) above).
\end{definition}

\noindent
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 category\footnote{Namely, let
$\mathcal{I}'$ have the same objects as $\mathcal{I}$ but
where $\Mor_{\mathcal{I}'}(x, y)$ is the quotient of $\Mor_\mathcal{I}(x, y)$
by the equivalence relation which identifies
$a, b : x \to y$ if $M(a) = M(b)$.}
such that $\colim_\mathcal{I} M$ exists if and only if
$\colim_{\mathcal{I}'} M'$ exists in which case the colimits are
canonically isomorphic.

\medskip\noindent
Suppose that $M : \mathcal{I} \to \textit{Sets}$ is a filtered diagram. In
this case we may describe the equivalence relation in the formula
$$\colim_\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''.

\begin{lemma}
\label{lemma-directed-commutes}
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
$$\colim_i \lim_j M_{i, j} = \lim_j \colim_i M_{i, j}.$$
In particular, colimits over $\mathcal{I}$ commute with finite products,
fibre products, and equalizers of sets.
\end{lemma}

\begin{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).
\end{proof}

\noindent
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}$ consist of 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
$\colim_i M_{i, j} = \mathbf{N}$ and hence
$$\lim_j \colim_i M_{i, j} = \prod\nolimits_j \mathbf{N} = \mathbf{N}^\mathbf{N}$$
On the other hand $\lim_j M_{i, j} = \prod\nolimits_j M_{i, j}$ and
hence
$$\colim_i \lim_j M_{i, j} = \bigcup\nolimits_i \{1, 2, \ldots, i\}^{\mathbf{N}}$$
which is smaller than the other limit.

\begin{lemma}
\label{lemma-cofinal-in-filtered}
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}$.
\end{lemma}

\begin{proof}
Omitted. Pleasant exercise of the notions involved.
\end{proof}

\noindent
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.

\begin{lemma}
\label{lemma-preserve-products}
Let $\mathcal{I}$ be an index category, i.e., a category. Assume
that for every pair of objects $x, y$ of $\mathcal{I}$
there exists an object $z$ and morphisms $x \to z$ and $y \to z$.
Then
\begin{enumerate}
\item If $M$ and $N$ are diagrams of sets over $\mathcal{I}$,
then $\colim (M_i \times N_i) \to \colim M_i \times \colim N_i$
is surjective,
\item in general colimits of diagrams of sets over $\mathcal{I}$
do not commute with finite nonempty products.
\end{enumerate}
\end{lemma}

\begin{proof}
Proof of (1). Let $(\overline{m}, \overline{n})$
be an element of $\colim M_i \times \colim N_i$.
Then we can find $m \in M_x$ and $n \in N_y$ for some
$x, y \in \Ob(\mathcal{I})$ such that $m$ mapsto
$\overline{m}$ and $n$ mapsto $\overline{n}$. See
Section \ref{section-limit-sets}.
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 $\colim (M_i \times N_i)$
maps to $(\overline{m}, \overline{n})$ as desired.

\medskip\noindent
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
$$\colim_\mathcal{I} G \times \colim_\mathcal{I} G \cong G/G \times G/G$$
is not isomorphic to
$$\colim_\mathcal{I} (G \times G) \cong (G \times G)/G$$
This example indicates that you cannot just drop the additional
condition Lemma \ref{lemma-directed-commutes}
even if you only care about finite products.
\end{proof}

\begin{lemma}
\label{lemma-colimits-abelian-as-sets}
Let $\mathcal{I}$ be an index category, i.e., a category. Assume
that for every pair of objects $x, y$ of $\mathcal{I}$
there exists 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.
\end{lemma}

\begin{proof}
Recall that the colimit in the category of sets is the quotient of
the disjoint union $\coprod M_i$ by relation, see
Section \ref{section-limit-sets}.
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 \Ob(\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.
\end{proof}

\begin{lemma}
\label{lemma-split-into-connected}
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 exists 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.
\end{lemma}

\begin{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 exists a $z$ and
morphisms $x \to z$ and $y \to z$. This is an equivalence
relation by the assumption of the lemma. Hence $\Ob(\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.
\end{proof}

\begin{lemma}
\label{lemma-preserve-injective-maps}
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 exists an object $w$ and dotted arrows
making the diagram commute. Then
\begin{enumerate}
\item an injective morphism $M \to N$ of diagrams of sets over
$\mathcal{I}$ gives rise to an injective map $\colim M_i \to \colim N_i$
of sets,
\item in general the same is not the case for diagrams of abelian
groups and their colimits.
\end{enumerate}
\end{lemma}

\begin{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 \ref{lemma-split-into-connected}. Since
$\colim_\mathcal{I} M = \coprod_j \colim_{\mathcal{I}_j} M|_{\mathcal{I}_j}$
this reduces the proof of (1) to the connected case.

\medskip\noindent
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 \ref{section-limit-sets} without further mention.
Let $s, s' \in \colim M_i$ map to the same element of $\colim 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 $\colim 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.

\medskip\noindent
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 $\colim_\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.
\end{proof}

\begin{lemma}
\label{lemma-split-into-directed}
Let $\mathcal{I}$ be an index category, i.e., a category.
Assume
\begin{enumerate}
\item for every pair of morphisms $a : w \to x$ and $b : w \to y$
in $\mathcal{I}$ there exists an object $z$ and morphisms $c : x \to z$
and $d : y \to z$ such that $c \circ a = d \circ b$, and
\item 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$.
\end{enumerate}
Then $\mathcal{I}$ is a (possibly empty) union
of disjoint filtered index categories $\mathcal{I}_j$.
\end{lemma}

\begin{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 exists a $z$ and
morphisms $x \to z$ and $y \to z$. This is an equivalence
relation by the first assumption of the lemma. Hence $\Ob(\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.
\end{proof}

\begin{lemma}
\label{lemma-almost-directed-commutes-equalizers}
Let $\mathcal{I}$ be an index category satisfying the hypotheses of
Lemma \ref{lemma-split-into-directed} above. Then colimits over $\mathcal{I}$
commute with fibre products and equalizers in sets (and more generally
with finite connected limits).
\end{lemma}

\begin{proof}
By
Lemma \ref{lemma-split-into-directed}
we may write $\mathcal{I} = \coprod \mathcal{I}_j$ with each $\mathcal{I}_j$
filtered. By
Lemma \ref{lemma-directed-commutes}
we see that colimits of $\mathcal{I}_j$ commute with equalizers and
fibred 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.
\end{proof}

Comment #2260 by Dario Weißmann on October 25, 2016 a 4:31 pm UTC

I think the counterexample for 'directed colimits do in general not commute with limits' following Lemma 4.19.2 is wrong. The cardinality of $N^N$ is $2^N$, as $2^N \leq N^N \leq (2^N)^N = 2^(N\times N) = 2^N$. The other cardinality in the counterexample is $2^N$ as well.

Comment #2261 by Johan (site) on October 25, 2016 a 6:55 pm UTC

Don't understand your comment as there is nothing said about cardinalities in the text. The text only claims that the natural map $\mathop{\rm colim}\nolimits \mathop{\rm lim}\nolimits \to \mathop{\rm lim}\nolimits \mathop{\rm colim}\nolimits$ is not a bijection because the sides are different. The map is injective and not surjective.

Comment #2263 by Dario Weißmann on October 25, 2016 a 8:01 pm UTC

Oh, yes of course. I guess I got confused by the 'smaller' in the last sentence and thought it was meant in terms of cardinality. Thank you.

## Add a comment on tag 04AX

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the lower-right corner).