# stacks/stacks-project

Fetching contributors…
Cannot retrieve contributors at this time
8239 lines (7455 sloc) 284 KB
 \input{preamble} % OK, start here. % \begin{document} \title{Categories} \maketitle \phantomsection \label{section-phantom} \tableofcontents \section{Introduction} \label{section-introduction} \noindent Categories were first introduced in \cite{GenEqui}. The category of categories (which is a proper class) is a $2$-category. Similarly, the category of stacks forms a $2$-category. If you already know about categories, but not about $2$-categories you should read Section \ref{section-formal-cat-cat} as an introduction to the formal definitions later on. \section{Definitions} \label{section-definition-categories} \noindent We recall the definitions, partly to fix notation. \begin{definition} \label{definition-category} A {\it category} $\mathcal{C}$ consists of the following data: \begin{enumerate} \item A set of objects $\Ob(\mathcal{C})$. \item For each pair $x, y \in \Ob(\mathcal{C})$ a set of morphisms $\Mor_\mathcal{C}(x, y)$. \item For each triple $x, y, z\in \Ob(\mathcal{C})$ a composition map $\Mor_\mathcal{C}(y, z) \times \Mor_\mathcal{C}(x, y) \to \Mor_\mathcal{C}(x, z)$, denoted $(\phi, \psi) \mapsto \phi \circ \psi$. \end{enumerate} These data are to satisfy the following rules: \begin{enumerate} \item For every element $x\in \Ob(\mathcal{C})$ there exists a morphism $\text{id}_x\in \Mor_\mathcal{C}(x, x)$ such that $\text{id}_x \circ \phi = \phi$ and $\psi \circ \text{id}_x = \psi$ whenever these compositions make sense. \item Composition is associative, i.e., $(\phi \circ \psi) \circ \chi = \phi \circ ( \psi \circ \chi)$ whenever these compositions make sense. \end{enumerate} \end{definition} \noindent It is customary to require all the morphism sets $\Mor_\mathcal{C}(x, y)$ to be disjoint. In this way a morphism $\phi : x \to y$ has a unique {\it source} $x$ and a unique {\it target} $y$. This is not strictly necessary, although care has to be taken in formulating condition (2) above if it is not the case. It is convenient and we will often assume this is the case. In this case we say that $\phi$ and $\psi$ are {\it composable} if the source of $\phi$ is equal to the target of $\psi$, in which case $\phi \circ \psi$ is defined. An equivalent definition would be to define a category as a quintuple $(\text{Ob}, \text{Arrows}, s, t, \circ)$ consisting of a set of objects, a set of morphisms (arrows), source, target and composition subject to a long list of axioms. We will occasionally use this point of view. \begin{remark} \label{remark-big-categories} Big categories. In some texts a category is allowed to have a proper class of objects. We will allow this as well in these notes but only in the following list of cases (to be updated as we go along). In particular, when we say: Let $\mathcal{C}$ be a category'' then it is understood that $\Ob(\mathcal{C})$ is a set. \begin{enumerate} \item The category $\textit{Sets}$ of sets. \item The category $\textit{Ab}$ of abelian groups. \item The category $\textit{Groups}$ of groups. \item Given a group $G$ the category $G\textit{-Sets}$ of sets with a left $G$-action. \item Given a ring $R$ the category $\text{Mod}_R$ of $R$-modules. \item Given a field $k$ the category of vector spaces over $k$. \item The category of rings. \item The category of schemes. \item The category $\textit{Top}$ of topological spaces. \item Given a topological space $X$ the category $\textit{PSh}(X)$ of presheaves of sets over $X$. \item Given a topological space $X$ the category $\Sh(X)$ of sheaves of sets over $X$. \item Given a topological space $X$ the category $\textit{PAb}(X)$ of presheaves of abelian groups over $X$. \item Given a topological space $X$ the category $\textit{Ab}(X)$ of sheaves of abelian groups over $X$. \item Given a small category $\mathcal{C}$ the category of functors from $\mathcal{C}$ to $\textit{Sets}$. \item Given a category $\mathcal{C}$ the category of presheaves of sets over $\mathcal{C}$. \item Given a site $\mathcal{C}$ the category of sheaves of sets over $\mathcal{C}$. \end{enumerate} One of the reason to enumerate these here is to try and avoid working with something like the collection'' of big'' categories which would be like working with the collection of all classes which I think definitively is a meta-mathematical object. \end{remark} \begin{remark} \label{remark-unique-identity} It follows directly from the definition that any two identity morphisms of an object $x$ of $\mathcal{A}$ are the same. Thus we may and will speak of {\it the} identity morphism $\text{id}_x$ of $x$. \end{remark} \begin{definition} \label{definition-isomorphism} A morphism $\phi : x \to y$ is an {\it isomorphism} of the category $\mathcal{C}$ if there exists a morphism $\psi : y \to x$ such that $\phi \circ \psi = \text{id}_y$ and $\psi \circ \phi = \text{id}_x$. \end{definition} \noindent An isomorphism $\phi$ is also sometimes called an {\it invertible} morphism, and the morphism $\psi$ of the definition is called the {\it inverse} and denoted $\phi^{-1}$. It is unique if it exists. Note that given an object $x$ of a category $\mathcal{A}$ the set of invertible elements $\text{Aut}_\mathcal{A}(x)$ of $\Mor_\mathcal{A}(x, x)$ forms a group under composition. This group is called the {\it automorphism} group of $x$ in $\mathcal{A}$. \begin{definition} \label{definition-groupoid} A {\it groupoid} is a category where every morphism is an isomorphism. \end{definition} \begin{example} \label{example-group-groupoid} A group $G$ gives rise to a groupoid with a single object $x$ and morphisms $\Mor(x, x) = G$, with the composition rule given by the group law in $G$. Every groupoid with a single object is of this form. \end{example} \begin{example} \label{example-set-groupoid} A set $C$ gives rise to a groupoid $\mathcal{C}$ defined as follows: As objects we take $\Ob(\mathcal{C}) := C$ and for morphisms we take $\Mor(x, y)$ empty if $x\neq y$ and equal to $\{\text{id}_x\}$ if $x = y$. \end{example} \begin{definition} \label{definition-functor} A {\it functor} $F : \mathcal{A} \to \mathcal{B}$ between two categories $\mathcal{A}, \mathcal{B}$ is given by the following data: \begin{enumerate} \item A map $F : \Ob(\mathcal{A}) \to \Ob(\mathcal{B})$. \item For every $x, y \in \Ob(\mathcal{A})$ a map $F : \Mor_\mathcal{A}(x, y) \to \Mor_\mathcal{B}(F(x), F(y))$, denoted $\phi \mapsto F(\phi)$. \end{enumerate} These data should be compatible with composition and identity morphisms in the following manner: $F(\phi \circ \psi) = F(\phi) \circ F(\psi)$ for a composable pair $(\phi, \psi)$ of morphisms of $\mathcal{A}$ and $F(\text{id}_x) = \text{id}_{F(x)}$. \end{definition} \noindent Note that every category $\mathcal{A}$ has an {\it identity} functor $\text{id}_\mathcal{A}$. In addition, given a functor $G : \mathcal{B} \to \mathcal{C}$ and a functor $F : \mathcal{A} \to \mathcal{B}$ there is a {\it composition} functor $G \circ F : \mathcal{A} \to \mathcal{C}$ defined in an obvious manner. \begin{definition} \label{definition-faithful} Let $F : \mathcal{A} \to \mathcal{B}$ be a functor. \begin{enumerate} \item We say $F$ is {\it faithful} if for any objects $x, y$ of $\Ob(\mathcal{A})$ the map $$F : \Mor_\mathcal{A}(x, y) \to \Mor_\mathcal{B}(F(x), F(y))$$ is injective. \item If these maps are all bijective then $F$ is called {\it fully faithful}. \item The functor $F$ is called {\it essentially surjective} if for any object $y \in \Ob(\mathcal{B})$ there exists an object $x \in \Ob(\mathcal{A})$ such that $F(x)$ is isomorphic to $y$ in $\mathcal{B}$. \end{enumerate} \end{definition} \begin{definition} \label{definition-subcategory} A {\it subcategory} of a category $\mathcal{B}$ is a category $\mathcal{A}$ whose objects and arrows form subsets of the objects and arrows of $\mathcal{B}$ and such that source, target and composition in $\mathcal{A}$ agree with those of $\mathcal{B}$. We say $\mathcal{A}$ is a {\it full subcategory} of $\mathcal{B}$ if $\Mor_\mathcal{A}(x, y) = \Mor_\mathcal{B}(x, y)$ for all $x, y \in \Ob(\mathcal{A})$. We say $\mathcal{A}$ is a {\it strictly full} subcategory of $\mathcal{B}$ if it is a full subcategory and given $x \in \Ob(\mathcal{A})$ any object of $\mathcal{B}$ which is isomorphic to $x$ is also in $\mathcal{A}$. \end{definition} \noindent If $\mathcal{A} \subset \mathcal{B}$ is a subcategory then the identity map is a functor from $\mathcal{A}$ to $\mathcal{B}$. Furthermore a subcategory $\mathcal{A} \subset \mathcal{B}$ is full if and only if the inclusion functor is fully faithful. Note that given a category $\mathcal{B}$ the set of full subcategories of $\mathcal{B}$ is the same as the set of subsets of $\Ob(\mathcal{B})$. \begin{remark} \label{remark-functor-into-sets} Suppose that $\mathcal{A}$ is a category. A functor $F$ from $\mathcal{A}$ to $\textit{Sets}$ is a mathematical object (i.e., it is a set not a class or a formula of set theory, see Sets, Section \ref{sets-section-sets-everything}) even though the category of sets is big''. Namely, the range of $F$ on objects will be a set $F(\Ob(\mathcal{A}))$ and then we may think of $F$ as a functor between $\mathcal{A}$ and the full subcategory of the category of sets whose objects are elements of $F(\Ob(\mathcal{A}))$. \end{remark} \begin{example} \label{example-group-homomorphism-functor} A homomorphism $p : G\to H$ of groups gives rise to a functor between the associated groupoids in Example \ref{example-group-groupoid}. It is faithful (resp.\ fully faithful) if and only if $p$ is injective (resp.\ an isomorphism). \end{example} \begin{example} \label{example-category-over-X} Given a category $\mathcal{C}$ and an object $X\in \Ob(\mathcal{C})$ we define the {\it category of objects over $X$}, denoted $\mathcal{C}/X$ as follows. The objects of $\mathcal{C}/X$ are morphisms $Y\to X$ for some $Y\in \Ob(\mathcal{C})$. Morphisms between objects $Y\to X$ and $Y'\to X$ are morphisms $Y\to Y'$ in $\mathcal{C}$ that make the obvious diagram commute. Note that there is a functor $p_X : \mathcal{C}/X\to \mathcal{C}$ which simply forgets the morphism. Moreover given a morphism $f : X'\to X$ in $\mathcal{C}$ there is an induced functor $F : \mathcal{C}/X' \to \mathcal{C}/X$ obtained by composition with $f$, and $p_X\circ F = p_{X'}$. \end{example} \begin{example} \label{example-category-under-X} Given a category $\mathcal{C}$ and an object $X\in \Ob(\mathcal{C})$ we define the {\it category of objects under $X$}, denoted $X/\mathcal{C}$ as follows. The objects of $X/\mathcal{C}$ are morphisms $X\to Y$ for some $Y\in \Ob(\mathcal{C})$. Morphisms between objects $X\to Y$ and $X\to Y'$ are morphisms $Y\to Y'$ in $\mathcal{C}$ that make the obvious diagram commute. Note that there is a functor $p_X : X/\mathcal{C}\to \mathcal{C}$ which simply forgets the morphism. Moreover given a morphism $f : X'\to X$ in $\mathcal{C}$ there is an induced functor $F : X/\mathcal{C} \to X'/\mathcal{C}$ obtained by composition with $f$, and $p_{X'}\circ F = p_X$. \end{example} \begin{definition} \label{definition-transformation-functors} Let $F, G : \mathcal{A} \to \mathcal{B}$ be functors. A {\it natural transformation}, or a {\it morphism of functors} $t : F \to G$, is a collection $\{t_x\}_{x\in \Ob(\mathcal{A})}$ such that \begin{enumerate} \item $t_x : F(x) \to G(x)$ is a morphism in the category $\mathcal{B}$, and \item for every morphism $\phi : x \to y$ of $\mathcal{A}$ the following diagram is commutative $$\xymatrix{ F(x) \ar[r]^{t_x} \ar[d]_{F(\phi)} & G(x) \ar[d]^{G(\phi)} \\ F(y) \ar[r]^{t_y} & G(y) }$$ \end{enumerate} \end{definition} \noindent Sometimes we use the diagram $$\xymatrix{ \mathcal{A} \rtwocell^F_G{t} & \mathcal{B} }$$ to indicate that $t$ is a morphism from $F$ to $G$. \medskip\noindent Note that every functor $F$ comes with the {\it identity} transformation $\text{id}_F : F \to F$. In addition, given a morphism of functors $t : F \to G$ and a morphism of functors $s : E \to F$ then the {\it composition} $t \circ s$ is defined by the rule $$(t \circ s)_x = t_x \circ s_x : E(x) \to G(x)$$ for $x \in \Ob(\mathcal{A})$. It is easy to verify that this is indeed a morphism of functors from $E$ to $G$. In this way, given categories $\mathcal{A}$ and $\mathcal{B}$ we obtain a new category, namely the category of functors between $\mathcal{A}$ and $\mathcal{B}$. \begin{remark} \label{remark-functors-sets-sets} This is one instance where the same thing does not hold if $\mathcal{A}$ is a big'' category. For example consider functors $\textit{Sets} \to \textit{Sets}$. As we have currently defined it such a functor is a class and not a set. In other words, it is given by a formula in set theory (with some variables equal to specified sets)! It is not a good idea to try to consider all possible formulae of set theory as part of the definition of a mathematical object. The same problem presents itself when considering sheaves on the category of schemes for example. We will come back to this point later. \end{remark} \begin{definition} \label{definition-equivalence-categories} An {\it equivalence of categories} $F : \mathcal{A} \to \mathcal{B}$ is a functor such that there exists a functor $G : \mathcal{B} \to \mathcal{A}$ such that the compositions $F \circ G$ and $G \circ F$ are isomorphic to the identity functors $\text{id}_\mathcal{B}$, respectively $\text{id}_\mathcal{A}$. In this case we say that $G$ is a {\it quasi-inverse} to $F$. \end{definition} \begin{lemma} \label{lemma-construct-quasi-inverse} Let $F : \mathcal{A} \to \mathcal{B}$ be a fully faithful functor. Suppose for every $X \in \Ob(\mathcal{B})$ given an object $j(X)$ of $\mathcal{A}$ and an isomorphism $i_X : X \to F(j(X))$. Then there is a unique functor $j : \mathcal{B} \to \mathcal{A}$ such that $j$ extends the rule on objects, and the isomorphisms $i_X$ define an isomorphism of functors $\text{id}_\mathcal{B} \to F \circ j$. Moreover, $j$ and $F$ are quasi-inverse equivalences of categories. \end{lemma} \begin{proof} This lemma proves itself. \end{proof} \begin{lemma} \label{lemma-equivalence-categories} A functor is an equivalence of categories if and only if it is both fully faithful and essentially surjective. \end{lemma} \begin{proof} Let $F : \mathcal{A} \to \mathcal{B}$ be essentially surjective and fully faithful. As by convention all categories are small and as $F$ is essentially surjective we can, using the axiom of choice, choose for every $X \in \Ob(\mathcal{B})$ an object $j(X)$ of $\mathcal{A}$ and an isomorphism $i_X : X \to F(j(X))$. Then we apply Lemma \ref{lemma-construct-quasi-inverse} using that $F$ is fully faithful. \end{proof} \begin{definition} \label{definition-product-category} Let $\mathcal{A}$, $\mathcal{B}$ be categories. We define the {\it product category} $\mathcal{A} \times \mathcal{B}$ to be the category with objects $\Ob(\mathcal{A} \times \mathcal{B}) = \Ob(\mathcal{A}) \times \Ob(\mathcal{B})$ and $$\Mor_{\mathcal{A} \times \mathcal{B}}((x, y), (x', y')) := \Mor_\mathcal{A}(x, x')\times \Mor_\mathcal{B}(y, y').$$ Composition is defined componentwise. \end{definition} \section{Opposite Categories and the Yoneda Lemma} \label{section-opposite} \begin{definition} \label{definition-opposite} Given a category $\mathcal{C}$ the {\it opposite category} $\mathcal{C}^{opp}$ is the category with the same objects as $\mathcal{C}$ but all morphisms reversed. \end{definition} \noindent In other words $\Mor_{\mathcal{C}^{opp}}(x, y) = \Mor_\mathcal{C}(y, x)$. Composition in $\mathcal{C}^{opp}$ is the same as in $\mathcal{C}$ except backwards: if $\phi : y \to z$ and $\psi : x \to y$ are morphisms in $\mathcal{C}^{opp}$, in other words arrows $z \to y$ and $y \to x$ in $\mathcal{C}$, then $\phi \circ^{opp} \psi$ is the morphism $x \to z$ of $\mathcal{C}^{opp}$ which corresponds to the composition $z \to y \to x$ in $\mathcal{C}$. \begin{definition} \label{definition-contravariant} Let $\mathcal{C}$, $\mathcal{S}$ be categories. A {\it contravariant} functor $F$ from $\mathcal{C}$ to $\mathcal{S}$ is a functor $\mathcal{C}^{opp}\to \mathcal{S}$. \end{definition} \noindent Concretely, a contravariant functor $F$ is given by a map $F : \Ob(\mathcal{C}) \to \Ob(\mathcal{S})$ and for every morphism $\psi : x \to y$ in $\mathcal{C}$ a morphism $F(\psi) : F(y) \to F(x)$. These should satisfy the property that, given another morphism $\phi : y \to z$, we have $F(\phi \circ \psi) = F(\psi) \circ F(\phi)$ as morphisms $F(z) \to F(x)$. (Note the reverse of order.) \begin{definition} \label{definition-presheaf} Let $\mathcal{C}$ be a category. \begin{enumerate} \item A {\it presheaf of sets on $\mathcal{C}$} or simply a {\it presheaf} is a contravariant functor $F$ from $\mathcal{C}$ to $\textit{Sets}$. \item The category of presheaves is denoted $\textit{PSh}(\mathcal{C})$. \end{enumerate} \end{definition} \noindent Of course the category of presheaves is a proper class. \begin{example} \label{example-hom-functor} Functor of points. For any $U\in \Ob(\mathcal{C})$ there is a contravariant functor $$\begin{matrix} h_U & : & \mathcal{C} & \longrightarrow & \textit{Sets} \\ & & X & \longmapsto & \Mor_\mathcal{C}(X, U) \end{matrix}$$ which takes an object $X$ to the set $\Mor_\mathcal{C}(X, U)$. In other words $h_U$ is a presheaf. Given a morphism $f : X\to Y$ the corresponding map $h_U(f) : \Mor_\mathcal{C}(Y, U)\to \Mor_\mathcal{C}(X, U)$ takes $\phi$ to $\phi\circ f$. We will always denote this presheaf $h_U : \mathcal{C}^{opp} \to \textit{Sets}$. It is called the {\it representable presheaf} associated to $U$. If $\mathcal{C}$ is the category of schemes this functor is sometimes referred to as the \emph{functor of points} of $U$. \end{example} \noindent Note that given a morphism $\phi : U \to V$ in $\mathcal{C}$ we get a corresponding natural transformation of functors $h(\phi) : h_U \to h_V$ defined simply by composing with the morphism $U \to V$. It is trivial to see that this turns composition of morphisms in $\mathcal{C}$ into composition of transformations of functors. In other words we get a functor $$h : \mathcal{C} \longrightarrow \text{Fun}(\mathcal{C}^{opp}, \textit{Sets}) = \textit{PSh}(\mathcal{C})$$ Note that the target is a big'' category, see Remark \ref{remark-big-categories}. On the other hand, $h$ is an actual mathematical object (i.e.\ a set), compare Remark \ref{remark-functor-into-sets}. \begin{lemma}[Yoneda lemma] \label{lemma-yoneda} \begin{reference} Appeared in some form in \cite{Yoneda-homology}. Used by Grothendieck in a generalized form in \cite{Gr-II}. \end{reference} Let $U, V \in \Ob(\mathcal{C})$. Given any morphism of functors $s : h_U \to h_V$ there is a unique morphism $\phi : U \to V$ such that $h(\phi) = s$. In other words the functor $h$ is fully faithful. More generally, given any contravariant functor $F$ and any object $U$ of $\mathcal{C}$ we have a natural bijection $$\Mor_{\textit{PSh}(\mathcal{C})}(h_U, F) \longrightarrow F(U), \quad s \longmapsto s_U(\text{id}_U).$$ \end{lemma} \begin{proof} For the first statement, just take $\phi = s_U(\text{id}_U) \in \Mor_\mathcal{C}(U, V)$. For the second statement, given $\xi \in F(U)$ define $s$ by $s_V : h_U(V) \to F(V)$ by sending the element $f : V \to U$ of $h_U(V) = \Mor_\mathcal{C}(V, U)$ to $F(f)(\xi)$. \end{proof} \begin{definition} \label{definition-representable-functor} A contravariant functor $F : \mathcal{C}\to \textit{Sets}$ is said to be {\it representable} if it is isomorphic to the functor of points $h_U$ for some object $U$ of $\mathcal{C}$. \end{definition} \noindent Let $\mathcal{C}$ be a category and let $F : \mathcal{C}^{opp} \to \textit{Sets}$ be a representable functor. Choose an object $U$ of $\mathcal{C}$ and an isomorphism $s : h_U \to F$. The Yoneda lemma guarantees that the pair $(U, s)$ is unique up to unique isomorphism. The object $U$ is called an object {\it representing} $F$. By the Yoneda lemma the transformation $s$ corresponds to a unique element $\xi \in F(U)$. This element is called the {\it universal object}. It has the property that for $V \in \Ob(\mathcal{C})$ the map $$\Mor_\mathcal{C}(V, U) \longrightarrow F(V),\quad (f : V \to U) \longmapsto F(f)(\xi)$$ is a bijection. Thus $\xi$ is universal in the sense that every element of $F(V)$ is equal to the image of $\xi$ via $F(f)$ for a unique morphism $f : V \to U$ in $\mathcal{C}$. \section{Products of pairs} \label{section-products-pairs} \begin{definition} \label{definition-products} Let $x, y\in \Ob(\mathcal{C})$. A {\it product} of $x$ and $y$ is an object $x \times y \in \Ob(\mathcal{C})$ together with morphisms $p\in \Mor_{\mathcal C}(x \times y, x)$ and $q\in\Mor_{\mathcal C}(x \times y, y)$ such that the following universal property holds: for any $w\in \Ob(\mathcal{C})$ and morphisms $\alpha \in \Mor_{\mathcal C}(w, x)$ and $\beta \in \Mor_\mathcal{C}(w, y)$ there is a unique $\gamma\in \Mor_{\mathcal C}(w, x \times y)$ making the diagram $$\xymatrix{ w \ar[rrrd]^\beta \ar@{-->}[rrd]_\gamma \ar[rrdd]_\alpha & & \\ & & x \times y \ar[d]_p \ar[r]_q & y \\ & & x & }$$ commute. \end{definition} \noindent If a product exists it is unique up to unique isomorphism. This follows from the Yoneda lemma as the definition requires $x \times y$ to be an object of $\mathcal{C}$ such that $$h_{x \times y}(w) = h_x(w) \times h_y(w)$$ functorially in $w$. In other words the product $x \times y$ is an object representing the functor $w \mapsto h_x(w) \times h_y(w)$. \begin{definition} \label{definition-has-products-of-pairs} We say the category $\mathcal{C}$ {\it has products of pairs of objects} if a product $x \times y$ exists for any $x, y \in \Ob(\mathcal{C})$. \end{definition} \noindent We use this terminology to distinguish this notion from the notion of having products'' or having finite products'' which usually means something else (in particular it always implies there exists a final object). \section{Coproducts of pairs} \label{section-coproducts-pairs} \begin{definition} \label{definition-coproducts} Let $x, y \in \Ob(\mathcal{C})$. A {\it coproduct}, or {\it amalgamated sum} of $x$ and $y$ is an object $x \amalg y \in \Ob(\mathcal{C})$ together with morphisms $i \in \Mor_{\mathcal C}(x, x \amalg y)$ and $j \in \Mor_{\mathcal C}(y, x \amalg y)$ such that the following universal property holds: for any $w \in \Ob(\mathcal{C})$ and morphisms $\alpha \in \Mor_{\mathcal C}(x, w)$ and $\beta \in \Mor_\mathcal{C}(y, w)$ there is a unique $\gamma \in \Mor_{\mathcal C}(x \amalg y, w)$ making the diagram $$\xymatrix{ & y \ar[d]^j \ar[rrdd]^\beta \\ x \ar[r]^i \ar[rrrd]_\alpha & x \amalg y \ar@{-->}[rrd]^\gamma \\ & & & w }$$ commute. \end{definition} \noindent If a coproduct exists it is unique up to unique isomorphism. This follows from the Yoneda lemma (applied to the opposite category) as the definition requires $x \amalg y$ to be an object of $\mathcal{C}$ such that $$\Mor_\mathcal{C}(x \amalg y, w) = \Mor_\mathcal{C}(x, w) \times \Mor_\mathcal{C}(y, w)$$ functorially in $w$. \begin{definition} \label{definition-has-coproducts-of-pairs} We say the category $\mathcal{C}$ {\it has coproducts of pairs of objects} if a coproduct $x \amalg y$ exists for any $x, y \in \Ob(\mathcal{C})$. \end{definition} \noindent We use this terminology to distinguish this notion from the notion of having coproducts'' or having finite coproducts'' which usually means something else (in particular it always implies there exists an initial object in $\mathcal{C}$). \section{Fibre products} \label{section-fibre-products} \begin{definition} \label{definition-fibre-products} Let $x, y, z\in \Ob(\mathcal{C})$, $f\in \Mor_\mathcal{C}(x, y)$ and $g\in \Mor_{\mathcal C}(z, y)$. A {\it fibre product} of $f$ and $g$ is an object $x \times_y z\in \Ob(\mathcal{C})$ together with morphisms $p \in \Mor_{\mathcal C}(x \times_y z, x)$ and $q \in \Mor_{\mathcal C}(x \times_y z, z)$ making the diagram $$\xymatrix{ x \times_y z \ar[r]_q \ar[d]_p & z \ar[d]^g \\ x \ar[r]^f & y }$$ commute, and such that the following universal property holds: for any $w\in \Ob(\mathcal{C})$ and morphisms $\alpha \in \Mor_{\mathcal C}(w, x)$ and $\beta \in \Mor_\mathcal{C}(w, z)$ with $f \circ \alpha = g \circ \beta$ there is a unique $\gamma \in \Mor_{\mathcal C}(w, x \times_y z)$ making the diagram $$\xymatrix{ w \ar[rrrd]^\beta \ar@{-->}[rrd]_\gamma \ar[rrdd]_\alpha & & \\ & & x \times_y z \ar[d]^p \ar[r]_q & z \ar[d]^g \\ & & x \ar[r]^f & y }$$ commute. \end{definition} \noindent If a fibre product exists it is unique up to unique isomorphism. This follows from the Yoneda lemma as the definition requires $x \times_y z$ to be an object of $\mathcal{C}$ such that $$h_{x \times_y z}(w) = h_x(w) \times_{h_y(w)} h_z(w)$$ functorially in $w$. In other words the fibre product $x \times_y z$ is an object representing the functor $w \mapsto h_x(w) \times_{h_y(w)} h_z(w)$. \begin{definition} \label{definition-cartesian} We say a commutative diagram $$\xymatrix{ w \ar[r] \ar[d] & z \ar[d] \\ x \ar[r] & y }$$ in a category is {\it cartesian} if $w$ and the morphisms $w \to x$ and $w \to z$ form a fibre product of the morphisms $x \to y$ and $z \to y$. \end{definition} \begin{definition} \label{definition-has-fibre-products} We say the category $\mathcal{C}$ {\it has fibre products} if the fibre product exists for any $f\in \Mor_{\mathcal C}(x, y)$ and $g\in \Mor_{\mathcal C}(z, y)$. \end{definition} \begin{definition} \label{definition-representable-morphism} A morphism $f : x \to y$ of a category $\mathcal{C}$ is said to be {\it representable} if for every morphism $z \to y$ in $\mathcal{C}$ the fibre product $x \times_y z$ exists. \end{definition} \begin{lemma} \label{lemma-composition-representable} Let $\mathcal{C}$ be a category. Let $f : x \to y$, and $g : y \to z$ be representable. Then $g \circ f : x \to z$ is representable. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{lemma} \label{lemma-base-change-representable} Let $\mathcal{C}$ be a category. Let $f : x \to y$ be representable. Let $y' \to y$ be a morphism of $\mathcal{C}$. Then the morphism $x' := x \times_y y' \to y'$ is representable also. \end{lemma} \begin{proof} Let $z \to y'$ be a morphism. The fibre product $x' \times_{y'} z$ is supposed to represent the functor \begin{eqnarray*} w & \mapsto & h_{x'}(w)\times_{h_{y'}(w)} h_z(w) \\ & = & (h_x(w) \times_{h_y(w)} h_{y'}(w)) \times_{h_{y'}(w)} h_z(w) \\ & = & h_x(w) \times_{h_y(w)} h_z(w) \end{eqnarray*} which is representable by assumption. \end{proof} \section{Examples of fibre products} \label{section-example-fibre-products} \noindent In this section we list examples of fibre products and we describe them. \medskip\noindent As a really trivial first example we observe that the category of sets has fibred products and hence every morphism is representable. Namely, if $f : X \to Y$ and $g : Z \to Y$ are maps of sets then we define $X \times_Y Z$ as the subset of $X \times Z$ consisting of pairs $(x, z)$ such that $f(x) = g(z)$. The morphisms $p : X \times_Y Z \to X$ and $q : X \times_Y Z \to Z$ are the projection maps $(x, z) \mapsto x$, and $(x, z) \mapsto z$. Finally, if $\alpha : W \to X$ and $\beta : W \to Z$ are morphisms such that $f \circ \alpha = g \circ \beta$ then the map $W \to X \times Z$, $w\mapsto (\alpha(w), \beta(w))$ obviously ends up in $X \times_Y Z$ as desired. \medskip\noindent In many categories whose objects are sets endowed with certain types of algebraic structures the fibre product of the underlying sets also provides the fibre product in the category. For example, suppose that $X$, $Y$ and $Z$ above are groups and that $f$, $g$ are homomorphisms of groups. Then the set-theoretic fibre product $X \times_Y Z$ inherits the structure of a group, simply by defining the product of two pairs by the formula $(x, z) \cdot (x', z') = (xx', zz')$. Here we list those categories for which a similar reasoning works. \begin{enumerate} \item The category $\textit{Groups}$ of groups. \item The category $G\textit{-Sets}$ of sets endowed with a left $G$-action for some fixed group $G$. \item The category of rings. \item The category of $R$-modules given a ring $R$. \end{enumerate} \section{Fibre products and representability} \label{section-representable-map-presheaves} \noindent In this section we work out fibre products in the category of contravariant functors from a category to the category of sets. This will later be superseded during the discussion of sites, presheaves, sheaves. Of some interest is the notion of a representable morphism'' between such functors. \begin{lemma} \label{lemma-fibre-product-presheaves} Let $\mathcal{C}$ be a category. Let $F, G, H : \mathcal{C}^{opp} \to \textit{Sets}$ be functors. Let $a : F \to G$ and $b : H \to G$ be transformations of functors. Then the fibre product $F \times_{a, G, b} H$ in the category $\text{Fun}(\mathcal{C}^{opp}, \textit{Sets})$ exists and is given by the formula $$(F \times_{a, G, b} H)(X) = F(X) \times_{a_X, G(X), b_X} H(X)$$ for any object $X$ of $\mathcal{C}$. \end{lemma} \begin{proof} Omitted. \end{proof} \noindent As a special case suppose we have a morphism $a : F \to G$, an object $U \in \Ob(\mathcal{C})$ and an element $\xi \in G(U)$. According to the Yoneda Lemma \ref{lemma-yoneda} this gives a transformation $\xi : h_U \to G$. The fibre product in this case is described by the rule $$(h_U \times_{\xi, G, a} F)(X) = \{ (f, \xi') \mid f : X \to U, \ \xi' \in F(X), \ G(f)(\xi) = a_X(\xi')\}$$ If $F$, $G$ are also representable, then this is the functor representing the fibre product, if it exists, see Section \ref{section-fibre-products}. The analogy with Definition \ref{definition-representable-morphism} prompts us to define a notion of representable transformations. \begin{definition} \label{definition-representable-map-presheaves} Let $\mathcal{C}$ be a category. Let $F, G : \mathcal{C}^{opp} \to \textit{Sets}$ be functors. We say a morphism $a : F \to G$ is {\it representable}, or that {\it $F$ is relatively representable over $G$}, if for every $U \in \Ob(\mathcal{C})$ and any $\xi \in G(U)$ the functor $h_U \times_G F$ is representable. \end{definition} \begin{lemma} \label{lemma-representable-over-representable} Let $\mathcal{C}$ be a category. Let $a : F \to G$ be a morphism of contravariant functors from $\mathcal{C}$ to $\textit{Sets}$. If $a$ is representable, and $G$ is a representable functor, then $F$ is representable. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{lemma} \label{lemma-representable-diagonal} Let $\mathcal{C}$ be a category. Let $F : \mathcal{C}^{opp} \to \textit{Sets}$ be a functor. Assume $\mathcal{C}$ has products of pairs of objects and fibre products. The following are equivalent: \begin{enumerate} \item the diagonal $\Delta : F \to F \times F$ is representable, \item for every $U$ in $\mathcal{C}$, and any $\xi \in F(U)$ the map $\xi : h_U \to F$ is representable, \item for every pair $U, V$ in $\mathcal{C}$ and any $\xi \in F(U)$, $\xi' \in F(V)$ the fibre product $h_U \times_{\xi, F, \xi'} h_V$ is representable. \end{enumerate} \end{lemma} \begin{proof} We will continue to use the Yoneda lemma to identify $F(U)$ with transformations $h_U \to F$ of functors. \medskip\noindent Equivalence of (2) and (3). Let $U, \xi, V, \xi'$ be as in (3). Both (2) and (3) tell us exactly that $h_U \times_{\xi, F, \xi'} h_V$ is representable; the only difference is that the statement (3) is symmetric in $U$ and $V$ whereas (2) is not. \medskip\noindent Assume condition (1). Let $U, \xi, V, \xi'$ be as in (3). Note that $h_U \times h_V = h_{U \times V}$ is representable. Denote $\eta : h_{U \times V} \to F \times F$ the map corresponding to the product $\xi \times \xi' : h_U \times h_V \to F \times F$. Then the fibre product $F \times_{\Delta, F \times F, \eta} h_{U \times V}$ is representable by assumption. This means there exists $W \in \Ob(\mathcal{C})$, morphisms $W \to U$, $W \to V$ and $h_W \to F$ such that $$\xymatrix{ h_W \ar[d] \ar[r] & h_U \times h_V \ar[d]^{\xi \times \xi'} \\ F \ar[r] & F \times F }$$ is cartesian. Using the explicit description of fibre products in Lemma \ref{lemma-fibre-product-presheaves} the reader sees that this implies that $h_W = h_U \times_{\xi, F, \xi'} h_V$ as desired. \medskip\noindent Assume the equivalent conditions (2) and (3). Let $U$ be an object of $\mathcal{C}$ and let $(\xi, \xi') \in (F \times F)(U)$. By (3) the fibre product $h_U \times_{\xi, F, \xi'} h_U$ is representable. Choose an object $W$ and an isomorphism $h_W \to h_U \times_{\xi, F, \xi'} h_U$. The two projections $\text{pr}_i : h_U \times_{\xi, F, \xi'} h_U \to h_U$ correspond to morphisms $p_i : W \to U$ by Yoneda. Consider $W' = W \times_{(p_1, p_2), U \times U} U$. It is formal to show that $W'$ represents $F \times_{\Delta, F \times F} h_U$ because $$h_{W'} = h_W \times_{h_U \times h_U} h_U = (h_U \times_{\xi, F, \xi'} h_U) \times_{h_U \times h_U} h_U = F \times_{F \times F} h_U.$$ Thus $\Delta$ is representable and this finishes the proof. \end{proof} \section{Pushouts} \label{section-pushouts} \noindent The dual notion to fibre products is that of pushouts. \begin{definition} \label{definition-pushouts} Let $x, y, z\in \Ob(\mathcal{C})$, $f\in \Mor_\mathcal{C}(y, x)$ and $g\in \Mor_{\mathcal C}(y, z)$. A {\it pushout} of $f$ and $g$ is an object $x\amalg_y z\in \Ob(\mathcal{C})$ together with morphisms $p\in \Mor_{\mathcal C}(x, x\amalg_y z)$ and $q\in\Mor_{\mathcal C}(z, x\amalg_y z)$ making the diagram $$\xymatrix{ y \ar[r]_g \ar[d]_f & z \ar[d]^q \\ x \ar[r]^p & x\amalg_y z }$$ commute, and such that the following universal property holds: For any $w\in \Ob(\mathcal{C})$ and morphisms $\alpha \in \Mor_{\mathcal C}(x, w)$ and $\beta \in \Mor_\mathcal{C}(z, w)$ with $\alpha \circ f = \beta \circ g$ there is a unique $\gamma\in \Mor_{\mathcal C}(x\amalg_y z, w)$ making the diagram $$\xymatrix{ y \ar[r]_g \ar[d]_f & z \ar[d]^q \ar[rrdd]^\beta & & \\ x \ar[r]^p \ar[rrrd]^\alpha & x \amalg_y z \ar@{-->}[rrd]^\gamma & & \\ & & & w }$$ commute. \end{definition} \noindent It is possible and straightforward to prove the uniqueness of the triple $(x\amalg_y z, p, q)$ up to unique isomorphism (if it exists) by direct arguments. Another possibility is to think of the pushout as the fibre product in the opposite category, thereby getting this uniqueness for free from the discussion in Section \ref{section-fibre-products}. \begin{definition} \label{definition-cocartesian} We say a commutative diagram $$\xymatrix{ y \ar[r] \ar[d] & z \ar[d] \\ x \ar[r] & w }$$ in a category is {\it cocartesian} if $w$ and the morphisms $x \to w$ and $z \to w$ form a pushout of the morphisms $y \to x$ and $y \to z$. \end{definition} \section{Equalizers} \label{section-equalizers} \begin{definition} \label{definition-equalizers} Suppose that $X$, $Y$ are objects of a category $\mathcal{C}$ and that $a, b : X \to Y$ are morphisms. We say a morphism $e : Z \to X$ is an {\it equalizer} for the pair $(a, b)$ if $a \circ e = b \circ e$ and if $(Z, e)$ satisfies the following universal property: For every morphism $t : W \to X$ in $\mathcal{C}$ such that $a \circ t = b \circ t$ there exists a unique morphism $s : W \to Z$ such that $t = e \circ s$. \end{definition} \noindent As in the case of the fibre product above, equalizers when they exist are unique up to unique isomorphism. There is a straightforward generalization of this definition to the case where we have more than $2$ morphisms. \section{Coequalizers} \label{section-coequalizers} \begin{definition} \label{definition-coequalizers} Suppose that $X$, $Y$ are objects of a category $\mathcal{C}$ and that $a, b : X \to Y$ are morphisms. We say a morphism $c : Y \to Z$ is a {\it coequalizer} for the pair $(a, b)$ if $c \circ a = c \circ b$ and if $(Z, c)$ satisfies the following universal property: For every morphism $t : Y \to W$ in $\mathcal{C}$ such that $t \circ a = t \circ b$ there exists a unique morphism $s : Z \to W$ such that $t = s \circ c$. \end{definition} \noindent As in the case of the pushouts above, coequalizers when they exist are unique up to unique isomorphism, and this follows from the uniqueness of equalizers upon considering the opposite category. There is a straightforward generalization of this definition to the case where we have more than $2$ morphisms. \section{Initial and final objects} \label{section-initial-final} \begin{definition} \label{definition-initial-final} Let $\mathcal{C}$ be a category. \begin{enumerate} \item An object $x$ of the category $\mathcal{C}$ is called an {\it initial} object if for every object $y$ of $\mathcal{C}$ there is exactly one morphism $x \to y$. \item An object $x$ of the category $\mathcal{C}$ is called a {\it final} object if for every object $y$ of $\mathcal{C}$ there is exactly one morphism $y \to x$. \end{enumerate} \end{definition} \noindent In the category of sets the empty set $\emptyset$ is an initial object, and in fact the only initial object. Also, any {\it singleton}, i.e., a set with one element, is a final object (so it is not unique). \section{Monomorphisms and Epimorphisms} \label{section-mono-epi} \begin{definition} \label{definition-mono-epi} Let $\mathcal{C}$ be a category and let $f : X \to Y$ be a morphism of $\mathcal{C}$. \begin{enumerate} \item We say that $f$ is a {\it monomorphism} if for every object $W$ and every pair of morphisms $a, b : W \to X$ such that $f \circ a = f \circ b$ we have $a = b$. \item We say that $f$ is an {\it epimorphism} if for every object $W$ and every pair of morphisms $a, b : Y \to W$ such that $a \circ f = b \circ f$ we have $a = b$. \end{enumerate} \end{definition} \begin{example} \label{example-mono-epi-sets} In the category of sets the monomorphisms correspond to injective maps and the epimorphisms correspond to surjective maps. \end{example} \begin{lemma} \label{lemma-characterize-mono-epi} Let $\mathcal{C}$ be a category, and let $f : X \to Y$ be a morphism of $\mathcal{C}$. Then \begin{enumerate} \item $f$ is a monomorphism if and only if $X$ is the fibre product $X \times_Y X$, and \item $f$ is an epimorphism if and only if $Y$ is the pushout $Y \amalg_X Y$. \end{enumerate} \end{lemma} \begin{proof} Omitted. \end{proof} \section{Limits and colimits} \label{section-limits} \noindent Let $\mathcal{C}$ be a category. A {\it diagram} in $\mathcal{C}$ is simply a functor $M : \mathcal{I} \to \mathcal{C}$. We say that $\mathcal{I}$ is the {\it index category} or that $M$ is an $\mathcal{I}$-diagram. We will use the notation $M_i$ to denote the image of the object $i$ of $\mathcal{I}$. Hence for $\phi : i \to i'$ a morphism in $\mathcal{I}$ we have $M(\phi) : M_i \to M_{i'}$. \begin{definition} \label{definition-limit} A {\it limit} of the $\mathcal{I}$-diagram $M$ in the category $\mathcal{C}$ is given by an object $\lim_\mathcal{I} M$ in $\mathcal{C}$ together with morphisms $p_i : \lim_\mathcal{I} M \to M_i$ such that \begin{enumerate} \item for $\phi : i \to i'$ a morphism in $\mathcal{I}$ we have $p_{i'} = M(\phi) \circ p_i$, and \item for any object $W$ in $\mathcal{C}$ and any family of morphisms $q_i : W \to M_i$ (indexed by $i \in \mathcal{I}$) such that for all $\phi : i \to i'$ in $\mathcal{I}$ we have $q_{i'} = M(\phi) \circ q_i$ there exists a unique morphism $q : W \to \lim_\mathcal{I} M$ such that $q_i = p_i \circ q$ for every object $i$ of $\mathcal{I}$. \end{enumerate} \end{definition} \noindent Limits $(\lim_\mathcal{I} M, (p_i)_{i\in \Ob(\mathcal{I})})$ are (if they exist) unique up to unique isomorphism by the uniqueness requirement in the definition. Products of pairs, fibred products, and equalizers are examples of limits. The limit over the empty diagram is a final object of $\mathcal{C}$. In the category of sets all limits exist. The dual notion is that of colimits. \begin{definition} \label{definition-colimit} A {\it colimit} of the $\mathcal{I}$-diagram $M$ in the category $\mathcal{C}$ is given by an object $\colim_\mathcal{I} M$ in $\mathcal{C}$ together with morphisms $s_i : M_i \to \colim_\mathcal{I} M$ such that \begin{enumerate} \item for $\phi : i \to i'$ a morphism in $\mathcal{I}$ we have $s_i = s_{i'} \circ M(\phi)$, and \item for any object $W$ in $\mathcal{C}$ and any family of morphisms $t_i : M_i \to W$ (indexed by $i \in \mathcal{I}$) such that for all $\phi : i \to i'$ in $\mathcal{I}$ we have $t_i = t_{i'} \circ M(\phi)$ there exists a unique morphism $t : \colim_\mathcal{I} M \to W$ such that $t_i = t \circ s_i$ for every object $i$ of $\mathcal{I}$. \end{enumerate} \end{definition} \noindent Colimits $(\colim_\mathcal{I} M, (s_i)_{i\in \Ob(\mathcal{I})})$ are (if they exist) unique up to unique isomorphism by the uniqueness requirement in the definition. Coproducts of pairs, pushouts, and coequalizers are examples of colimits. The colimit over an empty diagram is an initial object of $\mathcal{C}$. In the category of sets all colimits exist. \begin{remark} \label{remark-diagram-small} The index category of a (co)limit will never be allowed to have a proper class of objects. In this project it means that it cannot be one of the categories listed in Remark \ref{remark-big-categories} \end{remark} \begin{remark} \label{remark-limit-colim} We often write $\lim_i M_i$, $\colim_i M_i$, $\lim_{i\in \mathcal{I}} M_i$, or $\colim_{i\in \mathcal{I}} M_i$ instead of the versions indexed by $\mathcal{I}$. Using this notation, and using the description of limits and colimits of sets in Section \ref{section-limit-sets} below, we can say the following. Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram. \begin{enumerate} \item The object $\lim_i M_i$ if it exists satisfies the following property $$\Mor_\mathcal{C}(W, \lim_i M_i) = \lim_i \Mor_\mathcal{C}(W, M_i)$$ where the limit on the right takes place in the category of sets. \item The object $\colim_i M_i$ if it exists satisfies the following property $$\Mor_\mathcal{C}(\colim_i M_i, W) = \lim_{i\in \mathcal{I}^\text{opp}} \Mor_\mathcal{C}(M_i, W)$$ where on the right we have the limit over the opposite category with value in the category of sets. \end{enumerate} By the Yoneda lemma (and its dual) this formula completely determines the limit, respectively the colimit. \end{remark} \noindent As an application of the notions of limits and colimits we define products and coproducts. \begin{definition} \label{definition-product} Suppose that $I$ is a set, and suppose given for every $i \in I$ an object $M_i$ of the category $\mathcal{C}$. A {\it product} $\prod_{i\in I} M_i$ is by definition $\lim_\mathcal{I} M$ (if it exists) where $\mathcal{I}$ is the category having only identities as morphisms and having the elements of $I$ as objects. \end{definition} \noindent An important special case is where $I = \emptyset$ in which case the product is a final object of the category. The morphisms $p_i : \prod M_i \to M_i$ are called the {\it projection morphisms}. \begin{definition} \label{definition-coproduct} Suppose that $I$ is a set, and suppose given for every $i \in I$ an object $M_i$ of the category $\mathcal{C}$. A {\it coproduct} $\coprod_{i\in I} M_i$ is by definition $\colim_\mathcal{I} M$ (if it exists) where $\mathcal{I}$ is the category having only identities as morphisms and having the elements of $I$ as objects. \end{definition} \noindent An important special case is where $I = \emptyset$ in which case the coproduct is an initial object of the category. Note that the coproduct comes equipped with morphisms $M_i \to \coprod M_i$. These are sometimes called the {\it coprojections}. \begin{lemma} \label{lemma-functorial-colimit} Suppose that $M : \mathcal{I} \to \mathcal{C}$, and $N : \mathcal{J} \to \mathcal{C}$ are diagrams whose colimits exist. Suppose $H : \mathcal{I} \to \mathcal{J}$ is a functor, and suppose $t : M \to N \circ H$ is a transformation of functors. Then there is a unique morphism $$\theta : \colim_\mathcal{I} M \longrightarrow \colim_\mathcal{J} N$$ such that all the diagrams $$\xymatrix{ M_i \ar[d]_{t_i} \ar[r] & \colim_\mathcal{I} M \ar[d]^{\theta} \\ N_{H(i)} \ar[r] & \colim_\mathcal{J} N }$$ commute. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{lemma} \label{lemma-functorial-limit} Suppose that $M : \mathcal{I} \to \mathcal{C}$, and $N : \mathcal{J} \to \mathcal{C}$ are diagrams whose limits exist. Suppose $H : \mathcal{I} \to \mathcal{J}$ is a functor, and suppose $t : N \circ H \to M$ is a transformation of functors. Then there is a unique morphism $$\theta : \lim_\mathcal{J} N \longrightarrow \lim_\mathcal{I} M$$ such that all the diagrams $$\xymatrix{ \lim_\mathcal{J} N \ar[d]^{\theta} \ar[r] & N_{H(i)} \ar[d]_{t_i} \\ \lim_\mathcal{I} M \ar[r] & M_i }$$ commute. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{lemma} \label{lemma-colimits-commute} Let $\mathcal{I}$, $\mathcal{J}$ be index categories. Let $M : \mathcal{I} \times \mathcal{J} \to \mathcal{C}$ be a functor. We have $$\colim_i \colim_j M_{i, j} = \colim_{i, j} M_{i, j} = \colim_j \colim_i M_{i, j}$$ provided all the indicated colimits exist. Similar for limits. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{lemma} \label{lemma-limits-products-equalizers} Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram. Write $I = \Ob(\mathcal{I})$ and $A = \text{Arrow}(\mathcal{I})$. Denote $s, t : A \to I$ the source and target maps. Suppose that $\prod_{i \in I} M_i$ and $\prod_{a \in A} M_{t(a)}$ exist. Suppose that the equalizer of $$\xymatrix{ \prod_{i \in I} M_i \ar@<1ex>[r]^\phi \ar@<-1ex>[r]_\psi & \prod_{a \in A} M_{t(a)} }$$ exists, where the morphisms are determined by their components as follows: $p_a \circ \psi = M(a) \circ p_{s(a)}$ and $p_a \circ \phi = p_{t(a)}$. Then this equalizer is the limit of the diagram. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{lemma} \label{lemma-colimits-coproducts-coequalizers} \begin{slogan} If all coproducts and coequalizers exist, all colimits exist. \end{slogan} Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram. Write $I = \Ob(\mathcal{I})$ and $A = \text{Arrow}(\mathcal{I})$. Denote $s, t : A \to I$ the source and target maps. Suppose that $\coprod_{i \in I} M_i$ and $\coprod_{a \in A} M_{s(a)}$ exist. Suppose that the coequalizer of $$\xymatrix{ \coprod_{a \in A} M_{s(a)} \ar@<1ex>[r]^\phi \ar@<-1ex>[r]_\psi & \coprod_{i \in I} M_i }$$ exists, where the morphisms are determined by their components as follows: The component $M_{s(a)}$ maps via $\psi$ to the component $M_{t(a)}$ via the morphism $a$. The component $M_{s(a)}$ maps via $\phi$ to the component $M_{s(a)}$ by the identity morphism. Then this coequalizer is the colimit of the diagram. \end{lemma} \begin{proof} Omitted. \end{proof} \section{Limits and colimits in the category of sets} \label{section-limit-sets} \noindent Not only do limits and colimits exist in $\textit{Sets}$ but they are also easy to describe. Namely, let $M : \mathcal{I} \to \textit{Sets}$, $i \mapsto M_i$ be a diagram of sets. Denote $I = \Ob(\mathcal{I})$. The limit is described as $$\lim_\mathcal{I} M = \{ (m_i)_{i\in I} \in \prod\nolimits_{i\in I} M_i \mid \forall \phi : i \to i' \text{ in }\mathcal{I}, M(\phi)(m_i) = m_{i'} \}.$$ So we think of an element of the limit as a compatible system of elements of all the sets $M_i$. \medskip\noindent On the other hand, the colimit is $$\colim_\mathcal{I} M = (\coprod\nolimits_{i\in I} M_i)/\sim$$ where the equivalence relation $\sim$ is the equivalence relation generated by setting $m_i \sim m_{i'}$ if $m_i \in M_i$, $m_{i'} \in M_{i'}$ and $M(\phi)(m_i) = m_{i'}$ for some $\phi : i \to i'$. In other words, $m_i \in M_i$ and $m_{i'} \in M_{i'}$ are equivalent if there is a chain of morphisms in $\mathcal{I}$ $$\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 $m_{i_j} \in M_{i_j}$ mapping to each other under the maps $M_{i_{2k-1}} \to M_{i_{2k-2}}$ and $M_{i_{2k-1}} \to M_{i_{2k}}$ induced from the maps in $\mathcal{I}$ above. \medskip\noindent This is not a very pleasant type of object to work with. But if the diagram is filtered then it is much easier to describe. We will explain this in Section \ref{section-directed-colimits}. \section{Connected limits} \label{section-connected-limits} \noindent A (co)limit is called connected if its index category is connected. \begin{definition} \label{definition-category-connected} We say that a category $\mathcal{I}$ is {\it connected} if the equivalence relation generated by $x \sim y \Leftrightarrow \Mor_\mathcal{I}(x, y) \not = \emptyset$ has exactly one equivalence class. \end{definition} \noindent Here we follow the convention of Topology, Definition \ref{topology-definition-connected-components} that connected spaces are nonempty. The following in some vague sense characterizes connected limits. \begin{lemma} \label{lemma-connected-limit-over-X} Let $\mathcal{C}$ be a category. Let $X$ be an object of $\mathcal{C}$. Let $M : \mathcal{I} \to \mathcal{C}/X$ be a diagram in the category of objects over $X$. If the index category $\mathcal{I}$ is connected and the limit of $M$ exists in $\mathcal{C}/X$, then the limit of the composition $\mathcal{I} \to \mathcal{C}/X \to \mathcal{C}$ exists and is the same. \end{lemma} \begin{proof} Let $M \to X$ be an object representing the limit in $\mathcal{C}/X$. Consider the functor $$W \longmapsto \lim_i \Mor_\mathcal{C}(W, M_i).$$ Let $(\varphi_i)$ be an element of the set on the right. Since each $M_i$ comes equipped with a morphism $s_i : M_i \to X$ we get morphisms $f_i = s_i \circ \varphi_i : W \to X$. But as $\mathcal{I}$ is connected we see that all $f_i$ are equal. Since $\mathcal{I}$ is nonempty there is at least one $f_i$. Hence this common value $W \to X$ defines the structure of an object of $W$ in $\mathcal{C}/X$ and $(\varphi_i)$ defines is an element of $\lim_i \Mor_{\mathcal{C}/X}(W, M_i)$. Thus we obtain a unique morphism $\phi : W \to M$ such that $\varphi_i$ is the composition of $\phi$ with $M \to M_i$ as desired. \end{proof} \begin{lemma} \label{lemma-connected-colimit-under-X} Let $\mathcal{C}$ be a category. Let $X$ be an object of $\mathcal{C}$. Let $M : \mathcal{I} \to X/\mathcal{C}$ be a diagram in the category of objects under $X$. If the index category $\mathcal{I}$ is connected and the colimit of $M$ exists in $X/\mathcal{C}$, then the colimit of the composition $\mathcal{I} \to X/\mathcal{C} \to \mathcal{C}$ exists and is the same. \end{lemma} \begin{proof} Omitted. Hint: This lemma is dual to Lemma \ref{lemma-connected-limit-over-X}. \end{proof} \section{Cofinal and initial categories} \label{section-cofinal} \noindent In the literature sometimes the word final'' is used instead of cofinal in the following definition. \begin{definition} \label{definition-cofinal} Let $H : \mathcal{I} \to \mathcal{J}$ be a functor between categories. We say {\it $\mathcal{I}$ is cofinal in $\mathcal{J}$} or that $H$ is {\it cofinal} if \begin{enumerate} \item for all $y \in \Ob(\mathcal{J})$ there exists a $x \in \Ob(\mathcal{I})$ and a morphism $y \to H(x)$, and \item given $y \in \Ob(\mathcal{J})$, $x, x' \in \Ob(\mathcal{I})$ and morphisms $y \to H(x)$ and $y \to H(x')$ there exists a sequence of morphisms $$x = x_0 \leftarrow x_1 \rightarrow x_2 \leftarrow x_3 \rightarrow \ldots \rightarrow x_{2n} = x'$$ in $\mathcal{I}$ and morphisms $y \to H(x_i)$ in $\mathcal{J}$ such that the diagrams $$\xymatrix{ & y \ar[ld] \ar[d] \ar[rd] \\ H(x_{2k}) & H(x_{2k + 1}) \ar[l] \ar[r] & H(x_{2k + 2}) }$$ commute for $k = 0, \ldots, n - 1$. \end{enumerate} \end{definition} \begin{lemma} \label{lemma-cofinal} Let $H : \mathcal{I} \to \mathcal{J}$ be a functor of categories. Assume $\mathcal{I}$ is cofinal in $\mathcal{J}$. Then for every diagram $M : \mathcal{J} \to \mathcal{C}$ we have a canonical isomorphism $$\colim_\mathcal{I} M \circ H = \colim_\mathcal{J} M$$ if either side exists. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{definition} \label{definition-initial} Let $H : \mathcal{I} \to \mathcal{J}$ be a functor between categories. We say {\it $\mathcal{I}$ is initial in $\mathcal{J}$} or that $H$ is {\it initial} if \begin{enumerate} \item for all $y \in \Ob(\mathcal{J})$ there exists a $x \in \Ob(\mathcal{I})$ and a morphism $H(x) \to y$, \item for any $y \in \Ob(\mathcal{J})$, $x , x' \in \Ob(\mathcal{I})$ and morphisms $H(x) \to y$, $H(x') \to y$ in $\mathcal{J}$ there exists a sequence of morphisms $$x = x_0 \leftarrow x_1 \rightarrow x_2 \leftarrow x_3 \rightarrow \ldots \rightarrow x_{2n} = x'$$ in $\mathcal{I}$ and morphisms $H(x_i) \to y$ in $\mathcal{J}$ such that the diagrams $$\xymatrix{ H(x_{2k}) \ar[rd] & H(x_{2k + 1}) \ar[l] \ar[r] \ar[d] & H(x_{2k + 2}) \ar[ld] \\ & y }$$ commute for $k = 0, \ldots, n - 1$. \end{enumerate} \end{definition} \noindent This is just the dual notion to cofinal'' functors. \begin{lemma} \label{lemma-initial} Let $H : \mathcal{I} \to \mathcal{J}$ be a functor of categories. Assume $\mathcal{I}$ is initial in $\mathcal{J}$. Then for every diagram $M : \mathcal{J} \to \mathcal{C}$ we have a canonical isomorphism $$\lim_\mathcal{I} M \circ H = \lim_\mathcal{J} M$$ if either side exists. \end{lemma} \begin{proof} Omitted. \end{proof} \begin{lemma} \label{lemma-colimit-constant-connected-fibers} Let $F : \mathcal{I} \to \mathcal{I}'$ be a functor. Assume \begin{enumerate} \item the fibre categories (see Definition \ref{definition-fibre-category}) of $\mathcal{I}$ over $\mathcal{I}'$ are all connected, and \item for every morphism $\alpha' : x' \to y'$ in $\mathcal{I}'$ there exist a morphism $\alpha : x \to y$ in $\mathcal{I}$ such that $F(\alpha) = \alpha'$. \end{enumerate} Then for every diagram $M : \mathcal{I}' \to \mathcal{C}$ the colimit $\colim_\mathcal{I} M \circ F$ exists if and only if $\colim_{\mathcal{I}'} M$ exists and if so these colimits agree. \end{lemma} \begin{proof} One can prove this by showing that $\mathcal{I}$ is cofinal in $\mathcal{I}'$ and applying Lemma \ref{lemma-cofinal}. But we can also prove it directly as follows. It suffices to show that for any object $T$ of $\mathcal{C}$ we have $$\lim_{\mathcal{I}^{opp}} \Mor_\mathcal{C}(M_{F(i)}, T) = \lim_{(\mathcal{I}')^{opp}} \Mor_\mathcal{C}(M_{i'}, T)$$ If $(g_{i'})_{i' \in \Ob(\mathcal{I}')}$ is an element of the right hand side, then setting $f_i = g_{F(i)}$ we obtain an element $(f_i)_{i \in \Ob(\mathcal{I})}$ of the left hand side. Conversely, let $(f_i)_{i \in \Ob(\mathcal{I})}$ be an element of the left hand side. Note that on each (connected) fibre category $\mathcal{I}_{i'}$ the functor $M \circ F$ is constant with value $M_{i'}$. Hence the morphisms $f_i$ for $i \in \Ob(\mathcal{I})$ with $F(i) = i'$ are all the same and determine a well defined morphism $g_{i'} : M_{i'} \to T$. By assumption (2) the collection $(g_{i'})_{i' \in \Ob(\mathcal{I}')}$ defines an element of the right hand side. \end{proof} \begin{lemma} \label{lemma-product-with-connected} Let $\mathcal{I}$ and $\mathcal{J}$ be a categories and denote $p : \mathcal{I} \times \mathcal{J} \to \mathcal{J}$ the projection. If $\mathcal{I}$ is connected, then for a diagram $M : \mathcal{J} \to \mathcal{C}$ the colimit $\colim_\mathcal{J} M$ exists if and only if $\colim_{\mathcal{I} \times \mathcal{J}} M \circ p$ exists and if so these colimits are equal. \end{lemma} \begin{proof} This is a special case of Lemma \ref{lemma-colimit-constant-connected-fibers}. \end{proof} \section{Finite limits and colimits} \label{section-finite-limits} \noindent A {\it finite} (co)limit is a (co)limit whose diagram category is finite, i.e., the diagram category has finitely many objects and finitely many morphisms. A (co)limit is called {\it nonempty} if the index category is nonempty. A (co)limit is called {\it connected} if the index category is connected, see Definition \ref{definition-category-connected}. It turns out that there are enough'' finite diagram categories. \begin{lemma} \label{lemma-finite-diagram-category} Let $\mathcal{I}$ be a category with \begin{enumerate} \item $\Ob(\mathcal{I})$ is finite, and \item there exist finitely many morphisms $f_1, \ldots, f_m \in \text{Arrows}(\mathcal{I})$ such that every morphism of $\mathcal{I}$ is a composition $f_{j_1} \circ f_{j_2} \circ \ldots \circ f_{j_k}$. \end{enumerate} Then there exists a functor $F : \mathcal{J} \to \mathcal{I}$ such that \begin{enumerate} \item[(a)] $\mathcal{J}$ is a finite category, and \item[(b)] for any diagram $M : \mathcal{I} \to \mathcal{C}$ the (co)limit of $M$ over $\mathcal{I}$ exists if and only if the (co)limit of $M \circ F$ over $\mathcal{J}$ exists and in this case the (co)limits are canonically isomorphic. \end{enumerate} Moreover, $\mathcal{J}$ is connected (resp.\ nonempty) if and only if $\mathcal{I}$ is so. \end{lemma} \begin{proof} Say $\Ob(\mathcal{I}) = \{x_1, \ldots, x_n\}$. Denote $s, t : \{1, \ldots, m\} \to \{1, \ldots, n\}$ the functions such that $f_j : x_{s(j)} \to x_{t(j)}$. We set $\Ob(\mathcal{J}) = \{y_1, \ldots, y_n, z_1, \ldots, z_n\}$ Besides the identity morphisms we introduce morphisms $g_j : y_{s(j)} \to z_{t(j)}$, $j = 1, \ldots, m$ and morphisms $h_i : y_i \to z_i$, $i = 1, \ldots, n$. Since all of the nonidentity morphisms in $\mathcal{J}$ go from a $y$ to a $z$ there are no compositions to define and no associativities to check. Set $F(y_i) = F(z_i) = x_i$. Set $F(g_j) = f_j$ and $F(h_i) = \text{id}_{x_i}$. It is clear that $F$ is a functor. It is clear that $\mathcal{J}$ is finite. It is clear that $\mathcal{J}$ is connected, resp.\ nonempty if and only if $\mathcal{I}$ is so. \medskip\noindent Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram. Consider an object $W$ of $\mathcal{C}$ and morphisms $q_i : W \to M(x_i)$ as in Definition \ref{definition-limit}. Then by taking $q_i : W \to M(F(y_i)) = M(F(z_i)) = M(x_i)$ we obtain a family of maps as in Definition \ref{definition-limit} for the diagram $M \circ F$. Conversely, suppose we are given maps $qy_i : W \to M(F(y_i))$ and $qz_i : W \to M(F(z_i))$ as in Definition \ref{definition-limit} for the diagram $M \circ F$. Since $$M(F(h_i)) = \text{id} : M(F(y_i)) = M(x_i) \longrightarrow M(x_i) = M(F(z_i))$$ we conclude that $qy_i = qz_i$ for all $i$. Set $q_i$ equal to this common value. The compatibility of $q_{s(j)} = qy_{s(j)}$ and $q_{t(j)} = qz_{t(j)}$ with the morphism $M(f_j)$ guarantees that the family $q_i$ is compatible with all morphisms in $\mathcal{I}$ as by assumption every such morphism is a composition of the morphisms $f_j$. Thus we have found a canonical bijection $$\lim_{B \in \Ob(\mathcal{J})} \Mor_\mathcal{C}(W, M(F(B))) = \lim_{A \in \Ob(\mathcal{I})} \Mor_\mathcal{C}(W, M(A))$$ which implies the statement on limits in the lemma. The statement on colimits is proved in the same way (proof omitted). \end{proof} \begin{lemma} \label{lemma-fibre-products-equalizers-exist} Let $\mathcal{C}$ be a category. The following are equivalent: \begin{enumerate} \item Connected finite limits exist in $\mathcal{C}$. \item Equalizers and fibre products exist in $\mathcal{C}$. \end{enumerate} \end{lemma} \begin{proof} Since equalizers and fibre products are finite connected limits we see that (1) implies (2). For the converse, let $\mathcal{I}$ be a finite connected diagram category. Let $F : \mathcal{J} \to \mathcal{I}$ be the functor of diagram categories constructed in the proof of Lemma \ref{lemma-finite-diagram-category}. Then we see that we may replace $\mathcal{I}$ by $\mathcal{J}$. The result is that we may assume that $\Ob(\mathcal{I}) = \{x_1, \ldots, x_n\} \amalg \{y_1, \ldots, y_m\}$ with $n, m \geq 1$ such that all nonidentity morphisms in $\mathcal{I}$ are morphisms $f : x_i \to y_j$ for some $i$ and $j$. \medskip\noindent Suppose that $n > 1$. Since $\mathcal{I}$ is connected there exist indices $i_1, i_2$ and $j_0$ and morphisms $a : x_{i_1} \to y_{j_0}$ and $b : x_{i_2} \to y_{j_0}$. Consider the category $$\mathcal{I}' = \{x\} \amalg \{x_1, \ldots, \hat x_{i_1}, \ldots, \hat x_{i_2}, \ldots x_n\} \amalg \{y_1, \ldots, y_m\}$$ with $$\Mor_{\mathcal{I}'}(x, y_j) = \Mor_\mathcal{I}(x_{i_1}, y_j) \amalg \Mor_\mathcal{I}(x_{i_2}, y_j)$$ and all other morphism sets the same as in $\mathcal{I}$. For any functor $M : \mathcal{I} \to \mathcal{C}$ we can construct a functor $M' : \mathcal{I}' \to \mathcal{C}$ by setting $$M'(x) = M(x_{i_1}) \times_{M(a), M(y_j), M(b)} M(x_{i_2})$$ and for a morphism $f' : x \to y_j$ corresponding to, say, $f : x_{i_1} \to y_j$ we set $M'(f) = M(f) \circ \text{pr}_1$. Then the functor $M$ has a limit if and only if the functor $M'$ has a limit (proof omitted). Hence by induction we reduce to the case $n = 1$. \medskip\noindent If $n = 1$, then the limit of any $M : \mathcal{I} \to \mathcal{C}$ is the successive equalizer of pairs of maps $x_1 \to y_j$ hence exists by assumption. \end{proof} \begin{lemma} \label{lemma-almost-finite-limits-exist} Let $\mathcal{C}$ be a category. The following are equivalent: \begin{enumerate} \item Nonempty finite limits exist in $\mathcal{C}$. \item Products of pairs and equalizers exist in $\mathcal{C}$. \item Products of pairs and fibre products exist in $\mathcal{C}$. \end{enumerate} \end{lemma} \begin{proof} Since products of pairs, fibre products, and equalizers are limits with nonempty index categories we see that (1) implies both (2) and (3). Assume (2). Then finite nonempty products and equalizers exist. Hence by Lemma \ref{lemma-limits-products-equalizers} we see that finite nonempty limits exist, i.e., (1) holds. Assume (3). If $a, b : A \to B$ are morphisms of $\mathcal{C}$, then the equalizer of $a, b$ is $$(A \times_{a, B, b} A)\times_{(pr_1, pr_2), A \times A, \Delta} A.$$ Thus (3) implies (2), and the lemma is proved. \end{proof} \begin{lemma} \label{lemma-finite-limits-exist} Let $\mathcal{C}$ be a category. The following are equivalent: \begin{enumerate} \item Finite limits exist in $\mathcal{C}$. \item Finite products and equalizers exist. \item The category has a final object and fibred products exist. \end{enumerate} \end{lemma} \begin{proof} Since products of pairs, fibre products, equalizers, and final objects are limits over finite index categories we see that (1) implies both (2) and (3). By Lemma \ref{lemma-limits-products-equalizers} above we see that (2) implies (1). Assume (3). Note that the product $A \times B$ is the fibre product over the final object. If $a, b : A \to B$ are morphisms of $\mathcal{C}$, then the equalizer of $a, b$ is $$(A \times_{a, B, b} A)\times_{(pr_1, pr_2), A \times A, \Delta} A.$$ Thus (3) implies (2) and the lemma is proved. \end{proof} \begin{lemma} \label{lemma-push-outs-coequalizers-exist} Let $\mathcal{C}$ be a category. The following are equivalent: \begin{enumerate} \item Connected finite colimits exist in $\mathcal{C}$. \item Coequalizers and pushouts exist in $\mathcal{C}$. \end{enumerate} \end{lemma} \begin{proof} Omitted. Hint: This is dual to Lemma \ref{lemma-fibre-products-equalizers-exist}. \end{proof} \begin{lemma} \label{lemma-almost-finite-colimits-exist} Let $\mathcal{C}$ be a category. The following are equivalent: \begin{enumerate} \item Nonempty finite colimits exist in $\mathcal{C}$. \item Coproducts of pairs and coequalizers exist in $\mathcal{C}$. \item Coproducts of pairs and pushouts exist in $\mathcal{C}$. \end{enumerate} \end{lemma} \begin{proof} Omitted. Hint: This is the dual of Lemma \ref{lemma-almost-finite-limits-exist}. \end{proof} \begin{lemma} \label{lemma-colimits-exist} Let $\mathcal{C}$ be a category. The following are equivalent: \begin{enumerate} \item Finite colimits exist in $\mathcal{C}$, \item Finite coproducts and coequalizers exist in $\mathcal{C}$, and \item The category has an initial object and pushouts exist. \end{enumerate} \end{lemma} \begin{proof} Omitted. Hint: This is dual to Lemma \ref{lemma-finite-limits-exist}. \end{proof} \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} \section{Cofiltered limits} \label{section-codirected-limits} \noindent Limits are easier to compute or describe when they are over a cofiltered diagram. Here is the definition. \begin{definition} \label{definition-codirected} We say that a diagram $M : \mathcal{I} \to \mathcal{C}$ is {\it codirected} or {\it cofiltered} 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 $z \to x$, $z \to y$, 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 : w \to x$ of $\mathcal{I}$ such that $M(a \circ c) = M(b \circ c)$ as morphisms in $\mathcal{C}$. \end{enumerate} We say that an index category $\mathcal{I}$ is {\it codirected}, or {\it cofiltered} if $\text{id} : \mathcal{I} \to \mathcal{I}$ is cofiltered (in other words you erase the $M$ in part (3) above). \end{definition} \noindent We observe that any diagram with cofiltered index category is cofiltered, and this is how this situation usually occurs. \medskip\noindent As an example of why cofiltered limits of sets are easier'' than general ones, we mention the fact that a cofiltered diagram of finite nonempty sets has nonempty limit (Lemma \ref{lemma-nonempty-limit}). This result does not hold for a general limit of finite nonempty sets. \section{Limits and colimits over preordered sets} \label{section-posets-limits} \noindent A special case of diagrams is given by systems over preordered sets. \begin{definition} \label{definition-directed-set} Let $I$ be a set and let $\leq$ be a binary relation on $I$. \begin{enumerate} \item We say $\leq$ is a {\it preorder} if it is transitive (if $i \leq j$ and $j \leq k$ then $i \leq k$) and reflexive ($i \leq i$ for all $i \in I$). \item A {\it preordered set} is a set endowed with a preorder. \item A {\it directed set} is a preordered set $(I, \leq)$ such that $I$ is not empty and such that $\forall i, j \in I$, there exists $k \in I$ with $i \leq k, j \leq k$. \item We say $\leq$ is a {\it partial order} if it is a preorder which is antisymmetric (if $i \leq j$ and $j \leq i$, then $i = j$). \item A {\it partially ordered set} is a set endowed with a partial order. \item A {\it directed partially ordered set} is a direct set whose ordering is a partial order. \end{enumerate} \end{definition} \noindent It is customary to drop the $\leq$ from the notation when talking about preordered sets, that is, one speaks of the preordered set $I$ rather than of the preordered set $(I, \leq)$. Given a preordered set $I$ the symbol $\geq$ is defined by the rule $i \geq j \Leftrightarrow j \leq i$ for all $i, j \in I$. The phrase partially ordered set'' is sometimes abbreviated to poset''. \medskip\noindent Given a preordered set $I$ we can construct a category: the objects are the elements of $I$, there is exactly one morphism $i \to i'$ if $i \leq i'$, and otherwise none. Conversely, given a category $\mathcal{C}$ with at most one arrow between any two objects, the set $\Ob(\mathcal{C})$ is endowed with a preorder defined by the rule $x \leq y \Leftrightarrow \Mor_\mathcal{C}(x, y) \not = \emptyset$. \begin{definition} \label{definition-system-over-poset} Let $(I, \leq)$ be a preordered set. Let $\mathcal{C}$ be a category. \begin{enumerate} \item A {\it system over $I$ in $\mathcal{C}$}, sometimes called a {\it inductive system over $I$ in $\mathcal{C}$} is given by objects $M_i$ of $\mathcal{C}$ and for every $i \leq i'$ a morphism $f_{ii'} : M_i \to M_{i'}$ such that $f_{ii} = \text{id}$ and such that $f_{ii''} = f_{i'i''} \circ f_{i i'}$ whenever $i \leq i' \leq i''$. \item An {\it inverse system over $I$ in $\mathcal{C}$}, sometimes called a {\it projective system over $I$ in $\mathcal{C}$} is given by objects $M_i$ of $\mathcal{C}$ and for every $i' \leq i$ a morphism $f_{ii'} : M_i \to M_{i'}$ such that $f_{ii} = \text{id}$ and such that $f_{ii''} = f_{i'i''} \circ f_{i i'}$ whenever $i'' \leq i' \leq i$. (Note reversal of inequalities.) \end{enumerate} We will say $(M_i, f_{ii'})$ is a (inverse) system over $I$ to denote this. The maps $f_{ii'}$ are sometimes called the {\it transition maps}. \end{definition} \noindent In other words a system over $I$ is just a diagram $M : \mathcal{I} \to \mathcal{C}$ where $\mathcal{I}$ is the category we associated to $I$ above: objects are elements of $I$ and there is a unique arrow $i \to i'$ in $\mathcal{I}$ if and only $i \leq i'$. An inverse system is a diagram $M : \mathcal{I}^{opp} \to \mathcal{C}$. From this point of view we could take (co)limits of any (inverse) system over $I$. However, it is customary to take {\it only colimits of systems over $I$} and {\it only limits of inverse systems over $I$}. More precisely: Given a system $(M_i, f_{ii'})$ over $I$ the colimit of the system $(M_i, f_{ii'})$ is defined as $$\colim_{i \in I} M_i = \colim_\mathcal{I} M,$$ i.e., as the colimit of the corresponding diagram. Given a inverse system $(M_i, f_{ii'})$ over $I$ the limit of the inverse system $(M_i, f_{ii'})$ is defined as $$\lim_{i \in I} M_i = \lim_{\mathcal{I}^{opp}} M,$$ i.e., as the limit of the corresponding diagram. \begin{remark} \label{remark-preorder-versus-partial-order} Let $I$ be a preordered set. From $I$ we can construct a canonical partially ordered set $\overline{I}$ and an order preserving map $\pi : I \to \overline{I}$. Namely, we can define an equivalence relation $\sim$ on $I$ by the rule $$i \sim j \Leftrightarrow (i \leq j\text{ and }j \leq i).$$ We set $\overline{I} = I/\sim$ and we let $\pi : I \to \overline{I}$ be the quotient map. Finally, $\overline{I}$ comes with a unique partial ordering such that $\pi(i) \leq \pi(j) \Leftrightarrow i \leq j$. Observe that if $I$ is a directed set, then $\overline{I}$ is a directed partially ordered set. Given an (inverse) system $N$ over $\overline{I}$ we obtain an (inverse) system $M$ over $I$ by setting $M_i = N_{\pi(i)}$. This construction defines a functor between the category of inverse systems over $I$ and $\overline{I}$. In fact, this is an equivalence. The reason is that if $i \sim j$, then for any system $M$ over $I$ the maps $M_i \to M_j$ and $M_j \to M_i$ are mutually inverse isomorphisms. More precisely, choosing a section $s : \overline{I} \to I$ of $\pi$ a quasi-inverse of the functor above sends $M$ to $N$ with $N_{\overline{i}} = M_{s(\overline{i})}$. Finally, this correspondence is compatible with colimits of systems: if $M$ and $N$ are related as above and if either $\colim_{\overline{I}} N$ or $\colim_I M$ exists then so does the other and $\colim_{\overline{I}} N = \colim_I M$. Similar results hold for inverse systems and limits of inverse systems. \end{remark} \noindent The upshot of Remark \ref{remark-preorder-versus-partial-order} is that while computing a colimit of a system or a limit of an inverse system, we may always assume the preorder is a partial order. \begin{definition} \label{definition-directed-system} Let $I$ be a preordered set. We say a system (resp.\ inverse system) $(M_i, f_{ii'})$ is a {\it directed system} (resp.\ {\it directed inverse system}) if $I$ is a directed set (Definition \ref{definition-directed-set}): $I$ is nonempty and for all $i_1, i_2 \in I$ there exists $i\in I$ such that $i_1 \leq i$ and $i_2 \leq i$. \end{definition} \noindent In this case the colimit is sometimes (unfortunately) called the direct limit''. We will not use this last terminology. It turns out that diagrams over a filtered category are no more general than directed systems in the following sense. Before we do so we discuss the difference between \begin{lemma} \label{lemma-directed-category-system} Let $\mathcal{I}$ be a filtered index category. There exists a directed set $I$ and a system $(x_i, \varphi_{ii'})$ over $I$ in $\mathcal{I}$ with the following properties: \begin{enumerate} \item 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 $\colim_{i \in I} M(x_i)$ exists then so does $\colim_\mathcal{I} M$ and the transformation $$\theta : \colim_{i \in I} M(x_i) \longrightarrow \colim_\mathcal{I} M$$ of Lemma \ref{lemma-functorial-colimit} is an isomorphism. \item 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 $\lim_{i \in I} M(x_i)$ exists then so does $\lim_\mathcal{I} M$ and the transformation $$\theta : \lim_{\mathcal{I}^{opp}} M \longrightarrow \lim_{i \in I} M(x_i)$$ of Lemma \ref{lemma-functorial-limit} is an isomorphism. \end{enumerate} \end{lemma} \begin{proof} As explained in the text following Definition \ref{definition-system-over-poset}, 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 set\footnote{In fact, our construction will produce a directed partially ordered set.}, and a cofinal functor $M_0 : \mathcal{I}_0 \to \mathcal{I}$. Then, by Lemma \ref{lemma-cofinal}, 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. \medskip\noindent A category $\mathcal{F}$ is called {\em 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. \medskip\noindent 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. \medskip\noindent 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}$ for the diagram $\mathcal{F} \to \mathcal{I}$. 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\circ f_{i'}$. 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 \ref{lemma-cofinal}, the colimit of any diagram $M : \mathcal{I} \to \mathcal{C}$ coincides with the colimit of $M\circ\Pi$ , this gives the desired reduction. \medskip\noindent 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. \medskip\noindent 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 \ref{definition-cofinal} is satisfied. Given an object $i$ of $\mathcal{I}$, $\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. \end{proof} \begin{remark} \label{remark-trick-needed} Note that a finite directed set $(I, \geq)$ always has a greatest object $i_\infty$. Hence any colimit of a system $(M_i, f_{ii'})$ over such a set is trivial in the sense that the colimit equals $M_{i_\infty}$. In contrast, a colimit indexed by a finite filtered category need not be trivial. For instance, let $\mathcal{I}$ be the category with a single object $i$ and a single non-trivial morphism $e$ satisfying $e = e \circ e$. The colimit of a diagram $M : \mathcal{I} \to Sets$ is the image of the idempotent $M(e)$. This illustrates that something like the trick of passing to $\mathcal{I}\times \omega$ in the proof of Lemma \ref{lemma-directed-category-system} is essential. \end{remark} \begin{lemma} \label{lemma-nonempty-limit} If $S : \mathcal{I} \to \textit{Sets}$ is a cofiltered diagram of sets and all the $S_i$ are finite nonempty, then $\lim_i S_i$ is nonempty. In other words, the limit of a directed inverse system of finite nonempty sets is nonempty. \end{lemma} \begin{proof} The two statements are equivalent by Lemma \ref{lemma-directed-category-system}. Let $I$ be a directed set and let $(S_i)_{i \in I}$ be an inverse system of finite nonempty sets over $I$. Let us say that a {\it subsystem} $T$ is a family $T = (T_i)_{i \in I}$ of nonempty subsets $T_i \subset S_i$ such that $T_{i'}$ is mapped into $T_i$ by the transition map $S_{i'} \to S_i$ for all $i' \geq i$. Denote $\mathcal{T}$ the set of subsystems. We order $\mathcal{T}$ by inclusion. Suppose $T_\alpha$, $\alpha \in A$ is a totally ordered family of elements of $\mathcal{T}$. Say $T_\alpha = (T_{\alpha, i})_{i \in I}$. Then we can find a lower bound $T = (T_i)_{i \in I}$ by setting $T_i = \bigcap_{\alpha \in A} T_{\alpha, i}$ which is manifestly a finite nonempty subset of $S_i$ as all the $T_{\alpha, i}$ are nonempty and as the $T_\alpha$ form a totally ordered family. Thus we may apply Zorn's lemma to see that $\mathcal{T}$ has minimal elements. \medskip\noindent Let's analyze what a minimal element $T \in \mathcal{T}$ looks like. First observe that the maps $T_{i'} \to T_i$ are all surjective. Namely, as $I$ is a directed set and $T_i$ is finite, the intersection $T'_i = \bigcap_{i' \geq i} \Im(T_{i'} \to T_i)$ is nonempty. Thus $T' = (T'_i)$ is a subsystem contained in $T$ and by minimality $T' = T$. Finally, we claim that $T_i$ is a singleton for each $i$. Namely, if $x \in T_i$, then we can define $T'_{i'} = (T_{i'} \to T_i)^{-1}(\{x\})$ for $i' \geq i$ and $T'_j = T_j$ if $j \not \geq i$. This is another subsystem as we've seen above that the transition maps of the subsystem $T$ are surjective. By minimality we see that $T = T'$ which indeed implies that $T_i$ is a singleton. This holds for every $i \in I$, hence we see that $T_i = \{x_i\}$ for some $x_i \in S_i$ with $x_{i'} \mapsto x_i$ under the map $S_{i'} \to S_i$ for every $i' \geq i$. In other words, $(x_i) \in \lim S_i$ and the lemma is proved. \end{proof} \section{Essentially constant systems} \label{section-essentially-constant} \noindent Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram in a category $\mathcal{C}$. Assume the index category $\mathcal{I}$ is filtered. In this case there are three successively stronger notions which pick out an object $X$ of $\mathcal{C}$. The first is just $$X = \colim_{i \in \mathcal{I}} M_i.$$ Then $X$ comes equipped with the coprojections $M_i \to X$. A stronger condition would be to require that $X$ is the colimit and that there exists an $i \in \mathcal{I}$ and a morphism $X \to M_i$ such that the composition $X \to M_i \to X$ is $\text{id}_X$. A stronger condition is the following. \begin{definition} \label{definition-essentially-constant-diagram} Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram in a category $\mathcal{C}$. \begin{enumerate} \item Assume the index category $\mathcal{I}$ is filtered. We say $M$ {\it is essentially constant} with {\it value} $X$ if $X = \colim_i M_i$ and there exists an $i \in \mathcal{I}$ and a morphism $X \to M_i$ such that \begin{enumerate} \item $X \to M_i \to X$ is $\text{id}_X$, and \item for all $j$ there exist $k$ and morphisms $i \to k$ and $j \to k$ such that the morphism $M_j \to M_k$ equals the composition $M_j \to X \to M_i \to M_k$. \end{enumerate} \item Assume the index category $\mathcal{I}$ is cofiltered. We say $M$ is {\it essentially constant} with {\it value} $X$ if $X = \lim_i M_i$ and there exists an $i \in \mathcal{I}$ and a morphism $M_i \to X$ such that \begin{enumerate} \item $X \to M_i \to X$ is $\text{id}_X$, and \item for all $j$ there exist $k$ and morphisms $k \to i$ and $k \to j$ such that the morphism $M_k \to M_j$ equals the composition $M_k \to M_i \to X \to M_j$. \end{enumerate} \end{enumerate} \end{definition} \noindent Which of the two versions is meant will be clear from context. If there is any confusion we will distinguish between these by saying that the first version means $M$ is essentially constant as an {\it ind-object}, and in the second case we will say it is essentially constant as a {\it pro-object}. This terminology is further explained in Remarks \ref{remark-ind-category} and \ref{remark-pro-category}. In fact we will often use the terminology essentially constant system'' which formally speaking is only defined for systems over directed sets. \begin{definition} \label{definition-essentially-constant-system} Let $\mathcal{C}$ be a category. A directed system $(M_i, f_{ii'})$ is an {\it essentially constant system} if $M$ viewed as a functor $I \to \mathcal{C}$ defines an essentially constant diagram. A directed inverse system $(M_i, f_{ii'})$ is an {\it essentially constant inverse system} if $M$ viewed as a functor $I^{opp} \to \mathcal{C}$ defines an essentially constant inverse diagram. \end{definition} \noindent If $(M_i, f_{ii'})$ is an essentially constant system and the morphisms $f_{ii'}$ are monomorphisms, then for all $i \leq i'$ sufficiently large the morphisms $f_{ii'}$ are isomorphisms. In general this need not be the case however. An example is the system $$\mathbf{Z}^2 \to \mathbf{Z}^2 \to \mathbf{Z}^2 \to \ldots$$ with maps given by $(a, b) \mapsto (a + b, 0)$. This system is essentially constant with value $\mathbf{Z}$. A non-example is to let $M = \bigoplus_{n \geq 0} \mathbf{Z}$ and to let $S : M \to M$ be the shift operator $(a_0, a_1, \ldots) \mapsto (a_1, a_2, \ldots)$. In this case the system $M \to M \to M \to \ldots$ with transition maps $S$ has colimit $0$ and the composition $0 \to M \to 0$ is the identity, but the system is not essentially constant. \begin{remark} \label{remark-ind-category} Let $\mathcal{C}$ be a category. There exists a big category $\text{Ind-}\mathcal{C}$ of {\it ind-objects of} $\mathcal{C}$. Namely, if $F : \mathcal{I} \to \mathcal{C}$ and $G : \mathcal{J} \to \mathcal{C}$ are filtered diagrams in $\mathcal{C}$, then we can define $$\Mor_{\text{Ind-}\mathcal{C}}(F, G) = \lim_i \colim_j \Mor_\mathcal{C}(F(i), G(j)).$$ There is a canonical functor $\mathcal{C} \to \text{Ind-}\mathcal{C}$ which maps $X$ to the {\it constant system} on $X$. This is a fully faithful embedding. In this language one sees that a diagram $F$ is essentially constant if and only $F$ is isomorphic to a constant system. If we ever need this material, then we will formulate this into a lemma and prove it here. \end{remark} \begin{remark} \label{remark-pro-category} Let $\mathcal{C}$ be a category. There exists a big category $\text{Pro-}\mathcal{C}$ of {\it pro-objects} of $\mathcal{C}$. Namely, if $F : \mathcal{I} \to \mathcal{C}$ and $G : \mathcal{J} \to \mathcal{C}$ are cofiltered diagrams in $\mathcal{C}$, then we can define $$\Mor_{\text{Pro-}\mathcal{C}}(F, G) = \lim_j \colim_i \Mor_\mathcal{C}(F(i), G(j)).$$ There is a canonical functor $\mathcal{C} \to \text{Pro-}\mathcal{C}$ which maps $X$ to the {\it constant system} on $X$. This is a fully faithful embedding. In this language one sees that a diagram $F$ is essentially constant if and only $F$ is isomorphic to a constant system. If we ever need this material, then we will formulate this into a lemma and prove it here. \end{remark} \begin{lemma} \label{lemma-image-essentially-constant} Let $\mathcal{C}$ be a category. Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram with filtered (resp.\ cofiltered) index category $\mathcal{I}$. Let $F : \mathcal{C} \to \mathcal{D}$ be a functor. If $M$ is essentially constant as an ind-object (resp.\ pro-object), then so is $F \circ M : \mathcal{I} \to \mathcal{D}$. \end{lemma} \begin{proof} If $X$ is a value for $M$, then it follows immediately from the definition that $F(X)$ is a value for $F \circ M$. \end{proof} \begin{lemma} \label{lemma-characterize-essentially-constant-ind} Let $\mathcal{C}$ be a category. Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram with filtered index category $\mathcal{I}$. The following are equivalent \begin{enumerate} \item $M$ is an essentially constant ind-object, and \item $X = \colim_i M_i$ exists and for any $W$ in $\mathcal{C}$ the map $$\colim_i \Mor_\mathcal{C}(W, M_i) \longrightarrow \Mor_\mathcal{C}(W, X)$$ is bijective. \end{enumerate} \end{lemma} \begin{proof} Assume (2) holds. Then $\text{id}_X \in \Mor_\mathcal{C}(X, X)$ comes from a morphism $X \to M_i$ for some $i$, i.e., $X \to M_i \to X$ is the identity. Then both maps $$\Mor_\mathcal{C}(W, X) \longrightarrow \colim_i \Mor_\mathcal{C}(W, M_i) \longrightarrow \Mor_\mathcal{C}(W, X)$$ are bijective for all $W$ where the first one is induced by the morphism $X \to M_i$ we found above, and the composition is the identity. This means that the composition $$\colim_i \Mor_\mathcal{C}(W, M_i) \longrightarrow \Mor_\mathcal{C}(W, X) \longrightarrow \colim_i \Mor_\mathcal{C}(W, M_i)$$ is the identity too. Setting $W = M_j$ and starting with $\text{id}_{M_j}$ in the colimit, we see that $M_j \to X \to M_i \to M_k$ is equal to $M_j \to M_k$ for some $k$ large enough. This proves (1) holds. The proof of (1) $\Rightarrow$ (2) is omitted. \end{proof} \begin{lemma} \label{lemma-characterize-essentially-constant-pro} Let $\mathcal{C}$ be a category. Let $M : \mathcal{I} \to \mathcal{C}$ be a diagram with cofiltered index category $\mathcal{I}$. The following are equivalent \begin{enumerate} \item $M$ is an essentially constant pro-object, and \item $X = \lim_i M_i$ exists and for any $W$ in $\mathcal{C}$ the map $$\colim_{i \in \mathcal{I}^{opp}} \Mor_\mathcal{C}(M_i, W) \longrightarrow \Mor_\mathcal{C}(X, W)$$ is bijective. \end{enumerate} \end{lemma} \begin{proof} Assume (2) holds. Then $\text{id}_X \in \Mor_\mathcal{C}(X, X)$ comes from a morphism $M_i \to X$ for some $i$, i.e., $X \to M_i \to X$ is the identity. Then both maps $$\Mor_\mathcal{C}(X, W) \longrightarrow \colim_i \Mor_\mathcal{C}(M_i, W) \longrightarrow \Mor_\mathcal{C}(X, W)$$ are bijective for all $W$ where the first one is induced by the morphism $M_i \to X$ we found above, and the composition is the identity. This means that the composition $$\colim_i \Mor_\mathcal{C}(M_i, W) \longrightarrow \Mor_\mathcal{C}(X, W) \longrightarrow \colim_i \Mor_\mathcal{C}(M_i, W)$$ is the identity too. Setting $W = M_j$ and starting with $\text{id}_{M_j}$ in the colimit, we see that $M_k \to M_i \to X \to M_j$ is equal to $M_k \to M_j$ for some $k$ large enough. This proves (1) holds. The proof of (1) $\Rightarrow$ (2) is omitted. \end{proof} \begin{lemma} \label{lemma-cofinal-essentially-constant} Let $\mathcal{C}$ be a category. Let $H : \mathcal{I} \to \mathcal{J}$ be a functor of filtered index categories. If $H$ is cofinal, then any diagram $M : \mathcal{J} \to \mathcal{C}$ is essentially constant if and only if $M \circ H$ is essentially constant. \end{lemma} \begin{proof} This follows formally from Lemmas \ref{lemma-characterize-essentially-constant-ind} and \ref{lemma-cofinal}. \end{proof} \begin{lemma} \label{lemma-essentially-constant-over-product} Let $\mathcal{I}$ and $\mathcal{J}$ be filtered categories and denote $p : \mathcal{I} \times \mathcal{J} \to \mathcal{J}$ the projection. Then $\mathcal{I} \times \mathcal{J}$ is filtered and a diagram $M : \mathcal{J} \to \mathcal{C}$ is essentially constant if and only if $M \circ p : \mathcal{I} \times \mathcal{J} \to \mathcal{C}$ is essentially constant. \end{lemma} \begin{proof} We omit the verification that $\mathcal{I} \times \mathcal{J}$ is filtered. The equivalence follows from Lemma \ref{lemma-cofinal-essentially-constant} because $p$ is cofinal (verification omitted). \end{proof} \begin{lemma} \label{lemma-initial-essentially-constant} Let $\mathcal{C}$ be a category. Let $H : \mathcal{I} \to \mathcal{J}$ be a functor of cofiltered index categories. If $H$ is initial, then any diagram $M : \mathcal{J} \to \mathcal{C}$ is essentially constant if and only if $M \circ H$ is essentially constant. \end{lemma} \begin{proof} This follows formally from Lemmas \ref{lemma-characterize-essentially-constant-pro}, \ref{lemma-initial}, \ref{lemma-cofinal}, and the fact that if $\mathcal{I}$ is initial in $\mathcal{J}$, then $\mathcal{I}^{opp}$ is cofinal in $\mathcal{J}^{opp}$. \end{proof} \section{Exact functors} \label{section-exact-functor} \begin{definition} \label{definition-exact} Let $F : \mathcal{A} \to \mathcal{B}$ be a functor. \begin{enumerate} \item Suppose all finite limits exist in $\mathcal{A}$. We say $F$ is {\it left exact} if it commutes with all finite limits. \item Suppose all finite colimits exist in $\mathcal{A}$. We say $F$ is {\it right exact} if it commutes with all finite colimits. \item We say $F$ is {\it exact} if it is both left and right exact. \end{enumerate} \end{definition} \begin{lemma} \label{lemma-characterize-left-exact} Let $F : \mathcal{A} \to \mathcal{B}$ be a functor. Suppose all finite limits exist in $\mathcal{A}$, see Lemma \ref{lemma-finite-limits-exist}. The following are equivalent: \begin{enumerate} \item $F$ is left exact, \item $F$ commutes with finite products and equalizers, and \item $F$ transforms a final object of $\mathcal{A}$ into a final object of $\mathcal{B}$, and commutes with fibre products. \end{enumerate} \end{lemma} \begin{proof} Lemma \ref{lemma-limits-products-equalizers} shows that (2) implies (1). Suppose (3) holds. The fibre product over the final object is the product. If $a, b : A \to B$ are morphisms of $\mathcal{A}$, then the equalizer of $a, b$ is $$(A \times_{a, B, b} A)\times_{(pr_1, pr_2), A \times A, \Delta} A.$$ Thus (3) implies (2). Finally (1) implies (3) because the empty limit is a final object, and fibre products are limits. \end{proof} \section{Adjoint functors} \label{section-adjoint} \begin{definition} \label{definition-adjoint} Let $\mathcal{C}$, $\mathcal{D}$ be categories. Let $u : \mathcal{C} \to \mathcal{D}$ and $v : \mathcal{D} \to \mathcal{C}$ be functors. We say that $u$ is a {\it left adjoint} of $v$, or that $v$ is a {\it right adjoint} to $u$ if there are bijections $$\Mor_\mathcal{D}(u(X), Y) \longrightarrow \Mor_\mathcal{C}(X, v(Y))$$ functorial in $X \in \Ob(\mathcal{C})$, and $Y \in \Ob(\mathcal{D})$. \end{definition} \noindent In other words, this means that there is a {\it given} isomorphism of functors $\mathcal{C}^{opp} \times \mathcal{D} \to \textit{Sets}$ from $\Mor_\mathcal{D}(u(-), -)$ to $\Mor_\mathcal{C}(-, v(-))$. For any object $X$ of $\mathcal{C}$ we obtain a morphism $X \to v(u(X))$ corresponding to $\text{id}_{u(X)}$. Similarly, for any object $Y$ of $\mathcal{D}$ we obtain a morphism $u(v(Y)) \to Y$ corresponding to $\text{id}_{v(Y)}$. These maps are called the {\it adjunction maps}. The adjunction maps are functorial in $X$ and $Y$, hence we obtain morphisms of functors $$\text{id}_\mathcal{C} \to v \circ u\quad (\text{unit}) \quad\text{and}\quad u \circ v \to \text{id}_\mathcal{D}\quad (\text{counit}).$$ Moreover, if $\alpha : u(X) \to Y$ and $\beta : X \to v(Y)$ are morphisms, then the following are equivalent \begin{enumerate} \item $\alpha$ and $\beta$ correspond to each other via the bijection of the definition, \item $\beta$ is the composition $X \to v(u(X)) \xrightarrow{v(\alpha)} v(Y)$, and \item $\alpha$ is the composition $u(X) \xrightarrow{u(\beta)} u(v(Y)) \to Y$. \end{enumerate} In this way one can reformulate the notion of adjoint functors in terms of adjunction maps. \begin{lemma} \label{lemma-adjoint-exists} Let $u : \mathcal{C} \to \mathcal{D}$ be a functor between categories. If for each $y \in \Ob(\mathcal{D})$ the functor $x \mapsto \Mor_\mathcal{D}(u(x), y)$ is representable, then $u$ has a right adjoint. \end{lemma} \begin{proof} For each $y$ choose an object $v(y)$ and an isomorphism $\Mor_\mathcal{C}(-, v(y)) \to \Mor_\mathcal{D}(u(-), y)$ of functors. By Yoneda's lemma (Lemma \ref{lemma-yoneda}) for any morphism $g : y \to y'$ the transformation of functors $$\Mor_\mathcal{C}(-, v(y)) \to \Mor_\mathcal{D}(u(-), y) \to \Mor_\mathcal{D}(u(-), y') \to \Mor_\mathcal{C}(-, v(y'))$$ corresponds to a unique morphism $v(g) : v(y) \to v(y')$. We omit the verification that $v$ is a functor and that it is right adjoint to $u$. \end{proof} \begin{lemma} \label{lemma-adjoint-fully-faithful} Let $u$ be a left adjoint to $v$ as in Definition \ref{definition-adjoint}. Then \begin{enumerate} \item $u$ is fully faithful $\Leftrightarrow \text{id} \cong v \circ u$. \item $v$ is fully faithful $\Leftrightarrow u \circ v \cong \text{id}$. \end{enumerate} \end{lemma} \begin{proof} Assume $u$ is fully faithful. We have to show the adjunction map $X \to v(u(X))$ is an isomorphism. Let $X' \to v(u(X))$ be any morphism. By adjointness this corresponds to a morphism $u(X') \to u(X)$. By fully faithfulness of $u$ this corresponds to a morphism $X' \to X$. Thus we see that $X \to v(u(X))$ defines a bijection $\Mor(X', X) \to \Mor(X', v(u(X)))$. Hence it is an isomorphism. Conversely, if $\text{id} \cong v \circ u$ then $u$ has to be fully faithful, as $v$ defines an inverse on morphism sets. \medskip\noindent Part (2) is dual to part (1). \end{proof} \begin{lemma} \label{lemma-adjoint-exact} Let $u$ be a left adjoint to $v$ as in Definition \ref{definition-adjoint}. \begin{enumerate} \item Suppose that $M : \mathcal{I} \to \mathcal{C}$ is a diagram, and suppose that $\colim_\mathcal{I} M$ exists in $\mathcal{C}$. Then $u(\colim_\mathcal{I} M) = \colim_\mathcal{I} u \circ M$. In other words, $u$ commutes with (representable) colimits. \item Suppose that $M : \mathcal{I} \to \mathcal{D}$ is a diagram, and suppose that $\lim_\mathcal{I} M$ exists in $\mathcal{D}$. Then $v(\lim_\mathcal{I} M) = \lim_\mathcal{I} v \circ M$. In other words $v$ commutes with representable limits. \end{enumerate} \end{lemma} \begin{proof} A morphism from a colimit into an object is the same as a compatible system of morphisms from the constituents of the limit into the object, see Remark \ref{remark-limit-colim}. So $$\begin{matrix} \Mor_\mathcal{D}(u(\colim_{i \in \mathcal{I}} M_i), Y) & = & \Mor_\mathcal{C}(\colim_{i \in \mathcal{I}} M_i, v(Y)) \\ & = & \lim_{i \in \mathcal{I}^{opp}} \Mor_\mathcal{C}(M_i, v(Y)) \\ & = & \lim_{i \in \mathcal{I}^{opp}} \Mor_\mathcal{D}(u(M_i), Y) \end{matrix}$$ proves that $u(\colim_{i \in \mathcal{I}} M_i)$ is the colimit we are looking for. A similar argument works for the other statement. \end{proof} \begin{lemma} \label{lemma-exact-adjoint} Let $u$ be a left adjoint of $v$ as in Definition \ref{definition-adjoint}. \begin{enumerate} \item If $\mathcal{C}$ has finite colimits, then $u$ is right exact. \item If $\mathcal{D}$ has finite limits, then $v$ is left exact. \end{enumerate} \end{lemma} \begin{proof} Obvious from the definitions and Lemma \ref{lemma-adjoint-exact}. \end{proof} \begin{lemma} \label{lemma-transformation-between-functors-and-adjoints} Let $u_1, u_2 : \mathcal{C} \to \mathcal{D}$ be functors with right adjoints $v_1, v_2 : \mathcal{D} \to \mathcal{C}$. Let $\beta : u_2 \to u_1$ be a transformation of functors. Let $\beta^\vee : v_1 \to v_2$ be the corresponding transformation of adjoint functors. Then $$\xymatrix{ u_2 \circ v_1 \ar[r]_\beta \ar[d]_{\beta^\vee} & u_1 \circ v_1 \ar[d] \\ u_2 \circ v_2 \ar[r] & \text{id} }$$ is commutative where the unlabeled arrows are the counit transformations. \end{lemma} \begin{proof} This is true because $\beta^\vee_D : v_1D \to v_2D$ is the unique morphism such that the induced maps $\Mor(C, v_1D) \to \Mor(C, v_2D)$ is the map $\Mor(u_1C, D) \to \Mor(u_2C, D)$ induced by $\beta_C : u_2C \to u_1C$. Namely, this means the map $$\Mor(u_1 v_1 D, D') \to \Mor(u_2 v_1 D, D')$$ induced by $\beta_{v_1 D}$ is the same as the map $$\Mor(v_1 D, v_1 D') \to \Mor(v_1 D, v_2 D')$$ induced by $\beta^\vee_{D'}$. Taking $D' = D$ we find that the counit $u_1 v_1 D \to D$ precomposed by $\beta_{v_1D}$ corresponds to $\beta^\vee_D$ under adjunction. This exactly means that the diagram commutes when evaluated on $D$. \end{proof} \section{A criterion for representability} \label{section-representable} \noindent The following lemma is often useful to prove the existence of universal objects in big categories, please see the discussion in Remark \ref{remark-how-to-use-it}. \begin{lemma} \label{lemma-a-version-of-brown} Let $\mathcal{C}$ be a big\footnote{See Remark \ref{remark-big-categories}.} category which has limits. Let $F : \mathcal{C} \to \textit{Sets}$ be a functor. Assume that \begin{enumerate} \item $F$ commutes with limits, \item there exists a family $\{x_i\}_{i \in I}$ of objects of $\mathcal{C}$ and for each $i \in I$ an element $f_i \in F(x_i)$ such that for $y \in \Ob(\mathcal{C})$ and $g \in F(y)$ there exists an $i$ and a morphism $\varphi : x_i \to y$ with $F(\varphi)(f_i) = g$. \end{enumerate} Then $F$ is representable, i.e., there exists an object $x$ of $\mathcal{C}$ such that $$F(y) = \Mor_\mathcal{C}(x, y)$$ functorially in $y$. \end{lemma} \begin{proof} Let $\mathcal{I}$ be the category whose objects are the pairs $(x_i, f_i)$ and whose morphisms $(x_i, f_i) \to (x_{i'}, f_{i'})$ are maps $\varphi : x_i \to x_{i'}$ in $\mathcal{C}$ such that $F(\varphi)(f_i) = f_{i'}$. Set $$x = \lim_{(x_i, f_i) \in \mathcal{I}} x_i$$ (this will not be the $x$ we are looking for, see below). The limit exists by assumption. As $F$ commutes with limits we have $$F(x) = \lim_{(x_i, f_i) \in \mathcal{I}} F(x_i).$$ Hence there is a universal element $f \in F(x)$ which maps to $f_i \in F(x_i)$ under $F$ applied to the projection map $x \to x_i$. Using $f$ we obtain a transformation of functors $$\xi : \Mor_\mathcal{C}(x, - ) \longrightarrow F(-)$$ see Section \ref{section-opposite}. Let $y$ be an arbitrary object of $\mathcal{C}$ and let $g \in F(y)$. Choose $x_i \to y$ such that $f_i$ maps to $g$ which is possible by assumption. Then $F$ applied to the maps $$x \longrightarrow x_i \longrightarrow y$$ (the first being the projection map of the limit defining $x$) sends $f$ to $g$. Hence the transformation $\xi$ is surjective. \medskip\noindent In order to find the object representing $F$ we let $e : x' \to x$ be the equalizer of all self maps $\varphi : x \to x$ with $F(\varphi)(f) = f$. Since $F$ commutes with limits, it commutes with equalizers, and we see there exists an $f' \in F(x')$ mapping to $f$ in $F(x)$. Since $\xi$ is surjective and since $f'$ maps to $f$ we see that also $\xi' : \Mor_\mathcal{C}(x', -) \to F(-)$ is surjective. Finally, suppose that $a, b : x' \to y$ are two maps such that $F(a)(f) = F(b)(f)$. We have to show $a = b$. Consider the equalizer $e' : x'' \to x'$. Again we find $f'' \in F(x'')$ mapping to $f'$. Choose a map $\psi : x \to x''$ such that $F(\psi)(f) = f''$. Then we see that $e \circ e' \circ \psi : x \to x$ is a morphism with $F(e \circ e' \circ \psi)(f) = f$. Hence $e \circ e' \circ \psi \circ e = e$. Since $e$ is a monomorphism, this implies that $e'$ is an epimorphism, thus $a = b$ as desired. \end{proof} \begin{remark} \label{remark-how-to-use-it} The lemma above is often used to construct the free something on something. For example the free abelian group on a set, the free group on a set, etc. The idea, say in the case of the free group on a set $E$ is to consider the functor $$F : \textit{Groups} \to \textit{Sets},\quad G \longmapsto \text{Map}(E, G)$$ This functor commutes with limits. As our family of objects we can take a family $E \to G_i$ consisting of groups $G_i$ of cardinality at most $\max(\aleph_0, |E|)$ and set maps $E \to G_i$ such that every isomorphism class of such a structure occurs at least once. Namely, if $E \to G$ is a map from $E$ to a group $G$, then the subgroup $G'$ generated by the image has cardinality at most $\max(\aleph_0, |E|)$. The lemma tells us the functor is representable, hence there exists a group $F_E$ such that $\Mor_{\textit{Groups}}(F_E, G) = \text{Map}(E, G)$. In particular, the identity morphism of $F_E$ corresponds to a map $E \to F_E$ and one can show that $F_E$ is generated by the image without imposing any relations. \medskip\noindent Another typical application is that we can use the lemma to construct colimits once it is known that limits exist. We illustrate it using the category of topological spaces which has limits by Topology, Lemma \ref{topology-lemma-limits}. Namely, suppose that $\mathcal{I} \to \textit{Top}$, $i \mapsto X_i$ is a functor. Then we can consider $$F : \textit{Top} \longrightarrow \textit{Sets},\quad Y \longmapsto \lim_\mathcal{I} \Mor_{\textit{Top}}(X_i, Y)$$ This functor commutes with limits. Moreover, given any topological space $Y$ and an element $(\varphi_i : X_i \to Y)$ of $F(Y)$, there is a subspace $Y' \subset Y$ of cardinality at most $|\coprod X_i|$ such that the morphisms $\varphi_i$ map into $Y'$. Namely, we can take the induced topology on the union of the images of the $\varphi_i$. Thus it is clear that the hypotheses of the lemma are satisfied and we find a topological space $X$ representing the functor $F$, which precisely means that $X$ is the colimit of the diagram $i \mapsto X_i$. \end{remark} \begin{theorem}[Adjoint functor theorem] \label{theorem-adjoint-functor} Let $G : \mathcal{C} \to \mathcal{D}$ be a functor of big categories. Assume $\mathcal{C}$ has limits, $G$ commutes with them, and for every object $y$ of $\mathcal{D}$ there exists a set of pairs $(x_i, f_i)_{i \in I}$ with $x_i \in \Ob(\mathcal{C})$, $f_i \in \Mor_\mathcal{D}(y, G(x_i))$ such that for any pair $(x, f)$ with $x \in \Ob(\mathcal{C})$, $f \in \Mor_\mathcal{C}(y, G(x))$ there is an $i$ and a morphism $h : x_i \to x$ such that $f = G(h) \circ f_i$. Then $G$ has a left adjoint $F$. \end{theorem} \begin{proof} The assumptions imply that for every object $y$ of $\mathcal{D}$ the functor $x \mapsto \Mor_\mathcal{D}(y, G(x))$ satisfies the assumptions of Lemma \ref{lemma-a-version-of-brown}. Thus it is representable by an object, let's call it $F(y)$. An application of Yoneda's lemma (Lemma \ref{lemma-yoneda}) turns the rule $y \mapsto F(y)$ into a functor which by construction is an adjoint to $G$. We omit the details. \end{proof} \section{Localization in categories} \label{section-localization} \noindent The basic idea of this section is given a category $\mathcal{C}$ and a set of arrows $S$ to construct a functor $F : \mathcal{C} \to S^{-1}\mathcal{C}$ such that all elements of $S$ become invertible in $S^{-1}\mathcal{C}$ and such that $F$ is universal among all functors with this property. References for this section are \cite[Chapter I, Section 2]{GZ} and \cite[Chapter II, Section 2]{Verdier}. \begin{definition} \label{definition-multiplicative-system} Let $\mathcal{C}$ be a category. A set of arrows $S$ of $\mathcal{C}$ is called a {\it left multiplicative system} if it has the following properties: \begin{enumerate} \item[LMS1] The identity of every object of $\mathcal{C}$ is in $S$ and the composition of two composable elements of $S$ is in $S$. \item[LMS2] Every solid diagram $$\xymatrix{ X \ar[d]_t \ar[r]_g & Y \ar@{..>}[d]^s \\ Z \ar@{..>}[r]^f & W }$$ with $t \in S$ can be completed to a commutative dotted square with $s \in S$. \item[LMS3] For every pair of morphisms $f, g : X \to Y$ and $t \in S$ with target $X$ such that $f \circ t = g \circ t$ there exists a $s \in S$ with source $Y$ such that $s \circ f = s \circ g$. \end{enumerate} A set of arrows $S$ of $\mathcal{C}$ is called a {\it right multiplicative system} if it has the following properties: