7
$\begingroup$

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

  • 0
    @wildildildlife: I did say that I am likely to misuse some terms in the question...2012-06-28

2 Answers 2

4

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.

  • 0
    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.2012-06-29
8

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

  • 1
    @Asaf: colimits have maps going into them from the diagram, but satisfy a universal property with respect to maps going out of them. (This is why I think people just shouldn't use "direct limit" and "inverse limit." Nowadays you can say "directed colimit" and "codirected limit" instead.)2012-07-01