The Eventual Image

December 8, 2011

Posted by Tom Leinster

$MathML-enabled post (click for more details).$

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?

$MathML-enabled post (click for more details).$

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 automorphism.

Theorem For 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……?

Posted at December 8, 2011 6:18 AM UTC

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

54 Comments & 2 Trackbacks

Re: The Eventual Image

$MathML-enabled post (click for more details).$

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

Let G be a group, let $\ell^2(G)$ be the (Hilbert) space of square-summable functions on $G$ ; this is a right $G$ -module in a canonical way. If a bounded, linear right $G$ -module map $T:\ell^2(G)\to\ell^2(G)$ is injective and has closed range, then it is surjective.
Again fix a group $G$ : now let $X$ be $\{0,1\}^G$ , given the product topology and the natural shift action of $G$ . A conjecture of Gottschalk states/claims that every injective, continuous, $G$ -map from $X$ to itself is surjective. (By work of Gromov, if $G$ is “sofic” then the conjecture is true. No group is known to be non-sofic. I think Gromov may also be responsible for the term “surjunctive”.)

So I’d be very interested in seeing any unified approach to the three examples you mention, and wondering how if at all the two mentioned above might relate to that approach…

Posted by: Yemon Choi on December 8, 2011 7:16 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

One thing I maybe didn’t emphasize is that I really have no idea what properties of the three categories I’m using in the proofs. Yes, I use the fact that (to put it fancily) every regular monic endomorphism is an isomorphism. But I seem to need to use a whole lot more. It’s all undergraduate stuff — messing about with convergent subsequences or whatever — but it’s very specific to the categories concerned, and quite involved.

If I knew about the two examples you mention, I might try to prove similar results in those contexts. But I don’t, so I won’t. If you decide to give it a try, let us know here!

Posted by: Tom Leinster on December 8, 2011 7:54 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Yemon, let me try a specific question. Let $H$ be a Hilbert space and let $T: H \to H$ be a bounded linear map. (Assume it has closed image/range if you like.) Is there a decent notion of the eventual image of $T$ ?

And if there is, can you construct a canonical idempotent $T^\infty: H \to H$ whose image is the eventual image of $T$ ?

Posted by: Tom Leinster on December 8, 2011 8:09 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

In the case where $T$ has closed range, I think that the same definition as you have before works: the eventual image is the intersection of the images of the iterates of $T$ . Then, since it’s a closed subspace, one can always take the orthogonal projection onto it – I think this is usually called the range projection of $T$ .

However, I don’t think that can be canonical in the sense you require, because if I take $T$ to be the right shift on $\ell^\infty(N)$ , then this is injective but not surjective. In this case the eventual kernel is zero, but so is the eventual image, since any non-zero vector eventually lies outside $im T^n$ for some $n$ .

The first example I mentioned has the moral that endomrphisms of the type described there can’t look like one-sided shifts: it’s a manifestation of the fact that the algebra of all such endomorphisms forms a “finite von Neumann algebra”, and that in a finite von Neumann algebra all left-invertible elements are invertible.

I’ll have to go away and think about why range projections for finite von Neumann algebras behave better than arbitrary ones in $B(H)$ , and whether they are canonical in something like the sense you’re after.

The proofs of left-invertible implies invertible all use, as far as I’m aware, the construction of a well-behaved trace on the algebra; I don’t know if that can be related to some more categori(c)al notion of trace on the collection of endormorphisms in your settings.

Posted by: Yemon Choi on December 8, 2011 8:45 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Thanks. I guess the question I should really have asked is this: does the inclusion functor

$U: \mathbf{Auto} \hookrightarrow \mathbf{Endo}$

have a simultaneous left and right adjoint, when $\mathbf{Auto}$ is the category of Hilbert spaces equipped with an automorphism and $\mathbf{Endo}$ is the category of Hilbert spaces equipped with an endomorphism?

I don’t know whether the maps of Hilbert spaces should be bounded linear maps, or linear maps of norm $\leq 1$ , or what, but in any case, I think the answer’s going to be no.

Let’s consider the example you mentioned: right shift $T$ on $\ell^2(\mathbb{N})$ . (I assume you meant $\ell^2$ , not $\ell^\infty$ , seeing as we’re talking about Hilbert spaces, though it doesn’t really matter.) If $S$ is an automorphism of a Hilbert space $H$ then any map

$F: (H, S) \to (\ell^2(\mathbb{N}), T)$

must be zero. (For let $x \in H$ . For each $n \in \mathbb{N}$ , we have $F(x) = T^n(F(S^{-n}(x)) \in im(T^n)$ , and so $F(x)$ is zero in the first $n$ positions. This holds for all $n$ , so $F(x) = 0$ .)

In other words, any map from (a Hilbert space, an automorphism) to $(\ell^2(\mathbb{N}), T)$ is zero. So if $U$ has a right adjoint $R$ then $R(\ell^2(\mathbb{N}), T) = (0, 0)$ .

But if $R$ were also the left adjoint then any map to (a Hilbert space, an automorphism) from $(\ell^2(\mathbb{N}), T)$ would be zero. And this isn’t true. For example, we can embed $(\ell^2(\mathbb{N}), T)$ into $(\ell^2(\mathbb{Z}), \bar{T})$ , where $\bar{T}$ is right shift on $\ell^2(\mathbb{Z})$ , an automorphism.

So it seems that the same story can’t be told for Hilbert spaces. I’m not surprised, as they don’t have that finite flavour about them that the other examples do. But maybe you can think of some suitably finite variant?

Posted by: Tom Leinster on December 8, 2011 4:50 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

I don’t understand enough about functors that have a simultaneous left-and-right adjoint.

For example: is there a useful condition on a functor $F$ guaranteeing that if it has both adjoints, they’re equal?

My standard example of a simultaneous left-and-right adjunction (an ambijunction) had been

$\mathbf{Ab} \stackrel{\to}{\leftarrow} \mathbf{Ab} \times \mathbf{Ab}$

where one functor is the diagonal and the other is $\oplus$ . But now I see another, probably very significant, example: for any Cauchy-complete category $\mathbf{C}$ , the inclusion

$\mathbf{C} \hookrightarrow \mathbf{Idem}$

has a two-sided adjoint. Here $\mathbf{Idem}$ is the category whose objects are pairs $(X, e)$ with $X \in \mathbf{C}$ and $e$ an idempotent on $X$ , the inclusion sends $X$ to $(X, 1)$ , and the left-and-right adjoint sends $(X, e)$ to the object splitting $e$ .

The central question of my post was, essentially, this: why are the left and right adjoints to the inclusion

$\mathbf{Auto} \hookrightarrow \mathbf{Endo}$

equal, when we’re operating in any of three familiar categories $\mathbf{C}$ ?

I still don’t know, but my instinct is that the equality of the left and right adjoints to $\mathbf{C} \hookrightarrow \mathbf{Idem}$ should provide a clue.

Posted by: Tom Leinster on December 10, 2011 12:23 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

I believe one interesting fact is that “having an ambijoint” should be regarded as structure on a functor rather than a property of it. The space of left adjoints to a given functor is a (-1)-type — contractible if inhabited — but the space of adjunction data between two given functors is not. Thus, if a functor has an ambijoint, then I have a contractible space of choices for its left adjoint, but if I then want to make that same functor into its right adjoint, I no longer necessarily have a contractible space of choice — so a functor could have an ambijoint in more than one distinct way.

Posted by: Mike Shulman on December 10, 2011 6:58 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

That does sound interesting, Mike. Let’s see if I understand.

Fix a functor $U$ . There is a category $Ambi(U)$ of ambijoints to $U$ . An object is a functor in the opposite direction equipped with two unit maps and two counit maps, satisfying a total of four triangle identities. A map is a natural transformation commuting with the units and counits.

Now, I think you’re telling me that $Ambi(U)$ need not be either empty or equivalent to $1$ .

Certainly $Ambi(U)$ is a preordered set (i.e. each of its homsets has at most one element), since between any two left adjoints to $U$ there’s just one structure-preserving natural transformation. It’s also a groupoid. So, $Ambi(U)$ is both a preorder and a groupoid: in other words, it’s an equivalence relation (viewed as a category). The only way the category $Ambi(U)$ could fail to be either empty or equivalent to 1 is if there were multiple equivalence classes, i.e. multiple non-isomorphic ambijoints.

This could happen as follows. Suppose we have two ambijoints $P_1$ , $P_2$ to $U$ . There’s a unique natural isomorphism $i: P_1 \to P_2$ commuting with the structure maps that make $P_1$ and $P_2$ left adjoint to $U$ . Similarly, there’s a unique natural isomorphism $j: P_1 \to P_2$ commuting with the structure maps that make $P_1$ and $P_2$ right adjoint to $U$ . But maybe $i \neq j$ . I guess you’re telling me that there are examples where this happens. Am I understanding you right?

Posted by: Tom Leinster on December 10, 2011 9:26 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Aha. Mike mentioned the possibility that a functor might have two non-isomorphic ambijoints ( $=$ simultaneous left and right adjoints). But I see that in the situation at hand, this is impossible.

The “situation at hand” involves a faithful functor called $U$ , which has an ambijoint called $im^\infty$ . If you look at the Theorem in my post, you’ll see that the ambijunction satisfies a special condition: the composite

$U \circ im^\infty \to 1 \to U \circ im^\infty$

is the identity. (The two maps are the appropriate unit and counit.) It’s not hard to see that any two ambijoints to a faithful functor $U$ that satisfy this ‘special’ condition must in fact be isomorphic.

Another example of an ambijunction satisfying this ‘special’ condition is the one I just mentioned: $\mathbf{C} \stackrel{\to}{\leftarrow} \mathbf{Idem}$ . Again, the functor $\mathbf{C} \hookrightarrow \mathbf{Idem}$ is faithful, so there’s a unique ambijoint.

As you can read in this paper of Aaron Lauda’s, if $U$ and $P$ are adjoint both ways round then $U \circ P$ acquires the structure of a Frobenius object (in the appropriate endofunctor category). Here, $U \circ im^\infty$ is a Frobenius object in the category $[\mathbf{Endo}, \mathbf{Endo}]$ , made monoidal via composition.

The ‘special’ condition above says that the counit followed by the unit is the identity. (It’s a nullary cousin of what’s usually called a ‘special Frobenius algebra’, in which comultiplication followed by multiplication is the identity.) For Frobenius algebras $V$ in the ordinary sense, this would say that

$(V \to k \to V) = id,$

which of course is never going to happen except when $V$ is $0$ or $k$ . So from the classical point of view, the ‘special’ condition is rather strange. But maybe it has a name. Does anyone know?

Posted by: Tom Leinster on December 10, 2011 9:45 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Nice. I guess that condition also means you have an “idempotent ambijunction”?

Posted by: Mike Shulman on December 11, 2011 9:38 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Yes indeed — whatever that means, it must be true. The composite $im^\infty \circ U$ , which is an endofunctor of $\mathbf{Auto}$ , is just the identity, and the structure maps between $im^\infty \circ U$ and $1_{\mathbf{Auto}}$ are also identities.

Posted by: Tom Leinster on December 12, 2011 2:14 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

(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.)

Making $f$ be surjective on $B$ solves the surjectivity problem of the infinite case (where a point has an infinite collection of finite feeder chains of arbitrary length, but is itself sent further downstream by $f$ ). But it doesn’t solve the injectivity problem:

Consider the natural numbers with the endomorphism defined by

$\array{f(n)=n-1&if n\gt 0\\f(n)=0&if n=0}$

Unless I’m much mistaken, the “largest subspace $B$ of $(\mathbb{N}, f)$ such that $B\subseteq f B$ ” seems to be $\mathbb{N}$ itself, on which $f$ is surjective but not injective. Maybe it would be better to define $im^\infty f$ as the largest subspace on which $f$ acts as an automorphism!

Infinite sets seem to present two different problems here: systems which are infinite upwards, like the one above, where injectivity or surjectivity of $f$ can fail on the intersection of successive images; and systems which are infinite downwards (e.g. $(\mathbb{N}, f:n\rightarrow n+1)$ ), where the problem is that the eventual image is empty, so the desired nilpotent has nowhere to send (some of) the points of the space.

The first problem can perhaps be fixed by using the correct definition of $im^\infty f$ ; the second does seem to need some kind of generalised sequential compactness condition on the spaces.

Posted by: Tim Silverman on December 10, 2011 12:51 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Longish time no see, Tim! Or maybe I’ve just been reading the wrong posts.

the surjectivity problem of the infinite case (where a point has an infinite collection of finite feeder chains of arbitrary length, but is itself sent further downstream by $f$ ).

Right! This is the crucial example! Here’s a quick picture:

Here, the chain

$im(f) \supseteq im(f^2) \supseteq \cdots$

does not stabilize after $\omega$ steps. That is, the image of $\bigcap_{n \in \mathbb{N}} im(f^n)$ under $f$ is a proper subset of $\bigcap_{n \in \mathbb{N}} im(f^n)$ . Explicitly, $\bigcap_{n \in \mathbb{N}} im(f^n)$ is the set of points to the right of the central point, including the central point itself. After applying $f$ one more time, the central point is no longer included.

As for the other example (left shift on $\mathbb{N}$ ), it’s true that the largest subset $B$ such that $B \subseteq f B$ is $\mathbb{N}$ itself, on which $f$ does not act bijectively. Does that mean we shouldn’t call it $im^\infty(f)$ ? Well, it depends how we want to use notation.

I think the main point is that you can always make a dynamical system reversible, in either of two universal ways. (They’re Kan extensions.) In the case of sets, this means that there are left and right universal ways of turning a set equipped with an endomorphism into a set equipped with a permutation.

In your left-shift example, we start with the set $\mathbb{N}$ with the endomorphism $f: n \mapsto max\{0, n - 1\}$ . The “left way” (i.e. left adjoint) produces a very boring set-with-permutation, namely, the one-element set $\{\star\}$ with its unique permutation. The “right way” produces something a bit more interesting: $\mathbb{Z}$ with left-shift (which is of course a permutation, i.e. invertible). But neither $\{\star\}$ nor $\mathbb{Z}$ has a decent claim to be called the eventual image of $f$ .

I guess the moral is that in “finite cases” (whatever that means), three things you might do to an endomorphism $f: X \to X$ give the same result:

applying the left adjoint to $\mathbf{Auto} \hookrightarrow \mathbf{Endo}$
applying the right adjoint to $\mathbf{Auto} \hookrightarrow \mathbf{Endo}$
taking the eventual image (defined to be the largest subspace $B$ such that $B \subseteq f B$ ).

Without “finiteness”, these three processes can give three different results, as your left-shift example demonstrates. But making that “finite” precise is what’s giving me trouble.

Posted by: Tom Leinster on December 10, 2011 1:44 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

But neither $\{\star\}$ nor $\mathbb{Z}$ has a decent claim to be called the eventual image of $f$ .

No, though $\mathbb{Z}$ might be called the “Grothendieck $\mathbb{Z}$ -set” of this $f$ . Quick! has someone reserved this terminology?

Posted by: Jesse C. McKeown on December 10, 2011 4:28 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Puzzled… why “Grothendieck $\mathbb{Z}$ -set”? It’s a $\mathbb{Z}$ -set, in the sense of being a set acted on by the additive group $\mathbb{Z}$ , since such a thing amounts to a set equipped with an automorphism. But why “Grothendieck”?

People sometimes refer to the left adjoint to $\mathbf{Group} \hookrightarrow \mathbf{Monoid}$ as sending a monoid to its “Grothendieck group”, don’t they? Or some such similar usage. Is this what you have in mind? But the $\mathbb{Z}$ here is the result of applying a right adjoint.

Posted by: Tom Leinster on December 10, 2011 8:44 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Yes, that’s what I was thinking of; and I think that I can further justify the odd implicit op by remarking that $\mathbb{Z}$ is also the Gothendieck group of $\mathbb{N}$ — though I should sit down and write something before saying it, it sounds nice and poetic at least that the action $f$ of $\mathbb{N}$ on $X$ should induce an action of $\mathbb{N}$ ’s right adjoint on the left adjoint of the action.

Posted by: Jesse C McKeown on December 11, 2011 12:46 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

left… right… I’m thinking in a looking-glass.

(Irrelevant aside: if I tell the comment form to “remember” my claimed Name/et.c., it promptly forgets. If I tell it to Forget, it seems to remember that very well.)

Posted by: Jesse C. McKeown on December 11, 2011 12:51 AM | Permalink | Reply to this

Re: The Eventual Image

Dear Tom,

I may have missed something…

Is it really true that every distance-decreasing surjective endomap of compact metric space is monic (hence bijective) ? It is a consequence of the eventual image THEOREM. I would like to see the argument…

A related question:

Is it true that every distance-decreasing bijective endomap of compact metric space is distance preserving?
I dont have a counterexample.

Posted by: André Joyal on December 11, 2011 4:57 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

The answer to both questions is yes. Thus:

Corollary A distance-decreasing surjective endomorphism of a compact metric space is distance-preserving and bijective.

I hadn’t realized this until you said it, but it’s an easy consequence of the earlier theorem (or its proof). We know that for a compact metric space $X$ , any distance-decreasing map $f: X \to X$ acts as an automorphism (i.e. a distance-preserving bijection) on $im^\infty (f)$ . But if $f$ is surjective then $im^\infty(f) = X$ .

I’ll give a direct proof in a moment, but first let me say why I like this result. Finiteness of a set $X$ is often characterized as “every injection $X \to X$ is an isomorphism”. But it could equally well be characterized as “every surjection $X \to X$ is an isomorphism”. Similarly, a vector space is finite-dimensional if and only if every surjective linear operator on it is an isomorphism. And now we know that for a compact metric space, every surjective distance-decreasing map $X \to X$ is an isomorphism. Maybe this characterizes compactness. I don’t know.

Now here’s a direct proof of the Corollary. Take a compact metric space $X$ and a distance-decreasing surjection $f: X \to X$ . We prove that $f$ is distance-preserving, which also implies that it is injective.

Let $x, y \in X$ . Since $f$ is surjective, we can choose backwards trajectories

$\cdots \mapsto x_2 \mapsto x_1 \mapsto x, \quad\quad \cdots \mapsto y_2 \mapsto y_1 \mapsto y.$

Since $X \times X$ is compact, the sequence $((x_n, y_n))$ in $X \times X$ has a convergent subsequence $((x_{n_i}, y_{n_i}))$ . Then $x_{n_i} \to a$ and $y_{n_i} \to b$ , say. It follows that $f^{n_i} a \to x$ , since

$d(x, f^{n_i} a) = d(f^{n_i} x_{n_i}, f^{n_i}a) \leq d(x_{n_i}, a).$

Similarly, $f^{n_i} b \to y$ . (We now forget about $(x_n)$ and $(y_n)$ .)

Let $\varepsilon \gt 0$ . Choose $I$ such that $d(f^{n_i}a, x) \lt \varepsilon/4$ and $d(f^{n_i}b, y) \lt \varepsilon/4$ for all $i \geq I$ . Write $m = n_{I+1} - n_I \geq 1$ . We have

$\begin{aligned} d(x, y)& \leq d(x, f^{n_{I+1}}a) + d(f^{n_{I+1}}a, f^{n_{I+1}}b) + d(f^{n_{I+1}}b, y)\\ {}& \lt d(f^{n_{I+1}} a, f^{n_{I+1}} b) + \varepsilon/2\\ {}& = d(f^m f^{n_I} a, f^m f^{n_I} b) + \varepsilon/2\\ {}& \leq d(f^m f^{n_I} a, f^m x) + d(f^m x, f^m y) + d(f^m y, f^m f^{n_I} b) + \varepsilon/2\\ {}& \leq d(f^{n_I} a, x) + d(f^m x, f^m y) + d(y, f^{n_I} b) + \varepsilon/2\\ {}& \lt d(f^m x, f^m y) + \varepsilon\\ {}& \leq d(f x, f y) + \varepsilon. \end{aligned}$

So $d(x, y) \lt d(f x, f y) + \varepsilon$ . But $\varepsilon$ was arbitrary, so $d(x, y) \leq d(f x, f y)$ . On the other hand, $f$ is distance-decreasing; hence $d(f x, f y) = d(x, y)$ .

Posted by: Tom Leinster on December 12, 2011 4:11 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Tom wrote:

Similarly, a vector space is finite-dimensional if and only if every surjective linear operator on it is an isomorphism.

There is reason to think that the surjectivity condition is more important than the injectivity condition:

Theorem: Let $R$ be a commutative ring. A free module $M$ over $R$ is of finite rank iff every surjective module endomorphism $M \to M$ is an isomorphism. (NB: this is false when the word ‘surjective’ is replaced by ‘injective’, as is already clear in the case $R = \mathbb{Z}$ , seen as a module over itself.)

Proof of “only if”: Suppose $f: R^n \to R^n$ is surjective, where $n$ is finite. Notice that we can split $f$ : there exists $g$ such that $f \circ g = 1_{R^n}$ . Taking determinants on this equation, this means $\det(f)$ is a unit in $R$ . Then, by Cramer’s rule, we can invert the standard matrix representation for $f$ , i.e., $f$ must have been invertible. $\Box$

I think the same result holds if we replace the word ‘free’ by ‘projective’. I haven’t thought about the situation for still more general modules.

Posted by: Todd Trimble on December 12, 2011 4:31 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Nice example, Todd!

Of course, one might argue that if, in this sense, surjections (regular epics) are more important in categories of algebras, then embeddings (regular monics) should be more important in categories of spaces. I don’t have anything to back that up; it’s just a thought.

Let me try to summarize part of this discussion in categorical terms. We have:

Theorem Let $X$ be a compact metric space and $f: X \to X$ a distance-decreasing map. Then

$f$ is distance-preserving $\iff$ $f$ is surjective.

In other words, if $f$ is distance-preserving or surjective then $f$ is a distance-preserving bijection.

Here $\Rightarrow$ is the result that I mentioned at the top of the post (linking to MathOverflow), and $\Leftarrow$ is this corollary.

In the category of compact metric spaces and distance-decreasing maps, the regular monics are the distance-preserving maps and the epics are the surjections. (To prove this, one can use the fact that every subspace $Y$ of a metric space $X$ has a kind of characteristic function $\chi_Y: X \to [0, \infty]$ , defined by $\chi_Y(x) = d(Y, x) = \inf_{y \in Y} d(y, x)$ .)

So we have the following:

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

finite sets

finite-dimensional vector spaces

compact metric spaces and distance-decreasing maps.

Let $f$ be an endomorphism of an object in $\mathbf{C}$ . Then

$f$ is regular monic $\iff$ $f$ is epic.

In other words, if $f$ is regular monic or epic then $f$ is iso.

In finite sets or finite-dimensional vector spaces, every monic and every epic is regular. So we could add $FinSet^{op}$ and $FDVect^{op}$ to the list of possible values of $\mathbf{C}$ . Doubtless there are further values of $\mathbf{C}$ we could add: e.g. finite groups, rings, etc, I think. And what else?

Posted by: Tom Leinster on December 13, 2011 3:12 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

I don’t really have anything to contribute to the question of “what do these categories have in common?”, but it’s maybe worth pointing out that it has a name: Dedekind-finiteness. An object of any category is called Dedekind-finite if every endo-monomorphism of it is an automorphism. One can of course replace monics by regular monics, or dualize to get epics.

Posted by: Mike Shulman on December 13, 2011 6:07 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Someone should have mentioned the Ax-Grothendieck theorem! It says: let $f: \mathbb{C}^n \to \mathbb{C}^n$ be a polynomial map (meaning that each component $\mathbb{C}^n \to \mathbb{C}$ is polynomial). If $f$ is injective, then it’s bijective.

Actually, there’s a model theory proof that magically reduces it to the pigeonhole principle, or more precisely the statement that it’s true if $\mathbb{C}$ is replaced by a finite field. (That’s the first and only proof I’ve cast my eyes over, years ago, but I gather now from the wikipedia page that other proofs make a similar reduction.)

The dual statement, that a surjective polynomial map $\mathbb{C}^n \to \mathbb{C}^n$ is bijective, is false. Just take the squaring map $\mathbb{C} \to \mathbb{C}$ .

Posted by: Tom Leinster on January 2, 2012 4:52 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

This is “ancient”, I know, but it seems there was a question in passing about whether the converse of the following statement holds. The context is that we are given a metric space $(X, d)$ and a function $f: X \to X$ such that $\forall_{x, y}\; d(f(x), f(y)) \leq d(x, y)$ .

If $X$ is compact, then $f$ is an isometry provided that $f$ is surjective.

(Tom had asked whether this characterizes compactness; my understanding is that he was asking whether compactness follows from the condition that all surjective Lipschitz- $1$ functions are isometries.)

The answer is no. This is rather dramatically illustrated by the following fact: there are non-compact subspaces of the real line whose only continuous self-maps are either constant or the identity. The buzzword for such spaces is (topological) “rigidity”; there are loads of paper on this topic, but one good source seems to be here; see especially Theorems 1-3.

Posted by: Todd Trimble on March 9, 2015 12:04 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Thanks! It now seems naive of me to have expected that this might be true, given that in general topology there are counterexamples to just about everything. I’m impressed that you found that paper, anyway.

Posted by: Tom Leinster on March 9, 2015 3:24 AM | Permalink | Reply to this

Re: The Eventual Image

Thank you Tom!
This is a very nice argument!
I find the result rather surprising!

It shows that a compact metric space cannot be weakly contracted on itself without leaving some room.
As if the space had some kind of intrinsic volume which should decrease when contracted.
A new Archimedes principle?

Posted by: André Joyal on December 12, 2011 2:03 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

I thought a bit about this. Perhaps it’s worth going through one proof of the fact that a distance-preserving endomorphism of a compact metric space is surjective. This is a converse to the fact that André was talking about, but it does illustrate the idea of an invariant that always decreases when a space is made smaller.

For a compact metric space $X$ and a real number $\varepsilon \gt 0$ , write $N_\varepsilon(X)$ for the minimum number of sets of diameter $\leq \varepsilon$ needed to cover $X$ . (The function $\varepsilon \mapsto N_\varepsilon(X)$ , or something very like it, is called the metric entropy or Kolmogorov entropy of $X$ .) It’s easy to see that if $Y$ is a proper closed subspace of $X$ then $N_\varepsilon(Y) \lt N_\varepsilon(X)$ for sufficiently small $\varepsilon$ . So $X$ cannot be isometric to a proper subspace of itself.

This tells us that for endomorphisms in the category $\mathbf{M}$ of metric spaces and distance-decreasing maps,

$distance preserving \implies surjective.$

This fact implies its converse, as follows. First observe that $\mathbf{M}$ has a closed structure: given spaces $X, Y \in \mathbf{M}$ , the set $Hom(X, Y)$ can be given the uniform or sup metric, and is then compact. The key fact is that if $s: X \to Y$ is a surjective map then for any space $Z$ , the map

$s^*: Hom(Y, Z) \to Hom(X, Z)$

is distance-preserving. Now let $s: X \to X$ be a surjective endomorphism in $\mathbf{M}$ . The induced map

$s^*: Hom(X, X) \to Hom(X, X)$

is a distance-preserving endomorphism of $Hom(X, X)$ , and therefore surjective. In particular, there exists $t \in Hom(X, X)$ such that $s^*(t) = 1_X$ , that is, $t \circ s = 1_X$ . But $s$ is surjective, so this forces $s$ to be an isomorphism.

This provides an alternative to the proof I gave above.

Both results are presumably very old, though I don’t know anything about their history. A textbook containing different proofs of both is A Course in Metric Geometry by Burago, Burago and Ivanov (page 16).

Posted by: Tom Leinster on December 24, 2011 12:06 AM | Permalink | Reply to this

Re: The Eventual Image

I think of the compact metric space case and the finite case in the same way. They are both consequences of the existence of idempotents in compact semigroups. Let me sketch the proof of existence of idempotents in compact semigroups and explain the relevance.

If $S$ is a compact semigroup (jointly continuous multiplication), then by compactness there is a minimal closed subsemigroup (non-empty) $T$. Then if $t\in T$, one has $tT=T=Tt$ by minimality. An easy exercise in semigroup theory shows that a semigroup $T$ such that $tT=T=Tt$ is a group and hence $T$ has an idempotent.

Now if $f$ is a distance non-increasing function on a compact metric space then the semigroup generated by f is equicontinuous and hence has compact closure in the compact-open topology. That closure contains an idempotent and it is your $f^{\infty}$. Actually it is not difficult to prove that the accumulation points of the sequence $f^n$ form a compact monogenic abelian group and so this idempotent is unique. It is straightforward to show that the image of $f^{\infty}$ is your eventual range and the compact abelian monogenic abelian group I described above is just the image of the $\overline{\langle f\rangle}$ acting on the eventual range.

It is a general fact that any compact monoid $T$ of homeomorphisms (in the compact-open topology) of a compact Hausdorff space $X$ has the property that each surjection is bijective. Here is the proof. First one shows that the surjective elements of the $T$ form a closed subsemigroup $S$ (its complement is the union over all points $x\in X$ of the open sets $N(X,X\setminus \{x\})$ of maps $f$ with
$f(X)\subseteq $X \setminus \{x\}$). A surjective idempotent is the identity and so $S$ contains the identity and no other idempotent. But a compact Hausdorff monoid with a unique idempotent is a compact group so every element of $S$ is invertible. (This follows because $sS$ and $Ss$ contains an idempotent and hence the identity for all $s\in S$ and so each element is both left and right invertible hence invertible; thus the monoid is algebraically a group, but a deep theorem of Ellis guarantees the inverse is continuous).

It is also a fact that if one has a compact abelian monoid of transformations on a compact Hausdorff space (with respect to the compact-open topology) that there is a notion of an eventual range (these are the uniformly recurrent points of the dynamical system) and the abelian monoid acts by homeomorphisms on the eventual range. In the monogenic case, the eventual range can be described as either the recurrent points or the uniformly recurrent points because they are the same. The situation is more complicated when you have a dynamical system whose closure is not compact in the compact-open topology. Then you get into enveloping semigroups and Ellis-Furstenburg theory.

Now one can play a similar game in the linear case. One can take the Zariski closure of the subsemigroup generated by $f$. Putcha-Renner theory of algebraic semigroups will give you an idempotent. I am not familiar enough with the theories to see if one can give a unified proof. What is common in both cases is that one has a unique minimal ideal and in both cases the minimal ideal is a commutative group.

Of course nothing here is categorical. Sorry :(

Posted by: Benjamin Steinberg on December 18, 2011 1:52 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Thanks again for these comments, Ben. There’s a lot of new stuff here for me. For years I’ve wanted to learn some topological dynamics, but never got round to it. Now here’s another reason.

I’ll note, for the record, two important facts that you explained:

every nonempty compact semigroup contains at least one idempotent
if $X$ is a compact Hausdorff space, and $T$ is a compact submonoid of the monoid of continuous maps $X \to X$ (with its compact-open topology), then every surjection in $T$ is a bijection.

In the second fact, you said ‘every compact monoid $T$ of homeomorphisms’, which was presumably a slip: the elements of $T$ can be any old continuous maps $X \to X$ . Also, it seems to me that the theorem of Ellis isn’t needed for the proof of this.

Posted by: Tom Leinster on December 24, 2011 1:25 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Tom, You are right that homomorphism is a slip. Also for the compact case I don’t need Ellis, the inverse is trivially continuous. Ellis is for the locally compact case.

Posted by: Benjamin Steinberg on December 25, 2011 3:27 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Sorry I forgot the TeX filter on my last post.

I think the compact metric space case can be viewed in the following way, which is more categorical than my last post.

Let $S$ be the free compact semigroup on $1$ -generator $s$ and $G$ be the free compact group on $1$ -generator $g$ . There is a canonical surjective homomorphism $f\colon S\to G$ sending $s$ to $g$ . Surjectivity follows from the easy to verify fact that any closed subsemigroup of a compact group is a subgroup.

Let $e$ be the unique idempotent of $S$ . Then standard structure theory of compact monogenic semigroups implies that $eS$ is a compact abelian group. Since $S$ is commutative, the mapping $s\mapsto es$ is a surjective homomorphism and hence $eS$ is a compact monogenic group with generator $es$ . Trivially $f(es)=f(s)=g$ and so $eS$ maps surjectively onto $G$ with the generator $es$ mapping to $g$ . But then by freeness of $G$ , this splits. It follows that $G\cong eS$ and we can identify $f$ with $s\mapsto es$ .

Since any weak contraction generates an equicontinuous semigroup, which will have compact closure, your category Endo is the category of continuous actions of $S$ by weak contractions on metric spaces and Auto is the category of continuous actions of $G$ by contractions of metric spaces.

Now if $S$ is a semigroup and $e$ is an idempotent of $S$ , there is a functor from $S$ -sets to $eSe$ -sets that takes $X$ to $eX$ . This functor is exact and has left and right adjoints. Now for the case of $S$ above with idempotent $e$ , one has that $eX$ is giving the eventual image and the right adjoint is the inclusion of Endo into Auto. The left adjoint of the restriction probably takes you out of this context.

By the way, any action of a compact semigroup on a metric space can be changed to one by weak contractions by changing the metric to a new metric. Similarly for compact groups you can change to an action by contractions.

You can replace compact metric spaces everywhere by compact Hausdorff spaces as long as you change weak contraction to asking that the semigroup generated by the transformation be equicontinuous with respect to the unique uniform structure. So probably one should really define Endo and Auto as categories of equicontinuous actions on compact Hausdorff spaces. This will get your finite spaces back into the fold without introducing an artificial metric.

Posted by: Benjamin Steinberg on December 18, 2011 4:06 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

By the way, any action of a compact semigroup on a metric space can be changed to one by weak contractions by changing the metric to a new metric.

Is this obvious? I’m not seeing it. Actually, I’m having trouble coming up with an example of an action of a compact semigroup that isn’t by weak contractions, though I have the feeling that shouldn’t be hard.

Similarly for compact groups you can change to an action by contractions.

Either I’m misunderstanding or this is a mistake, because according to the definition of contraction that I use, the identity is never a contraction. (Also, the inverse of a contraction is never a contraction.) I guess you didn’t mean ‘weak contraction’, because otherwise you wouldn’t have bothered saying this separately from the general semigroup case. So I’m puzzled as to what you did mean.

You can replace compact metric spaces everywhere by compact Hausdorff spaces as long as you change weak contraction to asking that the semigroup generated by the transformation be equicontinuous with respect to the unique uniform structure.

That’s interesting. Do you know what equicontinuity with respect to the unique uniform structure means in direct topological terms? (I should be able to work it out, but my brain is tired…)

I wonder if it’s even continuity. I’ve only just come across this notion, and I came across it in this paper:

Carlos R. Borges, How to recognize homeomorphisms and isometries, Pacific Journal of Mathematics 37 (1971), 625–633.

This paper seems to be relevant to what we’re talking about. It also proves some theorems about when a map of topological (not metric!) spaces is a ‘topological isometry’, without defining the term, unfortunately. I don’t know what it means.

Posted by: Tom Leinster on December 24, 2011 1:52 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Tom, Sorry there was a typo. Any compact group action on a metric space is equivalent to one by isometries. For the monoid case you redefine the distance to be

d'(x,y) = \sup d(mx,my)

the sup over

m

in the monoid. This sup is achieved by compactness. It is easy to check this is an equivalent metric and the action is by weak contractions if I made no mistakes (this is from memory). The group case will give isometries. Equicontinuous is the uniform space setting is in Kelley’s book. It is something like given any entourage R of the codomain of the family of functions there is an entourage R’ of the domain so that all functions from the family send R’ into R. I have a paper on the ArXiv on endomorphism monoids of profinite monoids where these ideas are used.

Posted by: Benjamin Steinberg on December 24, 2011 7:24 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

I suspect the vector space case is similar. One can take the pro-algebraic completion of the free semigroup $S$ on $1$ -generator and the pro-algebraic completion $G$ of the free group on one-generator. I assume one can show the former has a unique idempotent $e$ and that $eS\cong G$ .

Assuming this is true, one then has the same categorical interpretation as in the above case.

Posted by: Benjamin Steinberg on December 18, 2011 4:23 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Sorry for the multiple posts, but it took time to crystallize. I believe the uniform explanation (but not proof) is the following. The free profinite, the free compact and most likely the free pro-algebraic semigroup on 1-generator all look like the free semigroup on one-generator together with an ideal which is respectively the free profinite, free compact and free pro-algebraic group on 1-generator. The adjunction Tom speaks of is then the usual adjunction associated to a semigroup S and a monoid of the form eSe with e an idempotent.

Posted by: Benjamin Steinberg on December 18, 2011 5:06 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Thanks very much for all the comments, Benjamin! It’s going to take me a little while to read what you’ve written and have something intelligent to say, but as the demands of the semester recede and the holidays begin, I look forward to spending some time on this.

Posted by: Tom Leinster on December 19, 2011 7:50 PM | Permalink | Reply to this

Re: The Eventual Image

Tom,

Take your time. Thanks for getting me to think categorically about a construction I use every day with your nice post. Now if only I could get you to use omega (this notation was introduced by Schutzenberger) :)

Ben

Posted by: Benjamin Steinberg on December 21, 2011 2:40 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Now if only I could get you to use omega

This I can reply to without hard thought. I’m pretty open to changing notation, as I’m still very much figuring things out.

I think the choice of notation hinges on what the primary definition of eventual image should be. If we define the eventual image of $f: X \to X$ as the intersection of the countable chain

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

then $f^\omega X$ seems very reasonable (and $f^\omega$ very reasonable for the idempotent whose image is $f^\omega X$ ). Still, $f^\infty X$ and $f^\infty$ would be reasonable too. (In the world of higher categories, people said ‘ $\omega$ -category’ for years, but now the dominant usage is ‘ $\infty$ -category’.)

On the other hand, if we define the eventual image of $f: X \to X$ as the largest subspace $W$ such that $f W \supseteq W$ (or equivalently, such that $f W = W$ ) then $f^\omega$ isn’t so reasonable. In the case of an infinite set, you might, of course, have to go further through the ordinals before you stabilize.

The problem is that for finite sets (and other “finite” structures), there are several equivalent characterizations, and different characterizations suggest different notation.

Posted by: Tom Leinster on December 21, 2011 7:25 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Tom, Your notational argument makes sense. In fact I don’t know Schutzenberger’s reason for using omega. I guess I should learn what is an

\infty

-category at some point. Ben

Posted by: Benjamin Steinberg on December 22, 2011 4:39 AM | Permalink | Reply to this

Re: The Eventual Image

I find the explanations of Benjamin very illuminating. Another name for the eventual image could be the *recurrent image*. I wonder if the free compact monoid on one generator has applications to the theory of Markov chains? What about continuous Markov chains? The half real line is a continuous semi-group. What about the compact monoid generated by the half line?

Posted by: André Joyal on December 23, 2011 8:37 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Andre, I have a neat proof using the theory of compact monogenic semigroups of all the usual convergence results for finite Markov chains. I don’t know the infinite case well enough but it is plausible. I could send it to you if you like. Ben

Posted by: Benjamin Steinberg on December 24, 2011 7:30 PM | Permalink | Reply to this

Re: The Eventual Image

I would love to see your treatment of finite Markov chains!

I have another question about compactification of monoids. By Gelfand duality, a compact space is entirely determined by the C-star algebra of continuous functions on that space. It follows that there is a bijection between the compactifications of a space and the sub-C-star-algebras of the algebra of all complex valued bounded continuous function on that space. For examples,
the Stone-Chech compactification of the set of natural numbers is defined by the algebra of all bounded sequences of complex numbers, while the Alexandroff one-point compactification is defined by the sub-algebra of convergent sequences. The compactification of the monoid of natural numbers is lying in between. Do you have a description of the corresponding sub-algebra of bounded sequences?

Merry Christmas to all!

Posted by: André Joyal on December 24, 2011 10:10 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Andre, I can email you the PDF file for the finite Markov chains, should I use your university address. The key ideas are the following: The standard Perron-Frobenious results are trivial for idempotent positive stochastic matrices. Now use that stochastic matrices form a compact semigroup and look at the closed monogenic semigroup generated by an aperiodic irreducible stochastic matrix to reduce to the idempotent case. Along the same lines, here is the Banach fixed point theorem for strict contractions of a compact metric space. One takes the closed subsemigroup generated by the contraction and observed that an idempotent strict contraction is a constant map. The image of the constant map is the fixed point. Ben

Posted by: Benjamin Steinberg on December 25, 2011 3:37 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

By the natural numbers as a monoid, do you allow the natural numbers to include zero and use addition to define a monoid? Or do you just want to equip the strictly positive integers with addition and treat this as a semigroup?

Moreover, there are different uses of the word “semigroup compactification” in harmonic analysis - should the resulting semigroup be a compact space $S$ where the semigroup product is

– continuous on one side (in the Stone-Cech compactification, there are two different extensions of the semigroup product on $N$ ; one is continuous on the left but not on the right; the other, the reverse)

– on both sides separately (this would be the weakly almost periodic compactification)

– or continuous as a map $S \times S \to S$ (my *suspicion* is that this would be the almost periodic compactification, or the closure of $N$ inside the Bohr compactification of the group of integers)

(Joyeux Noel)

Posted by: Yemon Choi on December 26, 2011 2:30 AM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Yemon, Here we want the multiplication map to be continuous so the free compact semigroup on one-generator is the Bohr compactification of the positive natural numbers. This is because Tom is discussing equicontinuous dynamics. To understand arbitrary dynamics you must use the Stone-Čech compactification and you do have one-sided continuity. But as I know you know,

\beta N

is not jointly continuous, is non-commutative and has uncountable many idempotents in the minimal ideal and so there is no eventual range as Tom likes. In general you have the uniformly recurrent points of the system, which are the fixed points of idempotents of Stone-Čech. The recurrent points are the fixed points of arbitrary (non-identity) idempotents and so are more general. In the case of equicontinuous actions there is only one non-trivial idempotent. I recommend the wonderful book of Hindman and Strauss, Algebra in the Stone-Čech compactification for more on this. The issue of having an identity or not doesn’t matter in this context. Feel free to include the identity if you like.

Posted by: Benjamin Steinberg on December 26, 2011 5:09 AM | Permalink | Reply to this

Re: The Eventual Image

Yemon, I think that the image of N in B (the Bohr compactification of the group of integers) is dense. Because its closure in B is a subgroup. An this is because every closed submonoid of a compact group is a subgroup. And this is because every compact cancellation monoid is a group. And this is because a compact monoid which is not a group contains a non-trivial idempotent.

The compactification N’ of N is obtained by gluing the discrete space N with the compact space B. The precise nature of this gluing is unclear to me. There is a general procedure for gluing a space X to a space Y, so that X becomes an open subspace of the total space, with Y the complement of X. The glue is provided by a map preserving finite meets from the lattice of open subsets of X to the lattice of open subsets of Y. We want a similar procedure for compactifying a locally compact space X by using a continuous map X->Y with values in a compact space Y. The space N’ should be obtained by using the canonical map N–>B.

Posted by: André Joyal on December 26, 2011 8:46 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

André: I am probably being slow, but if we let $S$ denote the closure of $N$ inside $G$ , the Bohr compactification of $Z$ , then even if $S$ is a group I dont see why this implies $S=G$ .

Posted by: Yemon Choi on December 28, 2011 2:13 PM | Permalink | Reply to this

Re: The Eventual Image

Sorry, I should have given the argument in full. You seem to agree that S is a group. It follows that S contains Z, since it contains N. But Z is dense in G. It follows S=G, since S is closed. This shows that N is dense in G.

Posted by: André Joyal on December 28, 2011 4:49 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

The following question just arose in some chat that I was having with Tim Porter:

What can we say about existence and properties of eventual images of geometric endomorphisms of a topos?

Has anyone thought about that?

(I haven’t at all, unfrotunately, I am absorbed with something different, but I just thought I’d forward this question here.)

Posted by: Urs Schreiber on February 13, 2012 6:58 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

There’s now a discussion of the “one-to-one iff onto” phenomenon on MathOverflow, prompted by this question of Uday.

Posted by: Tom Leinster on February 17, 2012 10:30 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

I’ll take this opportunity to upgrade my own modest contribution to this discussion, to the stronger statement that a surjective endomorphism on any finitely generated module over a commutative ring is an isomorphism. This currently appears as Proposition 3 in an nLab article on determinants.

Posted by: Todd Trimble on February 18, 2012 5:07 PM | Permalink | Reply to this

Read the post PSSL 93 trip report
Weblog: The n-Category Café
Excerpt: A report on several talks from the PSSL 93 in Cambridge.
Tracked: April 25, 2012 4:16 PM

Re: The Eventual Image

$MathML-enabled post (click for more details).$

As pointed out recently on MathOverflow, particularly in a comment by Mariano Suárez-Alvarez and with an enthusiastic reception by Yemon Choi, the term “hopfian/cohopfian object” can serve as search terms for a wealth of material related to this post. An object $X$ in a category is hopfian if every epimorphism $X \to X$ is an isomorphism. Dually for “cohopfian”.

This paper by Varadarajan has a lot of material, for various categories.

Posted by: Todd Trimble on October 16, 2012 4:09 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

(Link fixed; thanks for pointing out the error, Rod.)

Posted by: Tom Leinster on October 16, 2012 5:40 PM | Permalink | Reply to this

Re: The Eventual Image

$MathML-enabled post (click for more details).$

Excellent — thanks very much. So if I understand correctly, “cohopfian” and “Dedekind finite” are synonymous.

Yesterday I got asked to give an algebra seminar at my new home, and I was thinking about presenting this stuff. One reason for that choice was that (some) algebraists know a lot about delicate finiteness conditions and the relationships between them, so I thought they might be able to shed some light on this hopfian/cohopfian business. I should look over Varadarajan’s paper first, I guess.

Posted by: Tom Leinster on October 16, 2012 6:14 PM | Permalink | Reply to this

Read the post The Eventual Image, Eventually
Weblog: The n-Category Café
Excerpt: The many-sided concept of the eventual image.
Tracked: October 7, 2022 6:06 PM

The n-Category Café

Skip to the Main Content

December 8, 2011