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)*+1

David Corfield (Mar 21 2026 at 15:47):

Is there anything in the observation that for species the derivative is defined as $F'(X) \cong F(X + \{\bullet\})$? So here we have $F(F(X)) \cong 1 + F'(X)$.

John Baez (Mar 22 2026 at 00:34):

Just to say it out loud, this says a list of lists of elements in X is either a list containing only the empty list, or a list of elements of X and 'markers': copies of $\bullet$.

But one thing it implies, when taken with other observations here, is that the function

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

obeys the differential equation

$f'(x) = f(f(x)) - 1$

John Baez (Mar 22 2026 at 00:50):

One thing that's intrigued me for a long time - I've probably discussed it with @David Corfield on the n-Category Cafe - is that

$f(f(f(x))) = x$

This always makes me wonder if there's some weak sense in which

$X^{\ast \ast \ast} \simeq X .$

I don't think

$X^{\ast \ast \ast } \cong X ,$

say as endofunctors on $\text{Set}$. This would be saying a list of lists of lists of elements of $X$ is the same as an element of $X$!

John Baez (Mar 22 2026 at 00:55):

But let's see what we can do with @Vincent Moreau/@Oscar Cunningham's nice fact that

$X^{\ast \ast} \cong (X + 1)^\ast + 1$

This implies that

$X^{\ast\ast\ast} \cong ((X + 1)^\ast + 1)^\ast,$

where we leave the outer star alone, and also that

$X^{\ast\ast\ast} \cong (X^\ast + 1)^\ast + 1 ,$

where we leave the inner star alone. Can we do anything with this other than annoying our friends by asking them to show there's a natural isomorphism

$((X + 1)^\ast + 1)^\ast \cong (X^\ast + 1)^\ast + 1 \quad ?$

Vincent Moreau (Mar 22 2026 at 01:01):

John Baez said:

I don't think

$X^{\ast \ast \ast } \cong X ,$

say as endofunctors on $\text{Set}$. This would be saying a list of lists of lists of elements of $X$ is the same as an element of $X$!

Indeed, there is no such bijection when $X$ is a finite set, because the left hand side is then infinite.

Vincent Moreau (Mar 22 2026 at 01:06):

John Baez said:

Can we do anything with this other than annoying our friends

The reason I wanted another formula for $(X^*)^*$ was to represent words of words as simply typed $\lambda$-terms of a certain type (with just $\times$ and $\Rightarrow$, no coproducts) -- as described in the second message of the thread -- and to see if this yields an interesting viewpoint on the Kleene star of regular languages. Well, at the end of the day I can still represent non-empty words of words, which is not exactly what I wanted but still better than nothing I guess, and along the way I eventually got interested in the formula itself.

David Corfield (Mar 22 2026 at 08:13):

John Baez said:

This implies that

$X^{\ast\ast\ast} \cong ((X + 1)^\ast + 1)^\ast,$

To help intuitions, we might consider Morse code, with $X = \{dot, dash\}$. Then $X^\ast$ contains a representative of each letter of the alphabet (and each numeral). $X^{\ast\ast}$ contains each word and $X^{\ast\ast\ast}$ contains each sentence.

But to send sentences unambiguously we use spaces. So, $(X + 1)^\ast$ contains all words of a language with the $1$, a silence lasting 3 units, marking the boundary of a letter. Then $((X + 1)^\ast + 1)^\ast$ contains all sentences with the final $1$, a silence lasting 7 units, marking the boundary of a word.

John Baez (Mar 22 2026 at 16:22):

This is indeed a nice example of lists of lists of lists. Is this how the silences are actually used in Morse code?

David Corfield (Mar 22 2026 at 17:41):

Yes, that's how they use silences. To end a sentence they seem to use a special combination of dots and dashes, rather than go for an even longer silence.

Marking the trace of $X^{\ast \ast \ast} \cong X$ via a new symbol. :grinning: