On Fri, 30 Jul 2010, Sergey Goncharov wrote:
Sorry, the previous posting was nonsense -- a bisemilattice is the same thing as a semilattice, by the Eckmann-Hilton argument. However, if you leave out the zero, and consider the "set of nonempty subsets" monad, this time on the category of sets of cardinality 2^n - 1 for some n, you do get a counterexample. This looks fine! But I guess, Eckmann-Hilton argument does not apply to your
On 07/29/2010 03:24 PM, Prof. Peter Johnstone wrote: previous example because it presupposes that the monoidal structures share the unit, which was not the case there, was it?
Yes, it was: the fact that the unit for each semilattice structure is a homomorphism for the other forces them to be the same. Peter Johnstone P.S. -- You can enlarge the base category to contain all finite sets of odd cardinality (so that, for example, it's cartesian closed). The free bi-(semilattice-without-unit) on three generators has 20 elements. [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
On Fri, 30 Jul 2010, Prof. Peter Johnstone wrote:
On Fri, 30 Jul 2010, Sergey Goncharov wrote:
This looks fine! But I guess, Eckmann-Hilton argument does not apply to your previous example because it presupposes that the monoidal structures share the unit, which was not the case there, was it?
Yes, it was: the fact that the unit for each semilattice structure is a homomorphism for the other forces them to be the same.
In any case, it doesn't matter: the Eckmann-Hilton argument *doesn't* presuppose that the monoid structures share the unit. Here are the weakest hypotheses I know for the elementary Eckmann-Hilton argument: Let A be a set. Let . be a binary operation on A with two-sided unit 1. Let * be a binary operation on A with two-sided unit e. Suppose that (a * b) . (a' * b') = (a . a') * (b . b') for all a, b, a', b' in A. Then . = *, 1 = e, and (A, ., 1) is a commutative monoid. So equality of the units and associativity, as well as the more familiar stuff, come for free. (I bet you can weaken "two-sided", too.) Tom [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Looking at the two ways of evaluating (say with . vertically and * horizontally) 1 e e 1 is what gives 1=e but it seems to need two sided units. Ronnie Tom Leinster wrote:
On Fri, 30 Jul 2010, Prof. Peter Johnstone wrote:
On Fri, 30 Jul 2010, Sergey Goncharov wrote:
This looks fine! But I guess, Eckmann-Hilton argument does not apply to your previous example because it presupposes that the monoidal structures share the unit, which was not the case there, was it?
Yes, it was: the fact that the unit for each semilattice structure is a homomorphism for the other forces them to be the same.
In any case, it doesn't matter: the Eckmann-Hilton argument *doesn't* presuppose that the monoid structures share the unit.
Here are the weakest hypotheses I know for the elementary Eckmann-Hilton argument:
Let A be a set. Let . be a binary operation on A with two-sided unit 1. Let * be a binary operation on A with two-sided unit e. Suppose that
(a * b) . (a' * b') = (a . a') * (b . b')
for all a, b, a', b' in A. Then . = *, 1 = e, and (A, ., 1) is a commutative monoid.
So equality of the units and associativity, as well as the more familiar stuff, come for free. (I bet you can weaken "two-sided", too.)
Tom
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
There is another possibly relevant area. It used to be standard (e.g. Huppert, Endliche Gruppen) that the only tensor product of groups was the usual tensor product of their abelianisations. This is because if b:G \times G \to H is a bimorphism then by expanding b(gg',hh') in two ways, and applying cancellation, you get a commutativity condition. However with Jean-Louis Loday we realised, as others had before us, that another interesting condition is for b to be a biderivation, since this is one of the rules satisfied by the commutator map [ , ] : G \times G \to G. The universal object for biderivations is then the nonabelian tensor square G \otimes G. This idea applies to other areas such as Lie algebras. A bibliography of 100 items is on www.bangor.ac.uk/r.brown/nonabtens.html Any possibility for monads?? This may be wild, but on the other hand........ On another tack, my memory is, and this puzzled me at first, that the paper Loday, Jean-Louis <http://0-ams.mpim-bonn.mpg.de.unicat.bangor.ac.uk/mathscinet/search/publications.html?pg1=IID&s1=115225> $K$-théorie algébrique et représentations de groupes. *(French)* /Ann. Sci. École Norm. Sup. (4)/ <http://0-ams.mpim-bonn.mpg.de.unicat.bangor.ac.uk/mathscinet/search/journaldoc.html?cn=Ann_Sci_Ecole_Norm_Sup_4> * 9 * (1976), no. 3, 309--377. uses a multiplication induced essentially by a structure of a monoid with a compatible structure of semigroup; so the Eckmann-Hilton argument does not apply! Ronnie Brown [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
I must admit to feeling slightly confused by both Peter's and André's examples. In both cases, the monads considered arise on a category other than the category of sets; and it is not clear to me what is meant by forming the tensor product of two such monads. In the case of finitary monads on Set, the meaning is clear, since a finitary monad corresponds to a Lawvere theory, a Lawvere theory is a special kind of small category with finite products, and we know how to form the tensor product of two categories with finite products (essentially because the doctrine of finite products is a pseudo-commutative one). This extends without problem to monads with rank on Set; and even to monads without rank on Set, so long as one recognises that the correlate notion of Lawvere theory will be a large one, so that the tensor product may not always exist. In the case of base categories other than Set, one would have to use a generalisation of the notion of Lawvere theory: such has been given by Nishizawa-Power (see also Lack-Power) but they require that the base category be locally presentable, which is not the case in the examples of André and Peter. My own take on what Peter's example is doing is the following. Given any finitary monad L on Sets, there is a corresponding Lawvere theory T, and so for any category C, we can consider the category Mod(T,C) of T-models in C: it's the category of finite-product preserving functors T -> C. There is a forgetful functor Mod(T,C)-->C given by evaluation at 1, and this will be monadic so long as it has a left adjoint; in which case we induce a monad L' on C. In particular, letting L be the finitary monad on Set whose algebras are sup-semilattices-without-a-unit, letting L * L be its tensor with itself, and letting C be the category of finite sets of odd cardinality, then Peter's example seems to show that: -- The induced monad L' on C exists but the induced monad (L * L)' does not. On the other hand, André's example raises a question which I find quite interesting. André describes two reflective subcategories of the ordered class of ordinal numbers, and then says that, their intersection being empty, the tensor of the corresponding idempotent monads cannot exist. I would be inclined to say that this shows that the coproduct of these monads does not exist, but this leads on to my question, which is: -- Given idempotent monads S, T on a category C for which we can speak of the tensor of S and T, is it always the case that S * T is isomorphic to S + T? Here is a test case. Power's 2000 paper "Enriched Lawvere theories" shows that, for a symmetric monoidal closed V which is lfp as a closed category, finitary V-monads are equivalent to enriched Lawvere theories, which are certain small V-categories with finite cotensors. Using the tensor of such V-categories, we can define a tensor of such monads. Consider in particular when V is [D^op, Set] for some small D, and let S and T be two idempotent strong (=V-enriched) monads on V. Now it should be possible to calculate S + T and S * T in terms of the corresponding Lawvere theories and to see if they coincide. I haven't tried this yet but it should be an interesting exercise. (The obvious thing to try first is to take S and T corresponding to sheaf subtoposes of [D^op, Set]. Then these monads, being product-preserving, are commutative, and so it's natural to think that S * T should be the monad corresponding to the intersection of these subtoposes. S + T, on the other hand, I'm inclined to think may be something bigger, and not necessarily cartesian.) Richard [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
On 1 Aug 2010, at 01:31, Richard Garner wrote:
I must admit to feeling slightly confused by both Peter's and André's examples. In both cases, the monads considered arise on a category other than the category of sets; and it is not clear to me what is meant by forming the tensor product of two such monads.
Here is a suggestion; I don't know how it relates to yours. Let S and T be monads on a category C. An "S,T-algebra" is a C-object X together with an S-algebra structure theta and T-algebra structure phi. An S,T-algebra morphism is a C- morphism that is homomorphic in both components. Let D be the category of S,T-algebras and homomorphisms, and U : D --> C the forgetful functor. Then U creates U-split coequalizers. If it has a left adjoint, we call the monad the "sum" of S and T. I think the sum of S and T, if it exists, has to be a coproduct in the category of monads, but haven't checked the details. Next suppose that C is cartesian, and S and T are strong. Now D will be a locally C-indexed (by this I mean [C^op,Set]-enriched) category. A morphism from (X,theta,phi) to (X',theta',phi') over Z is a C- morphism from Z x X to X' that's homomorphic in its second argument, with respect to both structures. If U has a (locally C-indexed) left adjoint, we get the "sum" of strong monads. Again, I think it's a coproduct in the category of strong monads. Next suppose C is cartesian closed and S and T are strong. For an S,T-algebra (X,theta,phi), the following are equivalent: (1) for all C-objects Y and Z, the two C-morphisms from SY x TZ x X^(YxZ) to X are equal (2) for every C-object Y, the two C-morphisms from SY x T(X^Y) to X are equal (2') for every C-object Z, the two C-morphisms from TZ x S(X^Z) to X are equal. When these hold, we say that (X,theta,phi) "commutes". (I'd like to express this without quantification over objects, but I can't see how.) We thus obtain a full (locally C-indexed) subcategory D' of D consisting of the commuting S,T-algebras and homomorphisms, and U' : D' --> C the restriction of U. Then U' creates U'-split coequalizers. If it has a left adjoint, we call the induced monad the "tensor" of S and T. Now a cocone of strong monads S -----> M <----- T is said to "commute" when for all C-objects X and Y the two C- morphisms from SX x TY to M(X x Y) are equal. I think a tensor of S and T will always give an initial commuting cocone, but haven't checked the details. Paul -- Paul Blain Levy School of Computer Science, University of Birmingham +44 (0)121 414 4792 http://www.cs.bham.ac.uk/~pbl [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear Paul, Thanks for your perspicuous message. Your general definition of tensor product really cuts to the heart of the matter, and agrees with the cases where I knew how to take tensors previously. Has it been written down somewhere? It seems very natural. It can actually be generalised further still. Let C be any symmetric monoidal category. In this setting, your last definition, which to me looks to be the key one, still makes sense: Now a cocone of strong monads
S -----> M <----- T
is said to "commute" when for all C-objects X and Y the two C-morphisms from SX * TY to M(X * Y) are equal.
In this generality we may _define_ the tensor product S * T to be the vertex of the universal commuting cospan, if such exists (and even if it doesn't, we still get a multicategory). To see that this agrees with your definition in the case where C is monoidal closed, we make a few observations. 1) For every X in C, there's a strong monad [X,X] such that strong monad morphisms S -> [X,X] correspond to S-algebra structures on X; it's the continuation monad A |-> (A -o X) -o X. 2) For every f : X -> Y, there's a monad {f,f} and a monomorphism of monads {f,f} --> [X,X] x [Y,Y] such that a strong monad morphism k: S --> [X,X] x [Y,Y] factors through {f,f} if and only if f is an S-algebra morphism with respect to the S-algebra structures on X and Y classified by k. Explicitly, we have {f,f}A given by the pullback of (A -o X) -o X and (A -o Y) -o Y over (A -o X) -o Y. 3) Given morphisms of monads f : S -> M, g : T -> M and j : M -> N, if jf commutes with jg and j is a monomorphism, then also f commutes with g. In other words, if the tensor product S * T exists, then the pair of maps S --> S * T <-- T are jointly strongly epic. 4) Taking (3) together with (2) we deduce that (S * T)-Alg will be a full subcategory of S-Alg x_C T-Alg. 5) It remains only to ascertain the objects which lie in this full subcategory: and these will be those (X, theta, phi) in S-Alg x_C T-Alg for which the corresponding pair of monad maps S --> [X,X] <-- T commute: which are precisely those satisfying your equivalent conditions (1), (2) and (2'). It's interesting to note the parallel between this setting and Dominique Bourn's notion of "intrinsic centrality". Using his terminology, we might say that monad maps S --> M <-- T "cooperate", rather than "commute". We would then call a monad morphism S -> M "central" if it cooperated with the identity on M: and call M "commutative" if the identity on M cooperated with itself. This last, rather fortunately, coincides with the established monad-theoretic terminology. This parallel provides a context for the following proposition about the tensor product of monads that I previously had no good explanation for: Prop: For a strong monad M, the following are equivalent: 1) M is commutative. 2) M is a commutative monoid with respect to the tensor product of monads. 3) M is a unitary magma with respect to the tensor product of monads. Finally, this also tells us how to construct the commutative reflection of a monad in an extremely compact manner: take the coequaliser of the two maps S --> S*S. More constructively: take the full subcategory D of S-Alg whose objects are algebras theta : SX -> X such that (X, theta, theta) commutes in your sense. If D -> C has a left adjoint, then the monad so generated is the commutative reflection of S. Richard [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Thank you Peter and André and all the participants of the discussion. It is indeed very helpful. Richard Garner wrote:
On the other hand, André's example raises a question which I find quite interesting. André describes two reflective subcategories of the ordered class of ordinal numbers, and then says that, their intersection being empty, the tensor of the corresponding idempotent monads cannot exist. I would be inclined to say that this shows that the coproduct of these monads does not exist I guess it applies both to the tensor and to the sum as well as to any other case where we need to form a span of monad morphism: S -> R <- T and which precisely can not be formed in this case.
It looks like there are two counterexamples, both of which are based on the construction of tricky underlying categories. But what about existence of the tensor over Sets? I guess this is still open. I tried to think about the tensor product of a continuation monad with itself as a possible counterexample, without any success though. Usually, continuation monad performs well when it comes to constructing counterexamples but it is difficult to see what the tensor product of it with itself is supposed to look like. Thanks again, Sergey. [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear Sergey, In the paper by Hyland, Levy, Power and myself, Combining algebraic effects with continuations, there is a proof that the tensor of the continuations monad R^(R^-) (|R| >= 2) with itself, or, indeed with any monad T with a constant (i.e. such that T(0) is not empty), is the trivial monad. It is not hard to see this directly, via large Lawvere theories. The large Lawvere theory L of the continuations monad has: L(X,Y) = Set(R^X,R^Y) and so the constants L(0,1) correspond to maps 1 --> R. Further, using two distinct constants, any two operations R^X --> R^Y can be coded up into one operation R^(X +1) --> R^Y and then recovered via the two constants. Given maps of large Lawvere theories L_T ---> M <----L such that the images of any two operations in L_T and L commute, as L_T has a constant all (the images of) constants in L are identified, as usual, but then so are all images of any two operations R^X --> R^Y (which will, for example, include all pairs of projections) and so M is trivial. A more general theorem is also proved in the paper which has as a consequence that the tensor of any monad with rank with the continuations monad exists. On Thu, Aug 5, 2010 at 9:06 PM, Sergey Goncharov <sergey@informatik.uni-bremen.de> wrote:
Thank you Peter and André and all the participants of the discussion. It is indeed very helpful.
Richard Garner wrote:
On the other hand, André's example raises a question which I find quite interesting. André describes two reflective subcategories of the ordered class of ordinal numbers, and then says that, their intersection being empty, the tensor of the corresponding idempotent monads cannot exist. I would be inclined to say that this shows that the coproduct of these monads does not exist
I guess it applies both to the tensor and to the sum as well as to any other case where we need to form a span of monad morphism: S -> R <- T and which precisely can not be formed in this case.
It looks like there are two counterexamples, both of which are based on the construction of tricky underlying categories. But what about existence of the tensor over Sets? I guess this is still open. I tried to think about the tensor product of a continuation monad with itself as a possible counterexample, without any success though. Usually, continuation monad performs well when it comes to constructing counterexamples but it is difficult to see what the tensor product of it with itself is supposed to look like.
Thanks again, Sergey.
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
On 3 Aug 2010, at 12:03, Paul Levy wrote:
On 3 Aug 2010, at 07:39, Richard Garner wrote:
Dear Paul,
Thanks for your perspicuous message.
And thanks for your more perspicuous reply! Your argument apparently applies to both coproduct and tensor of strong monads, and also to a free strong monad on a strong endofunctor. Each of these can be characterized both by a universal property and by a left adjoint to a forgetful functor from an algebra category. Nice.
Your general definition of tensor product really cuts to the heart of the matter, and agrees with the cases where I knew how to take tensors previously. Has it been written down somewhere? It seems very natural.
The universal property is alluded to in the TCS paper "Combining effects: sum and tensor" by Hyland, Plotkin and Power: page 4, paragraph beginning "There is also relevant unpublished work by Paul Levy". I gave up on it (i.e. the universal property) thinking it was too weak. Now you've shown me it wasn't.
I should also have said that the universal property - though not the notion of "commuting S,T-algebra" in the form I stated it - did appear in the paper Combining algebraic effects with continuations, by Hyland, me, Plotkin and Power. Sorry for forgetting this, it's been a while. Also, the proof of Theorem 4 (and also that of Prop. 3) is similar to the one you provided, although the result is somewhat different. Paul -- Paul Blain Levy School of Computer Science, University of Birmingham +44 (0)121 414 4792 http://www.cs.bham.ac.uk/~pbl [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (7)
-
Gordon Plotkin -
Paul Levy -
Prof. Peter Johnstone -
Richard Garner -
Ronnie Brown -
Sergey Goncharov -
Tom Leinster