non-unital monads

non-unital monads

[Vladimir Voevodsky]

Hello,

I am trying to find some information about non-unital monads (gadgets with \mu but without \eta).

In particular I am interested in the following two questions:

1. Given a non-unital monad can it have two different "unitality" structures?

2. Is there a concept of a free non-unital monad? For example, I can think of
the "free" non-unital monad generated by the functor X |-> X^2 on sets as the monad
that sends a set X into the set of "homogeneous" expressions made with one binary operation
s such that there is s(x1,x2) and s(s(x1,x2),s(x3,x4)) but no x1 itself and no s(x1,s(x2,x3)). 
But what is the universal characterization of it? 

Thanks!
Vladimir.


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

Re: non-unital monads

[Peter Johnstone]

The answer to Vladimir's first question is no. Suppose \mu: TT --> T
has two units \eta, \zeta: 1 --> T. Then, for any A, the composite
\mu_A.T\eta_A.\zeta_A reduces to \zeta_A by one unit law; but it's
equal to \mu_A.\zeta_TA.\eta_A by naturality of \zeta, and this reduces
to \eta_A by the other unit law. (If you don't demand that the units be
`two-sided' then the answer is yes.)

Peter Johnstone

On Sat, 18 Oct 2014, Vladimir Voevodsky wrote:

> Hello,
>
> I am trying to find some information about non-unital monads (gadgets 
> with \mu but without \eta).
>
> In particular I am interested in the following two questions:
>
> 1. Given a non-unital monad can it have two different "unitality"
>    structures?
>
> 2. Is there a concept of a free non-unital monad? For example, I can
>    think of the "free" non-unital monad generated by the functor X |->
>    X^2 on sets as the monad that sends a set X into the set of
>    "homogeneous" expressions made with one binary operation s such that
>    there is s(x1,x2) and s(s(x1,x2),s(x3,x4)) but no x1 itself and no
>    s(x1,s(x2,x3)).  But what is the universal characterization of it?
>
> Thanks!
> Vladimir.
>
>

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

Re: non-unital monads

[Marek Zawadowski]

Hi,

Monads on a category C are monoids in the strict monoidal category End(C)
of endofunctors on C and natural transformations. We have the
forgetful functors

Mon( End(C) ) ---> nuMon ( End(C) ) ---> End(C)

forgetting from monoids to non-unital monoids and then to endofunctors.
These functors might have left adjoints. This answers the second question
concerning universal properties.

If C is Set, and we restrict objects in End(Set) to functors with rank
at most m
(for some cardinal m) , then it was shown in

M. Barr, Coequalizers and Free Triples, Math. Z. 116, pp. 307-322 (1970)

that the left adjoint to the composition of the above functors exists
giving rise
to a monad for monads on End(Set) with rank at most m. There are also
refinements of this result saying that the free monads on polynomial,
analytic, and semi-analytic functors are polynomial, analytic, and
semi-analytic, respectively. The first occurs in the unpunlished book
of Joachim Kock and the last two in the papers I wrote recently with
S. Szawiel

Theories of analytic monads. Math. Str. in Comp. Sci. pp. 1-33, (2014)

Monads of regular theories. Appl. Cat. Struct. pp. 9331-9364, (2013)

As Tom and Peter remarked, if a monoid has a left unit and a right unit,
they need to be equal.

Best regards,
Marek

Cytowanie Vladimir Voevodsky <vladimir@ias.edu>:

> Hello,
>
> I am trying to find some information about non-unital monads
> (gadgets with \mu but without \eta).
>
> In particular I am interested in the following two questions:
>
> 1. Given a non-unital monad can it have two different "unitality" structures?
>
> 2. Is there a concept of a free non-unital monad? For example, I can think of
> the "free" non-unital monad generated by the functor X |-> X^2 on
> sets as the monad
> that sends a set X into the set of "homogeneous" expressions made
> with one binary operation
> s such that there is s(x1,x2) and s(s(x1,x2),s(x3,x4)) but no x1
> itself and no s(x1,s(x2,x3)).
> But what is the universal characterization of it?
>
> Thanks!
> Vladimir.
>
>




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

Re: non-unital monads

[Tarmo Uustalu]

Dear Vladimir,

1. The answer to the first question is no, there can only be one unit
for a given underlying functor and multiplication.

(But for a given underlying functor and unit, there can of course be
multiple multiplications.)

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


On Sat, 18 Oct 2014, Vladimir Voevodsky wrote:

> Hello,
>
> I am trying to find some information about non-unital monads (gadgets
> with \mu but without \eta).
>
> In particular I am interested in the following two questions:
>
> 1. Given a non-unital monad can it have two different "unitality"
> structures?
>
> 2. Is there a concept of a free non-unital monad? For example, I can
> think of the "free" non-unital monad generated by the functor X |-> X^2
> on sets as the monad that sends a set X into the set of "homogeneous"
> expressions made with one binary operation s such that there is s(x1,x2)
> and s(s(x1,x2),s(x3,x4)) but no x1 itself and no s(x1,s(x2,x3)). But
> what is the universal characterization of it?
>
> Thanks!
> Vladimir.
>

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

Re: non-unital monads

[Richard Garner]

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/ ]

Re: non-unital monads

[Tom Leinster]

Dear Vladimir,

> 1. Given a non-unital monad can it have two different "unitality" structures?

No.  Write T for the endofunctor, m for the multiplication, and e and e'
for the two units.  Then

    e = m(e'T)e = m(Te)e' = e',

the first and third equalities by the monad axioms, and the second by
naturality of e'.

Best wishes,
Tom





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

Re: non-unital monads

[Vladimir Voevodsky]

Many thanks to everybody who answered my questions!

I understand the picture with unitality being a property and not a structure now.

As for the universal characterization I have in mind something like this:

1. For a functor F on a category with finite coproducts such that for each X0 there exists the initial
algebra I(F\coprod X0) of the functor X |-> F(X)\coprd X0, these initial algebras are functorial 
and in fact X |-> I(F\coprod X) has an obvious monad structure and this monad is the free monad
generated by F. 

This construction is what connects free monads with free algebras.

2. What can one do for a non-unital monad? It seems to me at the moment that the functor

X |-> I(F\coprod F(X)) 

may be the free non-unital monad generated by F. 

Vladimir.




> On Oct 20, 2014, at 5:47 PM, Marek Zawadowski <zawado@mimuw.edu.pl> wrote:
> 
> Hi,
> 
> Monads on a category C are monoids in the strict monoidal category End(C)
> of endofunctors on C and natural transformations. We have the forgetful functors
> 
> Mon( End(C) ) ---> nuMon ( End(C) ) ---> End(C)
> 
> forgetting from monoids to non-unital monoids and then to endofunctors.
> These functors might have left adjoints. This answers the second question
> concerning universal properties.
> 
> If C is Set, and we restrict objects in End(Set) to functors with rank at most m
> (for some cardinal m) , then it was shown in
> 
> M. Barr, Coequalizers and Free Triples, Math. Z. 116, pp. 307-322 (1970)
> 
> that the left adjoint to the composition of the above functors exists giving rise
> to a monad for monads on End(Set) with rank at most m. There are also
> refinements of this result saying that the free monads on polynomial,
> analytic, and semi-analytic functors are polynomial, analytic, and
> semi-analytic, respectively. The first occurs in the unpunlished book
> of Joachim Kock and the last two in the papers I wrote recently with S. Szawiel
> 
> Theories of analytic monads. Math. Str. in Comp. Sci. pp. 1-33, (2014)
> 
> Monads of regular theories. Appl. Cat. Struct. pp. 9331-9364, (2013)
> 
> As Tom and Peter remarked, if a monoid has a left unit and a right unit,
> they need to be equal.
> 
> Best regards,
> Marek
> 

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