1
$\begingroup$

Here is the definition of finitary monad. The finite multiset monad has a functor that maps the category of sets to itself. It does this by taking a set to the set of all finite multisets on that set. A multiset is like a set with duplicates, and this monad has free commutative monoids as its category of algebras. Its multiplication takes a formal sums of formal sums to a formal sum. The unit natural transformation takes a set to the set of bags, each with exactly one set element. Is the finite multiset monad a finitary monad?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes. Call your monad $T$. Then $T(S)=\sqcup_{n\in \mathbb{N}}\mathrm{Set}(n,S)$. That is, a multiset in $S$ is just a map to $S$ from a finite set. Thus the finitarity of $T$ follows from the finite presentability of each $n$, and the fact that finitary functors $\mathrm{Set}\to\mathrm{Set}$ are closed under colimits. Indeed, if each $F_i$ is finitary, $I$ is any category such that the colimit exists (e.g. $I$ is small), and $J$ is filtered, then $$(\mathrm{colim}_I F_i)(\mathrm{colim}_J S_j) =\mathrm{colim}_I\mathrm{colim}_J F_i S_j=\mathrm{colim}_J((\mathrm{colim}_I F_i)(S_j)$$ using the facts that colimits in functor categories are pointwise, colimits commute with colimits, and the assumptions on $F_i$.

It's not correct that $T$'s algebras are free commutative monoids. A $T$-algebra is a summation map $TS\to S$ that turns any finite multiset in $S$ into an element of $S$ in a way coherent with the structure of $T$. So it's an arbitrary commutative monoid. This gives a more general way to see that $T$ is finitary: it's the monad for an equational algebraic theory.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .