# What's an example of a subcategory whose closure under colimits takes a lot of steps to form by iteration?

Let $\mathcal{C}$ be a cocomplete category and $\mathcal{S} \subseteq \mathcal{C}$ be a full subcategory. The colimit completion $\mathrm{Colim}^\mathcal{C}(\mathcal{S})$of $\mathcal{S}$ in $\mathcal{C}$ is the smallest full subcategory $\mathcal{S} \subseteq \mathrm{Colim}^\mathcal{C}(\mathcal{S}) \subseteq \mathcal{C}$ which is closed under the formation of small colimits in $\mathcal{C}$. Naturally, it can be attained via a transifinite induction: set $\mathrm{Colim}^\mathcal{C}_0(\mathcal{S}) = \mathcal{S}$; for successor ordinals define $\mathrm{Colim}^\mathcal{C}_{\alpha+1}(\mathcal{S})$ to be the full subcategory of $\mathcal{C}$ consisting of objects which are the colimits of small diagrams in $\mathrm{Colim}^\mathcal{C}_\alpha(\mathcal{S})$; and for limit ordinals take unions. If we iterate through all ordinals, we get $\mathrm{Colim}^\mathcal{C}(\mathcal{S})$ at the end.

In category theory, one is often interested in cases where this process stabilizes after one step. For instance if $\mathcal{S}$ is a dense generator in $\mathcal{C}$ (or even just colimit-dense), then the process stabilizes after one step. If $\mathcal{S}$ is a regular generator in $\mathcal{C}$, then the process stabilizes after at most two steps. And the canonical example of a category lacking a strong generator is $\mathsf{Top}$ where one can argue as for $k$-spaces that the process always stops after one step. One is also interested in cases where we close under not all colimits, but just those of certain shapes; if the class of diagrams is saturated or almost so, then in the free case where $\mathcal{C}$ is a presheaf category and $\mathcal{S}$ is the representables, the process stabilizes in one step.

But I'd like to see some examples where things go bad.

Question:

• What's an example of $\mathcal{S} \subseteq \mathcal{C}$ where $\mathrm{Colim}^\mathcal{C}(\mathcal{S})$ takes more than two steps to attain?
• Infinitely many steps?
• A proper class of steps?

I'm really interested in seeing a proper class of steps, but I'd be happy to at least see something easier. And I'm not at all averse to taking advantage of duality / doing everything with limits instead of colimits. And on the flip side,

• If $\mathcal{S}$ is small and $\mathcal{C}$ is locally presentable, must the process stop after a small number of steps?

An example where you need a proper class of steps is 6.38 in my book with Adámek. Concerning the last question, the answer is positive under Vopěnka's principle. The reason is that the colimit closure of $\mathcal S$ is locally presentable (see 6.28 and 6.29 in the same book) and thus it has a small dense subcategory. This argument works for $\mathcal S$ large as well.

• Thank you, Professor Rosický! This is another example of how your book is a continual source of inspiration. – Tim Campion Jul 8 '16 at 12:19
• Concerning the last question, is it known whether Vopěnka's Principle is necessary for this when $\mathcal{S}$ is small? – Tim Campion Jul 8 '16 at 13:06

Let me just give a community wiki exposition of the example 6.38 that Professor Rosický mentions from his book with Adámek, Locally Presentable and Accessible Categories, since although the book is quite clear, it doesn't quite reach the conclusion needed here, since the point of the example is slightly different.

Consider structures $X$ with partial unary operations indexed by the ordinals $\{\alpha_i\}_{i \in \mathrm{Ord}}$ such that the following condition is satisfied:

For every $j \in \mathrm{Ord}$ and $x \in X$, the value $\alpha_j(x)$ is defined if and only if for every $i<j$, $\alpha_i(x) = x$.

(So for each $x \in X$, there is an initial segment of the ordinals where $\alpha_i(x)$ is defined but just has $\alpha_i(x) = x$, and then at the top there is an ordinal $j$ where $\alpha_j(x)$ is defined but $\alpha_j(x) \neq x$; thereafter $\alpha_i(x)$ is not defined for bigger $i$ (actually there is an alternative which won't be relevant for the example: we could have $\alpha_i(x) = x$ for all $i \in \mathrm{Ord}$). The ordinal $j$ can vary with $x$.)

We let $\mathcal{C}$ be the category of all such structures, and all homomorphisms (i.e. a homomorphism is a function $f: X \to Y$ such that if $x\in X$ and $\alpha_i(x)$ is defined, then $\alpha_i(f(x))$ is defined and $\alpha_i(f(x)) = f(\alpha_i(x))$). Then $\mathcal{C}$ is cocomplete. Coproducts are just disjoint unions. Coequalizers are a little bit tricky (but this is sort of the point). To form the coequalizer of $f,g : X \overset{\to}{\to} Y$, first take the coequalizer in $\mathsf{Set}$, defining the operations in the only possible way. Then we may need to add in more points, because it may be the case that $\alpha_i([y]) = [y]$ for all $i< j$, but nevertheless there is no $y \in [y]$ such that $\alpha_j(y)$ is defined. In this case, we simply freely add a point $[y]_0$ with $\alpha_j([y]) = [y]_0$. Then we need to throw in more points $([y]_n)_{n \in \mathbb{N}}$ with $\alpha_0([y]_n) = [y]_{n+1}$.

For $j \in \mathrm{Ord}$, let $\mathcal{C}_j \subset \mathcal{C}$ denote the subcategory where all operations $\alpha_i$ are undefined for $i \geq j$. The point which is implicit in the book is that if $F: \mathcal{D} \to \mathcal{C}_j$ is a diagram in $\mathcal{C}_j$, then $\mathrm{colim} F \in \mathcal{C}_{j+1}$. After all, $\mathrm{colim} F$ is a coequalizer of coproducts of objects of $\mathcal{C}_j$ -- the coproducts don't introduce any new operations, and we can explicitly analyze the construction of coequalizers to see that we at worst added operations of one index higher than the sup of those already appearing.

Now Adámek and Rosický take $\mathcal{S}$ to be a certain singleton category $\{A\} \subset \mathcal{C}_1$ (namely, $A$ has underlying set $\mathbb{N}$ with $\alpha_0$ the successor operation), and show that at each step, $\mathrm{colim}^\mathcal{C}_j(\mathcal{S})$ does indeed add a new object $A_j \in \mathcal{C}_{j+1}$ (the underlying set is still $\mathbb{N}$, with successor operation, but at $0 \in \mathbb{N}$ the successor is delayed until the $j$th operation). I think this is quite clearly explained in the book. (Although I think there is a slight error -- the initial step of the induction should simply point out that $A = A_0$. The coequalizer of the indicated diagram is actually $A_1$.)

I wish I could give a reference but in 1965 John Isbell claimed that the limit completion of the 2 element group (considered as a one object category) requires a proper class of steps, but I didn't understand his argument and I don't believe he ever published it.

• Monoids are reflective in categories (though the reflector is nasty), and groups are reflective in monoids, and abelian groups are reflective in groups, and abelian groups where every element is of order dividing 2 are reflective in abelian groups, so we might as well take the limit completion there. And abelian groups where every element is of order dividing 2 are just $\mathbb{F}_2$-vector spaces, right? So we might as well take the limit completion in $\mathbb{F}_2$-vector spaces. – Tim Campion Jul 8 '16 at 18:19
• In the first step, we get finite dimensional vector spaces (among others?) by taking finite products. In the second step, we get vector spaces, not of every dimension, but of arbitrarily large dimension (in particular, every dimension which is a $\beth$ number), by taking more products. In the third step, we get all vector spaces by splitting idempotents. So it seems to me that this converges in at most 3 steps.... – Tim Campion Jul 8 '16 at 18:23