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: learning: questions

Topic: Free monads, multisets, and string diagrams

Ben Sprott (Jan 11 2021 at 19:16):

Take $Gpd$ as the 2-Category of groupoids. Consider the multiset monad on $Gpd$.

We know from this post that $Gpd$ is locally presentable.

A free monad is a free object relative to a forgetful functor whose domain is a category of monads. (See here).

There is some talk in the link just above about how locally presentable is related to having free monads on a category but I can't quite decipher it. I would like to say that, because $Gpd$ is locally presentable, the multiset monad on $Gpd$ is free. I'm not sure if this is true.

From this article we see that there is a string diagram calculus over free monads. I assume, then, that muliset-$Gpd$ can be incorporated into string diagrams and be combined with other free monads.

Does anyone know any examples of Free Monads?

Todd Trimble (Jan 12 2021 at 16:39):

The "multiset monad" (perhaps better known as the commutative monoid monad) is not a free monad, I'm positive. An example of a free monad is the monad whose algebras are magmas, where the theory is given by a single binary operation not subject to any equational axioms. Indeed, you should probably think of a typical free monad $F(M)$ on a monad $M$ as describing an algebraic theory that can be given by operations but with no equational axioms imposed.

It might be wise to consider the case of $Set$ before $Gpd$, just to get a sense of the meanings of these things. Given an endofunctor $M$ on $Set$, you can think of $M(X)$ as a set of formal $X$-ary operations; for example, of $M(2)$ as a set of binary operations. What the free monad does in effect is "close up" those formal operations under the process of substituting tuples of operations into an another operation to form a more complex operations. For example, closing up a single formal binary operation in this way, the operations encoded by the free monad are given by binary trees.

Commutative monoids, on the other hand, are models of a theory where equational axioms of associativity and commutativity are imposed, so you should be innately suspicious of a claim that these could be given by a free monad.

The business of local presentability and accessible functors is just to give some general criteria sufficient to guarantee that a free monad can be constructed. If $M$ is an accessible functor on a locally presentable category, then you can form the free monad on $M$. If some sorts of control like that are absent, e.g., if someone hands you an endofunctor $M$ that isn't accessible, all bets are off on whether the free monad on $M$ can be formed: maybe sometimes yes, maybe more times no, but it would depend on the specifics of $M$.

Ben Sprott (Jan 12 2021 at 18:24):

Excellent reply. Thank you @Todd Trimble . Is it possible that the list monad is free since the algebras are just( I think free) monads? I would take that monad on Set, so List-Set.

Todd Trimble (Jan 12 2021 at 18:29):

No. The algebras are just monoids, not necessarily free. The associativity equation is an imposed equational axiom on monoids.

Reid Barton (Jan 12 2021 at 18:36):

See also https://mail.haskell.org/pipermail/haskell-cafe/2017-January/126026.html

John Baez (Jan 12 2021 at 20:30):

That https://mail.haskell.org/pipermail/haskell-cafe/2017-January/126026.html comment is nice. Could someone spare me some trouble and explain in the language of mathematics what the monad "Unit" is?

John Baez (Jan 12 2021 at 20:31):

The comment talks about the free monad on Unit and then the free monad on that (or more precisely, on the underlying functor of that).

John Baez (Jan 12 2021 at 20:32):

By general abstract nonsense there should be a morphism FF(Unit) $\to$ Unit, where F means the underlying functor of the free monad on a endofunctor (which however may not always exist).

Nathanael Arkor (Jan 12 2021 at 20:40):

John Baez said:

That https://mail.haskell.org/pipermail/haskell-cafe/2017-January/126026.html comment is nice. Could someone spare me some trouble and explain in the language of mathematics what the monad "Unit" is?

By Unit, they mean the terminal functor, sending everything to the terminal object.

John Baez (Jan 12 2021 at 20:42):

Thanks! I figured it had to be something simple...

John Baez (Jan 12 2021 at 20:44):

So, people who want to understand free monads should try to compute the free monad on the terminal functor $F: \mathsf{Set} \to \mathsf{Set}$ and then compare their answer to what Ingo Blechschmidt said.

Reid Barton (Jan 12 2021 at 20:59):

The answer is the "free pointed set monad" $TX = 1 + X$ (aka Maybe).