December 25, 2011

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:

1. Any embedding from an object into itself is an isomorphism.
2. Every sequence $\cdots   \rightarrowtail \cdot \rightarrowtail \cdot \rightarrowtail \cdot$ of embeddings has a limit.
3. 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.

Posted at December 25, 2011 12:01 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2483

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?

Posted by: Mike Shulman on December 25, 2011 7:32 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Thank you, Mike.

Can you give a link or reference to the results you mention in your first paragraph?

As for regarding factorization systems as some kind of enrichment, that’s an interesting idea. I should think about it.

And as to whether eventual images are somehow ‘absolute’, this reminds me of the conversation we had after you mentioned the fact that objects with two universal properties need not be unique up to structure-preserving isomorphism. (If $X$ and $Y$ satisfy the same two universal properties then there’s a unique isomorphism $i: X \to Y$ that’s structure-preserving for the first property, and similarly $j: X \to Y$ for the second, but perhaps $i \neq j$.) In the case of the eventual image, it does actually have this uniqueness property. In this sense, it’s ‘robust’. That’s presumably not the same as absoluteness, whatever that might mean, but it feels similar somehow.

Posted by: Tom Leinster on December 25, 2011 2:53 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Can you give a link or reference to the results you mention in your first paragraph?

Unfortunately, I can’t. I can state it more precisely, though. Let $J\colon A ⇸ B$ be a $V$-profunctor between small $V$-categories, for some nice enriching category $V$ (complete, cocomplete, closed symmetric monoidal). Then the following are equivalent:

1. $J$ has a right adjoint $J^\ast\colon B ⇸ A$ in the bicategory of profunctors (i.e. $J$ is a “Cauchy module”).
2. $J$-weighted colimits are absolute, i.e. preserved by any $V$-functor.
3. There is a profunctor $J^\ast\colon B ⇸ A$ such that $J$-weighted colimits naturally coincide with $J^\ast$-weighted limits.

(1) $\Rightarrow$ (2) is in Street’s “Enriched categories and cohomology”, but I don’t know a reference for the rest of it. Does anyone?

Posted by: Mike Shulman on December 26, 2011 8:01 PM | Permalink | PGP Sig | Reply to this

Re: The Eventual Image, Part 2

I didn’t know that (3) was equivalent to the other two, but ‘(1) iff (2)’ is in Street’s Absolute colimits in enriched categories, Cahiers 1983.

Posted by: Finn Lawler on December 26, 2011 11:29 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

‘(1) iff (2)’ is in Street’s Absolute colimits in enriched categories

Excellent, thanks!

Posted by: Mike Shulman on December 30, 2011 4:52 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Is there some sense in which the presence of a factorization system can be regarded as an “enrichment”?

You know, this is the first surprising question I’ve heard about factorization systems in a while! And you (perhaps) know how I like to think about factorization systems, even if you’re better at it than I am.

Hmm… A factorization system asks for a $\mathcal{P}\{0,1\}$-filtration on all the homsets, and we ask that composition preserves this filtration: a composite of epis is epi, … of monos is mono, etc.

But the versalness of composing epis with monics gives more something; it sounds like a property (a property of factorization systems among $\mathcal{P}\{0,1\}$-filtration-enriched categories), and it can be specified by stuff (an algebraic factorization with properties…), but if it says more about each homset I can’t see yet.

Anyway, there’s a trivial start.

Posted by: Jesse C. McKeown on December 26, 2011 6:47 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Perhaps a way forward would involve the characterization of factorization systems as distributive laws in spans? (We discussed that back here in another context.)

My vague thought is that we don’t actually need categories-with-factorization-systems to literally be enriched categories; we just need the 2-category of categories-with-factorization-systems to be equipped with proarrows in a well-behaved way. And since the canonical proarrow equipment of profunctors arises from considering categories as monads in spans, perhaps it has a natural extension to distributive laws in spans.

Posted by: Mike Shulman on December 26, 2011 8:07 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Very interesting!

I don’t know if you have heard about inclusion systems, which are similar to these factorization systems you’re mentioning. It is a current area of research.

Posted by: Marduk on December 25, 2011 10:11 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

No, I hadn’t heard about inclusion systems — thanks. For some reason my PDF readers are unable to search for text in the PDF file you link to, so in case anyone else has the same problem, I’ll point out: the definition of inclusion system is on page 10.

My first impression is that inclusion systems seem against the geenral categorical spirit of not distinguishing between isomorphic objects. An inclusion system in a category consists of a class $E$ of epics and a class $I$ of maps, called ‘inclusions’, satisfying some axioms. A basic example is the category of sets with $E =$ surjections and $I =$ inclusions — not just injections, but actual subset inclusions. I find this puzzling. I’m not sure the distinction between a subset inclusion and an injection really makes sense to me. But is there a specific reason why you mention them in the context of this post? Do you see a role for them here?

Posted by: Tom Leinster on December 25, 2011 2:39 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

An enriched-category way to codify the distinction between injections and actual inclusions between material sets is via an $\mathcal{M}$-category structure, where the “tight morphisms” are taken to be subset inclusions.

Posted by: Todd Trimble on December 25, 2011 4:24 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

I first encountered this sort of thing in this paper, where the same idea (they call it a “system of inclusions”) is used to describe exactly the extra structure that the category of material sets has. My first reaction was like Tom’s: what the heck? But I got happier when I realized that I could think of it as an $\mathcal{M}$-category, like Todd mentions, rather than an ordinary category with extra (“evil”) structure.

On the other hand, like Tom, I don’t see any connection to the current post, where everything is happening up to isomorphism as usual.

Posted by: Mike Shulman on December 25, 2011 7:49 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

There’s something I forgot to say:

$im^\infty(f^r) = im^\infty(f),$

for all $r \geq 1$.

Here $f: X \to X$ is any endomorphism in any category $\mathbf{C}$ with the properties above. The equation says something like ‘$im^\infty$ is a dynamical construct’. By way of contrast, it is blatantly false that $im(f^r) = im(f)$, where $im$ is the ordinary image — the image of $f$ applied just once.

You might interpret it as follows. Think of $f$ as an operation on $X$ that’s applied over and over again, once every second. One observer might choose to observe the state of affairs only once every ten seconds, while another watches everything. They will see the same eventual image: $im^\infty(f^{10}) = im^\infty(f)$. The eventual image is independent of the time scale chosen.

Similar things happen in other dynamical systems. For example, let $f$ be a rational function with complex coefficients. It has a Julia set $J(f)$, which is the subset of the Riemann sphere consisting of the points at which iteration of $f$ is, in a precise sense, unstable. And it’s a fact that

$J(f^r) = J(f)$

for all $r \geq 1$.

Posted by: Tom Leinster on December 25, 2011 7:03 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Dear Tom, maybe we should regard the eventual image of an endomorphism f:X–>X as an object Evim(f) equipped with an automorphism (the automorphism induced by f), instead of a naked object. In which case the object Evim(f^n) is obtained from the the object Evim(f) by applying the n-fold power operation on the automorphism (this called an Adams operation). Another property of the eventual image is its invariance under conjugation, if f:X–>Y and g:Y–>X, then Evim(gf) is isomorphic to Evim(fg). Is this also true for Julia sets? It seems that the eventual image behaves like some kind of higher trace. Let me stress that the objects Evim(gf) and Evim(fg) are canonically isomorphic in two ways (at least)! I am confused with the meaning of this.

Posted by: André Joyal on January 1, 2012 11:30 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Evim(gf) is isomorphic to Evim(fg). Is this also true for Julia sets?

This is bad news for the analogy I was pushing, but maybe it was destined to break down. After all, the classical study of complex iteration is all about rational functions. These are holomorphic self-maps of the Riemann sphere that (except in trivial cases) are surjective but not injective. So it’s quite unlike the situations at hand, where surjective endomorphisms are automatically invertible.

Posted by: Tom Leinster on January 21, 2012 10:50 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

I definitely agree that we should regard the eventual image as coming equipped with an automorphism. I’m thinking of eventual image as a functor

$im^\infty: \mathbf{Endo} \to \mathbf{Auto}$

where $\mathbf{Endo}$ is the category of objects (of our category) equipped with an endomorphism, and $\mathbf{Auto}$ is the category of objects equipped with an automorphism.

Then the statement about $n$th powers (and thanks for the name “Adams operation”) becomes the following. Let $n \geq 0$. Each of the categories $\mathbf{Endo}$ and $\mathbf{Auto}$ has an endofunctor $A_n$ sending $(X, f)$ to $(X, f^n)$. For $n \geq 1$, the square

$\begin{matrix} \mathbf{Endo} &\stackrel{im^\infty}{\to} &\mathbf{Auto}\\ A_n \downarrow & &\downarrow A_n\\ \mathbf{Endo} &\stackrel{im^\infty}{\to}& \mathbf{Auto} \end{matrix}$

commutes.

The canonical isomorphism between $im^\infty(g f) = \im^\infty(f g)$ is nice — thanks. I hadn’t consciously realized, though I’d been thinking about very closely related things (more on which below). The way I’d see it is this. Given $f: X \to Y$ and $g: Y \to X$, we get a commutative square

$\begin{matrix} X &\stackrel{f}{\to} &Y \\ g f \downarrow& &\downarrow f g \\ X &\stackrel{f}{\to} &Y. \end{matrix}$

This is a map $f: (X, g f) \to (Y, f g)$ in $\mathbf{Endo}$. By functoriality, it induces a map $f: im^\infty(g f) \to im^\infty(f g)$ in $\mathbf{Auto}$. Similarly, $g$ induces a map in the opposite direction:

$im^\infty(g f) \stackrel{\stackrel{f}{\to}}{\stackrel{\longleftarrow}{g}} im^\infty(f g)$

The composite map $g f : im^\infty(g f) \to im^\infty(g f)$ is an isomorphism (because $g f$ acts as an automorphism on $im^\infty(g f)$), and similarly on the other side. So $f: im^\infty(g f) \to im^\infty(f g)$ is an isomorphism.

Similarly, $g: im^\infty(f g) \to im^\infty(g f)$ is an isomorphism. But it’s not the inverse to $f$, so $g^{-1}$ and $f$ are different canonical isomorphisms from $im^\infty(g f)$ to $im^\infty(f g)$.

OK, maybe I’ve recreated your thought now…

There must actually be a $\mathbb{Z}$-indexed family of isomorphisms $im^\infty(g f) \to im^\infty(f g)$, namely

$f(g f)^k = (f g)^k f : im^\infty(g f) \to im^\infty(f g)$

for each $k \in \mathbb{Z}$. When $k = 0$, this is $f$; when $k = -1$, this is $g^{-1}$.

(I don’t know whether the Julia set of $f g$ is equal to that of $g f$. It’s true in trivial cases, but I don’t know how to calculate the simplest nontrivial case. Julia sets do have another property that I find quite startling. Let $f$ and $g$ be complex rational functions, both of degree $\geq 2$. If $f g = g f$ then $J(f) = J(g)$.)

Posted by: Tom Leinster on January 2, 2012 12:51 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Speaking of eventual image as higher trace (as André was), there are some things that can be said in the vector space case.

Let $T$ be a linear operator on a finite-dimensional vector space $X$ over an algebraically closed field $k$. Write $ker^\infty(T)$ for its eventual kernel (the union of $ker(T^n)$ over all positive integers $n$). Then

$X = ker^\infty(T) \oplus im^\infty(T),$

but also

$X = \bigoplus_{\lambda \in k} ker^\infty(T - \lambda).$

In fact the decompositions are compatible, in the sense that

$im^\infty(T) = \bigoplus_{\lambda \neq 0} ker^\infty(T - \lambda).$

The dimensions of the subspaces $ker^\infty(T - \lambda)$ are the algebraic multiplicities of the eigenvalues. So the restricted operator $T$ on $im^\infty(T)$ has the same spectrum, with the same algebraic multiplicities, as $T$, except possibly at $0$. In particular, it has the same trace.

It’s also a fact (which some of us recently discussed) that if $f: X \to Y$ and $g: Y \to X$ are linear maps then

$ker^\infty(g f - \lambda) \cong ker^\infty(f g - \lambda)$

for each $\lambda \neq 0$. Taking the direct sum over all $\lambda \neq 0$ gives

$im^\infty(g f) \cong \im^\infty(f g).$

In fact, the proof of the isomorphism for the eventual kernels is similar to the one for eventual images. Whether $\lambda$ is zero or not, $f$ and $g$ restrict to maps

$ker^\infty(g f - \lambda) \stackrel{\stackrel{f}{\to}}{\stackrel{\longleftarrow}{g}} ker^\infty(f g - \lambda).$

The composite map $g f$ is an automorphism of $ker^\infty(g f - \lambda)$ unless $\lambda = 0$, and similarly on the other side. So, assuming that $\lambda \neq 0$, this restricted map $f$ is an isomorphism. So too is the inverse of the restricted map $g$, and more generally, so is $f (g f)^r = (g f)^r f$ for any $r \in \mathbb{Z}$.

Posted by: Tom Leinster on January 2, 2012 1:11 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Tom, there is a natural way to exclude 0 from the roots of the characteristic polynomial of a matrix A. It is to use the determinant of the matrix I-\lambda A instead of the matrix A-\lambda I. The former is a polynomial with constant terms 1. It may be called the *characteristic series* of A. It is closely related to the *Fredholm determinant* of A. The characteristic series of a nilpotent operator is equal to 1. The characteristic series of a trace class operator acting on an Hilbert space can be a true power series.

Posted by: André Joyal on January 2, 2012 5:27 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

André wrote:

Tom, there is a natural way to exclude 0 from the roots of the characteristic polynomial of a matrix $A$. It is to use the determinant of the matrix $I-\lambda A$ instead of the matrix $A-\lambda I$.

Ah, so simple! Thanks!

Posted by: Tom Leinster on January 2, 2012 6:55 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Tom, I have a semi-unified proof from a different viewpoint. If $K$ is a field, then equip $V=K^n$ with the discrete topology and notice that $End(V)$ is a closed submonoid in the compact-open topology on Cts(V,V) (=pointwise convergence topology). Let $f$ be an endomorphism of $V$ and consider the closed subsemigroup $S$ generated by $f$. Then one has that the ideals $f^nS$ have non-empty intersection because of descending chain condition on $V$. Moreover, if $I$ is the intersection, then using that $I=f^NS$ for $N$ large enough, it follows that $fI=I$. Now one can apply the same proof as in the case of compact semigroups to conclude that $I$ is a group etc. This is of course not categorical. Ben
Posted by: Benjamin Steinberg on December 27, 2011 8:42 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Merry C*****mas. As time goes on (ie as I upgrade Ubuntu) my ability to connect to the internet gets worse and worse, so I believe I’ve missed the day itself. But thanks for the present although instinctively I think that things with two different universal properties are suspicious, like washer-dryers, that neither wash nor dry quite as well as one would like.

Posted by: Eugenia Cheng on December 29, 2011 3:36 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Your comment made me realize that I’d missed a whole class of examples of objects with two universal properties. An object of a category $C$ is, as we know, initial iff it’s the colimit of the empty diagram in $C$. But it’s also initial iff it’s the limit of the identity functor on $C$. Since every universal property can be rephrased in terms of initial objects, every object with a universal property has two universal properties.

On the other hand, they’re not dual universal properties in the sense I’ve been using the term. One’s a limit and one’s a colimit, but they’re limits and colimits over different diagrams.

Posted by: Tom Leinster on December 29, 2011 10:07 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

That’s an interesting point.

The coinciding limits and colimits that I mentioned earlier are limits and colimits of the same diagram, but the weights might be different for the limit and the colimit. In fact, in general they have to be different: since weights for limits and weights for colimits have different variances, asking whether they’re the same would be a type error. But it happens that in many cases, the diagram shape is self-dual and both weights turn out to be “conical”, so the colimit can be regarded as the dual of the limit.

Posted by: Mike Shulman on December 30, 2011 4:51 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Here’s an example of a useful object that’s a limit and a colimit: the initial algebra in the category of algebras for a functor $F : \mathcal{C} \to \mathcal{C}$. Ghani et al. show in “Build, Augment and Destroy, Universally” that it’s also the colimit of the forgetful functor taking $F$-$\mathbf{alg}$ to $\mathcal{C}$. Liberal interpretation of the terms is required here, since they’re not quite limits in the same category. The former is in $F$-$\mathbf{alg}$ and the latter in $\mathcal{C}$. And they’re certainly not dual in the sense of this article.

The existence of the latter gives you a “build” operation on your datatype, which is very useful in the semantics of inductive datatypes.

Posted by: Tom Ellis on December 30, 2011 5:12 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Actually this result is not much more than Tom’s observation above that if the initial object exists then it’s the limit of the identity functor. It happens to be remarkably useful in this context though.

Posted by: Tom Ellis on December 31, 2011 8:35 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

I am impressed by Tom’s abstract theory of the eventual image. Another example, slightly more general than the category of finite dimensional vector spaces, is the category of finitely generated torsion modules over a principal ideal domain. I do not know if it can be extended to more general domains.

We may say that an endomorphism of a compact (metrisable) space is *chaotic* if it cannot be turned into a weak contraction with respect to a metric defining the topology of that space. Is this a standard terminology? Let me use it in this post. If I understand Benjamin correctly, an endomorphism is chaotic if and only if the set of its iterates is not equicontinuous. A surjective endomorphism which is not bijective must be chaotic by the proof of Tom. A simple example of a chaotic endomorphism is the endormorphism of the Cantor space {0,1}^N which is induced by the successor map of the set of natural numbers. An example of a chaotic automorphism is the automorphism of {0,1}^Z which is induced by the successor map of set of integers. The automorphism cannot be an isometry for any metric defining the topology of the Cantor space {0,1}^Z. It shows that the topological space {0,1}^Z cannot be a product of Z copies of {0,1} in any reasonnable category of metric spaces.

Happy New Years to all!

Posted by: André Joyal on December 30, 2011 7:24 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Andre, It is worse than this. Let $X$ be a compact Hausdorff space and $f$ a cts endomorphism of $X$. The enveloping semigroup $E(f)$ of $f$ (in the sense of Furstenburg and Ellis) is the closure of $\{f^n|n\geq 1\}$ in the topology of pointwise convergence. This is a compact left semitopological semigroup (left translations are continuous). This semigroup will be jointly continuous iff the powers of $f$ are equicontinuous. The action of $E(f)$ on $X$ is only one-sided continuous (for each fixed $s\in E(f)$, the action of $s$ is continuous). Nonetheless, many dynamical properties of $f$ are encoded in the action of $E(f)$ (e.g., recurrent points, uniformly recurrent points, etc.) If one considers the one-sided shift $f$ on the Cantor set, then it is known that $E(f)$ is the Stone-Cech compactification $\beta N$ with its natural left semitopological structure. So this is as “bad” an example as possible. Furstenburg used $E(f)$ in this case to give a nearly trivial proof of van der Waerden’s theorem on arithmetic progressions as a consequence of the existence of idempotents in the minimal ideal of $E(f)$ (one just needs one-sided continuity to get the existence of idempotents). The wonderful book of Hindmann and Strauss, Algebra in the Stone-Cech compactification, shows how to derive most Ramsey theoretic results using idempotents of Stone-Cech compactifications of semigroups. Ben
Posted by: Benjamin Steinberg on January 1, 2012 3:09 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Here is another example of a dual adjoint property which explains the eventual range case. Let $M$ be a monoid and $e$ a central idempotent. Then $eM$ is a monoid with identity $e$. There is a surjective homomorphism $f\colon M\to Me$ given by $f(m)=em$. This yields an essential geometric morphism of classifying toposes $(f_!,f^*,f_*)$ where in this case $f_!=f_*$ is the “restriction” $X\mapsto Xe$. Thus $X\mapsto Xe$ is both left and right adjoint to the “inclusion” of $BMe$ in $BM$. The eventual range adjunctions are a special case of this.
Posted by: Benjamin Steinberg on January 1, 2012 3:17 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Thanks Benjamin for the extra informations on the properties of the one-sided shift map. It is very interesting. I must absolutly get a copy the book of Hindmann and Strauss. I am delighted to learn that the theory of compact semi-group has applications to number theory! The connection between locally compact groups and number theory is an important theme in the work of André Weil. His book “Basic Number theory” is really about the classification of all locally compact (non-discrete) fields, commutative or skew. The adèles of a number field are forming a nice locally compact ring. The work of Langlands is rooted in the representation theory of semi-simple (locally compact) Lie groups. I would love to understand Langlands program… I have been studying it with a few collegues during last year. Our strategy is to study simple examples. A kind of bottom-up approach. We shall keep digging until we can see the light at the end of the tunnel. It may take us years.

Posted by: André Joyal on January 2, 2012 12:08 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

There is a nice paper by Bergelson, Furstenburg, Hindman and I think others in L’enseignments mathématiques giving the proof of van der Waerden’s theorem using the algebra of $\beta N$ from scratch. It is a proof I can usually reconstruct. The combinatorial proof I never remember at all. It is cute how to construct the semigroup structure on $\beta S$ for a semigroup S. It is pure category theory. If $s\in S$ the composition of the right translation by $s$ with the inclusion $S\to \beta S$ extends to a mapping $\beta S\to \beta S$ giving a right action of $S$ on $\beta S$. Now if you fix $t\in \beta S$ you get a map $S\to \beta S$ by having each element of $S$ acting on $t$. This also extends to a map $\lambda_t\colon \beta S\to \beta S$. We now define the semigroup product by $tu=\lambda_tz(u)$. Then left translations are cts by construction. It turns out (at least if S is cancellative) that the only right translations that are cts are the ones from $S$. Using the universal property of the Stone-Cech compactification one can show that the category of left actions of $S$ on compact Hausdorff spaces is equivalent as a concrete category to the category of left actions of $\beta S$ on compact Hausdorff spaces where an action of $\beta S$ on $X$ is a mapping $\beta S\times X\to X$ (not necessarily cts) such that each element of $\beta S$ as a cts function on $X$.
Posted by: Benjamin Steinberg on January 2, 2012 2:34 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

[Slightly off topic]

Benjamin, I’m in a bit of a hurry as I type this (things to do, courses to prepare, etc etc) but it looks like the construction you give is, as you may know, (more or less) what Banach algebraists call “constructing the first Arens product on the second dual of $l^1(S)$.”

As I keep meaning to write on the nLab but am constantly too lazy/disorganised to do, one of Arens’s papers on this subject observes that the whole process can be carried out more abstractly, in a setting which he describes using things he calls “phyla”… and which most readers of this blog would call a concrete, closed, symmetric monoidal category. I never worked out the details, but it always struck me as plausible that taking Set as the base category would give more or less what you outline, without the need to introduce Banach algebras.

For others reading: readers with long memories for trivia may recall a question I posted *years ago* to the category-theory mailing list, asking vaguely if people had been studying Arens products in category theory. The question/request still stands - I would particularly love to know if diagrammatic methods for working in closed categories could be used to streamline or clarify calculations that are usually done by Banach algebraists with iterated limits and spurious choices of approximating nets. (Email me if interested!)

Posted by: Yemon Choi on January 2, 2012 7:13 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Yemon, all I know about Arens product are via Matthias Neufang. My understanding is that all the usual semigroup compactifications are obtained from the Arens product by going to the spectrum of the appropriate Banach algebra. I thought one looks at bounded functions in the discrete case and weakly almost periodic functions in the topological setting. But I am an algebraist, so what do I know? I think that one can use in all these semigroup contexts an argument via universal properties but I don’t know if this can be pushed to Banach algebras in general.
Posted by: Benjamin Steinberg on January 3, 2012 10:00 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Ben, I found this comment of yours rather thought-provoking. Below are three thoughts it provoked.

First let me say back to you what I think you said, for the good of my soul. Any monoid homomorphism $f: M \to N$ induces a functor

$f^* = -\circ f: Set^{N^{op}} \to Set^{M^{op}}$

which has a left adjoint $f_!$ and a right adjoint $f_*$. (That much is true just because $f$ is a functor between small categories.) Now, given a monoid $M$ and a central idempotent $e \in M$, we get a new monoid $M e$ and a monoid homomorphism $f: M \to M e$. And in that case, as you explained, $f_! = f_*$.

My three thoughts:

1. You say this “explains the eventual range case”. What do you mean? What exactly is the connection between eventual images and this fact about monoids?
2. A special case of the fact you explained is this. Let $M$ be the two-element monoid $\{1, e\}$ consisting of the identity and an idempotent. Then $M e$ is the trivial monoid. Now $Set^{M^{op}}$ is the category in which an object is a set equipped with an idempotent, $Set^{(M e)^{op}} = Set$, and $f^*$ is the ‘diagonal’ functor equipping a set with its identity. The simultaneous left-and-right adjoint $f_! = f_*$ splits the idempotent. This is the double universal property mentioned at the beginning of my post.
3. In general, for which functors $F: \mathbf{A} \to \mathbf{B}$ is it the case that $F_! = F_*: Set^{\mathbf{A}^{op}} \to Set^{\mathbf{B}^{op}}?$ Is an explicit condition known? Any such functor is certainly final — that’s what you get by testing for equality at the presheaf with constant value $1$. And any such functor preserves all limits in $\mathbf{A}$ that exist. But those conditions can’t be enough. The answer must have something to do with absolute flatness.
Posted by: Tom Leinster on January 2, 2012 4:04 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

In general, for which functors $F\colon A\to B$ is it the case that $F_!=F_*$? Is an explicit condition known?

Well, $F_!$ is a colimit weighted by the profunctor $B(F,1)$, and $F_*$ is a limit weighted by the profunctor $B(1,F)$, so point (3) from my comment here implies that a necessary and sufficient condition is that $B(F,1) \dashv B(1,F)$ in the bicategory $Prof$. (The opposite adjunction $B(1,F) \dashv B(F,1)$ is the one that holds for any functor $F$.) This is sort of tautological and not very explicit, but it might be a starting point.

Posted by: Mike Shulman on January 2, 2012 7:36 AM | Permalink | PGP Sig | Reply to this

Re: The Eventual Image, Part 2

Tom, For the metric setting take M to be the free compact monoid on 1-generator, take e to be the unique non-identity idempotent. Then eM is the free compact group on 1-generator. Clearly a weak contraction is an action of M on a metric space by weak contractions and an isometry is an action of eM by isometries. The adjunction in my last comment restricts to these subcategories and is eventual range. The vector space setting is similar using free pro-algebraic monoids.
Posted by: Benjamin Steinberg on January 3, 2012 9:50 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

Tom, My original answer was in the metric space, take M the free compact monoid on 1-generator, e the unique non-identity and eM is then the free compact group on 1-generator and the eventual range for weak contractions is my adjunction restricted to appropriate subcategories. The vector space case uses pro-algebraic monoids. But here is a better answer: there is a free monoid with eventual range in some sense. It isn’t exact but does what you want in your cases. Let M be the disjoint union of the monoid of nonnegative integers and the integers. The integers form the unique minimal ideal of M and the non-negative integers act on the integers in the usual way. Clear an M-set is the same thing as a map f of a set X and a subset Y (non-empty if X is) on which f acts as a permutation. If e is the copy of 0 in Z, then an eM set is just a permutation. So we get an adjunction between permutations and mappings with a prescribed ‘eventual range’.
Posted by: Benjamin Steinberg on January 3, 2012 10:32 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

I want to put a topos perspective on eventual range in 3 contexts. Let (X,f) be a discrete set X and a self-map $f:X\to X$. The corresponding dynamical system is eventually periodic if for each $x\in X$ the trajectory $\{f^n(x)\}$ is finite. The periodic points (those points with a cyclic orbit under f) make up the eventual range The eventually periodic discrete dynamical systems form a category, in fact a coherent topos. If $M$ is the free profinite monoid on 1-generator, then this topos is BM, the category of cts left $M$-sets. This topos turns out to have two points: the underlying set functor and the eventual range. Note the above topos is the Ind completion of the subcategory of finite dynamical systems (which are the coherent objects I believe). The pro-completion of the category of finite dynamical systems is the category of equicontinuous compact totally disconnected dynamical systems: pairs $(X,f)$ where X is compact totally disconnected, f is a cts self-map and the submonoid generated by f is equicontinuous for the uniformity generated by finite partitions into open subsets. If $X$ is metrizable, one may assume f is a contraction. The eventual range, being a left exact functor, is pro-representable. The representing object is (Me,a) where e is the unique non-identity idempotent and a is the free generator. It follows that the eventual range is a representable functor on compact totally disconnected equicontinuous dynamical systems. I have a number of unpublished results on classifying toposes of profinite monoids.
Posted by: Benjamin Steinberg on January 11, 2012 5:30 PM | Permalink | Reply to this

Re: The Eventual Image, Part 2

I’ve been reading Awodey’s “Category Theory” and ran across a construction that seems quite close to the one desired. At example 5.33, he introduces the $\mathrm{\omega CPO}$, a poset that is $\omega$-cocomplete. This his theorem 5.34: “If $D$ is an $\mathrm{\omega CPO}$ with initial element $0$ and $h:D\to D$ is continuous, then $h$ has a fixed point $h\left(x\right)=x$ which, moreover, is least among all fixed points.”

Using a slightly different hammer… On thinking about the first post in this series, the switch from $f:X\to X$ to the category with objects all subsets of X, $𝑃\left(X\right)$, and two classes of arrows. The first class of arrows is the poset created by subset inclusion, which has initial object $X$ and terminal object $\varnothing$. The other class of arrows is the action of $f$, which perhaps we should label $f$Y$:Y\to f\left(Y\right)$ for Y each subset of X. The union of both classes of arrows preserves the initial and terminal objects. Then apply Zorn’s lemma to the chains of images of f, specifically the one containing X, and get a maximal element, the eventual image of f.

In an attempt to reduce the size of the hammer used, it may be worth noting that there’s an NNO (natural numbers object) in this category starting at X and proceeding by the successive applications of f.

Note that not all chains have the same eventual image as X. As a simple example, consider the positive Reals and f(x) = -x. Although this f does have ℝ as an eventual image when applied to all of ℝ, it does not have an eventual image when applied to, for instance, the positive Reals; f2 does. So we are reminded that f restricted to a subset of the eventual image may no longer be an endomorphism any more and its “eventual image” may well be a cycle in $𝑃\left(X\right)$.

I don’t see how to turn the above into a proof with tight, weaker hypotheses, but I’m only just learning Category theory.

Posted by: Eric Towers on January 19, 2012 5:29 AM | Permalink | Reply to this

Re: The Eventual Image, Part 2

This old MO question recently got bumped to the front page by a new answer, and on a hasty skim is reminiscent of some of the discussions here, although it does not seem to be an “eventual image” problem.

Posted by: Yemon Choi on February 12, 2012 4:26 AM | Permalink | Reply to this
Read the post PSSL 93 trip report
Weblog: The n-Category Café
Excerpt: A report on several talks from the PSSL 93 in Cambridge.
Tracked: April 25, 2012 4:15 PM

Post a New Comment