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.

May 15, 2008

Theorems Into Coffee III

Posted by John Baez

Okay… I was visiting George Washington University, takling to my friend Bill Schmitt about matroids and giving a practice version of my talk on the number 5 — but now I’m back and ready to offer more coffee for more theorems!

So, here are some more PROPs for you to ponder.

I’m afraid these blog entries don’t meet my standards for good exposition. I didn’t give a good explanation of PROPs. Instead, I was hoping some of you out there already know and love PROPs, and want to prove theorems about them. I guess I was right.

If you’ve never heard of PROPs, here’s the basic idea. A PROP consists of abstract ‘operations’ with multiple inputs and outputs. For each pair of natural numbers, it has a set hom(m,n)hom(m,n) consisting of abstract operations with nn inputs and mm outputs. We can compose these

:hom(m,n)×hom(n,)hom(m,) \circ : hom(m,n) \times hom(n,\ell) \to hom(m,\ell)

and also tensor them

:hom(m,n)×hom(p,q)hom(m+p,n+q) \otimes : hom(m,n) \times hom(p,q) \to hom(m+p, n+q)

and also permute the inputs and outputs to get new operations from old.

When we map a PROP to the category of sets, these abstract operations become actual operations — functions with a bunch of inputs and outputs! So, we wind up getting a set equipped with a bunch of operations satisfying a bunch of equations. We can use this trick to describe lots of algebraic gadgets. But the real power of PROPs becomes clear when we describe algebraic gadgets not just in the category of sets, but in other categories. For example, the same PROP that describes monoids in the category of sets describes associative algebras in the category of vector spaces!

The precise rules are most efficiently summarized as follows:

Definition: A PROP is a strict symmetric monoidal category XX with natural numbers as objects, for which the tensor product of objects nn and mm is n+mn + m. Given a symmetric monoidal category CC, an algebra of XX in CC is a symmetric monoidal functor F:XCF: X \to C, and a morphism of algebras in CC is a symmetric monoidal natural transformation between such symmetric monoidal functors. There is a category of algebras of XX in CC.

But the fun starts when we consider examples…

Suppose AA is some sort of algebraic gadget that makes sense in any symmetric monoidal category CC — for example, a monoid object, or a comonoid object, or a bimonoid object, or a Hopf object. (If C=VectC = Vect, these are called ‘algebras’, ‘coalgebras’, ‘bialgebras’ and ‘Hopf algebras’, respectively. But, they make sense more generally!)

Then, we say XX is the PROP for AA’s when for any symmetric monoidal category CC, the category of algebras of XX in CC is equivalent to the category of AA’s in CC.

We’ve looked at two examples already, both of the same general sort. For any commutative ring RR, there’s PROP called Mat(R)Mat(R) where hom(m,n)hom(m,n) is the set of n×mn \times m matrices with entries in RR, with composition and tensoring done as usual.

In Theorems for Coffee II, I challenged you to provide a proof that:

Theorem: Mat()Mat(\mathbb{Z}) is the PROP for bicommutative Hopf objects.

As of this instant — 5:29 pm GMT on Friday the 16th of May, 2008 — this challenge remains open.

But in fact, this Mat(R)Mat(R) idea works not just for commutative rings, but for commutative rigs! A rig is a ‘ring without negatives’ — just like a ring but possibly lacking additive inverses. The classic example is the natural numbers, \mathbb{N}. This is, in fact, the free rig on one generator.

Rigs are neglected in ordinary algebra texts, a deficiency that someday must be fixed. Why? First, a lot of stuff that’s true about rings is still true about rigs. Second, and much more importantly, any approach to algebra that doesn’t make room for the natural numbers is clearly defective: the natural numbers are a fundamental algebraic structure that must be reckoned with!

Puzzle: When Kronecker said something like “God made the …, all else is the work of man”, was he talking about the integers or the natural numbers?

(No coffee for this puzzle; just a fun little exercise in scholarship.)

So, in my original Theorems for Coffee challenge, I asked you to prove:

Theorem: Mat()Mat(\mathbb{N}) is the PROP for bicommutative bimonoids.

This one seems to have been solved by Samuel Mimram, though I still haven’t gotten around to carefully checking the proof and officially awarding the $15 coffee prize:

He calls a matrix TT of natural numbers a ‘multirelation’, since it’s like a relation where two items ii and jj can be related in more than one way — in T ijT_{i j} \in \mathbb{N} ways. I would be more likely to call it a ‘span of finite sets’. It’s interesting that he uses string diagrams to prove this result, since they bring in technical issues that might be a distraction. I love string diagrams, but for this particular theorem I hope there’s a more efficient proof that avoids them!

One can play this game for other commutative rigs. Here’s a weird little puzzle:

Puzzle: What sort of algebraic gadget is Mat()Mat(\mathbb{Q}) the PROP for?

Clearly it’s some sort of bicommutative Hopf object with extra bells and whistles, since the obvious ring homomorphism

\mathbb{Z} \to \mathbb{Q}

gives a symmetric monoidal functor

Mat()Mat()Mat(\mathbb{Z}) \to Mat(\mathbb{Q})

which lets us turn any algebra for Mat()Mat(\mathbb{Q}) into an algebra for Mat()Mat(\mathbb{Z}) — that is, a bicommutative Hopf object.

I think I know the answer to the above puzzle, but I don’t find it sufficiently thrilling to offer coffee for a proof. Perhaps I’m wrong — perhaps the answer really is thrilling! If so, please tell me why. Perhaps a really good answer will work uniformly, not just for \mathbb{Q}, but for every commutative rig.

Anyway, I prefer to consider the Boolean rig, also known as the rig of truth values:

B={0,1} B = \{0,1\}

with ‘or’ as addition and ‘and’ as multiplication. Mat(B)Mat(B) is equivalent to the category of finite sets and relations.

What is Mat(B)Mat(B) the PROP for? By the same sort of argument sketched above, the homomorphism B\mathbb{N} \to B means that Mat(B)Mat(B) is the PROP for bicommutative bimonoids with some extra bells and whistles. In Thm. 16 of his paper, Samuel Mimran shows:

Theorem: Mat(B)Mat(B) is the PROP for qualitative bicommutative bimonoids: that is, those for which comultiplication followed by multiplication AΔAAmA A \stackrel{\Delta}{\longrightarrow} A \otimes A \stackrel{m}{\longrightarrow} A is the identity.

Does anyone else working on bialgebras think about this ‘qualitative’ property? Frobenius algebras with this sort of property are called ‘strongly separable’. This could lead us into an interesting digression…

… but here’s today’s coffee problem, originally posed by Bill Schmitt. I think I know the answer, so I’m not offering coffee for the mere answer — though I urge people to guess it! As usual, I’m offering $15 in coffee for anyone who presents me with a sufficiently nice proof that their answer is correct. And, as usual, part of the game is that you must allow me to use this proof in possible future books or papers — with full credit given to you, of course!

Coffee Problem: Let XX be the sub-PROP of Mat(B)Mat(B) where a morphism fhom(m,n)f \in hom(m,n) is a partially defined function. What is XX the PROP for?

Perhaps a word of clarification will help. In Mat(B)Mat(B), a morphism f:mnf : m \to n is an n×mn \times m matrix of 0’s and 1’s. We can think of this as a relation between an mm-element set and an nn-element set. Among all these relations are certain special ones, the partially defined functions, where each element of the mm-element set is related to at most one element of the nn-element set. These are closed under composition, tensoring, and permutation of inputs and outputs. So, they form a sub-PROP XX.

Posted at May 15, 2008 7:56 PM UTC

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

39 Comments & 2 Trackbacks

Re: Theorems Into Coffee III

What’s your interest in matroids?

I’ve been thinking about them lots recently, but I don’t recall you mentioning them before.

Posted by: Allen K. on May 16, 2008 7:31 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

I’m just trying to learn about Bill Schmitt’s work on matroids. He graduated from MIT when I did, but did his thesis with Rota, working on Hopf algebras obtained from various structures defined on finite sets. (These structures are really ‘species’ in Joyal’s sense, and it was Bill who first taught me about species.)

For many types of structure, a structure on a finite set XX and a splitting X=Y+ZX = Y + Z determines a structure on YY and a structure on ZZ. This often serves to define the comultiplication in a Hopf algebra having these structures as basis. Typically this coproduct is cocommutative. However, for matroids, Schmitt and his pal Henry Crapo came up with an interesting variant on this idea which gives a noncocommutative Hopf algebra.

So, I was just learning about this and related stuff. I hadn’t known that matroids were invented by the topologist Whitney in his work on the 4-color theorem. There’s an interesting characterization of matroids that come from graphs, and a very interesting related characterization of those matroids that come from planar graphs.

Posted by: John Baez on May 16, 2008 8:26 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Apparently Mac Lane disliked matroids.

And Rota disliked the name, and “mounted a campaign to try to change the name to ‘geometry’, an abbreviation of ‘combinatorial geometry’.”

Posted by: David Corfield on May 17, 2008 10:20 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

The name ‘matroid’ is pretty lame, but I suspect it’s too late to change it. Instead of being a defective matrix-like entity, a matroid is a set equipped with a concept of when any subset counts as ‘independent’.

I don’t think ‘geometry’ is the right name for this notion — there are other different kinds of combinatorial geometry which don’t, I believe, fit into the matroid formalism. (If I’m wrong about that, I’d love to be corrected!)

Something like ‘set equipped with a notion of independence’ would be best — but in three syllables or less!

Posted by: John Baez on May 17, 2008 9:39 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Is there then a PROP for probabilistic functions, corresponding to row normalised matrices?

Posted by: David Corfield on May 16, 2008 9:42 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

A ‘row normalized matrix’ is a matrix whose entries are reals between 0 and 1, whose rows sum to 1? Also known as a right stochastic matrix?

To get a PROP, we need to check 1) the product of two such matrices (not necessarily square) is again such a matrix; 2) the tensor product of two such matrices is again such a matrix; 3) permuting the rows or columns of such a matrix again gives such a matrix.

I think these are all true. For 1) and 3), I have a conceptual reason for believing it and can also see it by mental computation. For 2), I have a conceptual reason for believing it but haven’t done the computation. Can someone verify 2)?

If we have a PROP, it’s then interesting to ask what it’s the PROP for!

Posted by: John Baez on May 17, 2008 12:25 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

Is forming the tensor product just to stick constituent matrices in as blocks in opposite corners? If so, the answer is obvious.

Posted by: David Corfield on May 17, 2008 12:34 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Oh, duh! You’re right.

I forgot that the abstract ‘tensor product’ in categories like Mat(R)Mat(R) and the one we’re discussing here is just the usual direct sum of matrices.

So, okay — that explains my trouble with this one.

So, yeah — we’ve got a PROP. Now what it’s the PROP for?

As you may have noticed, this whole series of puzzles is an attempt to expose strange new relations between generalized matrix mechanics and the traditional use of PROPs to describe algebraic gadgets. As usual, James Dolan got the ball rolling here.

Posted by: John Baez on May 17, 2008 9:29 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Hi,

I guess that X is the PROP for “erasable monoids” (M,µ,η,ε) where (M,µ,η) is a monoid and ε:M→I is an “erasure operator” satisfying εoµ=ε*ε and εoη=I. I think that a proof of this result can be made by “factorizing” the PRO(P) into two PRO(P)s: the PROP F of monoids and the PROP E of “erasable objects” that is objects (E,ε) with ε:E→I (without any axiom). I’ll try to sketch this informally. First remark that any partial function p:m→n can be factorized uniquely as foi where i:m→m’ is a “partial identity” (that is a surjective monotone partial function, with m’ the cardinal of the domain of p) and a (total) function f:m’→n. Now the same thing happens on the side of the PRO(P) X: any morphism π built up from µ,η,ε and γ (the symmetry) by composition, tensoring and identities can be factorized uniquely into φoι where ι is a morphism built up from ε by composition, tensoring and identities and φ is a morphism built up from µ, η and γ by composition, tensoring and identities. To show this we can use the rewriting system whose rules are εoµ => ε*ε, εoη => I, (ε*1)oγ => γo(1*ε) and (1*ε)oγ => γo(ε*1) which should be confluent. So, any morphism of X factorizes uniquely into a morphism of E followed by a morphism of F. Since we have the same phenomenon in X this should be enough to show that X is the PROP for erasable monoids if we assume that we know that F is isomorphic to the PROP of integers and functions and it is simple to see that E is isomorphic to the PRO of integers and partial identities. I am a bit fuzzy about the difference between PROs and PROPs but I hope that you get the general idea. Another way to show this is to remark that it is a particular case of the presentation of FinRel I give in my paper.

A more abstract way of stating this kind of things can be found in Composing PROPs of Steve Lack where he shows that PRO(P)s can be seen as monads in span bicategories and they can therefore be composed by giving distributive laws between them.

PS : my first name is Samuel and not Daniel ;)

Posted by: Samuel Mimram on May 16, 2008 9:53 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Samuel wrote:

I guess that XX is the PROP for “erasable monoids” (M,μ,η,ϵ)(M,\mu,\eta,\epsilon) where (M,μ,η)(M,\mu,\eta) is a monoid and ϵ:MI\epsilon : M \to I is an “erasure operator” satisfying ϵμ=ϵϵ\epsilon \circ \mu = \epsilon \otimes \epsilon and ϵη=1 I\epsilon \circ \eta = 1_I.

I almost agree with you: I think XX is the PROP for commutative erasable monoids.

In fact, algebraists spend a lot of time studying these things! But, they don’t use the term ‘erasable’. They especially study these things in the categories AbGpAbGp and VectVect.

In AbGpAbGp they’re called ‘- - - - - - - - -’ commutative rings, and in VectVect they’re called ‘- - - - - - - - -’ commutative algebras. I’m hoping some algebraist will come along and fill in the blanks!

I am a bit fuzzy about the difference between PROs and PROPs but I hope that you get the general idea.

I think I get the general idea, but I don’t know what you mean here: do you mean you’re not sure of the difference between a PRO and a PROP, or just how it affects this particular example?

I should explain the difference between a PRO and a PROP, just so everyone here knows.

In a nutshell, a PRO is a monoidal category, while a PROP is a symmetric monoidal category.

In a bit more detail:

Definition: A PRO is a strict monoidal category XX with natural numbers as objects, for which the tensor product of objects nn and mm is n+mn + m. Given a monoidal category CC, an algebra of XX in CC is a monoidal functor F:XCF: X \to C, and a morphism of algebras in CC is a monoidal natural transformation between such monoidal functors. There is a category of algebras of XX in CC.

Definition: A PROP is a strict symmetric monoidal category XX with natural numbers as objects, for which the tensor product of objects nn and mm is n+mn + m. Given a symmetric monoidal category CC, an algebra of XX in CC is a symmetric monoidal functor F:XCF: X \to C, and a morphism of algebras in CC is a symmetric monoidal natural transformation between such symmetric monoidal functors. There is a category of algebras of XX in CC.

We can also talk about a PROB, where we take the definition of a PROP and replace the word ‘symmetric’ by ‘braided’.

Wikipedia has a nice quick introduction to PROs, PROBs, and PROPs. I’ve written a longer introduction.

A great example of a PRO that’s not a PROP is Δ\Delta, the category of finite ordinals and order-preserving functions. This is the PRO for monoids. Similarly, Δ op\Delta^op is the PRO for comonoids.

By the way, I’m sorry for writing “Daniel” — I’ve fixed that.

Posted by: John Baez on May 17, 2008 12:51 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

I had Lack’s paper in mind, where the notion of factorization is defined between two PROs or two PROPs but not between a PRO and a PROP since they don’t live in the same category, as it is the case for E and F in my example. So when factorizing, F should get all the symmetries of the category X and I was a bit afraid of that, but actually this should not be so much of a problem.

Posted by: Samuel Mimram on May 17, 2008 10:34 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

I of course meant commutative monoids…

Posted by: Samuel Mimram on May 17, 2008 12:49 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

Okay, so we agree.

Posted by: John Baez on May 17, 2008 12:52 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

Don’t forget Operads which are even easier/more familiar as they correspond to maps n –>1.

Decaf Problem: What is the operad for Nambu algebras? A Nambu algebra has a single n-ary operation satisfying a Fundamental Identity which is NOT the restriction of the L\infty relation.

Posted by: jim stasheff on May 17, 2008 1:55 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Samuel mentioned:

“erasable monoids” (M,μ,η,ϵ)(M,\mu,\eta,\epsilon), where (M,μ,η)(M,\mu,\eta) is a monoid and ϵ:MI\epsilon : M \to I is an “erasure operator” satisfying ϵμ=ϵϵ\epsilon \circ \mu = \epsilon \otimes \epsilon and ϵη=1 I\epsilon \circ \eta = 1_I.

I wrote:

In fact, algebraists spend a lot of time studying these things! But, they don’t use the term ‘erasable’. They especially study these things in the categories AbGp and Vect.

In AbGp they’re called ‘- - - - - - - - -’ commutative rings, and in Vect they’re called ‘- - - - - - - - -’ commutative algebras. I’m hoping some algebraist will come along and fill in the blanks!

I’m really disappointed that no algebraist has stepped forward to reveal the standard names for these gadgets. I even said how many letters are in the name! What more must I do?

Posted by: John Baez on May 19, 2008 7:52 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

I’m no algebraist, but surely they’re what’s generally called augmented rings/algebras? At least, that seems to sometimes be used for exactly what you describe here (an algebra A with an algebra map from A to I) and sometimes the same except that the map isn’t required to commute with multiplication, so it’s just a splitting of the unit.

Posted by: Peter on May 19, 2008 11:41 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Peter wrote:

I’m no algebraist, but surely they’re what’s generally called augmented rings/algebras?

Right! At least that’s what I’ve always heard them called. And I’m used to people requiring the augmentation to get along with multiplication, as it does here — since people often call the kernel of the augmentation the ‘augmentation ideal’.

So, I would call one of Samuel’s ‘erasable monoids’ an augmented monoid: a monoid equipped with a monoid homomorphism to the unit of the monoidal category it lives in.

So, in terms of this jargon, I say that an algebra for the PROP of finite sets and partially defined functions is just an augmented commutative monoid.

The antonym of ‘augmented’ is ‘demented’.

Posted by: John Baez on May 22, 2008 3:27 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

I’ve been thinking about the question of what the algebras over the PROP Mat(RR) are for a general rig RR, and have convinced myself that it is just the category of bicommutative bialgebras (A,μ,Δ)(A,\mu,\Delta) equipped with a map of rigs RR to the rig of bialgebra endomorphisms of AA.

The addition operation on End(AA) is given by f+g=μ(fg)Δf+g=\mu(f\otimes g)\Delta.

The map of rigs is of course just given by the action of the 1 by 1 matrices on the algebra.

If this is correct then it is easy to see that the algebras for Mat(\mathbb{Z}) are indeed bicommutative Hopf algebras as the antipode will be given by the image of -1 under the rig map.

I think that this can be proved using fairly straightforward algebraic methods using the pleasing result that I was (unconciously) alluding to in my previous post in Theorems into Coffee I: the category of bicommutative Hopf algebras is enriched over the category of commutative monoids, that is each Hom set is a commutative moniod [under + given by f+g=μ(fg)Δf+g=\mu (f\otimes g)\Delta as before] and addition distributes over composition.

I do plan to write this all up this time, but it is unlikely to get done this week with teaching and the like.

Posted by: Simon Wadsley on May 20, 2008 10:23 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

When I said Hopf algebras in the penultimate paragraph I really meant bialgebras. I guess that if we work over Hopf algebras then in fact the category is enriched over abelian groups: the antipode provides the minus one.

Posted by: Simon Wadsley on May 20, 2008 7:20 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Simon wrote:

I’ve been thinking about the question of what the algebras over the PROP Mat(R)Mat(R) are for a general rig RR, and have convinced myself that it is just the category of bicommutative bialgebras (A,μ,Δ)(A,\mu,\Delta) equipped with a map of rigs RR to the rig of bialgebra endomorphisms of RR.

Cool! That sounds right! If you write up a valid proof, I’d say that’s worth 15 dollars of coffee.

When we have an algebra over Mat(R)Mat(R), we’ve got a bicommutative bialgebra for which each element of RR gives a unary operation — in fact a bialgebra endomorphism.

I was having fun thinking about the case R=R = \mathbb{Q}.

When nn \in \mathbb{Z} \subseteq \mathbb{Q}, the unary operation corresponding to nn can be thought of as a kind of ‘nnth power’ operation, since it sends gg to g ng^n for grouplike elements gg: that is, those with Δ(g)=gg\Delta(g) = g \otimes g.

So, it’s fun to extend this way of thinking to noninteger qq \in \mathbb{Q}, and talk about a bicommutative bialgebra equipped with ‘qqth power’ operations for all rational qq.

An obvious example is the group algebra of \mathbb{Q}… or indeed any abelian group that’s a \mathbb{Q}-module.

Posted by: John Baez on May 22, 2008 3:16 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

Version 0 of my write-up that Mat(RR) is the PROP for bicommutative bialgebras AAwith a map of rigs REnd(A)R\rightarrow End(A) can be found here.

It still needs a lot of work but I think it is basically complete and since it is the weekend…

Posted by: Simon Wadsley on May 23, 2008 5:20 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Hey, that looks good! I haven’t checked every last detail, but I’d already say it’s worth 15 dollars in coffee (even though it’s not the coffee problem announced in this blog entry). Will you be at any of the conferences I’ll be attending in Europe this summer? That would make it easy to deliver your prize.

(Samuel Mimram will be at Algebraic Topological Methods in Computer Science 2008, and I’ll give him his coffee money then.)

I especially like how your argument avoids the use of string diagrams — since while I love string diagrams, they seem like overkill for studying PROPs of the form Mat(R)Mat(R).

Posted by: John Baez on May 24, 2008 2:05 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

If we restrict the proof to the case where R is the rig of natural numbers then we can forget about the map of rigs φ since there is only one possible (since every integer is either zero or the sum of ones, right?). Now, given strict monoidal category C, the proof essentially gives a functor from the category Mat(N) to category of bicommutative bialgebras in C. However, I fail to see where the functor is shown to be full, which I think is required to show that Mat(N) is the PROP for bicommutative bialgebras (Mat(N) could “equate too many morphisms” for example). Did I miss something?

Posted by: Samuel Mimram on May 26, 2008 9:18 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

I meant a functor from the category of algebras of Mat(N) to the category of bicommutative bialgebras in C.

Posted by: Samuel Mimram on May 26, 2008 9:27 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

I think my final lemma describes how the functor acts on morphisms and proves that it is full.

The first paragraph show that every morphism of algebras for Mat(R) is a bialgebra morphism and the second paragraph shows that every bialgebra morphism arises in this way.

Posted by: Simon Wadsley on May 26, 2008 6:57 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

As far as I understand your final lemma, I think that it shows only an implication, i.e. an algebra of Mat(N) is a bicommutative bialgebra but not that every bialgebra arises this way (and by the way, it should also be shown that it arises in an unique way). For example, suppose that instead of Mat(N) I take FinRel and that I still want to show that FinRel is the PROP for bicommutative bialgebras. Since a relation can be seen as a matrix with only 0 and 1, I can still use the argument of the proof of the last lemma: “the condition for the (1 1) matrix implies that θ is an algebra map etc…”. So, I think that I can take the structure of your argumentation and “show” that FinRel is the PROP for bicommutative bialgebras. Unfortunately, it is only the PROP for qualitative bicommutative bialgebras. Where is it shown in your proof that my argumentation is flawed for FinRel?

Posted by: Samuel Mimram on May 27, 2008 8:36 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

Let me explain the structure of my proof when R=R=\mathbb{N}. As you say, in this case we can ignore the map of rigs because it is generated by the image of 1 which must be the identity.

After I state my theorem I prove three lemmas.

The first shows that given a bialgebra AA in 𝒞\mathcal{C}, I can construct FF over the PROP Mat(RR) such that F(1)F(1) is AA and the bialgebra structure is recoverable in a way I describe.

The second shows that if I start with an algebra FF over the PROP Mat(RR), I can put a bialgebra structure on F(1)F(1).

Although I do not explicitly say so [and in the next version I will], it is clear that the operations in these two lemmas are inverse to each other: i.e. I have described a correspondance between algebras over Mat(RR) and bialgebras in 𝒞\mathcal{C}.

Now as you said in your first response, it does not follow that the maps between algebras on the two sides of this correspondance are the same. This is the purpose of my third lemma. I show first that a natural transfomation between two algebras FF and GG over our PROP defines a morphism over bialgebras by considering the morphism it defines between F(1)F(1) and G(1)G(1). Finally I explain how a bialgebra map can be used to construct a natural transformation. Again it is clear, although I do not say so, that these two operations are mutual inverses.

Posted by: Simon Wadsley on May 27, 2008 9:07 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

I think that things are pretty clear to me now. Thanks a lot for your detailed explanations!

Posted by: Samuel Mimram on May 28, 2008 12:04 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

I’ve produced version 1 of my write-up here. The changes are mostly notational although I have added a corollary dealing with the problem posed in Theorems Into Coffee II.

I think it is clear from the write up that my proof really just says: “they just are the same”. There is no real content.

I don’t think I’ll be at any of those conferences to collect my prize but if you bump into anyone else from the maths department in Cambridge then I’m sure they’ll pass it on.

Posted by: Simon Wadsley on May 28, 2008 11:38 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

It’s great that the coffee prize has led to fruitful cooperation instead of mere competition! I like Simon’s new writeup a lot… except for the one word in his statement of the main theorem:

Theorem. If RR is a rig then Mat(R)Mat(R) is just the PROP for bicommutative bialgebras AA equipped with a map of rigs REnd(A)R \to End(A).

Namely, the word “just”. I don’t like my formal theorem statements to have “attitude”. Simon writes:

I think it is clear from the write up that my proof really just says: “they just are the same”. There is no real content.

But every theorem is a tautology; I think you’re just feeling that dismissive sense of triviality that comes near the end of proving something. As André Weil wrote:

The day dawns when the illusion vanishes; intuition turns to certitude […] as the Gita teaches us, knowledge and indifference are attained at the same moment. Metaphysics has become mathematics, ready to form the material for a treatise whose icy beauty no longer has the power to move us.

But this is a microscopic nitpick.

I’ll give both Samuel and Simon their 15 dollar coffee prizes at the earliest opportunity! I’m very happy at how well this worked.

I don’t think I’ll be at any of those conferences to collect my prize but if you bump into anyone else from the maths department in Cambridge then I’m sure they’ll pass it on.

You trust ‘em? Okay. Does anyone here know anyone at Cambridge who is going to Categorical Groups, HOCAT or ATMCS this summer?

Posted by: John Baez on May 28, 2008 5:41 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

I’ve removed the ‘just’ from my theorem statement. In fact it wasn’t supposed to be there. It was a hangover from when the theorem said something like ‘an algebra over the PROP Mat(R) is just a bicommutative bialgebra with …’

As for whether the proof has content, you may be right that it is only a triviality on the level that all proofs are, but it just feels to me that I do nothing but check that the axioms hold for various structures.

I suppose it would be more accurate to say that once you’ve guessed what the inverse functors that map between the two categories are [which could reasonably be encoded in the statement of the theorem] then proving that they really are functors is all that is to be done, and this is just mechanical axiom checking.

Posted by: Simon Wadsley on May 28, 2008 6:54 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Peter Freyd once said, “Perhaps the purpose of categorical algebra is to show that which is trivial is trivially trivial.” :-)

Posted by: Todd Trimble on May 28, 2008 10:51 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

This is an example of how the founders of category theory weren’t very good at selling the subject.

Posted by: John Baez on May 29, 2008 6:38 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Oh, I don’t know, in my (mathematical) neck of the woods I get the feeling that people are still reluctant even to use category theory for the purpose alluded to in Freyd’s aphorism/witticism. I see quite a few arguments which are “easily checked and left to the reader” rather than “trivial consequences of applying a functor in the right way”, or “taking a pullback and using universality”, or somesuch.

So some of us are still at the stage of gingerly sipping 1-category coffee ;-)

Posted by: yemon choi on May 30, 2008 8:26 AM | Permalink | Reply to this

Re: Theorems Into Coffee III

I was reflecting on the consequences of my theorem a couple of hours ago and came up with the following cute fact:

Suppose RR is the rig defined by the Boolean algebra given by the power set of 22 i.e. of a set with two elements.

So x+x=xx+x=x and x.x=xx.x=x for each of the four elements of RR, and if aa and bb are the two singleton sets in RR then a+b=1a+b=1 and ab=ba=0ab=ba=0

Then an algebra over RR is what Samuel calls a qualitative bicommutative bialgebra — and like John I would be interested to know if there are any natural examples of these in algebra — with a pair of bialgebra maps that are mututally orthogonal idempotents that sum to the identity under the addition given on End.

[As an aside, it is interesting to note that x+x=xx+x=x follows from 1+1=11+1=1 so is an empty condition on endomorphisms of a bialgebras of this type.]

I guess this isn’t surprising given the defining relations on RR, but I like it as it seems to relate to the classical decomposition of algebras into blocks.

Posted by: Simon Wadsley on May 29, 2008 10:10 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Nice observation!

By the way, something or someone has made it impossible to access the links to your work that appear on this page, namely

http://www.dpmms.cam.ac.uk/~sjw47/PROP.pdf

and

http://www.dpmms.cam.ac.uk/~sjw47/PROP2.pdf

Could you restore them somehow, or provide me with new links so I can fix things?

Posted by: John Baez on July 12, 2008 12:30 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

I think that it is just a (hopefully) temporary glitch with the DPMMS web-server. It doesn’t seem to allow me to access anyone’s homepages there.

For the time being I’ll just wait and see what happens. If that doesn’t work I’ll post the files somewhere else.

Posted by: Simon Wadsley on July 12, 2008 12:57 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

The server seems to be working again now.

Posted by: Simon Wadsley on July 14, 2008 1:44 PM | Permalink | Reply to this

Re: Theorems Into Coffee III

Yes, the server seems to be working again!

Alas, I didn’t bump into anyone who admitted to being from Cambridge, so I was unable to pass along your coffee prize. It remains available, waiting for you to claim it.

Posted by: John Baez on July 14, 2008 5:42 PM | Permalink | Reply to this
Read the post Theorems Into Coffee IV
Weblog: The n-Category Café
Excerpt: The first Theorems into Coffee prize is awarded. Read about Steve Lack's work on PROPs, and try your hand at the latest Theorems into Coffee challenge.
Tracked: July 12, 2008 2:09 PM
Read the post Koudenburg on Algebraic Weigthed Colimits
Weblog: The n-Category Café
Excerpt: Read about my student's thesis.
Tracked: April 17, 2013 5:58 PM

Post a New Comment