The n-Category Café

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)$ consisting of abstract operations with $n$ inputs and $m$ outputs. We can compose these

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

and also tensor them

$$\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 $X$ with natural numbers as objects, for which the tensor product of objects $n$ and $m$ is $n + m$. Given a symmetric monoidal category $C$, an algebra of $X$ in $C$ is a symmetric monoidal functor $F: X \to C$, and a morphism of algebras in $C$ is a symmetric monoidal natural transformation between such symmetric monoidal functors. There is a category of algebras of $X$ in $C$.

But the fun starts when we consider examples…

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

Then, we say $X$ is the PROP for $A$’s when for any symmetric monoidal category $C$, the category of algebras of $X$ in $C$ is equivalent to the category of $A$’s in $C$.

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

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

Theorem: $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)$ 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(\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:

• Samuel Mimram, Presentation of a game semantics for first-order propositional logic, Thm. 14, page 22.

He calls a matrix $T$ of natural numbers a ‘multirelation’, since it’s like a relation where two items $i$ and $j$ can be related in more than one way — in $T_{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(\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(\mathbb{Z}) \to Mat(\mathbb{Q})$$

which lets us turn any algebra for $Mat(\mathbb{Q})$ into an algebra for $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\}$$

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

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

Theorem: $Mat(B)$ is the PROP for qualitative bicommutative bimonoids: that is, those for which comultiplication followed by multiplication $$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 $X$ be the sub-PROP of $Mat(B)$ where a morphism $f \in hom(m,n)$ is a partially defined function. What is $X$ the PROP for?

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