## October 7, 2022

### The Eventual Image

#### 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 5:19 PM UTC

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