monad: (k-Set \downarrow -): Set -->Set

monad: (k-Set \downarrow -): Set -->Set

[David Spivak]

Dear Categorists,

Does anyone know a name for the monad described below and/or whether
it has been studied?

Let k-Set denote the category of k-small sets (for some small regular
cardinal k).  For a set S, we denote by

T(S)=(k-Set \downarrow {S})

the set whose elements are pairs (K,f), where K is a k-small set and
f:K-->S is a function.  This construction is functorial in S.  I
claim that the endo-functor T: Set -->Set is a monad.  The identity
transformation S-->T(S) is given by "singleton set" and the
multiplication transformation TT(S)-->T(S) is given by Grothendieck
construction.

(There is a similar monad on Cat, where we replace k-Set with k-Cat.)

Does this monad T have a name?  Has it been studied?

Thank you,
David


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

Re: monad: (k-Set \downarrow -): Set -->Set

[Anders Kock]

Mark Weber says rightly about David Spivak's "monad"
(and it applies to its natural extension to the "cocompletion under k-small coproducts-monad" on Cat as well):

"One could fix a skeleton of Set_k, and for k = cardinality of natural
numbers this works fine, and the monad on Set you get is the monoid monad.
However for bigger k you're likely to run into problems when trying to do
this sort of thing."

Yes, you do run into problems; however, they can be solved, as I showed in my Chicago thesis 1967. Namely, take for Set_k the (small) full subcategory of Sets whose objects are the  ORDINAL numbers of cardinality less than the regular cardinal k. Ordinal sum formation then allows you to get the multiplication of the monad to be strictly associative.

Similarly for the "similar monad" mentioned by David
(based on the Grothendieck-construction of categories) - this monad is also in my thesis, and Lawvere reports on it in his "Ordinal sums and equational doctrines", (Seminar on Triples, SLN 80 (1969), see p.152-153. ).

However, these cunning tricks to get strict associativity were in the 1960s forced on us, for historical reasons:  at that time we did not have the notion of 2-dimensional category well enough established to see these cocompletion "monads" in their true 2-dimensional nature.

The "similar monads", based on a suitable Cat_k, are also reported on in loc.cit.; and Cat_k could be replaced by any small category Cat_0 of categories which is stable under the Grothendieck construction, like the category of k-small posets, or of k-small directed categories. (I called these monads  "prelimit monads"; Lawvere calls them Dir_Cat_0. They also appear in Guitart's 1974-article, as referenced in my previous posting.)

Anders Kock




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

Re: monad: (k-Set \downarrow -): Set -->Set

[Richard Garner]

> In the case where k=omega, T is the well-known finite multiset monad,
> which associates to each S the free commutative monoid generated by S
> (whose elements are also known as finite multisets in S).
>
> For other k, I would call this the "monad of multisets of size less
> than k". I think this works for any infinite small cardinal, not just
> regular ones.

You really do need the regularity. Otherwise removing
brackets from a k-small multiset of k-small multisets might
yield something bigger than a k-small multiset, and then one
cannot define a multiplication for the monad.

Richard


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

Re: monad: (k-Set \downarrow -): Set -->Set

[Mark.Weber]

Peter Johnstone is right -- the monad David described doesn't exist, thus
neither does the monad morphism I described in my other post (... sorry!).
Perhaps the fibrations monad is still of interest.

One could fix a skeleton of Set_k, and for k = cardinality of natural
numbers this works fine, and the monad on Set you get is the monoid monad.
However for bigger k you're likely to run into problems when trying to do
this sort of thing.

However it isn't true that the monad

>> (... on Cat, where we replace k-Set with k-Cat.)

is the k-coproduct completion monad -- you need to keep k-Set but work in
Cat and take lax slices, ie take the monad on Cat which has underlying
endofunctor

X |-> k-Set // X

(where // means "lax slice") to get the k-coproduct completion monad.

Mark Weber



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

Re: monad: (k-Set \downarrow -): Set -->Set

[Anders Kock]

As Peter Johnstone also emphasized in his reply, the construction which  
David Spivak describes,
namely "T(S)=(k-Set \downarrow {S})",  is really a part of a well known 
"monad" on the category of categories: if S is any category, T(S) is the 
free cocompletion of S under k-small coproducts. It is only a monad up 
to canonical isomorphisms, because coproducts are not in general 
strictly associative. This cocompletion "monad"  under coproducts has 
been widely studied under the name "Fam" (because T(S) is the category 
of k-small Families of objects in S). It is an example of a KZ monad.

However,  replacing k-Set by k-Cat provides a monad on Cat which is not 
KZ; David observes:

"(There is a similar monad on Cat, where we replace k-Set with k-Cat.)"

and Peter's reply to this:

"This is correct, and it's well-known: it is the monad which freely adjoins
k-small coproducts to a category. "

does not apply here (it slipped into the wrong place of his reply): 
rather, David's "similar monad" is trying to provide free cocompletion 
under colimits indexed by k-small categories, but does not, until you 
make a category-of-fractions construction on its values. My University 
of Chicago thesis (1967) described this way of making free cocompletions.

This "similar monad" (before doing the fractions-part) has  been studied 
by Guitart, he calls it this monad DIAG. Reference: Guitart, René, 
Remarques sur les machines et les structures. Cahiers de Topologie et 
Géométrie Différentielle Catégoriques, 15 no. 2 (1974), p. 113-144 
(available electronically in NUMDAM).

Anders Kock






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

Re: monad: (k-Set \downarrow -): Set -->Set

[Peter Selinger]

David Spivak wrote:
>
> Dear Categorists,
>
> Does anyone know a name for the monad described below and/or whether
> it has been studied?
>
> Let k-Set denote the category of k-small sets (for some small regular
> cardinal k).  For a set S, we denote by
>
> T(S)=(k-Set \downarrow {S})
>
> the set whose elements are pairs (K,f), where K is a k-small set and
> f:K-->S is a function.  This construction is functorial in S.  I
> claim that the endo-functor T: Set -->Set is a monad.  The identity
> transformation S-->T(S) is given by "singleton set" and the
> multiplication transformation TT(S)-->T(S) is given by Grothendieck
> construction.
>
> (There is a similar monad on Cat, where we replace k-Set with k-Cat.)
>
> Does this monad T have a name?  Has it been studied?

I assume you mean to take such pairs (K,f) up to isomorphism, or else,
as Peter Johnstone has already pointed out, your construction will not
be well-defined. For instance, even the finite sets may form a proper
class, depending on your underlying set theory.

In the case where k=omega, T is the well-known finite multiset monad,
which associates to each S the free commutative monoid generated by S
(whose elements are also known as finite multisets in S).

For other k, I would call this the "monad of multisets of size less
than k". I think this works for any infinite small cardinal, not just
regular ones.

-- Peter



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

Re: monad: (k-Set \downarrow -): Set -->Set

[Mark.Weber]

Dear David

I'm not sure whether your specific construction has been looked at or
named, but it is a "submonad" of something very well known.

Let's work with 2 universes of sets, your "Set" being the topos of small
sets, and SET being a topos of sets large enough to include {arrows of
Set} as an object. For those not so comfortable doing this, fix two
regular cardinals far enough part, read "Set" as "the category of sets of
cardinality less than the smaller cardinal", and "SET" as "the category of
sets of cardinality less than the bigger one", and far enough apart means
Set is a category internal to SET.

Now the 2-category CAT (of category objects in SET) contains Set as an
object so one may form the slice 2-category

CAT/Set

in the strictest sense (1-cells being triangles commuting on the nose).
The big brother of your monad is a 2-monad on this 2-category. The
endofunctor part does the following:

S:A-->Set   |-->  Set \downarrow S --> Set

This is the underlying monad of what could be called the "fibration"
2-monad. That is applying to a functor produces the free split fibration
on what you started with. This construction works at the following
generality: replace CAT by any 2-category with comma objects and Set by
any object therein, and the first paper to see fibrations as algebras of a
monad in this way was

R. Street "Fibrations and yoneda's lemma in a 2-category" SLNM 420 1974

The relation between your monad and this one is that there's a canonical
inclusion

Set --> CAT/Set

which regards any Set S as a functor S:1-->Set, and this functor is the
1-cell data for a monad morphism (in the sense of Street: "Formal theory
of monads") from your monad to the monad I described.

With best regards

Mark Weber

> Dear Categorists,
>
> Does anyone know a name for the monad described below and/or whether
> it has been studied?
>
> Let k-Set denote the category of k-small sets (for some small regular
> cardinal k).  For a set S, we denote by
>
> T(S)=(k-Set \downarrow {S})
>
> the set whose elements are pairs (K,f), where K is a k-small set and
> f:K-->S is a function.  This construction is functorial in S.  I
> claim that the endo-functor T: Set -->Set is a monad.  The identity
> transformation S-->T(S) is given by "singleton set" and the
> multiplication transformation TT(S)-->T(S) is given by Grothendieck
> construction.
>
> (There is a similar monad on Cat, where we replace k-Set with k-Cat.)
>
> Does this monad T have a name?  Has it been studied?
>
> Thank you,
> David




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

Re: monad: (k-Set \downarrow -): Set -->Set

[Prof. Peter Johnstone]

On Fri, 19 Jun 2009, David Spivak wrote:

> Dear Categorists,
>
> Does anyone know a name for the monad described below and/or whether
> it has been studied?
>
> Let k-Set denote the category of k-small sets (for some small regular
> cardinal k).  For a set S, we denote by
>
> T(S)=(k-Set \downarrow {S})
>
> the set whose elements are pairs (K,f), where K is a k-small set and
> f:K-->S is a function.  This construction is functorial in S.  I
> claim that the endo-functor T: Set -->Set is a monad.  The identity
> transformation S-->T(S) is given by "singleton set" and the
> multiplication transformation TT(S)-->T(S) is given by Grothendieck
> construction.
>
I don't think this construction works at the level of sets rather than
categories. The problem is that k-Set is a category, not a set, so T(S)
also has a category structure, and you can't simply "forget" this. If
you do, then you have the problem "*which* singleton set?" for the
unit (i.e., which singleton set do you choose as the domain of the
functions 1 --> S which you identify with elements of S?), and
whichever choice you make you are going to run into problems verifying the
monad identities.

> (There is a similar monad on Cat, where we replace k-Set with k-Cat.)
>
This is correct, and it's well-known: it is the monad which freely adjoins
k-small coproducts to a category.

Peter Johnstone


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