Tensor of monads

Tensor of monads

[Sergey Goncharov]

Dear categorists,

in "Combining algebraic effects with continuations", by Hyland et al. the 
authors say carefully: "In general, the tensor product of two arbitrary 
monads seems not to exist.." without providing a counterexample though, 
presumably because they did not have any. Was there any progress 
reported on this issue since then? Or maybe someone can even make up a 
counterexample right on the nail?

Thanks,

-- 
Sergey Goncharov, Junior Researcher

DFKI Bremen                          Phone: +49-421-218-64276
Safe and Secure Cognitive Systems    Fax:   +49-421-218-9864276
Cartesium, Enrique-Schmidt-Str. 5    Email: Sergey.Goncharov@dfki.de
D-28359 Bremen                       Site:  www.dfki.de/sks/staff/sergey

-------------------------------------------------------------
Deutsches Forschungszentrum fuer Kuenstliche Intelligenz GmbH
Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern
Geschaeftsfuehrung:
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender)
Dr. Walter Olthoff
Vorsitzender des Aufsichtsrats:
Prof. Dr. h.c. Hans A. Aukes
Amtsgericht Kaiserslautern, HRB 2313
-------------------------------------------------------------



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

Re: Tensor of monads

[N.Bowler]

>in "Combining algebraic effects with continuations", by Hyland et al. the 
>authors say carefully: "In general, the tensor product of two arbitrary 
>monads seems not to exist.." without providing a counterexample though, 
>presumably because they did not have any. Was there any progress 
>reported on this issue since then? Or maybe someone can even make up a 
>counterexample right on the nail?
Martin asked me about this about a year ago, and at the time I came up with 
something I reckoned was a counterexample, though I recall that the details 
were pretty foul. Do you want me to try to reconstruct it?

Nathan


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

Re: Tensor of monads

[Prof. Peter Johnstone]

Here's a slightly artificial counterexample: let C be the category
of finite sets whose cardinality is a power of 2, and all functions
between them. The covariant power-set functor restricts to a
functor C --> C, and has a monad structure whose algebras are
semilattices. If the tensor product of this monad with itself
existed, its algebras would be bisemilattices, i.e. sets with two
semilattice structures which "commute with each other" in the
obvious sense. Free bisemilattices exist, but they don't
necessarily have cardinality a power of 2: by my calculation, the
free bisemilattice on two generators has seven elements. So the
free-bisemilattice functor doesn't exist as an endofunctor of C.

Peter Johnstone
-----------------------
On Wed, 28 Jul 2010, Sergey Goncharov wrote:

> Dear categorists,
>
> in "Combining algebraic e?ects with continuations", by Hyland et al. the
> authors say carefully: "In general, the tensor product of two arbitrary
> monads seems not to exist.." without providing a counterexample though,
> presumably because they did not have any. Was there any progress reported on
> this issue since then? Or maybe someone can even make up a counterexample
> right on the nail?
>
> Thanks,
>
> --
> Sergey Goncharov, Junior Researcher
>
> DFKI Bremen                          Phone: +49-421-218-64276
> Safe and Secure Cognitive Systems    Fax:   +49-421-218-9864276
> Cartesium, Enrique-Schmidt-Str. 5    Email: Sergey.Goncharov@dfki.de
> D-28359 Bremen                       Site:  www.dfki.de/sks/staff/sergey
>

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

Re: Tensor of monads

[Michael Barr]

There are examples in Ernie Manes's 1967 thesis.  Perhaps the simplest
(although it piggybacks on the non-existence of free complete boolean
algebras that had been know for only a few years at the time) is that the
tensor product of the complete sup semilattice triple with itself doesn't
exist.  The triple takes a set X to 2^X and can be interpreted also as the
complete inf semilattice triple.  On the other hand, I think Manes showed
that the tensor product of the beta triple with itself exists, but is one
of the two inconsistent triples, the one that fixes the empty set and
takes all non-empty sets to one point.  (The other inconsistent triple
takes all sets to one point.)

On Wed, 28 Jul 2010, Sergey Goncharov wrote:

> Dear categorists,
>
> in "Combining algebraic eects with continuations", by Hyland et al. the
> authors say carefully: "In general, the tensor product of two arbitrary
> monads seems not to exist.." without providing a counterexample though,
> presumably because they did not have any. Was there any progress reported on
> this issue since then? Or maybe someone can even make up a counterexample
> right on the nail?
>
> Thanks,
>
>


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

Re: Tensor of monads

[Prof. Peter Johnstone]

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.

Peter Johnstone

On Thu, 29 Jul 2010, Prof. Peter Johnstone wrote:

> Here's a slightly artificial counterexample: let C be the category
> of finite sets whose cardinality is a power of 2, and all functions
> between them. The covariant power-set functor restricts to a
> functor C --> C, and has a monad structure whose algebras are
> semilattices. If the tensor product of this monad with itself
> existed, its algebras would be bisemilattices, i.e. sets with two
> semilattice structures which "commute with each other" in the
> obvious sense. Free bisemilattices exist, but they don't
> necessarily have cardinality a power of 2: by my calculation, the
> free bisemilattice on two generators has seven elements. So the
> free-bisemilattice functor doesn't exist as an endofunctor of C.
>
> Peter Johnstone
> -----------------------
> On Wed, 28 Jul 2010, Sergey Goncharov wrote:
>
>> Dear categorists,
>>
>> in "Combining algebraic e?ects with continuations", by Hyland et al. the
>> authors say carefully: "In general, the tensor product of two arbitrary
>> monads seems not to exist.." without providing a counterexample though,
>> presumably because they did not have any. Was there any progress reported
>> on this issue since then? Or maybe someone can even make up a
>> counterexample right on the nail?
>>
>> Thanks,
>>
>> --
>> Sergey Goncharov, Junior Researcher
>>
>> DFKI Bremen                          Phone: +49-421-218-64276
>> Safe and Secure Cognitive Systems    Fax:   +49-421-218-9864276
>> Cartesium, Enrique-Schmidt-Str. 5    Email: Sergey.Goncharov@dfki.de
>> D-28359 Bremen                       Site:  www.dfki.de/sks/staff/sergey
>>

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

Re: Tensor of monads

[Sergey Goncharov]

On 07/29/2010 03:24 PM, Prof. Peter Johnstone 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 previous example because it presupposes that the monoidal
structures share the unit, which was not the case there, was it?

Thanks a lot,

-- 
Sergey Goncharov, Junior Researcher

DFKI Bremen                          Phone: +49-421-218-64276
Safe and Secure Cognitive Systems    Fax:   +49-421-218-9864276
Cartesium, Enrique-Schmidt-Str. 5    Email: Sergey.Goncharov@dfki.de
D-28359 Bremen                       Site:  www.dfki.de/sks/staff/sergey

-------------------------------------------------------------
Deutsches Forschungszentrum fuer Kuenstliche Intelligenz GmbH
Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern
Geschaeftsfuehrung:
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender)
Dr. Walter Olthoff
Vorsitzender des Aufsichtsrats:
Prof. Dr. h.c. Hans A. Aukes
Amtsgericht Kaiserslautern, HRB 2313
-------------------------------------------------------------



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

Tensor of monads

[Joyal, André]

Dear Sergey,

Here is a simple example, based on the ordered class ORD
of all ordinals numbers. The subclass LIMIT of all limit ordinals 
is reflexive in ORD. Let us denote by L the resulting reflection operator.
Similarly, the subclass SUCC of all successor ordinals is reflexive in ORD.
Let us denote by S the resulting reflection operator. 
The operators L and S cannot be bounded simultaneously
by a reflection operator (= monad) since the classes
LIMIT and SUCC have an empty intersection.

Best,
Andre



-------- Message d'origine--------
De: Sergey Goncharov [mailto:sergey@informatik.uni-bremen.de]
Date: mer. 28/07/2010 10:02
À: categories@mta.ca
Objet : categories: Tensor of monads
 
Dear categorists,

in "Combining algebraic e?ects with continuations", by Hyland et al. the 
authors say carefully: "In general, the tensor product of two arbitrary 
monads seems not to exist.." without providing a counterexample though, 
presumably because they did not have any. Was there any progress 
reported on this issue since then? Or maybe someone can even make up a 
counterexample right on the nail?

Thanks,

-- 
Sergey Goncharov, Junior Researcher

DFKI Bremen                          Phone: +49-421-218-64276
Safe and Secure Cognitive Systems    Fax:   +49-421-218-9864276
Cartesium, Enrique-Schmidt-Str. 5    Email: Sergey.Goncharov@dfki.de
D-28359 Bremen                       Site:  www.dfki.de/sks/staff/sergey


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

Re: Tensor of monads

[Prof. Peter Johnstone]

On Fri, 30 Jul 2010, Sergey Goncharov wrote:

> On 07/29/2010 03:24 PM, Prof. Peter Johnstone 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
> 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/ ]

Re: Tensor of monads

[Tom Leinster]

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

Re: Tensor of monads

[Richard Garner]

Isn't P * P isomorphic to P, by the Eckmann-Hilton argument?

On 29 July 2010 20:29, Michael Barr <barr@math.mcgill.ca> wrote:

> There are examples in Ernie Manes's 1967 thesis.  Perhaps the simplest
> (although it piggybacks on the non-existence of free complete boolean
> algebras that had been know for only a few years at the time) is that the
> tensor product of the complete sup semilattice triple with itself doesn't
> exist.  The triple takes a set X to 2^X and can be interpreted also as the
> complete inf semilattice triple.  On the other hand, I think Manes showed
> that the tensor product of the beta triple with itself exists, but is one
> of the two inconsistent triples, the one that fixes the empty set and
> takes all non-empty sets to one point.  (The other inconsistent triple
> takes all sets to one point.)
>
>
> On Wed, 28 Jul 2010, Sergey Goncharov wrote:
>
>  Dear categorists,
>>
>> in "Combining algebraic eects with continuations", by Hyland et al. the
>>
>> authors say carefully: "In general, the tensor product of two arbitrary
>> monads seems not to exist.." without providing a counterexample though,
>> presumably because they did not have any. Was there any progress reported
>> on
>> this issue since then? Or maybe someone can even make up a counterexample
>> right on the nail?
>>
>> Thanks,
>>

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

Re: Tensor of monads

[Michael Barr]

I am afraid you are right.  Here is what Manes says on the subject in
LNM80:

It is an open question whether or not
$\t\otimes\widetilde{\t}$ always exists. A constructive proof can be given
if both $\t$ and $\widetilde{\t}$ have a rank (in the sense of
\cite[2.2.6]{man}) by generalizing Freyd's proof in \cite{fre}.

What I had in mind involved two isomorphic, but distinct triples.  The one
coming from the underlying functor of complete sup semilattices (whose mu
would be union) and the other coming from complete inf semilattices (whose
mu is intersection).  The problem comes when you make those operations
commute with each other.  It would seem to me that would force complete
distributivity.  But completely distributive boolean algebras do give a
tripleable category.  Perhaps the moderator could throw some light on this
from his work on CCD lattices.

Could this still be unknown?  I guess it could.  It is not a topic that
has aroused a great deal of interest.

Sorry, Michael

On Sat, 31 Jul 2010, Richard Garner wrote:

> Isn't P * P isomorphic to P, by the Eckmann-Hilton argument?
>
> On 29 July 2010 20:29, Michael Barr <barr@math.mcgill.ca> wrote:
>
>> There are examples in Ernie Manes's 1967 thesis.  Perhaps the simplest
>> (although it piggybacks on the non-existence of free complete boolean
>> algebras that had been know for only a few years at the time) is that the
>> tensor product of the complete sup semilattice triple with itself doesn't
>> exist.  The triple takes a set X to 2^X and can be interpreted also as the
>> complete inf semilattice triple.  On the other hand, I think Manes showed
>> that the tensor product of the beta triple with itself exists, but is one
>> of the two inconsistent triples, the one that fixes the empty set and
>> takes all non-empty sets to one point.  (The other inconsistent triple
>> takes all sets to one point.)
>>
>>
>> On Wed, 28 Jul 2010, Sergey Goncharov wrote:
>>
>>  Dear categorists,
>>>
>>> in "Combining algebraic eects with continuations", by Hyland et al. the
>>>
>>> authors say carefully: "In general, the tensor product of two arbitrary
>>> monads seems not to exist.." without providing a counterexample though,
>>> presumably because they did not have any. Was there any progress reported
>>> on
>>> this issue since then? Or maybe someone can even make up a counterexample
>>> right on the nail?
>>>
>>> Thanks,
>>>
>>>


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

Eckmann-Hilton (Was: Tensor of monads)

[Toby Bartels]

Sergey Goncharov wrote in part:

>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?

Actually, the requirements for Eckmann-Hilton are surprsingly weak!

As long as you have two binary operations on a given set,
each with its own unit, where one is a homomorphism WRT the other,
then everything else (associativity, same unit, etc) follows.
See http://ncatlab.org/nlab/show/Eckmann-Hilton+argument for details.


--Toby


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

Re: Tensor of monads

[Richard Garner]

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

Re: Tensor of monads

[Richard Garner]

Further to my earlier question:

   -- 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?
>

I think I'm now happy that the answer is "no". Consider, as in my previous
message, a presheaf category [D^op, Set]. Let S and T be the idempotent
monads corresponding to two
Grothendieck topologies J and J' on [D^op, Set]. Then S + T is the monad
whose algebras are presheaves which are simultaneously J-sheaves and
J'-sheaves. On the other hand,
S * T has as algebras those presheaves X which are both J-sheaves and
J'-sheaves, but which satisfy an additional axiom (*). This axiom may be
expressed most expediently when D has finite products; so let us assume that
now. The condition says:

(*) Let f_i : U_i --> U be J-covering, and let g_k : V_k --> V be
J'-covering. Let ( x_ik \in X(U_i x V_k) ) be a compatible family for ( f_i
x g_k : U_i x V_j --> U x V ). Then the two natural ways of patching to an
element of X(U x V) agree.

These two ways of patching are as follows. For the first, note that since (
f_i x V_k | i \in I ) is J-covering for each k in K, we may patch to obtain
elements ( y_k \in X(U x V_k) | k \in K ). Then since ( U x g_k | k \in K )
is J'-covering, we may patch these to obtain an element z \in X(U x V). For
the second way of patching, we proceed entirely analogously, but this time
going via a family ( y'_i \in X(U_i x V) | i \in I).

Now (*) is a genuine extra condition which as far as I can see is not a
consequence of being both a J-sheaf and a J'-sheaf, so that S + T algebras
are not the same as S * T algebras. Note, however, that (*) _is_ a
consequence of being a (J n J')-sheaf, since ( f_i x g_j ) is covering in J
n J'. On the other hand, I'm not sure if (*) implies being a (J n J')-sheaf,
as I conjectured in my previous message; I don't have an Elephant to hand to
check.

Richard


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

Re: Tensor of monads

[Ronnie Brown]

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

Re: Tensor of monads

[Ronnie Brown]

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

Re: Tensor of monads

[Prof. Peter Johnstone]

Dear Richard,

Your (*) is not an additional condition. Being a sheaf for both J and J'
is equivalent to being a sheaf for their join (which I presume is what you
mean by J n J'). For a proof, see A4.5.16 in the Elephant.

Peter
---------------------------
On Sun, 1 Aug 2010, Richard Garner wrote:

> Further to my earlier question:
>
>   -- 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?
>>
>
> I think I'm now happy that the answer is "no". Consider, as in my previous
> message, a presheaf category [D^op, Set]. Let S and T be the idempotent
> monads corresponding to two
> Grothendieck topologies J and J' on [D^op, Set]. Then S + T is the monad
> whose algebras are presheaves which are simultaneously J-sheaves and
> J'-sheaves. On the other hand,
> S * T has as algebras those presheaves X which are both J-sheaves and
> J'-sheaves, but which satisfy an additional axiom (*). This axiom may be
> expressed most expediently when D has finite products; so let us assume that
> now. The condition says:
>
> (*) Let f_i : U_i --> U be J-covering, and let g_k : V_k --> V be
> J'-covering. Let ( x_ik \in X(U_i x V_k) ) be a compatible family for ( f_i
> x g_k : U_i x V_j --> U x V ). Then the two natural ways of patching to an
> element of X(U x V) agree.
>
> These two ways of patching are as follows. For the first, note that since (
> f_i x V_k | i \in I ) is J-covering for each k in K, we may patch to obtain
> elements ( y_k \in X(U x V_k) | k \in K ). Then since ( U x g_k | k \in K )
> is J'-covering, we may patch these to obtain an element z \in X(U x V). For
> the second way of patching, we proceed entirely analogously, but this time
> going via a family ( y'_i \in X(U_i x V) | i \in I).
>
> Now (*) is a genuine extra condition which as far as I can see is not a
> consequence of being both a J-sheaf and a J'-sheaf, so that S + T algebras
> are not the same as S * T algebras. Note, however, that (*) _is_ a
> consequence of being a (J n J')-sheaf, since ( f_i x g_j ) is covering in J
> n J'. On the other hand, I'm not sure if (*) implies being a (J n J')-sheaf,
> as I conjectured in my previous message; I don't have an Elephant to hand to
> check.
>
> Richard


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

Re: Tensor of monads

[Paul Levy]

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

Re: Tensor of monads

[Richard Garner]

[-- Attachment #1: Type: multipart/alternative, Size: 805 bytes --]

Re: Tensor of monads

[Richard Garner]

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

Re: Tensor of monads

[Paul Levy]

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.

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

Re: Tensor of monads

[Sergey Goncharov]

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

Re: Tensor of monads

[Gordon Plotkin]

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

Re: Tensor of monads

[Paul Levy]

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