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

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

TrackBack URL for this Entry:

0 Comments & 0 Trackbacks

Post a New Comment