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 $X$, an endomorphism $f$ of $X$, and a point $x \in X$. Then the sequence $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 $f$ 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, f X, f f X, \ldots$

of subspaces at $X$, or in other notation,

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

In the mathematical literature, the term “eventual image” is generally taken to mean $\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: 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 $f$ of a finite set $X$.

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

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

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

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

3. The eventual image of $f$ is the terminal finite set $im^\infty(f)$ equipped with an automorphism $\tilde{f}$ and a map $(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)$.

4. The eventual image of $f$ is the initial set $im^\infty(f)$ equipped with an automorphism $\tilde{f}$ and a map $(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)$.

5. The eventual image of $f$ is the limit of the diagram

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

Concretely, that means $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 $f$ is the colimit of the diagram

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

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

7. The eventual image of $f$ is the largest subset $A$ of $X$ satisfying $A \subseteq f A$. (In fact, it satisfies $A = f A$.)

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

9. The eventual image of $f$ is the set of periodic points of $f$.

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 $f$ 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, $x \in im^\infty(f) \iff x \in \{f(x), f^2(x), \ldots\}$;

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

• for compact metric spaces, $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

Re: The Eventual Image, Eventually

I assume what you really want for Definition 9 is to define periodic maps into and out of $X$, then show that these are the maps factoring through $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 $X$. There, we have $X = im^\infty(f) \oplus ker^\infty(f)$ for an endomorphism $f$, where $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^\infty(f) \to X/ker^\infty(f)$ given by $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^\infty(f) = im(f^N), \qquad ker^\infty(f) = ker(f^N)$ for all $N \gg 0$, so the first isomorphism theorem also implies that $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^\infty(f) = im(f^N) \cong X/ker(f^N) = X/ker^\infty(f)$ defined by $f^N(x) \leftrightarrow x + ker^\infty(f)$ ($x \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 $y \leftrightarrow y + ker^\infty(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 $N$, whereas the second one doesn’t.

All of this is further evidence that viewing the essential image as “$im(f^N)$ for $N \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