Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

October 7, 2022

The Eventual Image, Eventually

Posted by Tom Leinster

More than ten years ago, I wrote a series of posts (1, 2, 3) about what happens when you iterate a process for an infinite amount of time. I know just how that feels: it’s taken me until now to finish writing it up. But finally, it’s done:

Tom Leinster, The eventual image. arXiv:2210.00302, 2022.

What is the eventual image? I’ll tell you in nine ways.

But first let me explain the general idea.

The theory of dynamical systems is mostly about what happens eventually — towards time \infty. Some dynamical notions lay their hands on what happens “at” time \infty. The most basic example of this is the concept of limit. Here I’m thinking of examples like a space XX, an endomorphism ff of XX, and a point xXx \in X. Then the sequence x,f(x),f 2(x)=f(f(x)),x, f(x), f^2(x) = f(f(x)), \ldots may have a limit point.

Incidentally, I’m focusing here on discrete-time dynamical systems, where we apply ff once with every tick of the clock. Of course, continuous-time systems are super-important too, but I’m not going to talk about them here.

What becomes of the concept of the image (range) of a function at time \infty? With the same notation, we’re looking at the sequence

X,fX,ffX, X, f X, f f X, \ldots

of subspaces at XX, or in other notation,

X,im(f),im(f 2),. X, im(f), im(f^2), \ldots.

In the mathematical literature, the term “eventual image” is generally taken to mean n0im(f n)\bigcap_{n \geq 0} \im(f^n). Or in honest truth, what you see more often is “eventual range”, because the people who study this kind of thing are mostly people who say “range” where category theorists say “image”.

My paper is about some very humble dynamical systems, nothing like as complex as the ones that researchers in dynamical systems study. The distinguishing feature is that they’re endomorphisms on finite objects, whatever “finite” means — and I’ll come back to that. But because the systems I’m studying are so special, many things are true of them that aren’t true in general. The equivalence of the nine definitions of eventual image is a case in point.

Here we go.

Let f:XXf: X \to X be an endomorphism in some category. To keep my descriptions simple, I’ll assume it’s the category of finite sets. After the nine descriptions of the eventual image that I’m about to give you, I’ll come back to the question of which categories this all makes sense in.

Now, here are nine equivalent definitions of the eventual image of an endomorphism ff of a finite set XX.

  1. The eventual image im (f)im^\infty(f) of ff is the limit of the diagram

    fXfXfXf. \cdots \stackrel{f}{\to} X \stackrel{f}{\to} X \stackrel{f}{\to} X \stackrel{f}{\to} \cdots.

    That is, im (f)im^\infty(f) is the set of double sequences (x n) n(x_n)_{n \in \mathbb{Z}} satisfying f(x n)=x n+1f(x_n) = x_{n + 1} for all integers nn.

  2. The eventual image of ff is the colimit of the same diagram. That is, im (f)im^\infty(f) is the set of equivalence classes of “tails” (x n,x n+1,)(x_n, x_{n + 1}, \ldots) with f(x i)=x i+1f(x_i) = x_{i + 1} for all ii, where such a tail is equivalent to another tail (y m,y m+1,)(y_m, y_{m + 1}, \ldots) if x i=y ix_i = y_i for all sufficiently large ii.

  3. The eventual image of ff is the terminal finite set im (f)im^\infty(f) equipped with an automorphism f˜\tilde{f} and a map (im (f),f˜)(X,f)(im^\infty(f), \tilde{f}) \to (X, f) in the category of endomorphisms. That is: it’s the underlying set of the universal map from a finite-set-with-automorphism to the finite-set-with-endomorphism (X,f)(X, f).

  4. The eventual image of ff is the initial set im (f)im^\infty(f) equipped with an automorphism f˜\tilde{f} and a map (X,f)(im (f),f˜)(X, f) \to (im^\infty(f), \tilde{f}) in the category of endomorphisms. That is: it’s the underlying set of the universal map to a finite-set-with-automorphism from the finite-set-with-endomorphism (X,f)(X, f).

  5. The eventual image of ff is the limit of the diagram

    im(f 2)im(f)X. \cdots ↣ im(f^2) ↣ im(f) ↣ X.

    Concretely, that means im (f)= nim(f n)im^\infty(f) = \bigcap_{n \in \mathbb{N}} im(f^n). That’s the definition of eventual image/range that you’ll usually find in the literature.

  6. The eventual image of ff is the colimit of the diagram

    Xim(f)im(f 2). X ↠ im(f) ↠ im(f^2) ↠ \cdots.

    Concretely, im (f)=X/im^\infty(f) = X/{\sim}, where xyx \sim y if and only if f n(x)=f n(y)f^n(x) = f^n(y) for some nn \in \mathbb{N}.

  7. The eventual image of ff is the largest subset AA of XX satisfying AfAA \subseteq f A. (In fact, it satisfies A=fAA = f A.)

  8. The eventual image of ff is X/X/{\sim}, where \sim is the finest equivalence relation on XX such that f(x)f(y)xyf(x) \sim f(y) \implies x \sim y.

  9. The eventual image of ff is the set of periodic points of ff.

It’s not very hard to prove directly that these nine definitions are equivalent. In my paper, the proof is embedded in a larger theoretical framework.

In the nine definitions, I confined myself to the category of finite sets. What about other categories?

In the paper, I say that a general category 𝒞\mathcal{C} has eventual image duality if, for all endomorphisms ff in it, the limit in definition 1 and the colimit in definition 2 exist and the canonical map between them is an isomorphism. Then the two dual universal properties in definitions 3 and 4 follow.

For example, the category of finite sets has eventual image duality, but the category of all sets doesn’t (Example 2.2).

The main theorem says that any category admitting a factorization system “of finite type” has eventual image duality. The definition of finite type imposes several axioms, but the most important is a kind of two-way Dedekind finiteness: any endomorphism that belongs to either the left class or the right class of the factorization system is invertible. For example:

  • On the category of finite-dimensional vector spaces, the injections and surjections form a factorization system of finite type, as any injective or surjective linear endomorphism is invertible. Indeed, the category of finite-dimensional vector spaces has eventual image duality.

  • Less obviously, on the category of compact metric spaces and distance-decreasing maps, the isometries and surjections also form a factorization system of finite type. Hence this category too has eventual image duality.

The main theorem also tells us that eventual images can be constructed as in definitions 5 and 6, in a category with a factorization system of finite type.

Definitions 7 and 8 are special cases of the second-biggest result in the paper, Theorem 5.4. This characterizes the eventual image as a terminal coalgebra and, dually, an initial algebra. Again, the setting for this is a category with a factorization system of finite type. We need the factorization system to give us a proxy for the notion of subset in the case of finite sets.

Definition 9 is more ticklish. In the three examples I’ve mentioned, the following things are true:

  • for finite sets, xim (f)x{f(x),f 2(x),}x \in im^\infty(f) \iff x \in \{f(x), f^2(x), \ldots\};

  • for finite-dimensional vector spaces, xim (f)xspan{f(x),f 2(x),}x \in \im^\infty(f) \iff x \in span\{f(x), f^2(x), \ldots\};

  • for compact metric spaces, xim (f)xCl{f(x),f 2(x),}x \in \in \im^\infty(f) \iff x \in Cl\{f(x), f^2(x), \ldots\}.

But I don’t know a good general statement. Nor do I know if there’s a dual statement. (You’ll have noticed that 9 is an odd number.) I hope someone else will figure it out.

Posted at October 7, 2022 6:03 PM UTC

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

6 Comments & 0 Trackbacks

Re: The Eventual Image, Eventually

I assume what you really want for Definition 9 is to define periodic maps into and out of XX, then show that these are the maps factoring through im (f)im^\infty(f).

Posted by: unekdoud on October 8, 2022 4:03 PM | Permalink | Reply to this

Re: The Eventual Image, Eventually

Yes, that’s probably it. In honest truth, I went a very short way down that road then decided that getting the paper finished was more important to me than seeing this idea through. It was one of those times when the practicalities of life interfere, and it has nothing to do with the mathematical worth of the idea.

Posted by: Tom Leinster on October 8, 2022 9:43 PM | Permalink | Reply to this

Re: The Eventual Image, Eventually

Here is another result about the eventual image phenomenon. Let G be a finite group, and let phi : G —> G be a group homomorphism. Let I be the eventual image and let K be the eventual kernel, meaning those group elements g such that phi^N(g)=e for N sufficiently large.

Then G is the semidirect product of K by I.

I put this on our graduate qualifying exam, and about half the students got it. I thought it was a nice problem.

Posted by: David Speyer on October 12, 2022 3:49 AM | Permalink | Reply to this

Re: The Eventual Image, Eventually

That’s a nice exercise. I don’t think I’d seen it before, but as I imagine you know, it’s pretty much the same argument as for finite-dimensional vector spaces XX. There, we have X=im (f)ker (f) X = im^\infty(f) \oplus ker^\infty(f) for an endomorphism ff, where im (f)= nim(f n),ker (f)= nker(f n). im^\infty(f) = \bigcap_n im(f^n), \qquad ker^\infty(f) = \bigcup_n ker(f^n). This lemma usually seems to be attributed to Fitting, but I’ve never actually found the work of Fitting in which it appears. I’d be happy if someone can point me to it.

Incidentally, there’s a subtlety here. There’s an isomorphism im (f)X/ker (f) im^\infty(f) \to X/ker^\infty(f) given by yy+ker (f), y \mapsto y + ker^\infty(f), and similarly in the case of finite groups. That’s the isomorphism associated with the direct sum decomposition I just mentioned, or the semidirect product that David mentioned. But here’s the thing. In both the vector space and group cases, we have im (f)=im(f N),ker (f)=ker(f N) im^\infty(f) = im(f^N), \qquad ker^\infty(f) = ker(f^N) for all N0N \gg 0, so the first isomorphism theorem also implies that im (f)X/ker (f). im^\infty(f) \cong X/ker^\infty(f). But the isomorphism provided by the first isomorphism theorem is not the isomorphism above! At least, not usually. The first isomorphism theorem produces the isomorphism im (f)=im(f N)X/ker(f N)=X/ker (f) im^\infty(f) = im(f^N) \cong X/ker(f^N) = X/ker^\infty(f) defined by f N(x)x+ker (f) f^N(x) \leftrightarrow x + ker^\infty(f) (xXx \in X), whereas the one that comes out of the general theory of the eventual image, i.e. the direct sum or semidirect product description, is yy+ker (f) y \leftrightarrow y + ker^\infty(f) (yim (f)y \in im^\infty(f)). These are not the same isomorphism. In fact, it’s clear that the first one depends on a choice of a sufficently large NN, whereas the second one doesn’t.

All of this is further evidence that viewing the essential image as “im(f N)im(f^N) for N0N \gg 0” can sometimes be an unhelpful perspective.

Posted by: Tom Leinster on October 12, 2022 11:06 PM | Permalink | Reply to this

Re: The Eventual Image, Eventually

Does the theory change significantly if you don’t ask from the outset that both the limits and colimits in diagram (2) exist, but consider them as presheaves?

Motivation: I was wondering if one could use the Ax-Grothendieck theorem (say in the general form of EGAIV_3 Proposition 10.4.11, that any universally injective endomorphism of a finite type S-scheme is bijective) to say something about the essential image in the category of finite type S-schemes over some base S, but the first obstacle is that in that category the colimit in (2) will not exist in general.

Posted by: Simon Pepin Lehalleur on October 25, 2022 9:07 AM | Permalink | Reply to this

Re: The Eventual Image, Eventually

The paper is now published in Theory and Applications of Categories, in the volume dedicated to the memory of Pieter Hofstra.

Posted by: Tom Leinster on July 30, 2024 3:56 PM | Permalink | Reply to this

Post a New Comment