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/ ]
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/ ]
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/ ]
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/ ]
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/ ]
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/ ]
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/ ]
participants (6)
-
Marek Zawadowski -
Peter Johnstone -
Richard Garner -
Tarmo Uustalu -
Tom Leinster -
Vladimir Voevodsky