The Eventual Image, Part 2
Posted by Tom Leinster
We all love a good universal property. Objects with a simple universal property are usually important. So you might guess (mightn’t you?) that objects with two simple universal properties are more important still.
Perhaps the most famous example is direct sum. The direct sum of $A \oplus B$ of two vector spaces, modules, etc., is both the product and the coproduct of $A$ and $B$. And the importance of direct sums is written all over homological algebra.
In that example, the two universal properties are dual to one another. This is often the way. A less obvious example, but one whose importance becomes more and more apparent the deeper you dig into category theory, is the splitting of idempotents. This process can be viewed as either a limit or a colimit.
Objects with two universal properties are extra special, then. When the universe hands you one, it’s a treat.
Now: it’s Christmas. Ordinary people give each other socks. But since you already have enough socks, I give you instead: a machine for producing objects with two dual universal properties. Merry Christmas!
‘What kind of universal properties?’ I hear you ask. Well, in Part 1, I posed a puzzle. I mentioned three familiar categories: finite sets, finite-dimensional vector spaces, and compact metric spaces (with distance-decreasing maps). I pointed out that in all three, there is a ‘doubly universal’ way of turning an object equipped with an endomorphism into an object equipped with an automorphism. The puzzle was:
What do these three categories have in common, making this work?
Let me say that more precisely. Given an object $X$ of one of these categories, together with an endomorphism $f$, we automatically get:
- a new object $im^\infty(f)$, the so-called eventual image of $f$
- an automorphism $\bar{f}$ of $im^\infty(f)$
- maps $im^\infty(f) \to X \to im^\infty(f)$ commuting with the endomorphisms $f$ and $\bar{f}$, whose composite is the identity. (Thus, $im^\infty(f)$ is a retract of $X$.)
The eventual image has two, dual, universal properties:
- every map from $(X, f)$ to an object equipped with an automorphism factors uniquely through $(im^\infty(f), \bar{f})$
- every map to $(X, f)$ from an object equipped with an automorphism factors uniquely through $(im^\infty(f), \bar{f})$.
(When $(Y, g)$ and $(Z, h)$ are objects equipped with endomorphisms, by a ‘map’ from one to the other I mean a map $Y \to Z$ making the evident square commute.)
In all three cases, the eventual image can be constructed explicitly as the intersection of the subspaces $X$, $f X$, $f^2 X$, … — hence the name.
No one solved the puzzle, though there were a lot of interesting comments — especially those from Ben Steinberg, which I’ll come back to. So I thought I’d have a go at solving it myself; and I think I’ve managed to do it.
To recap: we’re trying to write down sufficient conditions on a category $\mathbf{C}$ such that endomorphisms in $\mathbf{C}$ can be turned into automorphisms in a doubly universal way. These sufficient conditions should be satisfied by all three of the categories mentioned.
Here goes.
We suppose that $\mathbf{C}$ comes equipped with a factorization system, satisfying the properties that I’ll list in a moment. If you don’t know what a factorization system is, the idea is straightforward: it consists of two distinguished classes of maps in $\mathbf{C}$, which I’ll call the surjections and embeddings, satisfying various axioms (most prominent among which is that every map can be factorized as a surjection followed by an embedding). In our three example categories, the factorization systems I have in mind are as follows:
- Sets: surjections are surjections, and embeddings are injections.
- Vector spaces: surjections are linear surjections, and embeddings are linear injections.
- Metric spaces: surjections are distance-decreasing surjections, and embeddings are isometries (that is, distance-preserving maps).
(In fact, in all three cases, the surjections are the epics and the embeddings are the regular monics.)
The properties required are:
- Any embedding from an object into itself is an isomorphism.
- Every sequence $\cdots \rightarrowtail \cdot \rightarrowtail \cdot \rightarrowtail \cdot$ of embeddings has a limit.
- For every commutative diagram $\begin{matrix} \cdots &\rightarrowtail &\cdot &\rightarrowtail & \cdot &\rightarrowtail &\cdot \\ & & ↡ & & ↡& & ↡ \\ \cdots &\rightarrowtail & \cdot &\rightarrowtail &\cdot &\rightarrowtail &\cdot\\ \end{matrix}$ in which the horizontal maps are embeddings and the vertical maps are surjections, the induced map between the limits is also a surjection.
We also require the dual properties, which I’ll call 1*, 2* and 3*. For example, 1* says that any surjection from an object to itself is an isomorphism.
I’ll explain those conditions soon, but first let me state the result. Briefly put: any such category $\mathbf{C}$ satisfies the conclusion of the theorem stated near the beginning of Part 1. That theorem was phrased in terms of a simultaneous left and right adjoint, but it can be rephrased more explicitly as follows:
Theorem Let $\mathbf{C}$ be a category with a factorization system, satisfying the conditions above. Let $X$ be an object of $\mathbf{C}$ and $f$ an endomorphism of $X$. Then there exist an object $im^\infty(f)$, an automorphism $\bar{f}$ of $im^\infty(f)$, and maps
$(im^\infty(f), \bar{f}) \rightarrowtail (X, f) ↠ (im^\infty(f), \bar{f})$
whose composite is the identity, with the following two universal properties:
- whenever $g$ is an automorphism of an object $Y$, every map $(Y, g) \to (X, f)$ factors uniquely through the embedding $(im^\infty(f), \bar{f}) \rightarrowtail (X, f)$
- whenever $g$ is an automorphism of an object $Y$, every map $(X, f) \to (Y, g)$ factors uniquely through the surjection $(X, f) ↠ (im^\infty(f), \bar{f})$.
I won’t say anything about the proof, which I don’t think is either very hard or very interesting. But I’ll say something about the three conditions on $\mathbf{C}$.
Condition 1 says, roughly, that no object is isomorphic to a proper subobject of itself. That’s true of finite sets because a proper subset has strictly smaller cardinality. It’s true of finite-dimensional vector spaces because a proper subspace has strictly smaller dimension. It’s true of compact metric spaces because a proper subspace has strictly smaller ‘metric entropy’ — see this comment here.
Condition 1* says, roughly, that no object is isomorphic to a proper quotient of itself. This comment shows that it can be deduced from condition 1 if $\mathbf{C}$ has a closed structure with suitable properties. All three of our running examples do.
The importance of satisfying both conditions was brought out by questions of André Joyal. The fact that some familiar categories satisfy one condition but not the other was highlighted by Todd Trimble.
Conditions 2 and 2* simply assert the existence of a few limits and colimits. They’re innocuous. The only thing to note is that although we wouldn’t normally expect infinite limits and colimits to exist in a category of ‘finite’ objects, it’s OK in this case: in condition 2, for instance, we’re taking the intersection of smaller and smaller subobjects.
It would be nice to do without conditions 3 and 3*. I don’t know whether that’s possible. My proof seems to need them. But what do they mean?
Let’s think about condition 3 in our three categories. In $\mathbf{FinSet}$ or $\mathbf{FDVect}$ it’s trivially true, just because in either of those categories, any infinite chain of embeddings eventually stabilizes. In the category of compact metric spaces it’s a little less trivial. To prove the condition, first consider the case where the bottom row consists entirely of copies of the one-point space. In that case, the condition says that given a chain
$\cdots \hookrightarrow X_2 \hookrightarrow X_1 \hookrightarrow X_0$
of nonempty compact subspaces of a compact metric space, the intersection is also nonempty. This is true by compactness. And the general case reduces easily to this special one.
There’s another way of looking at condition 3, which I suspect will be more appealing to some readers and less appealing to others. Briefly, condition 3 says ‘the sequential limit along embeddings of surjections is a surjection’. But it’s automatically true that the sequential limit along embeddings of embeddings is an embedding. With a little thought, it follows that condition 3 could be re-stated equivalently as: taking sequential limits along embeddings respects factorizations.
That, anyway, is the theorem. We have three examples: the categories of finite sets, finite-dimensional vector spaces, and compact metric spaces. What other examples exist? There are easy variants of these three (e.g. finite groups or finite-dimensional associative algebras), but what about something substantially different?
Here’s where I think Benjamin Steinberg’s comments might come in. He invoked a bunch of results from the theory of topological semigroups, which I hope might be used to provide other examples of categories satisfying the conditions above. ‘Eventual image’ would then make sense in those categories. I’m thinking, particularly, that there might be some category of topological or uniform spaces that works. But I don’t know.
The other dimension to Ben’s comments is that he talks about actions of arbitrary semigroups (or monoids). I, on the other hand, have been restricting myself to an object $X$ equipped with a single endomorphism, which is the same thing as an action on $X$ by the additive semigroup of positive integers (or equivalently, the additive monoid of nonnegative integers).
Acting by an arbitrary semigroup opens up a whole new world. Who among us has never wanted to act on a vector space with two commuting operators? And as soon as you call an object equipped with an endomorphism a ‘discrete-time dynamical system’, as I did last time, you have to ask yourself: what about continuous-time dynamical systems? These can be modelled as actions by the additive monoid $[0, \infty)$ or the additive group $\mathbb{R}$.
But for now, at least, I’m sticking to the humble world of a single endomorphism, and I’d like to understand it properly.
Re: The Eventual Image, Part 2
Very nice!
Until now, I think that all the examples I knew of limit-colimit coincidence were absolute colimits (a.k.a. Cauchy colimits) for some kind of enrichment. Under very general hypotheses, absolute colimits are automatically also absolute limits. In fact, there’s a converse too: under suitable hypotheses, whenever a limit and a colimit coincide, they are absolute.
However, the context of all those theorems is enriched category theory. Is there some sense in which the presence of a factorization system can be regarded as an “enrichment”? Is the eventual image “absolute” for some kind of “enriched” functor?