Filtered Colimits - Category Theory

6 Filtered Colimits

Definition 6.1 (Filtered). We say a category $C$ is filtered if every finite diagram $D : J \to C$ has a cone under it.

Lemma 6.2. $C$ is filtered if and only if:

(i)
$C$ is nonempty.
(ii)
Given $A, B \in ob C$ , there exists a cospan $A \to C \leftarrow B$ .
(iii)
Given $A ⇉_{g}^{f} B$ in $C$ , there exists $B \overset{h}{\to} C$ with $h f = h g$ .

Proof.

$\Rightarrow$ Since each of (i) - (iii) is a special case of Definition 6.1.
$\Leftarrow$ (i) deals with the empty diagram.
Given $D : J \to C$ with $J$ finite and non-empty, by repeated use of (ii) we can find $A$ with morphisms $D (j) \to A$ for all $j$ . Then by repeated use of (ii) we can find $A \to B$ coequalising
for each $α \in mor J$ . □

For preorders, we say directed instead of filtered.

Definition 6.3 (Has filtered colimits). We say $C$ has filtered colimits if every $D : J \to C$ , where $J$ is small and filtered, has a colimit.

Note that direct limits as in Example 4.3(g) are directed colimits.

Lemma 6.4. Assuming that:

$C$ has finite colimits
$C$ has directed colimits

Then

C

has all small colimits.

Proof. By Proposition 4.4(i), enough to show $C$ has all small coproducts.

Given a set-indexeud family $(A_{j} | j \in J)$ of objects, the finite coproducts $\sum_{j \in F} A_{j}$ , for $F \subseteq J$ finite, form the vertices of a diagram of shape $P_{f} J = {F \subseteq J | F finite}$ whose edges are coprojections. $P_{f} J$ is directed, and a colimit for this diagram has the universal property of a coproduct $\sum_{j \in J} A_{j}$ . □

Suppose given a $D : I \times J \to C$ , where $C$ has limits of shape $I$ and colimits of shape $J$ .

L(j) L(j′) colim L
J

limI M

D (i,j) D(i,j′) M (i)

LDDDMD(β(i(α(α(α(i),β,,)′,D)j)j′β))(i′,j) D(i′,j′) M (i′)

We can form

L (j) = \lim_{I} (D (∙, j) : I \to C)

, by Example 4.7(e) these are the vertices of a diagram

L : J \to C

, and we can form

{colim}_{J} L

Similarly, the colimits $M (i) = {colim}_{J} D (i, ∙)$ form a diagram of shape $I$ , and we can form $\lim_{I} M$ . We get an induced morphism ${colim}_{J} L \to \lim_{I} M$ ; if this is an isomorphism for all $D : I \times J \to C$ , we say colimits of shape $J$ commute with limits of shape $I$ in $C$ .

Equivalently, ${colim}_{J} : [J, C] \to C$ preserves limits of shape $I$ , or $\lim_{I} : [I, C] \to C$ preserves colimits of shape $J$ .

In Remark 5.13(d) we saw that reflexive coequalisers commute with finite products in $S e t$ .

Theorem 6.5. Assuming that:

$J$ a small category

Then colimits of shape

J

commute with all finite limits in

S e t

if and only if

J

is filtered.

Proof.

$\Rightarrow$ Let $D : I \to J$ be a diagram with $I$ finite. We have a diagram $E : I^{o p} \times J \to S e t$ defined by $E (i, j) = J (D (i), j)$ .
For each $i$ , $({colim}_{J} E) (i)$ is a singleton since every $D (i) \to j$ is identified with $1_{D (i)}$ in the colimit, so $\lim_{I} {colim}_{J} E$ is a singleton.

But elements of $\lim_{I} E (∙, j)$ are cones under $D$ with apex $j$ , so if ${colim}_{J} \lim_{I} E$ is nonempty there must be such a cone for some $j$ .
$\Leftarrow$ Suppose given $D : I \times J \to S e t$ where $I$ is finite and $J$ is filtered. In general, the colimitof $E : J \to S e t$ is the quotient of $∐_{j \in ob J} E (j)$ by the smallest equivalence relation identifying $x \in E (j)$ with $D (α) (x) \in E (j^{'})$ for all $α : j \to j^{'}$ in $J$ . For filtered $J$ , this identifies $x \in E (j)$ with $x^{'} \in E (j^{'})$ if and only if there exists $j \overset{α}{\to} j^{″} \overset{α^{'}}{\leftarrow} j^{'}$ with $E (α) (x) = E (α^{'}) (x^{'})$ , and moreover if $j = j^{'}$ we may assume $α = α^{'}$ .
Now, given an element $x$ of $\lim_{I} {colim}_{J} D$ , we can write it as $(x_{i} | i \in ob I)$ where $x_{i} \in {colim}_{J} D (i, ∙)$ is an equivalence class of elements $x_{i j} \in D (i, j)$ . If $α : i \to i^{'}$ in $I$ , then $D (α, j) (x_{i} j)$ and $x_{i^{'} j^{'}}$ represent the same element of ${colim}_{J} D (i^{'}, ∙)$ so by repeated use of Lemma 6.2(ii) we can choose representatives in $D (i, j_{0})$ for some fixed $j_{0}$ , and by repeated use of Lemma 6.2(iii) we can assume that these representatives define an element of $\lim_{I} D (∙, j_{0})$ . This defines an element of ${colim}_{J} \lim_{I} D$ mapping to the given element of $\lim_{I} {colim}_{J} D$ .

The proof of injectivity is similar: if two elements $x, y$ of ${colim}_{J} \lim_{I} D$ have the same image in $\lim_{I} {colim}_{J} D$ we can choose representatives $x_{j}, y_{j}$ in $\lim_{I} D (∙, j)$ and then find $j \to j^{'}$ so that each of the components $x_{i j}$ and $y_{i j}$ map to the same element of $D (i, j^{'})$ under $j \to j^{'}$ . So $x = y$ in ${colim}_{J} \lim_{I} D$ . □

Corollary 6.6. Assuming that:

$C$ a category of finitary algebras as in Example 5.14(a)

Then

(i) The forgetful functor $U : C \to S e t$ creates filtered colimits.
(ii) Filtered colimits commute with finite limits in $C$ .

Proof.

(i) This is just like Example 5.14(a): Given a filtered diagram $D : J \to C$ and a colimit for $U D$ with apex $L$ , then $L^{n}$ is the colimit of $U D^{n}$ for all $n$ , so each $n$ -ary operation on the $D (j)$ ’s induces an $n$ -ary operation on $L$ , and $L$ also inherits all the equations defining $C$ , so there’s a unique lifting of the colimit cone under $U D$ to a colimit cone for $D$ .
(ii) Follows from (i) and Theorem 6.5, since $U$ also creates finite limits (and reflects isomorphisms). □

Similar results hold for categories such as $C a t$ .

Example 6.7. Consider the diagram

of shape

ℕ^{o p} \times 2

S e t

. The inverse limit of the top row is

\emptyset

, but that of the bottom row is

1

. So

\lim_{ℕ^{o p}} [ℕ^{o p}, S e t] \to S e t

doesn’t preserve epimorphisms; equivalently

{colim}_{ℕ} : [ℕ, {S e t}^{o p}] \to {S e t}^{o p}

doesn’t preserve monomorphisms. Thus by Remark 4.8, directed colimits don’t commute with pullbacks in

{S e t}^{o p}

Given a functor $F : C \to S e t$ , the category of elements of $F$ is $(1 ↓ F)$ : its objects are pairs $(A, x)$ with $x \in F A$ and morphisms $(A, x) \to (B, y)$ are morphisms $f : A \to B$ such that $(F f) (x) = y$ .

Proposition 6.8. Assuming that:

$C$ a small category
$C$ has finite limits
$F : C \to S e t$ a functor

Then the following are equivalent:

(i)
$F$ preserves finite limits.
(ii)
$(1 ↓ F)$ is cofiltered.
(iii)
$F$ is expresible as a filtered colimit of representable functors.

Proof.

(i) $\Rightarrow$ (ii) By Lemma 4.10, $(1 ↓ F)$ has finite limits so ${(1 ↓ F)}^{o p}$ is filtered.
(ii) $\Rightarrow$ (iii) Consider the diagram ${(1 ↓ F)}^{o p} \overset{U}{\to} C^{o p} \overset{Y}{\to} [C, S e t]$ where $U$ is the forgetful functor and $Y$ is the Yoneda embedding. A cone under this diagram (with apex $G$ , say) yields a family of morphisms $C (A, ∙) \overset{λ_{(A, x)}}{\to} G$ for each $x \in F A$ , subject to compatibility conditions which say that $(G f) Φ (λ_{(A, x)}) = Φ (λ_{(B, y)})$ for every $f : (A, x) \to (B, y)$ in $(1 ↓ F)$ , i.e. such that $x \mapsto Φ (λ_{(A, x)})$ is a natural transformation $F \to G$ . So the cone $(C (A, ∙) \overset{Ψ (x)}{\to} F | (A, x) \in ob (1 ↓ F))$ has the universal property of a colimit for the diagram.
(iii) $\Rightarrow$ (i) Functors of the form $C (A, ∙)$ preserve any limits which exist, so this follows from Theorem 6.5 plus the fact that colimits in $[C, S e t]$ are computed pointwise. □

Given a category $C$ with filtered colimits, we say $F : C \to D$ is finitary if it preserves filtered colimits. If $C = S e t$ , then a finitary $F$ is determined by its restriction to ${S e t}_{f}$ , since any set is the directed union of its finite subsets.

In fact the restriction functor $[S e t, D] \to [{S e t}_{f}, D]$ has a left adjoint (the left Kan extension functor) and the finitary functors are those in the image of this left adjoint (up to isomorphism).

For a category $C$ as in Example 5.14(a) or Corollary 6.6, the corresponding monad $𝕋$ on $S e t$ is finitary. From now on, ${S e t}_{f}$ will denote the skeleton of the category of finite sets whose objects are the sets $[n] = {1, 2, \dots, n}$ .

Definition 6.9 (Lawvere theory). By a Lawvere theory, we mean a small category $T$ together with a functor ${S e t}_{f} \to T$ which is bijective on objects and preserves finite coproducts. A model of a Lawvere theory $T$ in any category $C$ with finite products is a functor $M : T^{o p} \to C$ preserving finite products.

For example, if $𝕋$ is a monad on $S e t$ , the full subcategory of ${S e t}_{𝕋}$ whose objects are the sets $[n]$ is a Lawvere theory.

Lemma 6.10. Assuming that:

$T$ a Lawvere theory

Then the category of

T

-models in

S e t

is (equivalent to) a finitary algebra category in the sense of Example 5.14(a).

Proof. Given a model $M : T^{o p} \to S e t$ , we have $M [n] ≅ M {[1]}^{n}$ for all $n$ . Also, any morphism $M {[1]}^{n} \to M {[1]}^{p}$ induced by a morphism $[p] \to [n]$ in $T$ is determined by its composites with the projections $M {[1]}^{p} \to M [1]$ , so specifying $M$ on morphisms is determined by its effect on morphisms with domain $[1]$ .

So, given a set $A$ , specifying a model $M$ with $M [1] = A$ is equivalent to specifying operations $α_{A} : A^{n} \to A$ for each $α : [1] \to [n]$ in $T$ , subject to ${(v_{i})}_{A} (a_{1}, \dots, a_{n}) = a_{i}$ whenever $v_{i} : [1] \to [n]$ is the $i$ -th coprojection, and

commutes whenever

commutes. □

Note that the characterisation of $T$ -models in any category with finite products. Note also that the equations of Lemma 6.10 allow us to reduce any compound operation $α (β_{1} (x \dots), β_{2} (x \dots), \dots, β_{n} (x \dots))$ to a single operation $γ$ .

Theorem 6.11. Assuming that:

$C$ a category

Then the following are equivalent:

(i)
$C$ is equivalent to a finitary algebraic category in the sense of Example 5.14(a). (Recall that these categories are those whose objects are sets with finitary operations satisfying some equations, and morphisms are homomorphisms between them.)
(ii)
$C$ is equivalent to the category of $S e t$ -models of a Lawvere theory.
(iii)
$C ≃ {S e t}^{𝕋}$ for a finitary monad $𝕋$ on $S e t$ .

Proof.

(ii) $\Rightarrow$ (i) Let $T$ be the full subcategory of $C$ on the free algebras $F [n]$ , for $n \in ℕ$ . Then $T$ is a Lawvere theory, and for every object $A$ of $C$ , the functor $C (∙, A)$ restricted to $T$ preserves finite products, so it’s a model of $T$ . This defines a functor $T - M o d (S e t) \overset{Y}{\leftarrow} {S e t}^{𝕋}$ ; but $T - M o d (S e t) ≃ {S e t}^{𝕋^{'}}$ for some finitary monad $𝕋^{'}$ on $S e t$ , so we get a functor ${S e t}^{𝕋} \overset{Y}{\to} {S e t}^{𝕋^{'}}$ which is the identity on underlying sets.
In this situation, $Y$ is induced by a morphism of monads $𝕋^{'} \to 𝕋$ , i.e. a natural transformation $𝜃 : T^{'} \to T$ commuting with the units and multiplications. (Clearly, such a $𝜃$ induces a functor ${S e t}^{𝕋} \to {S e t}^{𝕋^{'}}$ sending $(A, α)$ to $(A, α 𝜃_{A})$ ).

But we know $𝜃_{[n]}$ is bijective for all $n$ , since elements of the free algebras on $[n]$ are just morphisms $[1] \to [n]$ in $T$ . But both functors are finitary, so $𝜃_{A}$ is bijective for all $A$ , i.e. it’s an isomorphism of monads. □

For a general monad $𝕋$ on $S e t$ , this construction produces a finitary monad $𝕋^{'}$ which is the coreflection of $𝕋$ in the category of finitary monads.

For example:

For $𝕋 = (double power-set)$ , we obtain $𝕋^{'} = {Boolean algebras}$ .
For $𝕋 = Stone-Čech$ , we obtain the trivial monad $(1_{S e t}, 1_{1_{S e t}}, 1_{1_{S e t}})$ .