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: The coalgebraic dual of a monad is also a monad

Patrick Nicodemus (Jan 16 2024 at 09:15):

I just noticed something interesting. The List monad on sets, also known as the free monoid monad, is characterized by an "algebraic" or "inductive" universal property - given a set $A$, to explain where to send a list of elements $(a_1,\dots, a_n)$, we can go by recursion - it suffices to explain where to send the head of the list and the tail of the list, as well as the empty list. So we have a concatenation map $L\times A\to L$ and a distinguished empty list $[]\in L$, and this is initial among sets with maps $S\times A\to S$ and distinguished element $1\in S$. Initial algebra, defines a monad.

Now if we dualize everything and consider maps $S\to S\times A + 1$ instead of maps $S\times A + 1\to S$, and look at the terminal object in this category, we get the set of streams in $A$, which are finite or infinite sequences of elements of $A$. This, again, forms a monad on the category of sets, which I find a bit surprising - the list monad is a sub-monad of a larger stream monad containing infinite streams, and the universal property of these objects is a coalgebraic one.

I think this works when you consider trees of fixed arity, too. More specifically if you fix a set $E$ representing the arity, and for each set $A$ consider the initial algebra of the endofunctor $S\mapsto (S\times A)^E + E$, you should get a monad on sets which are roughly trees with interior nodes in $A$ with arity $|E|$ and leaves in $E$. But also if you consider the terminal coalgebra of this same endofunctor you get another monad, containing the first one as a submonad.

What is going on here? Why is this coalgebraic structure giving rise to algebraic structure?

Ralph Sarkis (Jan 16 2024 at 09:43):

Do you need to fix the arity? I think in general with a signature $\Sigma$, the initial algebra is the set of well-founded (rooted) trees internally labelled in $\Sigma$ and the final coalgebra is the set of all trees internally labelled in $\Sigma$.

Patrick Nicodemus (Jan 16 2024 at 10:05):

Probably not, it's just that the example that led me to think about this was the set of trees of fixed arity.

Patrick Nicodemus (Jan 16 2024 at 10:15):

Well, actually, I think we might be talking about something slightly different. I'm assuming you mean the monad which sends a set $A$ to the set of all terms in the signature $\Sigma$ with variables drawn $A$. That's not really what I have in mind here, I think. For example, if $\Sigma$ has a binary multiplication $m$ and a unit $e$, then the list monad $L(A)$ is a quotient of $\Sigma(A)$ by the usual relations asserting that $m$ is associative and $e$ is a two-sided unit. But i'm not aware of a way to express lists of elements in $A$ directly as the set of valid terms in a signature in this way.

Patrick Nicodemus (Jan 16 2024 at 10:16):

Put more simply, in $\Sigma(A)$ the elements of $A$ appear only at the leaves of the trees. In my version the elements of $A$ are labels for the interior nodes.

Patrick Nicodemus (Jan 16 2024 at 10:20):

$A$ plays the role of the signature, and all symbols in $A$ have the same given arity $|E|$; then we consider all trees with variables drawn from the set $E$.

Ralph Sarkis (Jan 16 2024 at 10:31):

If you let $\Sigma$ contain the symbol $a$ with arity $|E|$ for every $a \in A$ and a constant ($0$ -ary) $e$ for every $e \in E$, that works right? The set of terms over the empty set is the initial algebra.

For lists, the terms you get are stuff like $a(a(b(\ast)))$ and $a(c(a(b(\ast))))$, which are lists (without imposing equations).

James Deikun (Jan 16 2024 at 12:47):

I think there's a level slip in this discussion that goes a long way to explaining the phenomenon itself. The initial algebra/terminal coalgebra semantics happens on the level of a functor on Set where you take an initial or terminal fixpoint, and the being-a-monad happens on the level of an extra parameter you have that decides which functor you take the fixpoint of.

In general if you have a bifunctor $F : \bold{Set} \times \bold{Set} \to \bold{Set}$ and taking the initial algebra in the second variable gives you a monad, then the unit $\eta : \mathrm{Id} \to (T = A \mapsto \mathrm{Init}(F(A,-)))$ and multiplication $\mu$ may extend to $T' = A \mapsto \mathrm{Term}(F(A,-))$. The unit always extends because there's a canonical map from the initial algebra to the terminal coalgebra, which comes from the fact that each of them also carries a structure of the other type.

James Deikun (Jan 16 2024 at 13:51):

However, the extension of the multiplication is much trickier and List/Colist is a pathological example. The multiplication extends to a function in $\mathrm{Set}$ but there's no way to define this function in the programming languages this stuff is usually used as a model of. The problem is when there's an infinite tail of empty colists. The only thing you can really do with this is map it to $\mathsf{nil}$, however there's no way to write a function in a programming language that can inspect the infinitely many empty colists and decide to return that.

James Deikun (Jan 16 2024 at 13:59):

The other example is even worse. Say you have a cotree with an infinite path, and each node along the path contains a leaf, the element of $E$ that indicates the next node on the path. Then the correct thing to do in a situation like this is to return the leaf in the upper cotree where the path stops. But the path never stops at a leaf, there is nothing to return. In the special cases where $E$ is empty (the terminal monad either way) or a singleton (List/Colist) we can avoid the problem or hack around it because there's only (at most) one possible leaf, but in general this sinks the project entirely.

James Deikun (Jan 16 2024 at 14:06):

(Even List/Colist doesn't actually work as a monad: take a colist with first element an infinite colist of empty colists, and second element a singleton with another singleton inside. If you apply $\mu$ to the outer levels first you get an empty colist, and if you apply it at the inner levels first you get a singleton; this breaks the associative law.)

James Deikun (Jan 16 2024 at 14:09):

Something that is probably an example is the monad of nonempty lists/monad of nonempty colists.

James Deikun (Jan 16 2024 at 14:14):

(Nonempty lists are the initial algebras for the family of functors $X \mapsto A + A \times X$.)

James Deikun (Jan 16 2024 at 14:18):

Finite/potentially-infinite $E$-branching trees with an element of the carrier at internal nodes and an element of $E$ at leaves, and at least one internal node, are probably another example, but expressing them as an initial algebra/final coalgebra is tricky at best, and I'm not sure it's even possible using a single outer fixpoint and no indexing.

James Deikun (Jan 16 2024 at 14:22):

I guess it's possible: $X \mapsto A \times (E + X)^E$.

Patrick Nicodemus (Jan 16 2024 at 15:07):

Ralph Sarkis said:

If you let $\Sigma$ contain the symbol $a$ with arity $|E|$ for every $a \in A$ and a constant ($0$ -ary) $e$ for every $e \in E$, that works right? The set of terms over the empty set is the initial algebra.

For lists, the terms you get are stuff like $a(a(b(\ast)))$ and $a(c(a(b(\ast))))$, which are lists (without imposing equations).

This is what I had in mind in the previous message, yes. But I am interested in a monad $L$ which I call the "list monad" or "free monoid monad" whose underlying functor accepts $A$ and returns this tree constructed in terms of $E$ and $A$. You are describing a different monad $\Sigma_A$ with a different underlying functor which is defined in terms of $A$ and has a different unit and different multiplication, and it happens that $L(A) = \Sigma_A(\emptyset)$.

Patrick Nicodemus (Jan 16 2024 at 15:10):

James Deikun said:

However, the extension of the multiplication is much trickier and List/Colist is a pathological example. The multiplication extends to a function in $\mathrm{Set}$ but there's no way to define this function in the programming languages this stuff is usually used as a model of. The problem is when there's an infinite tail of empty colists. The only thing you can really do with this is map it to $\mathsf{nil}$, however there's no way to write a function in a programming language that can inspect the infinitely many empty colists and decide to return that.

This is a good observation! The language I have in mind is Turing complete and so realistically, the semantics of this would be that it diverges/loops infinitely when trying to flatten the infinite stream of empty lists.

Ralph Sarkis (Jan 16 2024 at 16:35):

I see, I was thinking only of the relation between initial algebra and final coalgebra, not the between the monads.