RE: Set as a monoidal category

RE: Set as a monoidal category

[Stephen Lack]

Dear Peter,

There's a paper 

Algebraic categories with few monoidal biclosed structures or none

of Foltz, Lair, and Kelly which studies monoidal closed structures on various
categories, and shows that the cartesian closed one is the only possibility for Set.
More generally, it shows that for many categories we know well, the only possible
monoidal closed structures are the ones we know well.

But this depends heavily on the closedness. Without that, as you say, one can use
the cocartesian monoidal structure (the coproduct). 

Here's a further infinite family of monoidal structures on Set. Let A be any set. Then 
define the tensor product * by X*Y=AXY+X+Y.

Steve.

-----Original Message-----
From: cat-dist@mta.ca on behalf of Peter Selinger
Sent: Wed 8/13/2008 10:23 AM
To: Categories List
Subject: categories: Set as a monoidal category
 
Dear Categoreans,

I know three monoidal structures on the category of sets, all of them
symmetric. Two are the product and coproduct, and I'll leave it to
your imagination to figure out the third one.

My question is: are these the only three? Proofs, counterexamples, or
references appreciated.

Thanks, -- Peter

Re: Set as a monoidal category

[Peter Selinger]

Peter Selinger wrote yesterday:
>
> I know three monoidal structures on the category of sets, all of them
> symmetric. Two are the product and coproduct, and I'll leave it to
> your imagination to figure out the third one.
>
> My question is: are these the only three? Proofs, counterexamples, or
> references appreciated.

Several people took up the challenge, and provided me with interesting
monoidal structures on Set. I'll briefly summarize the correct
responses that I have received.

Let me begin by revealing the "third" monoidal structure that I had in
mind. It is

 X*Y = XY + X + Y.                                          (1)

It is easy to see that this satisfies the axioms if one rewrites it,
by an abuse of notation, as

 X*Y = (X+1)(Y+1) - 1.

Steve Lack pointed out that this is part of an infinite family of
monoidal structures, each defined by

 X*Y = XSY + X + Y,                                         (2)

where S is some fixed set. Of course, for S=0 this is just the
coproduct, and for S=1, this is the same as (1).

In the case |S| > 1, coherence is not totally obvious; in fact, there
are two possible natural isomorphisms (X*Y)*Z -> X*(Y*Z), deriving
from the two natural maps from S^2 to itself. Only one of them is
coherent. The coherence proof is somewhat simpler if one writes (2)
in the form I have given, rather than in Steve's original form
SXY + X + Y.

It is interesting to note that, contrary to appearances, Steve's
monoidal structure is not symmetric (not even braided) for |S| > 1.
There is only one candidate braiding map X*Y -> Y*X, and it fails to
satisfy the hexagon axiom.

Ralph Loader proposed another monoidal structure, not contained in
Steve's family: let X*Y be the set of non-empty finite sequences in
X+Y, with no two consecutive elements from the same component of X+Y.
Using the Kleene star, this can be written as

 X*Y = (XY)^* (X+XY) + (YX)^* (Y+YX).                       (3)

(Here, A^* is the list monad, i.e., the initial solution for
A^* = 1 + A A^*, also known as the Kleene star).

After Ralph saw Steve's family, he noticed that his construction can
also be generalized to an infinite family, by alternating list
elements with elements of S, namely:

 X*Y = (XSYS)^* (X+XSY) + (YSXS)^* (Y+YSX).                 (4)

The case S=0 is again the coproduct, and the case S=1 is of course
(3). Unlike Steve's family, these tensors appear to be symmetric for
all S. Also unlike Steve's family, the construction does not restrict
to the category of finite sets.

Jeff Egger contributed another symmetric monoidal structure, which he
calls "par", and which is defined by:

 X*Y = X   if Y=0
 X*Y = Y   if X=0                                           (5)
 X*Y = 1   if both X and Y are non-empty.

This can be uniquely extended to morphisms such that f*0 = f = 0*f.

It is perhaps interesting to note that an attempt to make Jeff's
construction into an infinite family, by replacing "1" by some pointed
set S, *almost* succeeds: the resulting operation is functorial, with
coherent associativity and unit isomorphism. The only problem is that
associativity fails to be a natural transformation. I mention it here
because it might make for a really neat exercise in a course.


In summary, we have two infinite families (2) and (4) (both including
coproduct), plus product and Jeff's "par" (5). I admit that I did not
expect so many non-trivial monoidal structures to exist on Set, and I
now expect that there are many more. A complete classification would
be interesting, but is perhaps too much to expect.

I will close with another challenge: consider only *symmetric*
monoidal structures on the category of *finite* sets. So far, we have
seen four such structures, namely product, coproduct, and the tensors
(1) and (5). Are these the only four?

-- Peter

P.S. monoidal *closed* structures, as mentioned in Steve's message,
are an entirely different ball game. The requirement that tensor is
left adjoint implies that it preserves colimits in each components; on
Set, everything is therefore determined by 1*1. The only possibility
is 1*1=1, which yields the usual cartesian-closed structure.

Re: Set as a monoidal category

[RONALD BROWN]

Dear Categoreans, 

It is standard practice to answer a different question! But I can't resist referring to 
R. Brown   ``Ten topologies for $X\times Y$'', {\em Quart. J.Math.}
(2) 14 (1963),  303-319.
and asking if one can modify these topologies or underlying sets by some process to work sensibly for the category of sets? (a compact subset of a discrete space is of course finite). Maybe it is not possible. 

Ronnie






----- Original Message ----
From: Peter Selinger <selinger@mathstat.dal.ca>
To: Categories List <categories@mta.ca>
Sent: Wednesday, 13 August, 2008 1:23:59 AM
Subject: categories: Set as a monoidal category

Dear Categoreans,

I know three monoidal structures on the category of sets, all of them
symmetric. Two are the product and coproduct, and I'll leave it to
your imagination to figure out the third one.

My question is: are these the only three? Proofs, counterexamples, or
references appreciated.

Thanks, -- Peter

Set as a monoidal category

[Peter Selinger]

Dear Categoreans,

I know three monoidal structures on the category of sets, all of them
symmetric. Two are the product and coproduct, and I'll leave it to
your imagination to figure out the third one.

My question is: are these the only three? Proofs, counterexamples, or
references appreciated.

Thanks, -- Peter