Take the 2-minute tour ×

I recently found myself at a spot that I never believed I'll get (or at least not that soon in my career). I ran into a problem which seems to be best answered via categories.

The situation is this, I have a directed system of structures and the maps are all the inclusion map, that is $X_i$ for $i\in I$ where $(I,\leq)$ is a directed set; and if $i\leq j$ then $X_i$ is a substructure of $X_j$.

Suppose that the direct limit of the system exists. Can I be certain that this direct limit is actually the union? Namely, what sort of categories would ensure this, and what possible counterexamples are there?

I asked several folks around the department today, some assured me that this is the case for concrete categories, while others assured me that a counterexample can be found (although it won't be organic, and would probably be manufactured for this case).

The situation is such that the direct system is originating from forcing, so it's quite... wide and probably immune to some of the "thinkable" counterexamples (by arguments of [set theoretical] genericity from one angle or another), and so any counterexample which is essentially a linearly ordered system is not going to be useful as a counterexample.

Another typical counterexample which is irrelevant here is finitely-generated things, for example we can take a direct system of f.g. vector spaces whose limit is not f.g. but this aspect is also irrelevant to me; although I am not sure how to accurately describe this sort of irrelevance.

Last point (which came up with every person I discussed this question today), if we consider: $$\mathbb R\hookrightarrow\mathbb R^2\hookrightarrow\ldots$$ Then we consider those to be actually increasing sets in inclusion and not "natural identifications" as commonly done in categories. So the limit of the above would actually be $\mathbb R^{<\omega}$ (all finite sequences from $\mathbb R$).

share|improve this question
I hope that I gave a proper title, tags and didn't abuse the language too much. Do feel free to correct things if you see mistakes. –  Asaf Karagila Jun 28 '12 at 20:51
I should add that I did Google a bit, but I couldn't find anything that I figured was useful. Any particular pointing at a decent place to start (although I am mostly interested in the result and less in the theory of concrete categories) would be great. –  Asaf Karagila Jun 28 '12 at 20:57
Haven't really thought this through, but I guess if there is a free functor from Set to your category then it must be the union (since 'adjoints preserve limits'). –  wildildildlife Jun 28 '12 at 21:03
My category is not a specific one. I am sorta looking for some nice characterization of what sort of categories the direct limit would have to be union, and in what categories it won't be. –  Asaf Karagila Jun 28 '12 at 21:05
@wildildildlife: Not relevant here, since a direct "limit" is a colimit. –  Zhen Lin Jun 28 '12 at 21:23
show 3 more comments

2 Answers

up vote 4 down vote accepted

Your question essentially amounts to asking, "when does the forgetful functor $U : \mathcal{C} \to \textbf{Set}$ create directed colimits?" More generally, one could replace "directed colimit" by "filtered colimit". There is, as far as I know, no general answer.

Here is one reasonably general class of categories $\mathcal{C}$ for which there is such a forgetful functor. Let us consider a finitary algebraic theory $\mathfrak{T}$, i.e. a one-sorted first-order theory with a set of operations of finite arity and whose axioms form a set of universally-quantified equations. For example, $\mathfrak{T}$ could be the theory of groups, or the theory of $R$-modules for any fixed $R$-module. Then, the category $\mathcal{C}$ of models of $\mathfrak{T}$ will be a category in which filtered colimits are, roughly speaking, obtained by taking the union of the underlying sets. This can be proven "by hand", by showing that the obvious construction has the required universal property: the key lemma is that filtered colimits commute with finite limits in $\textbf{Set}$ – so, for example, $\varinjlim_{\mathcal{J}} X \times \varinjlim_{\mathcal{J}} Y \cong \varinjlim_{\mathcal{J}} X \times Y$ if $\mathcal{J}$ is a filtered category. Mac Lane spells out the details in [CWM, Ch. IX, §3, Thm 1].

Addenda. Fix a one-sorted first-order signature $\Sigma$. Consider the directed colimit of the underlying sets of some $\Sigma$-structures: notice that the colimit inherits a $\Sigma$-structure if and only if the operations and predicates of $\Sigma$ are all finitary. Qiaochu's counterexample with $\{ 0 \} \subset \{ 0, 1 \} \subset \{ 0, 1, 2 \} \subset \cdots$ can be pressed into service here as well.

So let us assume $\Sigma$ only has finitary operations and predicates. The problem is now to establish an analogue of Łoś's theorem for directed colimits. Let $\mathcal{J}$ be a directed set and let $X : \mathcal{J} \to \Sigma \text{-Str}$ be a directed system of $\Sigma$-structures. Let us say that a logical formula $\phi$ is "good" just if $X_j \vDash \phi$ for all $X_j$ implies $\varinjlim X \vDash \phi$ (where $\varinjlim X$ is computed in $\textbf{Set}$ and given the induced $\Sigma$-structure).

  1. It is not hard to check that universally quantified equations and atomic predicates are good formulae.

  2. The set of good formulae is closed under conjunction and disjunction.

  3. The set of good formulae is closed under universal quantification.

  4. The set of good formulae is not closed under existential quantification: the formula $\forall x . \, x \le m$ (with free variable $m$) is a good formula in the signature of posets, but $\exists m . \, \forall x . \, x \le m$ is clearly not preserved by direct limits.

  5. However, a quantifier-free good formula is still a good formula when prefixed with any number of existential quantifiers.

  6. In particular, the set of good formulae is not closed under negation: the property of being unbounded above can be expressed as a good formula in the signature of posets with inequality, but its negation is the property of being bounded above.

Section 6.5 of [Hodges, Model theory] seems to have some relevant material, but I haven't read it yet. The point, I suppose, is that there are some fairly strong conditions that the theory in question must satisfy before the directed colimit in $\textbf{Set}$ is even a model of the theory, let alone be a directed colimit in the category of models of the theory.

share|improve this answer
One also remarks that some people define "finitary algebraic theory" to mean "a monad $T : \textbf{Set} \to \textbf{Set}$ that preserves filtered colimits", making this very tautologous... –  Zhen Lin Jun 28 '12 at 22:05
I'm not sure if it's a good thing or a bad thing, but I didn't understand this answer due to an extreme chasm in form of [mathematical language. I'll get someone to translate it to me tomorrow (it's too late for understanding new category related topics anyway). Also, this makes me think that the model-theoretic approach would have been better for me... :-) –  Asaf Karagila Jun 28 '12 at 22:50
I actually proved part of the Łos theorem analogue in my case. It needs a minor tweaking to avoid trivialities it it works. I hope to extend it to simple second-order formulae too. –  Asaf Karagila Jun 29 '12 at 6:06
add comment

I don't understand whether you actually have a counterexample or not so let me supply one for the sake of completeness. Consider the category $\text{CHaus}$ of compact Hausdorff spaces. I can write down a filtered colimit of finite sets $\{ 1 \} \to \{ 1, 2 \} \to \{ 1, 2, 3, ... \}$ whose union is $\mathbb{N}$. The filtered colimit needs to be compact Hausdorff, so actually it's the Stone–Čech compactification $\beta \mathbb{N}$, which is much larger than the union.

In general colimits in $\text{CHaus}$ are obtained by first taking the colimit in $\text{Top}$ and then taking the Stone–Čech compactification. Limits are as in $\text{Top}$ because the forgetful functor to $\text{Top}$ has a left adjoint, namely the Stone–Čech compactification! On the other hand, limits and colimits in $\text{Top}$ have underlying sets the expected thing because the forgetful functor to $\text{Set}$ has both a left and a right adjoint, so preserves both limits and colimits.

If you just want to identify sufficient conditions, the forgetful functor having a right adjoint implies preserving colimits implies preserving filtered colimits so that seems like a good thing to try. (Note that this is not usually what is meant by being able to construct a free object; this is usually a left adjoint to the forgetful functor.) On the other hand this is far from necessary; the forgetful functor $\text{Ab} \to \text{Set}$ is far from preserving colimits but it preserves filtered colimits (I'm pretty sure).

share|improve this answer
I don't really have a counterexample. All those which were given to me were brushed aside as irrelevant to the case. I will have to sit and carefully verify this idea. It seems to have potential, but I wouldn't be surprised if the construction as a whole would cancel it out. As I said, linear systems are too "thin" to be of any real concern in this case. You have given me something to do for the time being, though. –  Asaf Karagila Jun 28 '12 at 21:46
@Asaf: well there are "thick" counterexamples here too. You can consider very big filtered colimits of compact Hausdorff spaces. –  Qiaochu Yuan Jun 28 '12 at 22:15
Well, as I said the directed systems rise naturally from forcing, and those tend to have quirks not always found in the "mathematical savanna". I have translated your suggestion into a forcing argument and I am about to finish the argument soon, although I cannot foresee the result (whether this counterexample is good, or does it falls into the list of interested-but-irrelevant). –  Asaf Karagila Jun 28 '12 at 22:19
Hmmm. This is actually much harder than I expected it to be (and I have a grave suspicion why, too). I suppose that compact Hausdorff spaces provide a sufficient counterexample (although it may be possible to remedy the situation by a minor modification of the forcing, I will have to think about it). Thanks. –  Asaf Karagila Jun 28 '12 at 22:36
I'm fairly certain how to fix things with the aid of an inaccessible cardinal, which would make this a non-issue. I was hoping large cardinals would come by eventually... Regardless to the above, I believe that there might be a way to get things working without the aid of large cardinals, but I'm not sure how (yet). –  Asaf Karagila Jun 28 '12 at 22:52
show 5 more comments

Your Answer


