Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 10, 2014

Describing PROPs Using Generators and Relations

Posted by John Baez

Here’s another post asking for a reference to stuff that should be standard. (The last ones succeeded wonderfully, so thanks!)

I should be able to say

CC is the symmetric monoidal category with the following presentation: it’s generated by objects xx and yy and morphisms L:xyyL: x \otimes y \to y and R:yxyR: y \otimes x \to y, with the relation

(L1)(1R)α x,y,x=(1R)(L1)(L \otimes 1)(1 \otimes R)\alpha_{x,y,x} = (1 \otimes R)(L \otimes 1)

Here α\alpha is the associator. Don’t worry about the specific example: I’m just talking about a presentation of a symmetric monoidal category using generators and relations.

Right now Jason Erbele and I have proved that a certain symmetric monoidal category has a certain presentation. I defined what this meant myself. But this has got to be standard, right?

So whom do we cite?

You are likely to mention PROPs, and that’s okay if they get the job done. But I don’t actually know a reference on describing PROPs by generators and relations. Furthermore, our actual example is not a strict symmetric monoidal category. It’s equivalent to one, of course, but it would be nice to have a concept of `presentation’ that specified the symmetric monoidal category only up to equivalence, not isomorphism. In other words, this is a ultimately a 2-categorical concept, not a 1-categorical one.

If it weren’t for this, we could use the fact that PROPs are models of an algebraic theory. But our paper is actually about control theory—a branch of engineering—so I’d rather avoid showing off, if possible.

Posted at July 10, 2014 11:34 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2752

9 Comments & 0 Trackbacks

Re: Describing PROPs Using Generators and Relations

Well, (non-strict) symmetric monoidal categories are the (strict) algebras for a 2-monad. So you could use the standard notion of “generators and relations” for algebras over a monad, i.e. a coequalizer of maps between free algebras. That would specify it up to isomorphism, though.

Your example suggests that maybe you’re thinking instead of a codescent object of maps between free algebras, where you would give generating objects, generating morphisms, and relations on the morphisms. Codescent objects (unlike coequalizers) are flexible colimits, so there the strict colimit is equivalent to the bicategorical one, and the latter is specified only up to isomorphism.

Posted by: Mike Shulman on July 10, 2014 6:20 PM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

My thoughts were the same as those in Mike’s first paragraph. I guess I’d be a little bit surprised if anyone had written specifically about generators and relations for PROPs.

As regards what to cite, maybe Blackwell, Kelly and Power’s 1989 paper “Two-dimensional monad theory”. It’s a time-honoured tradition to cite that paper whenever saying anything whatsoever about 2-monads.

Posted by: Tom Leinster on July 11, 2014 10:02 PM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

You guys are a bit too smart; you’d have me derive the necessary results for PROPs myself, starting from some more general theory. I admit to some attraction to doing this: we’d then have the first paper on control theory that used 2-monads. And if I need to do it, I will.

But there’s a humble tradition of citizens using PROPs for all sorts of practical chores. These people sometimes describe PROPs using generators and relations. It is, after all, one of the main ways to describe PROPs! It’s just like how in practice you often give an algebraic theory by giving a sketch.

Here’s an example:

You’ll see a bunch of definitions like

Definition 2. The PROP for commutative monoids is freely generated by morphisms i:1xi : 1 \to x, m:xxxm : x \otimes x \to x obeying equations…

and leading up to ones that are much more novel and interesting, like the PROP for interacting Hopf algebras. They know plenty of category theory—they use Steve Lack’s work on distributive laws for PROPs, for example. And they act like everyone knows what it means to specify a PROP by generators and relations. So I’m wondering who, if anyone, has discussed this.

Maybe everyone just thinks its too obvious. And if you think of PROPs as algebraic structures akin to groups and rings, it sort of is. But when you drift into thinking of them as ‘2-algebraic’, specified up to equivalence rather than isomorphism, it seems worth at least a page of discussion somewhere.

Mike wrote:

Codescent objects (unlike coequalizers) are flexible colimits, so there the strict colimit is equivalent to the bicategorical one, and the latter is specified only up to isomorphism.

Did you mean only up to equivalence?

Posted by: John Baez on July 12, 2014 7:47 AM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

Did you mean only up to equivalence?

Yes, sorry.

And they act like everyone knows what it means to specify a PROP by generators and relations.

Well, then, it sounds like they know the answer. Maybe you should ask them! (-: You could also ask (or try to guess from the paper — I haven’t looked at it) whether they ever think of PROPs as “2-algebraic”, or only “1-algebraic”.

Posted by: Mike Shulman on July 12, 2014 8:33 PM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

It’s not that I think it’s “too obvious”, or even that I know 2-monad theory very well (I don’t). It’s simply that I don’t know a direct reference for generators and relations of PROPs. If I did, then of course I wouldn’t have been shy about mentioning it. The 2-monad reference was the best I could do.

Come to think of it, I don’t know a reference for plain old categories presented by generators and relations. One often sees on-the-fly definitions such as:

Let C\mathbf{C} be the category freely generated by objects xx and yy and morphisms f:xyf: x \to y and g:yxg: y \to x subject to ….

And if I had to justify the meaning of such definitions (e.g. prove that such a category actually existed), I wouldn’t know what to do except reach for some 2-monad theory.

Of course, in the case of categories, it would be easier to do everything by hand than in the case of PROPs. But as I understand it, being able to do it by hand isn’t the issue — you simply want a reference.

Posted by: Tom Leinster on July 12, 2014 11:35 PM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

Maybe I’m not really understanding the problem here. Based on what you wrote, it seems you’ve got a symmetric monoidal category, and a proof that it’s symmetric monoidally equivalent to the free symmetric monoidal category on objects xx and yy and morphisms LL and RR, modulo an equation. Given this, I would say it’s perfectly reasonable for you to say that your category ‘has a presentation’. I wouldn’t see much need for you to cite anything in particular except for some category theory textbooks that explain what a symmetric monoidal category is.

Posted by: Jamie Vicary on July 12, 2014 10:00 PM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

I wonder why it seems to be so hard for mathematicians (myself apparently included) to understand and respond to a pure reference-request question. I’ve asked a few of them myself lately, and they always seem to provoke the kind of response you got from us — “here’s how you could do that very easily”, as if you’d asked “how can I do this?” — rather than an answer to the actual question “who can I cite that has already done this?”

Posted by: Mike Shulman on July 13, 2014 1:08 AM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

Perhaps the thing to do is arXiv a one-page paper on the subject and cite that?

Posted by: Jesse C. McKeown on July 13, 2014 3:40 AM | Permalink | Reply to this

Re: Describing PROPs Using Generators and Relations

For me it’s hard to give that kind of answer because in fact I don’t know the literature all that well, and it’s usually easier for me to figure it out rather than look it up or head down to a library.

Posted by: Todd Trimble on July 13, 2014 12:38 PM | Permalink | Reply to this

Post a New Comment