Lemma 4.21.5. Let $\mathcal{I}$ be a filtered index category. There exist a directed set $I$ and a system $(x_ i, \varphi _{ii'})$ over $I$ in $\mathcal{I}$ with the following properties:

1. For every category $\mathcal{C}$ and every diagram $M : \mathcal{I} \to \mathcal{C}$ with values in $\mathcal{C}$, denote $(M(x_ i), M(\varphi _{ii'}))$ the corresponding system over $I$. If $\mathop{\mathrm{colim}}\nolimits _{i \in I} M(x_ i)$ exists then so does $\mathop{\mathrm{colim}}\nolimits _\mathcal {I} M$ and the transformation

$\theta : \mathop{\mathrm{colim}}\nolimits _{i \in I} M(x_ i) \longrightarrow \mathop{\mathrm{colim}}\nolimits _\mathcal {I} M$

of Lemma 4.14.8 is an isomorphism.

2. For every category $\mathcal{C}$ and every diagram $M : \mathcal{I}^{opp} \to \mathcal{C}$ in $\mathcal{C}$, denote $(M(x_ i), M(\varphi _{ii'}))$ the corresponding inverse system over $I$. If $\mathop{\mathrm{lim}}\nolimits _{i \in I} M(x_ i)$ exists then so does $\mathop{\mathrm{lim}}\nolimits _{\mathcal{I}^{opp}} M$ and the transformation

$\theta : \mathop{\mathrm{lim}}\nolimits _{\mathcal{I}^{opp}} M \longrightarrow \mathop{\mathrm{lim}}\nolimits _{i \in I} M(x_ i)$

of Lemma 4.14.9 is an isomorphism.

Proof. As explained in the text following Definition 4.21.2, we may view preordered sets as categories and systems as functors. Throughout the proof, we will freely shift between these two points of view. We prove the first statement by constructing a category $\mathcal{I}_0$, corresponding to a directed set1, and a cofinal functor $M_0 : \mathcal{I}_0 \to \mathcal{I}$. Then, by Lemma 4.17.2, the colimit of a diagram $M : \mathcal{I} \to \mathcal{C}$ coincides with the colimit of the diagram $M \circ M_0 : \mathcal{I}_0 \to \mathcal{C}$, from which the statement follows. The second statement is dual to the first and may be proved by interpreting a limit in $\mathcal{C}$ as a colimit in $\mathcal{C}^{opp}$. We omit the details.

A category $\mathcal{F}$ is called finitely generated if there exists a finite set $F$ of arrows in $\mathcal{F}$, such that each arrow in $\mathcal{F}$ may be obtained by composing arrows from $F$. In particular, this implies that $\mathcal{F}$ has finitely many objects. We start the proof by reducing to the case when $\mathcal{I}$ has the property that every finitely generated subcategory of $\mathcal{I}$ may be extended to a finitely generated subcategory with a unique final object.

Let $\omega$ denote the directed set of finite ordinals, which we view as a filtered category. It is easy to verify that the product category $\mathcal{I}\times \omega$ is also filtered, and the projection $\Pi : \mathcal{I} \times \omega \to \mathcal{I}$ is cofinal.

Now let $\mathcal{F}$ be any finitely generated subcategory of $\mathcal{I}\times \omega$. By using the axioms of a filtered category and a simple induction argument on a finite set of generators of $\mathcal{F}$, we may construct a cocone $(\{ f_ i\} , i_\infty )$ in $\mathcal{I} \times \omega$ for the diagram $\mathcal{F} \to \mathcal{I} \times \omega$. That is, a morphism $f_ i : i \to i_\infty$ for every object $i$ in $\mathcal{F}$ such that for each arrow $f : i \to i'$ in $\mathcal{F}$ we have $f_ i = f_{i'} \circ f$. We can also choose $i_\infty$ such that there are no arrows from $i_\infty$ to an object in $\mathcal{F}$. This is possible since we may always post-compose the arrows $f_ i$ with an arrow which is the identity on the $\mathcal{I}$-component and strictly increasing on the $\omega$-component. Now let $\mathcal{F}^+$ denote the category consisting of all objects and arrows in $\mathcal{F}$ together with the object $i_\infty$, the identity arrow $\text{id}_{i_\infty }$ and the arrows $f_ i$. Since there are no arrows from $i_\infty$ in $\mathcal{F}^+$ to any object of $\mathcal{F}$, the arrow set in $\mathcal{F}^+$ is closed under composition, so $\mathcal{F}^+$ is indeed a category. By construction, it is a finitely generated subcategory of $\mathcal{I}$ which has $i_\infty$ as unique final object. Since, by Lemma 4.17.2, the colimit of any diagram $M : \mathcal{I} \to \mathcal{C}$ coincides with the colimit of $M\circ \Pi$ , this gives the desired reduction.

The set of all finitely generated subcategories of $\mathcal{I}$ with a unique final object is naturally ordered by inclusion. We take $\mathcal{I}_0$ to be the category corresponding to this set. We also have a functor $M_0 : \mathcal{I}_0 \to \mathcal{I}$, which takes an arrow $\mathcal{F} \subset \mathcal{F'}$ in $\mathcal{I}_0$ to the unique map from the final object of $\mathcal{F}$ to the final object of $\mathcal{F}'$. Given any two finitely generated subcategories of $\mathcal{I}$, the category generated by these two categories is also finitely generated. By our assumption on $\mathcal{I}$, it is also contained in a finitely generated subcategory of $\mathcal{I}$ with a unique final object. This shows that $\mathcal{I}_0$ is directed.

Finally, we verify that $M_0$ is cofinal. Since any object of $\mathcal{I}$ is the final object in the subcategory consisting of only that object and its identity arrow, the functor $M_0$ is surjective on objects. In particular, Condition (1) of Definition 4.17.1 is satisfied. Given an object $i$ of $\mathcal{I}$, objects $\mathcal{F}_1, \mathcal{F}_2$ in $\mathcal{I}_0$ and maps $\varphi _1 : i \to M_0(\mathcal{F}_1)$ and $\varphi _2 : i \to M_0(\mathcal{F}_2)$ in $\mathcal{I}$, we can take $\mathcal{F}_{12}$ to be a finitely generated category with a unique final object containing $\mathcal{F}_1$, $\mathcal{F}_2$ and the morphisms $\varphi _1, \varphi _2$. The resulting diagram commutes

$\xymatrix{ & M_0(\mathcal{F}_{12}) & \\ M_0(\mathcal{F}_{1}) \ar[ru] & & M_0(\mathcal{F}_{2}) \ar[lu] \\ & i \ar[lu] \ar[ru] }$

since it lives in the category $\mathcal{F}_{12}$ and $M_0(\mathcal{F}_{12})$ is final in this category. Hence also Condition (2) is satisfied, which concludes the proof. $\square$

[1] In fact, our construction will produce a directed partially ordered set.

Comment #309 by Daniel Bergh on

There seem to be some minor unclarities in the proof. According to point 3 and 4 in the description of the properties of the quadruples, the object $x$ and the morphisms $f_s$ are not required to be part of the sets $S$ and $A$ respectively. Yet this is used in the first paragraph where it is asserted that $x_i \in S_{i'}$. Also it is not true that $I$ is a partial ordering, since the quadruple is not uniquely determined by the sets $S$ and $A$. It is merely a partial pre-order.

I suggest the following reformulation of the proof: Take $I$ to be the set of finite sub-categories of $\mathcal{I}$ having terminal objects. This set is naturally ordered by inclusion. One could also view $I$ as a category with morphisms being inclusions. This category is filtered (which is the same thing as saying that the set is directed). A choice of terminal object in each subcategory gives a functor $H:I \to \mathcal{I}$. It is easy to see that this makes $I$ cofinal in $\mathcal{I}$. Hence the lemma follows from Lemma~4.17.2.

Comment #310 by Daniel Bergh on

Sorry. I missed the definition of $\bar{S}$ and $\bar{A}$ in the first paragraph. This fixes my first objection. But then the set $I$ becomes still more problematic, since it might not even be true that $i \leq i$.

Comment #313 by on

This idea doesn't work. For example, what if $\mathcal{I}$ has only one object, but lot's of morphisms? In this case there may not be enough subcategories of $\mathcal{I}$. Phrasing the proof in terms of finite categories with a final object endowed with a functor into $\mathcal{I}$ might be the right thing to do. But for now I've just fixed your (correct) complaint about the partial ordering by changing very slightly the definition of the partial ordering. See here. Thanks!

Comment #314 by Daniel Bergh on

You are right. My idea does not work as it stands.

But I'm still not convinced that you get a partial ordering on $I$. The underlying sets $S$ and $A$ could be equal but the choices of cones could be different. But that is probably fixable. What is worse is that I think your quick-fix just moved the problem. Now you don't get a system since $\varphi_{ii}$ need not be the identity.

Thinking of it, it looks like the current proof sufferes from a similar defect as my attempt. If $\mathcal{I}$ is finite, then $I$ is also finite. And a finite directed set always has a greatest element, which would get you a trivial colimit. But if $\mathcal{I}$ was the finite category consisting of one object and two morphisms, the identity and an idempotent morphism, then you would get a non-trivial colimit in general.

There is a clever fix to this which I just learned from the book "Locally Presentable and Accessible Categories" by Adámek and Rosicky. If you take the product category $\mathcal{I}\times \omega$, it has enough subcategories, and the projection to $\mathcal{I}$ is cofinal. It is even true that every finite subcategory of $\mathcal{I}\times \omega$ has an extension to a finite subcategory with a unique terminal object. Then you can apply the proof I sketched to this category instead.

If you think it is a good idea, I could give it a shot to write down a proof along these lines.

Comment #315 by on

OK, that sounds much better than what we have now (I still think it works with just minor modifications, but it is sloppy and a kludge). If you are willing please go ahead and write it. Thanks.

Comment #7528 by Samuel Tiersma on

Some typos. Part (2) of statement: "then so does $\lim_{\mathcal{I}}M$" should be "then so does $\lim_{\mathcal{I^{opp}}}M$" 4th paragraph of proof: 2th/3rd line should read "... we may construct a cocone in $\mathcal{I} \times \omega$ for the diagram $\mathcal{F} \rightarrow \mathcal{I} \times \omega$." 4th line: the order of the maps is reversed, it should be "$f_i = f_{i'} \circ f$".

There are also:

• 2 comment(s) on Section 4.21: Limits and colimits over preordered sets

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