The n-Category Café

Thanks, Anon. Your first couple of sentences give a neat way of looking at it. But this is exactly the algorithm embodied in my proof of the proposition, isn’t it?

(When I say “my proof”, I just mean the proof I gave in the post. The proposition has been known for decades, and I certainly don’t mean to claim any originality.)

oh, scooped… for once that I could answer a question here :(

Well, maybe the slogan “$k$th predecessor of the $k$th iterate” (where $k$ is the number of steps it takes to reach a cycle) is more useful than I originally thought.

It is the construction in the proof of the proposition, almost inevitably. But perhaps it provides some insight. For a start, if you abusively write the image of $x$ under the idempotent power as “$f^{-k}(f^k(x))$” then that suggests that it’s something “on the same level” as $x$ — a kind of modified version of $x$. That seems right, and also reinforces my hope that it’s characterized by some universal property.

The picture of trees is a wonderful and important one. But the last sentence “The idempotent you are referring to simply maps each element to the root of the tree to which it belongs!” is not correct, as explained in Anonymous’s post. Rather, Tom’s idempotent folds each tree down along the whirlpool, and sends a node in the tree to its whirlpool-element that is underneath it once you knock down the tree.

Sorry, my description was somewhat embarrassingly wrong. Your 3-element example shows this is not the idempotent. Grr…

Todd wrote:

Sure I know this idempotent! It feels like an old friend.

Excellent! That’s just the kind of thing I was hoping to hear.

I should have said in my original post what you said in your comment: the image of the idempotent power of $f$ can not only be described as the set of periodic points of $f$, but also as the eventual image of $f$, that is, the intersection $f^\infty X$ of the chain

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

And then, as you say, $f$ restricts to an automorphism of the eventual image.

I don’t know that proof of Cayley’s theorem from Joyal’s paper. I didn’t even know Cayley’s theorem. I should have a look.

Yes, this is also related to the notion of trace of a category, a kind of categorified dimension.

The trace of a ($Set$-enriched) category $C$ is the coend $\int^{c: C} \hom(c, c)$, if this exists. If $C$ is the category of finite sets, then its trace is the set of conjugacy classes of finite permutations; here the image of $f \in \hom(c, c)$ in the trace is the conjugacy class of the permutation on the stable set $f^{(\infty)}(c)$. This is explained in the examples section of the nLab article linked above.

Hi Federico! Thanks for that. Now I feel like I’m making some progress in understanding things abstractly, though the fog hasn’t completely cleared.

Let me develop what you wrote. Take the additive monoids $\mathbb{N}$ and $\mathbb{Z}$. I’ll write the corresponding one-object categories as $\mathbb{N}$ and $\mathbb{Z}$ — so, contrary to custom, the categories called $\mathbb{N}$ and $\mathbb{Z}$ are not discrete. I’ll write $i: \mathbb{N} \hookrightarrow \mathbb{Z}$ for the inclusion.

Consider the category $Set^\mathbb{N}$. An object is a set equipped with an endomorphism, and a map is a map of sets making the evident square commute (as in your comment). Similarly, an object of the category $Set^\mathbb{Z}$ is a set equipped with an automorphism. From this point of view, the functor $i^*: Set^{\mathbb{Z}} \to Set^\mathbb{N}$ is simply inclusion. I’ll usually leave it nameless.

For completely general reasons, the inclusion $i^*: Set^\mathbb{Z} \to Set^\mathbb{N}$ has both a left and a right adjoint: left and right Kan extension along $i$.

Here’s a description of the left adjoint. Let $X$ be a set equipped with an endomorphism $f$. The left adjoint sends $X = (X, f)$ to the set $i_! X = Lan_i X$ given by

$$i_! X = \bigl( \mathbb{Z} \times X \bigr) / \sim$$

where $\sim$ is the equivalence relation generated by $(n + 1, x) \sim (n, f(x))$. The automorphism with which $i_! X$ comes equipped sends the equivalence class of $(n, x)$ to that of $(n + 1, x)$. The component of the unit at $X$ (that is, the 2-cell inside the triangle, in the usual diagram for Kan extensions) is the map $X \to i_! X$ given by sending $x \in X$ to the equivalence class of $(0, x)$.

Here’s a description of the right adjoint. Let $X$ be a set equipped with an endomorphism $f$. The right adjoint sends $X = (X, f)$ to the set $i_* X = Ran_i X$ whose elements are doubly infinite trajectories

$$\cdots \mapsto x_{-1} \mapsto x_0 \mapsto x_1 \mapsto \cdots$$

in $(X, f)$. In other words, an element of $i_! X$ is a doubly infinite sequence $(x_n)_{n \in \mathbb{Z}}$ such that $x_{n + 1} = f(x_n)$ for all $n \in \mathbb{Z}$. The automorphism that it comes equipped with is left shift. The counit at $X$ is the map $i_* X \to X$ given by $(x_n)_{n \in \mathbb{Z}} \mapsto x_0$.

These two adjoints are different: $i_!$ is not isomorphic to $i_*$. But the surprising thing — at least, it surprised me — is that if you restrict to finite sets, they become the same.

In other words, the left and right adjoints to the inclusion

$$FinSet^\mathbb{Z} \to FinSet^\mathbb{N}$$

are equal.

To see this, one only needs to think about the two descriptions above in the case that $X$ is finite. It’s fairly easy to see that both $i_! X$ and $i_* X$ are equal to the eventual image $\bigcap_{n \in \mathbb{N}} f^n X$ of $f$, on which $f$ acts bijectively. As Todd pointed out, this is the same as the image of the idempotent power of $f$, and it’s also equal to the set of periodic points of $f$.

Moreover, given a finite set $X$ equipped with an endomorphism $f$, we can compose the unit and counit maps mentioned above:

$$X \to i_! X \cong i_* X \to X.$$

And the composite is the idempotent that I was seeking to understand.

Note that this abstract description of the idempotent is only available because of the fact that $i_! X \cong i_* X$ for finite sets $X$.

It’s hard not to be reminded of another situation in which finiteness forces a left and right adjoint to become equal. For arbitrary sets $X$, the diagonal functor

$$Vect \to Vect^X$$

has distinct left and right adjoints; but if $X$ is finite, they’re equal. (They each send a finite family of vector spaces to its direct sum.) However, I can’t see any real connection between the two situations.

That’s very interesting, Jesse. It hadn’t occurred to me that there was a connection with height in groups.

Here are a few thoughts.

Of course, in the case of a finite $X$, [the eventual quotient] is isomorphic to the eventual image (though, I think, not canonically, unless they’re both a bunch of fixed points).

Isn’t it canonical? Take an element $x$ of the eventual image, and send it to its equivalence class $[x]$ in the eventual quotient.

There may be nodes only supporting infinitely many finite branches

Did you mean to write “finitely many finite branches”?

Incidentally, the connection to p-height insinuates that Tom is still thinking about operator spectra and characteristic polynomials and prime ideals.

Yes! I’m glad you spotted that. I’ll reveal what actually lay behind my question.

Let $f$ be a linear endomorphism of a finite-dimensional vector space $X$. The eventual kernel of $f$ is the union $evKer(f)$ of the chain of subspaces

$$Ker(f) \subseteq Ker(f^2) \subseteq Ker(f^3) \subseteq \cdots,$$

while the eventual image of $f$ is the intersection $evIm(f)$ of the chain of subspaces

$$Im(f) \supseteq Im(f^2) \supseteq Im(f^3) \supseteq \cdots.$$

This is the same eventual image as before, though as traditional in linear algebra, I’m writing $Im(f^n)$ instead of $f^n X$.

It’s not hard to prove that for any operator $f$ on a finite-dimensional vector space $X$,

$$X = evKer(f) \oplus evIm(f).$$

Projection onto $evIm(f)$ gives us an idempotent operator on $X$. So, any endomorphism $f$ of a finite-dimensional vector space gives rise canonically to an idempotent whose image is the eventual image of $f$ — exactly as for sets. I was trying to understand that idempotent. But I realized that I didn’t even properly understand its set-theoretic analogue, which ought to be a simpler thing. Hence this post.

Here are a few simple facts about eventual kernel and image:

• $evKer(f) = Ker(f^N)$ and $evIm(f) = Im(f^N)$, where $N = dim(X)$
• the subspaces $evKer(f)$ and $evIm(f)$ are both $f$-invariant
• the restricted operator $f$ on $evKer(f)$ is nilpotent, and the restricted operator $f$ on $evIm(f)$ is an automorphism
• this is the only way to decompose $f$ as the direct sum of a nilpotent and an automorphism.

In my comment up here, I pointed out that in the world of finite sets, eventual image arises as a simultaneous left and right adjoint. The same is true in the world of finite-dimensional vector spaces, as follows.

Let $FDVect^\mathbb{N}$ denote the category in which an object is a finite-dimensional vector space equipped with an operator, and a map is a linear map commuting with the specified operators. Let $FDVect^\mathbb{Z}$ be the similar category in which an object is a finite-dimensional vector space equipped with an invertible operator, i.e. an automorphism. Then the inclusion

$$FDVect^\mathbb{Z} \to FDVect^\mathbb{N}$$

has a simultaneous left and right adjoint. It sends a pair $(X, f)$ (with $X$ a finite-dimensional vector space and $f$ an operator on $X$) to $(evIm(f), f|_{evIm(f)})$. Because it’s both a left and a right adjoint, there are canonical maps

$$X \to evIm(f) \to X,$$

which are projection and inclusion; their composite is our idempotent.

And something similar is true for eventual kernels. Let $FDNil$ be the category in which an object is a finite-dimensional vector space equipped with a nilpotent operator. Then the inclusion

$$FDNil \to FDVect^\mathbb{N}$$

also has a simultaneous left and right adjoint. It sends a pair $(X, f)$ to $(evKer(f), f|_{evKer(f)})$. Again, the projection, inclusion and idempotent associated with the subspace $evKer(f)$ all arise from the structure of the adjunctions.

I must say, I don’t really understand the reason for the existence of these simultaneous left and right adjoints.

Well, it’s not so much that I was interested in finding the smallest $n$ such that $f^n$ is idempotent. It must be possible to extract a value of $n$ that will do from the proof of the proposition that I gave. I certainly agree that $|X|!$ will do.

What I wanted was to improve my understanding of that idempotent power. That improved understanding might come in the form of a different way of calculating it, or in the form of a categorical explanation of its existence. I think we’ve made some progress on both fronts, thanks to various people’s contributions. Personally, I still don’t understand the idempotent power as well as I’d like to, although I now know how to describe it in several ways.

Thanks! I didn’t know the term “monounary algebra”.

I imagine that universal algebraists have a particular way of understanding the idempotent power of a unary operation. Can you pass any of that understanding on to us?

Google is aware of about a thousand pages containing both “mononunary algebra” and “idempotent”, but I haven’t found any specific discussion of the topic of this post. I’m sure such discussions exist and I’m just not seeing them.

Thanks for your comments! Incidentally, to make the math come out right, you need to select an appropriate “Text Filter” from the drop-down menu below where you enter your email address. Anything containing “itex” will do; I use “itex to MathML with parbreaks”. (I fixed the two comments you just made.)

I didn’t know the standard notation $s^\omega$; thanks. It’s also interesting what you write about prorepresentability, and it’s a completely different categorical point (as far as I know) from the one I’d arrived at up here. To say it briefly, the point there was as follows. The inclusion functor

$$(finite sets equipped with an automorphism) \hookrightarrow (finite sets equipped with an endomorphism)$$

has both left and right adjoints — and they’re the same. By putting together units and counits in a suitable way, this produces for each set $X$ equipped with an endomorphism $f: X \to X$ a canonical map $X \to X$. That canonical map is our idempotent, $f^\omega$.

I was hoping to be able to add a more general statement about arbitrary (commutative?) semigroup actions, not just single endomorphisms, but I haven’t figured it out.