### The Eventual Image

#### Posted by Tom Leinster

At its most basic, a discrete-time dynamical system is an object equipped
with an endomorphism. The word ‘dynamical’ becomes appropriate if we plan
to iterate the endomorphism. For example, the concept of image is not dynamical,
because the image of an endomorphism $f$ is the set of outputs after doing $f$ just once. But
the concept of *eventual image* — defined precisely below — *is*
dynamical: it’s the set of outputs after iterating $f$ *indefinitely*.

This post is a plea for someone to do some category theory. I’ll describe three categories in which dynamical systems behave in a strikingly similar way… but the three proofs I have are all different. If someone comes along, sees what’s really going on, and unifies the three strands, that will make me happy.

The three categories are these: finite sets, finite-dimensional vector spaces, and compact metric spaces. To give a hint of what they have in common:

- Every injective endomorphism of a finite set is bijective.
- Every injective linear operator on a finite-dimensional vector space is bijective.
- Every distance-preserving endomorphism of a compact metric space is bijective.

(The first two are very well-known; the third I learned from MathOverflow.)

But the three categories
have a lot more in common than that. For example, in each case, every
endomorphism $f: X \to X$ gives rise canonically to an *idempotent*
endomorphism $f^\infty: X \to X$. Why?

I’ll begin by making as concise a statement as I can of what these three categories have in common, dynamically speaking.

Let $\mathbf{C}$ be any of the following categories:

- The category $\mathbf{S}$ of finite sets
- The category $\mathbf{V}$ of finite-dimensional vector spaces. (Assume if necessary that the ground field is algebraically closed.)
- The category $\mathbf{M}$ of compact metric spaces, with distance-decreasing maps (in the non-strict sense: $d(f(x), f(y)) \leq d(x, y)$).

Write $\mathbf{Endo}$ for the category whose objects are (discrete-time)
‘dynamical systems’ in $\mathbf{C}$, that is, pairs $(X, f)$ where $X \in
\mathbf{C}$ and $f: X \to X$. The maps are the obvious things. Write
$\mathbf{Auto}$ for the subcategory consisting of the *reversible*
dynamical systems, that is, the pairs $(X, f)$ where $f: X \to X$ is an
*auto*morphism.

TheoremFor each of these three categories $\mathbf{C}$, the inclusion functor$U: \mathbf{Auto} \hookrightarrow \mathbf{Endo}$

has a simultaneous left and right adjoint, $im^\infty: \mathbf{Endo} \to \mathbf{Auto}$. Moreover, the composite natural transformation

$U \circ im^\infty \to 1_{\mathbf{Endo}} \to U \circ im^\infty$

(made up of the counit of $U \dashv im^\infty$ and the unit of $im^\infty \dashv U$) is the identity.

That’s the concise version. I’ll spend the rest of this post explaining what it means — including the reason for the notation $im^\infty$.

Concretely, let $f$ be an endomorphism of an object $X$ of our category $\mathbf{C}$, which is still any of $\mathbf{S}$ (finite sets), $\mathbf{V}$ (finite-dimensional vector spaces) and $\mathbf{M}$ (compact metric spaces). We get a chain of subsets

$X \supseteq f X \supseteq f^2 X \supseteq \cdots.$

The **eventual image** $im^\infty(f)$ of $f$ is the intersection of this
chain. One reason for calling this a ‘dynamical’ concept is the fact that
$im^\infty(f) = im^\infty(f^r)$ for any $r \geq 1$. But here’s a more
important fact:

$f$ restricts to an automorphism of $im^\infty(f)$.

This isn’t obvious. For example, try proving that $im^\infty(f) \subseteq f im^\infty(f)$, even in the case of finite sets. You’ll find that you need the finiteness condition, or if you do one of the other two cases, the finite-dimensionality or compactness condition.

(In fact, $im^\infty(f)$ is the largest subspace $B$ of $X$ such that $B \subseteq f B$, and this is probably the morally correct definition of eventual image in the absence of finiteness conditions.)

It’s straightforward to show now that

$(X, f) \mapsto (im^\infty(f), f|_{im^\infty(f)})$

defines a functor $im^\infty: \mathbf{Endo} \to \mathbf{Auto}$, right adjoint to the inclusion $U$. The counit is the natural transformation $U \circ im^\infty \to 1_{\mathbf{Endo}}$ whose component at $(X, f) \in \mathbf{Endo}$ is the inclusion $im^\infty(f) \hookrightarrow X$.

However, showing that $im^\infty$ is *left* adjoint to $U$ —

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

— is much more subtle and interesting.

Consider, for instance, the unit. It should be a natural transformation $1_{\mathbf{Endo}} \to U \circ im^\infty$. So to define it, we need to produce for each $(X, f) \in \mathbf{Endo}$ a canonical map $X \to im^\infty(f)$. The ‘moreover’ part of the theorem tells us that the composite

$X \to im^\infty(f) \hookrightarrow X$

has to be idempotent, and that the map $X \to im^\infty(f)$ has to be surjective. So our task boils down to:

For each endomorphism $f: X \to X$ in $\mathbf{C}$, produce a canonical idempotent $f^\infty: X \to X$ whose image is $im^\infty(f)$.

How can we do that?

When $\mathbf{C}$ is the category of finite sets, this gets us back to my recent question: Do you know this idempotent? I mentioned there that whenever $f$ is an endomorphism of a finite set, the set

$\{ f, f^2, f^3, \ldots \}$

contains precisely one idempotent. (There are infinitely many values of $r$ for which $f^r$ is idempotent, but all these idempotents $f^r$ are equal.) Benjamin Steinberg mentioned that in semigroup theory, this idempotent is usually called $f^\omega$, but I’ll call it $f^\infty$. The image of $f^\infty$ is $im^\infty(f)$:

$im(f^\infty) = im^\infty(f).$

And $f^\infty$ is the idempotent we need, providing the unit of the adjunction $im^\infty \dashv U$.

Still in the category of finite sets, it was pointed out in the comments on that post that $f^\infty$ can be constructed in a ‘forward-and-back’ way, as follows. Let $x \in X$. Keep applying $f$ until you land in $im^\infty(f)$: say $f^n(x) \in im^\infty(f)$. (This always happens after finitely many steps.) Now $f$ acts as an automorphism of $im^\infty(f)$, so there is a unique element $b \in im^\infty(f)$ such that $f^n(b) = f^n(x)$. This $b$ is $f^\infty(x)$.

When $\mathbf{C}$ is the category of finite-dimensional vector spaces, $f^\infty$ can be constructed in exactly the same forward-and-back way. But a couple of extra features make this category especially interesting.

First, the vector space $X$ has a canonical decomposition

$X = ker^\infty(f) \oplus im^\infty(f)$

where $ker^\infty(f)$ is the **eventual kernel** of $f$, that is, the union
of the chain

$ker(f) \subseteq ker(f^2) \subseteq \cdots.$

The projection onto $im^\infty(f)$ coming from this decomposition is exactly $f^\infty$.

Second, $f^\infty$ is a polynomial in $f$. I don’t understand much about the nature of this polynomial, beyond a bare formula. If you do, I’d like to know.

When $\mathbf{C}$ is the category of compact metric spaces, however, the idempotent $f^\infty$ *can’t* be
constructed in the same forward-and-back way. Take a compact metric space $X$
and an endomorphism $f$. Let $x \in X$. It might be that however many
times you apply $f$ to $x$, you never land in $im^\infty(f)$.

But we can adapt the strategy. (This paragraph is for the dedicated only.) By compactness, the sequence $(f^n(x))$ has a convergent subsequence $(f^{n_i}(x))$, and its limit $a$ belongs to $im^\infty(f)$. Since $f$ acts as an automorphism of $im^\infty(f)$, there is for each $i$ a unique element of $im^\infty(f)$ whose image under $f^{n_i}$ is $a$. We might, slightly riskily, call it $f^{-n_i}(a)$, so that $f^{n_i}(f^{-n_i}(a)) = a$. It turns out that $(f^{-n_i}(a))$ converges; call its limit $f^\infty(x)$. With some work, we can see that this defines a map $f^\infty: X \to X$ with all the properties required. In other words, it gives us the unit of an adjunction $im^\infty \dashv U$, as we were after all along

**Conclusion** In each of these three categories, we see the same
behaviour. There’s a canonical way of turning a dynamical system
$(X, f)$ into a reversible dynamical system $(im^\infty(f),
f|_{im^\infty(f)})$. This construction is universal in both the left
*and* the right sense. And this gives us, for each dynamical system $(X,
f)$, a canonical idempotent $f^\infty$ on $X$ whose image is $im^\infty(f)$.

But three different proofs were needed! This can’t be allowed to stand. Surely there’s a unified proof……?

## Re: The Eventual Image

No insights, I’m afraid, but two similar-looking examples to add to the three you gave.

and has closed range, then it is surjective.