Re: non-unital monads

[Richard Garner <richardgarner@fastmail.fm>]

With reference to Tarmo's examples---it's perhaps worth pointing out the
notion of an "ideal monad" on a category with coproducts. One way of
defining an ideal monad is in terms of an endofunctor T together with a
natural transformation m:T(1+T)--->T satisfying two axioms: 

- m.T(inl) = 1: T--->T
- m.T(inr.m) = m.(m.Tinr)(1+T): TT(1+T) ---> T. 

This is something stronger than a non-unital monad; if (T,m) is as
above, then (T, m.T(inr)) is a non-unital monad. The extra strength
means that from such a pair (T,m) one obtains a monad structure on 1+T
in an obvious way. All of the examples Tarmo mentions possess this extra
strength.

Some references:

P. Aczel, J. Adamek, S. Milius and J. Velebil, Infinite trees and
completely iterative theories: a coalgebraic view. Theor. Comput. Sci.
300 (2003) 1–45.

Neil Ghani and Tarmo Uustalu, Coproducts of ideal monads, Theoretical
Informatics and Applications 38 (2004), no. 4, 321–342.

Richard

> 2. "Non-unital monads" are not difficult to find.
> 
> On Set, you can consider, for example,
> 
> - T X  =  X x S   where (S, *) is some semigroup
> 
>                            ass                 X x *
>     mu_X  =  (X x S) x S -------> X x (S x S) ----- -> X x S
> 
>     The simplest special case is given by right zero semigroups: Take
>     any set S and define s * s' = s'; one gets
> 
>                          fst x S
>     mu_X  =  (X x S) x S -------> X x S
> 
>     (For S with 2 or more elements, there is no unit.)
> 
> - T X  =  lists over X of length at least n, for some fixed n
> 
>     mu_X  =  flattening of a list of lists into a list
> 
>     (For n \geq 2, there is no unit.)
> 
> - For an endofunctor F, the free non-unital monad on F would be
> 
>     F^+ X  =  F (F^* X)  \cong  F^* (F X)
> 
>     where F^* is the free monad on F (assuming this exists).
> 
>     So concretely you can construct F+ in terms of initial algebras by
> 
>     F^+ X  =  F (mu Z. X + F Z)  \cong  mu Z. F X + F Z
> 
>     (for comparison, F^* X  \cong  mu Z. X + F Z)
> 
>     The free non-unital monad exists precisely when the free monad does,
>     as you also have
> 
>     F^* X  \cong  X + F^+ X
> 
>     For your example, F X  =  X x X, one gets that F X is the set of all
>     composite terms over variables from X, for a signature with one
>     binary
>     operation.
> 
>     (And free would mean left adjoint to forgetful as usual.)
> 
> Kind regards,
> 
> Tarmo U
> 

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]