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.

December 8, 2011

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 ff is the set of outputs after doing ff just once. But the concept of eventual image — defined precisely below — is dynamical: it’s the set of outputs after iterating ff 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:XXf: X \to X gives rise canonically to an idempotent endomorphism f :XXf^\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 C\mathbf{C} be any of the following categories:

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

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

Theorem  For each of these three categories C\mathbf{C}, the inclusion functor

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

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

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

(made up of the counit of Uim U \dashv im^\infty and the unit of im Uim^\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 im^\infty.

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

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

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

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

This isn’t obvious. For example, try proving that im (f)fim (f)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 (f)im^\infty(f) is the largest subspace BB of XX such that BfBB \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)(im (f),f| im (f)) (X, f) \mapsto (im^\infty(f), f|_{im^\infty(f)})

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

However, showing that im im^\infty is left adjoint to UU

im :EndoAuto: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 EndoUim 1_{\mathbf{Endo}} \to U \circ im^\infty. So to define it, we need to produce for each (X,f)Endo(X, f) \in \mathbf{Endo} a canonical map Xim (f)X \to im^\infty(f). The ‘moreover’ part of the theorem tells us that the composite

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

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

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

How can we do that?

When C\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 ff is an endomorphism of a finite set, the set

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

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

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

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

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

When C\mathbf{C} is the category of finite-dimensional vector spaces, f 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 XX has a canonical decomposition

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

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

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

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

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

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

But we can adapt the strategy. (This paragraph is for the dedicated only.) By compactness, the sequence (f n(x))(f^n(x)) has a convergent subsequence (f n i(x))(f^{n_i}(x)), and its limit aa belongs to im (f)im^\infty(f). Since ff acts as an automorphism of im (f)im^\infty(f), there is for each ii a unique element of im (f)im^\infty(f) whose image under f n if^{n_i} is aa. We might, slightly riskily, call it f n i(a)f^{-n_i}(a), so that f n i(f n i(a))=af^{n_i}(f^{-n_i}(a)) = a. It turns out that (f n i(a))(f^{-n_i}(a)) converges; call its limit f (x)f^\infty(x). With some work, we can see that this defines a map f :XXf^\infty: X \to X with all the properties required. In other words, it gives us the unit of an adjunction im Uim^\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)(X, f) into a reversible dynamical system (im (f),f| im (f))(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)(X, f), a canonical idempotent f f^\infty on XX whose image is im (f)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

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

  1. Let G be a group, let 2(G)\ell^2(G) be the (Hilbert) space of square-summable functions on GG; this is a right GG-module in a canonical way. If a bounded, linear right GG-module map T: 2(G) 2(G)T:\ell^2(G)\to\ell^2(G) is injective and has closed range, then it is surjective.
  2. Again fix a group GG: now let XX be {0,1} G\{0,1\}^G, given the product topology and the natural shift action of GG. A conjecture of Gottschalk states/claims that every injective, continuous, GG-map from XX to itself is surjective. (By work of Gromov, if GG 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

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

Yemon, let me try a specific question. Let HH be a Hilbert space and let T:HHT: 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 TT?

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

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

Re: The Eventual Image

In the case where TT 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 TT. 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 TT.

However, I don’t think that can be canonical in the sense you require, because if I take TT to be the right shift on (N)\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 imT nim T^n for some nn.

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

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

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

have a simultaneous left and right adjoint, when Auto\mathbf{Auto} is the category of Hilbert spaces equipped with an automorphism and Endo\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 1\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 TT on 2()\ell^2(\mathbb{N}). (I assume you meant 2\ell^2, not \ell^\infty, seeing as we’re talking about Hilbert spaces, though it doesn’t really matter.) If SS is an automorphism of a Hilbert space HH then any map

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

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

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

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

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 FF guaranteeing that if it has both adjoints, they’re equal?

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

AbAb×Ab \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 C\mathbf{C}, the inclusion

CIdem \mathbf{C} \hookrightarrow \mathbf{Idem}

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

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

AutoEndo \mathbf{Auto} \hookrightarrow \mathbf{Endo}

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

I still don’t know, but my instinct is that the equality of the left and right adjoints to CIdem\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

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

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

Fix a functor UU. There is a category Ambi(U)Ambi(U) of ambijoints to UU. 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)Ambi(U) need not be either empty or equivalent to 11.

Certainly Ambi(U)Ambi(U) is a preordered set (i.e. each of its homsets has at most one element), since between any two left adjoints to UU there’s just one structure-preserving natural transformation. It’s also a groupoid. So, Ambi(U)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)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 1P_1, P 2P_2 to UU. There’s a unique natural isomorphism i:P 1P 2i: P_1 \to P_2 commuting with the structure maps that make P 1P_1 and P 2P_2 left adjoint to UU. Similarly, there’s a unique natural isomorphism j:P 1P 2j: P_1 \to P_2 commuting with the structure maps that make P 1P_1 and P 2P_2 right adjoint to UU. But maybe iji \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

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 UU, which has an ambijoint called im im^\infty. If you look at the Theorem in my post, you’ll see that the ambijunction satisfies a special condition: the composite

Uim 1Uim 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 UU 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: CIdem\mathbf{C} \stackrel{\to}{\leftarrow} \mathbf{Idem}. Again, the functor CIdem\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 UU and PP are adjoint both ways round then UPU \circ P acquires the structure of a Frobenius object (in the appropriate endofunctor category). Here, Uim U \circ im^\infty is a Frobenius object in the category [Endo,Endo][\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 VV in the ordinary sense, this would say that

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

which of course is never going to happen except when VV is 00 or kk. 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

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

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

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

Re: The Eventual Image

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

Making ff be surjective on BB 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 ff). But it doesn’t solve the injectivity problem:

Consider the natural numbers with the endomorphism defined by

f(n)=n1 ifn>0 f(n)=0 ifn=0\array{f(n)=n-1&if n\gt 0\\f(n)=0&if n=0}

Unless I’m much mistaken, the “largest subspace BB of (,f)(\mathbb{N}, f) such that BfBB\subseteq f B” seems to be \mathbb{N} itself, on which ff is surjective but not injective. Maybe it would be better to define im fim^\infty f as the largest subspace on which ff 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 ff can fail on the intersection of successive images; and systems which are infinite downwards (e.g. (,f:nn+1)(\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 fim^\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

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

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

Here, the chain

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

does not stabilize after ω\omega steps. That is, the image of nim(f n)\bigcap_{n \in \mathbb{N}} im(f^n) under ff is a proper subset of nim(f n)\bigcap_{n \in \mathbb{N}} im(f^n). Explicitly, nim(f n)\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 ff 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 BB such that BfBB \subseteq f B is \mathbb{N} itself, on which ff does not act bijectively. Does that mean we shouldn’t call it im (f)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:nmax{0,n1}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 ff.

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

  • applying the left adjoint to AutoEndo\mathbf{Auto} \hookrightarrow \mathbf{Endo}
  • applying the right adjoint to AutoEndo\mathbf{Auto} \hookrightarrow \mathbf{Endo}
  • taking the eventual image (defined to be the largest subspace BB such that BfBB \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

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

No, though \mathbb{Z} might be called the “Grothendieck \mathbb{Z}-set” of this ff. 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

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 GroupMonoid\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

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 ff of \mathbb{N} on XX 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

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

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 XX, any distance-decreasing map f:XXf: X \to X acts as an automorphism (i.e. a distance-preserving bijection) on im (f)im^\infty (f). But if ff is surjective then im (f)=Xim^\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 XX is often characterized as “every injection XXX \to X is an isomorphism”. But it could equally well be characterized as “every surjection XXX \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 XXX \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 XX and a distance-decreasing surjection f:XXf: X \to X. We prove that ff is distance-preserving, which also implies that it is injective.

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

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

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

d(x,f n ia)=d(f n ix n i,f n ia)d(x n i,a). 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 ibyf^{n_i} b \to y. (We now forget about (x n)(x_n) and (y n)(y_n).)

Let ε>0\varepsilon \gt 0. Choose II such that d(f n ia,x)<ε/4d(f^{n_i}a, x) \lt \varepsilon/4 and d(f n ib,y)<ε/4d(f^{n_i}b, y) \lt \varepsilon/4 for all iIi \geq I. Write m=n I+1n I1m = n_{I+1} - n_I \geq 1. We have

d(x,y) d(x,f n I+1a)+d(f n I+1a,f n I+1b)+d(f n I+1b,y) <d(f n I+1a,f n I+1b)+ε/2 =d(f mf n Ia,f mf n Ib)+ε/2 d(f mf n Ia,f mx)+d(f mx,f my)+d(f my,f mf n Ib)+ε/2 d(f n Ia,x)+d(f mx,f my)+d(y,f n Ib)+ε/2 <d(f mx,f my)+ε d(fx,fy)+ε. \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)<d(fx,fy)+εd(x, y) \lt d(f x, f y) + \varepsilon. But ε\varepsilon was arbitrary, so d(x,y)d(fx,fy)d(x, y) \leq d(f x, f y). On the other hand, ff is distance-decreasing; hence d(fx,fy)=d(x,y)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

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 RR be a commutative ring. A free module MM over RR is of finite rank iff every surjective module endomorphism MMM \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=R = \mathbb{Z}, seen as a module over itself.)

Proof of “only if”: Suppose f:R nR nf: R^n \to R^n is surjective, where nn is finite. Notice that we can split ff: there exists gg such that fg=1 R nf \circ g = 1_{R^n}. Taking determinants on this equation, this means det(f)\det(f) is a unit in RR. Then, by Cramer’s rule, we can invert the standard matrix representation for ff, i.e., ff 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

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 XX be a compact metric space and f:XXf: X \to X a distance-decreasing map. Then

ff is distance-preserving \iff ff is surjective.

In other words, if ff is distance-preserving or surjective then ff 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 YY of a metric space XX has a kind of characteristic function χ Y:X[0,]\chi_Y: X \to [0, \infty], defined by χ Y(x)=d(Y,x)=inf yYd(y,x)\chi_Y(x) = d(Y, x) = \inf_{y \in Y} d(y, x).)

So we have the following:

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

  • finite sets
  • finite-dimensional vector spaces
  • compact metric spaces and distance-decreasing maps.

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

ff is regular monic \iff ff is epic.

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

In finite sets or finite-dimensional vector spaces, every monic and every epic is regular. So we could add FinSet opFinSet^{op} and FDVect opFDVect^{op} to the list of possible values of C\mathbf{C}. Doubtless there are further values of C\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

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

Someone should have mentioned the Ax-Grothendieck theorem! It says: let f: n nf: \mathbb{C}^n \to \mathbb{C}^n be a polynomial map (meaning that each component n\mathbb{C}^n \to \mathbb{C} is polynomial). If ff 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 n n\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

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)(X, d) and a function f:XXf: X \to X such that x,yd(f(x),f(y))d(x,y)\forall_{x, y}\; d(f(x), f(y)) \leq d(x, y).

If XX is compact, then ff is an isometry provided that ff 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-11 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

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

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 XX and a real number ε>0\varepsilon \gt 0, write N ε(X)N_\varepsilon(X) for the minimum number of sets of diameter ε\leq \varepsilon needed to cover XX. (The function εN ε(X)\varepsilon \mapsto N_\varepsilon(X), or something very like it, is called the metric entropy or Kolmogorov entropy of XX.) It’s easy to see that if YY is a proper closed subspace of XX then N ε(Y)<N ε(X)N_\varepsilon(Y) \lt N_\varepsilon(X) for sufficiently small ε\varepsilon. So XX cannot be isometric to a proper subspace of itself.

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

distancepreservingsurjective. distance preserving \implies surjective.

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

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

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

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

is a distance-preserving endomorphism of Hom(X,X)Hom(X, X), and therefore surjective. In particular, there exists tHom(X,X)t \in Hom(X, X) such that s *(t)=1 Xs^*(t) = 1_X, that is, ts=1 Xt \circ s = 1_X. But ss is surjective, so this forces ss 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

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 XX is a compact Hausdorff space, and TT is a compact submonoid of the monoid of continuous maps XXX \to X (with its compact-open topology), then every surjection in TT is a bijection.

In the second fact, you said ‘every compact monoid TT of homeomorphisms’, which was presumably a slip: the elements of TT can be any old continuous maps XXX \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

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

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 SS be the free compact semigroup on 11-generator ss and GG be the free compact group on 11-generator gg. There is a canonical surjective homomorphism f:SGf\colon S\to G sending ss to gg. Surjectivity follows from the easy to verify fact that any closed subsemigroup of a compact group is a subgroup.

Let ee be the unique idempotent of SS. Then standard structure theory of compact monogenic semigroups implies that eSeS is a compact abelian group. Since SS is commutative, the mapping sess\mapsto es is a surjective homomorphism and hence eSeS is a compact monogenic group with generator eses. Trivially f(es)=f(s)=gf(es)=f(s)=g and so eSeS maps surjectively onto GG with the generator eses mapping to gg. But then by freeness of GG, this splits. It follows that GeSG\cong eS and we can identify ff with sess\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 SS by weak contractions on metric spaces and Auto is the category of continuous actions of GG by contractions of metric spaces.

Now if SS is a semigroup and ee is an idempotent of SS, there is a functor from SS-sets to eSeeSe-sets that takes XX to eXeX. This functor is exact and has left and right adjoints. Now for the case of SS above with idempotent ee, one has that eXeX 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

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

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)=supd(mx,my)d'(x,y) = \sup d(mx,my) the sup over mm 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

I suspect the vector space case is similar. One can take the pro-algebraic completion of the free semigroup SS on 11-generator and the pro-algebraic completion GG of the free group on one-generator. I assume one can show the former has a unique idempotent ee and that eSGeS\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

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

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

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:XXf: X \to X as the intersection of the countable chain

XfXf 2X X \supseteq f X \supseteq f^2 X \supseteq \cdots

then f ωXf^\omega X seems very reasonable (and f ωf^\omega very reasonable for the idempotent whose image is f ωXf^\omega X). Still, f Xf^\infty X and f 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:XXf: X \to X as the largest subspace WW such that fWWf W \supseteq W (or equivalently, such that fW=Wf W = W) then f ω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

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

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

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

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 SS where the semigroup product is

– continuous on one side (in the Stone-Cech compactification, there are two different extensions of the semigroup product on NN; 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×SSS \times S \to S (my *suspicion* is that this would be the almost periodic compactification, or the closure of NN 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

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, βN\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

André: I am probably being slow, but if we let SS denote the closure of NN inside GG, the Bohr compactification of ZZ, then even if SS is a group I dont see why this implies S=GS=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

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

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

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

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 XX in a category is hopfian if every epimorphism XXX \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

(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

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

Post a New Comment