Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: category theory

Topic: On the identity X** = (X+1)*

Vincent Moreau (Mar 20 2026 at 12:05):

Hi everyone, let me share a cute observation. I write $(-)^*$ for the monad of (set-theoretic) monoids, i.e. $X^*$ is the set of finite lists/words over the set $X$ seen as an alphabet. Writing $(-) \cdot (-)$ for the concatenation, I noticed that the function

$$\begin{matrix} (X^*)^* & \longrightarrow & (X + \{\bullet\})* \\ [[w_1, \dots, w_n] & \longmapsto & w_1 \cdot [\bullet] \dots [\bullet] \cdot w_n \end{matrix}$$

is a bijection natural in the set $X$. Moreover, the multiplication $(X^*)^* \to X^*$ corresponds to the unique monoid homomorphism $(X + \{\bullet\})^* \to X^*$ which is the identity on $X$ and sends $\bullet$ to the empty word. (Notice however that the natural bijection above is NOT a natural isomorphism for the free monoid structures!)

Vincent Moreau (Mar 20 2026 at 12:13):

For those interested, I came across this on my work on higher-order regular languages. Indeed, any finite set $\Sigma$ induces the type

$$\operatorname{Church}(\Sigma) \quad:=\quad (o \Rightarrow o)^{|\Sigma|} \Rightarrow o \Rightarrow o$$

whose closed simply typed $\lambda$-terms correspond exactly to words $w \in \Sigma^*$ on the alphabet $\Sigma$, through the Church encoding. This assignment goes from finite sets to simple types so cannot be composed with itself, but following the natural bijection above the inhabitants of the type

$$\operatorname{Church}(\Sigma + 1)$$

correspond exactly to words of words $W \in (\Sigma^*)^*$.

Vincent Moreau (Mar 20 2026 at 12:20):

This led me to consider which endofunctors $F$ on the category of sets can be equipped with a natural bijection

$$F \circ F \quad\cong\quad F \circ ((-) + 1)$$

For the moment, my only examples of such $F$ are the functors $(-)^*$, $(-) + 1$, and any constant functor. It is easy to take $F$ a polynomial functor induced by some family $E \to B$ and to compute what such an isomorphism amounts to on that family, but I want concrete examples.

Also, moving from the category of sets to the category of graphs/quivers, we can see that the free category monad, which I write $\operatorname{Path}$, verifies an analog property:

$$\operatorname{Path}(\operatorname{Path}(G)) \quad\cong\quad \operatorname{Path}(G + ||G||)$$

where $||G||$ is the graph with same vertices as $G$ and with just one "endo"-edge for every vertex.

Nathanael Arkor (Mar 20 2026 at 12:27):

Fiore and Leinster showed that any arithmetic statement that can be proven using complex numbers establishes a corresponding isomorphism between objects of a rig category (Objects of Categories as Complex Numbers). Can you prove $X^{**} = (X + 1)^*$ arithmetically and then deduce your isomorphism using the results of Fiore and Leinster?

Vincent Moreau (Mar 20 2026 at 12:27):

• Do you know a reference where the identity $(-)^* \circ (-)^* \cong (-)^* \circ ((-) + 1)$ is studied, or at least written down? I believe it must be somewhere, as it is a very basic observation.
• Do you know other examples of $F$ which verify $F \circ F = F \circ ((-) + 1)$? I tried similar monads, like the one of finite or infinite words, but they did not seem to verify the identity. Also, the whole topic is reminiscent to me of the contour/splice adjunction of the paper Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem by Paul-André Melliès and Noam Zeilberger, but this may be a déformation professionnelle :slight_smile:

Vincent Moreau (Mar 20 2026 at 12:29):

Nathanael Arkor said:

Fiore and Leinster showed that any arithmetic statement that can be proven using complex numbers establishes a corresponding isomorphism between objects of a rig category (Objects of Categories as Complex Numbers).

I did not know that paper, thanks! I'm going to check that.

Vincent Moreau (Mar 20 2026 at 12:51):

Well I just skimmed through the paper, but from what I understand the equation $X^* = 1 + X \times X^*$ would correspond on complex numbers to the function

$$x \quad\longmapsto\quad x^*\ :=\ \frac{1}{1-x}$$

on appropriate $x$, and we then compute that

$$(x^*)^* = \frac{1}{1 - \frac{1}{1 - x}} = \frac{1 - x}{1 - x - 1} = - \frac{1 - x}{x}$$

and that

$$(x + 1)^* = - \frac{1}{x}$$

Unless I am missing something, it therefore seems that the bijection above is not captured by the arithmetic of complex numbers?

David Corfield (Mar 20 2026 at 17:12):

Only have a moment now, but don't the empty list of lists and the singleton list of the empty list both get sent to the empty list? If so, it would explain why you have an extra one in the calculation of $(x^*)^*$ in the last message.

Morgan Rogers (he/him) (Mar 20 2026 at 17:13):

I don't think I've noticed this before. What did you mean when you said that "the natural bijection is not a natural isomorphism for the free monoid structures", does that mean it is not well-behaved with respect to the monad structure?

I ask because at first glance it seems like an isomorphism $ST \cong SS$ provides a different way to extract a monad structure on a composite of a monad with an endofunctor compared with the usual way (distributive law). Namely, we get $STST \to SSST \to ST$, where the latter is the multiplication of $S$ twice. Maybe someone has thought about this example in such a context?

Oscar Cunningham (Mar 20 2026 at 18:23):

David Corfield said:

Only have a moment now, but don't the empty list of lists and the singleton list of the empty list both get sent to the empty list? If so, it would explain why you have an extra one in the calculation of $(x^*)^*$ in the last message.

Right, it should be X** = (X+1)*+1

Nathanael Arkor (Mar 20 2026 at 18:26):

In which case, the isomorphism would arise from the Fiore–Leinster result, though this doesn't seem to explain the connection to the monad structure.

Vincent Moreau (Mar 20 2026 at 20:15):

Oops looks like I messed up my analysis, thanks for pointing out that corner case! Hopefully no future employer of mine will see this thread :)

Vincent Moreau (Mar 20 2026 at 20:27):

More generally, the correct formula for graphs is $\operatorname{Path}(\operatorname{Path}(G)) \cong \operatorname{Path}(G + ||G||) + ||G||$.

Vincent Moreau (Mar 20 2026 at 20:34):

Morgan Rogers (he/him) said:

I don't think I've noticed this before. What did you mean when you said that "the natural bijection is not a natural isomorphism for the free monoid structures", does that mean it is not well-behaved with respect to the monad structure?

Well, now I don't know how to answer as the formula was incorrect :( What I meant was that the function $(X^*)^* \to (X+1)^*$ defined in the first message does not preserve concatenation, i.e. is not a monoid morphism.

However, if we take the restriction to $(X^*)^+ \to (X + 1)^*$, where $(-)^+$ is the monad of semigroups given by non-empty lists, then we have a bijection which is a morphism of semigroups if the codomain set is endowed with the semigroup operation defined as $w \cdot_{\bullet} w' := w \cdot [\bullet] \cdot w'$, which adds a bullet in the middle of the concatenation. This is quite satisfying actually :)

John Baez (Mar 20 2026 at 20:41):

Oscar Cunningham said:

Right, it should be X** = (X+1)*+1

So if we make the interpretation

$\displaystyle{ x^* := \frac{1}{1-x}}$

then we get

$\displaystyle{ (x^*)^* = \frac{1}{1 - x^*} = \frac{1}{1 - \frac{1}{1-x}} }$

$\displaystyle{ = \frac{1 - x}{1 - x - 1}= - \frac{1 - x}{x} }$

$\displaystyle{ = 1 - \frac{1}{x} = 1 + \frac{1}{1 - (1+x)} = 1 + (1+x)^* }$

so the desired relation holds! :tada: :tada: