## 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, orfilteredif the following conditions hold:

- the category $\mathcal{I}$ has at least one object,
- for every pair of objects $x, y$ of $\mathcal{I}$ there exists 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, orfilteredif $\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 category

^{1}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 colimits of diagrams of sets over $\mathcal{I}$ commute with finite nonempty products.

Proof.Let $M$ and $N$ be diagrams of sets over $\mathcal{I}$. To prove the lemma we have to show that the canonical map $$ \mathop{\rm colim}\nolimits (M_i \times N_i) \longrightarrow \mathop{\rm colim}\nolimits M_i \times \mathop{\rm colim}\nolimits N_i $$ is an isomorphism. If $\mathcal{I}$ is empty, then this is true because the colimit of sets over the empty category is the empty set. If $\mathcal{I}$ is nonempty, then we construct a map $\mathop{\rm colim}\nolimits M_i \times \mathop{\rm colim}\nolimits N_i \to \mathop{\rm colim}\nolimits (M_i \times N_i)$ as follows. Suppose that $m \in M_i$ and $n \in N_j$ give rise to elements $s$ and $t$ of the respective colimits. By assumption we can find $a : i \to k$ and $b : j \to k$ in $\mathcal{I}$. Then $(M(a)(m), N(b)(n))$ is an element of $M_k \times N_k$ and we map $(s, t)$ to the corresponding element of $\mathop{\rm colim}\nolimits M_i \times N_i$. We omit the verification that this map is well defined and that it is an inverse of the map displayed above. $\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 set underlying $\mathop{\rm colim}\nolimits_i M_i$ is the colimit of $M$ viewed as a diagram of sets over $\mathcal{I}$.

Proof.In this proof all colimits are taken in the category of sets. By Lemma 4.19.4 we have $\mathop{\rm colim}\nolimits M_i \times \mathop{\rm colim}\nolimits M_i = \mathop{\rm colim}\nolimits (M_i \times M_i)$ hence we can use the maps $+ : M_i \times M_i \to M_i$ to define an addition map on $\mathop{\rm colim}\nolimits M_i$. A straightforward argument, which we omit, shows that the set $\mathop{\rm colim}\nolimits M_i$ with this addition is the colimit in the category of abelian groups. $\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 a (possibly empty) disjoint union of categories satisfying the condition above and the condition of Lemma 4.19.4.

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$ 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 an injective morphism $M \to N$ of diagrams of sets (resp. abelian groups) over $\mathcal{I}$ gives rise to an injective map $\mathop{\rm colim}\nolimits M_i \to \mathop{\rm colim}\nolimits N_i$ of sets (resp. abelian groups).

Proof.We first show that it suffices to prove the lemma for the case of a diagram of sets. Namely, by Lemma 4.19.6 we can write $\mathcal{I} = \coprod \mathcal{I}_j$ where each $\mathcal{I}_j$ satisfies the condition of the lemma as well as the condition of Lemma 4.19.4. Thus, if $M$ is a diagram of abelian groups over $\mathcal{I}$, then $$ \mathop{\rm colim}\nolimits_\mathcal{I} M = \bigoplus\nolimits_j \mathop{\rm colim}\nolimits_{\mathcal{I}_j} M|_{\mathcal{I}_j} $$ It follows that it suffices to prove the result for the categories $\mathcal{I}_j$. However, colimits of abelian groups over these categories are computed by the colimits of the underlying sets (Lemma 4.19.5) hence we reduce to the case of an injective map of diagrams of sets.Here we say that $M \to N$ is injective if all the maps $M_i \to N_i$ are injective. In fact, we will 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 the lemma is complete. $\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 exists 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 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$

- 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–2325 (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 colimits of diagrams of sets over $\mathcal{I}$
commute with finite nonempty products.
\end{lemma}
\begin{proof}
Let $M$ and $N$ be diagrams of sets over $\mathcal{I}$.
To prove the lemma we have to show that the canonical map
$$
\colim (M_i \times N_i) \longrightarrow \colim M_i \times \colim N_i
$$
is an isomorphism.
If $\mathcal{I}$ is empty, then this is true because the colimit
of sets over the empty category is the empty set.
If $\mathcal{I}$ is nonempty, then we construct a map
$\colim M_i \times \colim N_i \to \colim (M_i \times N_i)$ as follows.
Suppose that $m \in M_i$ and $n \in N_j$ give rise to elements
$s$ and $t$ of the respective colimits. By assumption we can find
$a : i \to k$ and $b : j \to k$
in $\mathcal{I}$. Then $(M(a)(m), N(b)(n))$ is an element of
$M_k \times N_k$ and we map $(s, t)$ to the corresponding element
of $\colim M_i \times N_i$. We omit the verification that this map
is well defined and that it is an inverse of the map displayed
above.
\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 set underlying $\colim_i M_i$
is the colimit of $M$ viewed as a diagram of sets over $\mathcal{I}$.
\end{lemma}
\begin{proof}
In this proof all colimits are taken in the category of sets.
By Lemma \ref{lemma-preserve-products} we have
$\colim M_i \times \colim M_i = \colim (M_i \times M_i)$
hence we can use the maps $+ : M_i \times M_i \to M_i$
to define an addition map on $\colim M_i$. A straightforward
argument, which we omit, shows that the set $\colim M_i$ with this
addition is the colimit in the category of abelian groups.
\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 a (possibly empty)
disjoint union of categories satisfying the condition above and
the condition of Lemma \ref{lemma-preserve-products}.
\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$ 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 an injective morphism $M \to N$
of diagrams of sets (resp.\ abelian groups) over $\mathcal{I}$ gives
rise to an injective map $\colim M_i \to \colim N_i$ of sets
(resp.\ abelian groups).
\end{lemma}
\begin{proof}
We first show that it suffices to prove the lemma for the case of
a diagram of sets. Namely, by Lemma \ref{lemma-split-into-connected}
we can write $\mathcal{I} = \coprod \mathcal{I}_j$ where each
$\mathcal{I}_j$ satisfies the condition of the lemma as well as the
condition of Lemma \ref{lemma-preserve-products}.
Thus, if $M$ is a diagram of abelian groups over $\mathcal{I}$, then
$$
\colim_\mathcal{I} M =
\bigoplus\nolimits_j \colim_{\mathcal{I}_j} M|_{\mathcal{I}_j}
$$
It follows that it suffices to prove the result for the categories
$\mathcal{I}_j$. However, colimits of abelian groups over these categories
are computed by the colimits of the underlying sets
(Lemma \ref{lemma-colimits-abelian-as-sets})
hence we reduce to the case of an injective map of diagrams of sets.
\medskip\noindent
Here we say that $M \to N$ is injective if all the maps $M_i \to N_i$
are injective. In fact, we will 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 the lemma is complete.
\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}
```

## Comments (3)

## Add a comment on tag `04AX`

Your email address will not be published. Required fields are marked.

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).

All contributions are licensed under the GNU Free Documentation License.