The n-Category Café

Well, looking over the nice proof from your notes, it all seems to hinge on the all-important identity

$$p \circ (u_{k_1}, u_{k_2}, \ldots, u_{k_n}) = u_k$$

in the case where $p = (\frac{k_1}{k}, \frac{k_2}{k}, \ldots, \frac{k_n}{k})$ is a rational point of the simplex. So that would seem to be the thing one needs to feel in one’s bones, and how it relates to symmetry.

As for myself: I don’t really know what to make of this chain rule. The usual chain rule from calculus really says the derivative is a functor in a suitable sense – in my favorite formulation, the tangent bundle functor. But this chain rule I don’t have much feeling for, yet.

Todd, there’s always so much to respond to in your comments. Each one requires serious thought, and so many of them are gold mines!

So I’ll just respond to one particular point here, and even this will be a long comment.

As for myself: I don’t really know what to make of this chain rule. The usual chain rule from calculus really says the derivative is a functor in a suitable sense - in my favorite formulation, the tangent bundle functor. But this chain rule I don’t have much feeling for, yet.

Here’s the best I can do. A longer version of the following is in this post, but here I’ll try to say this as directly and briefly as possible. Which turns out to be “not very”.

There is a (topological, symmetric) operad $\Delta$ whose $n$-ary operations are the probability distributions on $n$ elements, with the composition described. A $\Delta$-algebra in $Set$ is something like a convex algebra, but the law

$$\lambda x + (1 - \lambda) x = x$$

is not required to hold (and indeed can’t be expressed operadically). We can consider $\Delta$-algebras in $Cat$ instead of $Set$ — or better, in $Cat(Top)$ (topological categories). To keep the overhead down, I’ll suppress the “$Top$” bit in what follows, but it really should be there — that is, everything should be continuous.

One $\Delta$-algebra in $Cat$ is $FinProb$, the category of finite sets equipped with a probability distribution and measure-preserving transformations between them. The $\Delta$-algebra structure is given like this: if you have a probability distribution $p$ on a set $X$, and another distribution $p'$ on $X'$, then for every $\lambda \in [0, 1]$ you get a distribution $\lambda p \oplus (1 - \lambda) p'$ on $X \amalg X'$. I haven’t defined the notation, but I’m sure you know what I mean.

Whenever $C$ is a categorical $\Delta$-algebra (by which I mean a $\Delta$-algebra in $Cat$), you can talk about internal $\Delta$-algebras in $C$. This is just like the fact that whenever $M$ is a monoidal category, you can talk about internal monoids in $M$. (In one case we’re using the operad $\Delta$; in the other we’re using the terminal operad.) A $\Delta$-algebra in $C$ consists of an object $X$ together with a map $\lambda X \oplus (1 - \lambda) X \to X$ for each $\lambda \in [0, 1]$, satisfying some axioms.

For instance, in $FinProb$ there is an internal $\Delta$-algebra consisting of the one-element set $1$ together with the unique probability distribution on it. It’s an internal $\Delta$-algebra in a unique way.

The monoidal category $D$ of finite totally ordered sets has inside it the monoid $1$ (the one-element set). As is well known, this is the initial example of a monoidal category containing a monoid. It’s the “free monoidal category on a monoid”. So, for an arbitrary monoidal category $A$, the (strict) monoidal functors $D \to A$ are in canonical bijection with the monoids in $A$.

In exactly the same sense, $FinProb$ together with the internal $\Delta$-algebra $1$ is the free categorical $\Delta$-algebra on an internal $\Delta$-algebra. So, for an arbitrary categorical $\Delta$-algebra $A$, the structure-preserving functors $FinProb \to A$ are in canonical bijection with the $\Delta$-algebras in $A$.

(There was a white lie just then. It’s not quite FinProb that has this universal property; it’s a near-identical category that I called $FP$ in that previous post. The difference lies in some delicacy involving zero probabilities. I’ll ignore it here.)

Now, the monoid $(\mathbb{R}^+, +, 0)$ is a convex algebra in the obvious way (it’s a convex set!), and when you view this monoid as a one-object category, it becomes a categorical $\Delta$-algebra. The internal $\Delta$-algebras in $\mathbb{R}^+$ are, therefore, in canonical bijection with the structure-preserving functors $FinProb \to \mathbb{R}^+$.

Now, at last, we get to the chain rule. What is a structure-preserving functor $F \colon FinProb \to \mathbb{R}^+$? It’s a way of associating to each measure-preserving map $\theta$ a real number $F(\theta)$. For instance, given any probability distribution $p$ on a finite set $X$, there is a unique map

$$!_p \colon (X, p) \to (1, u_1)$$

(where $u_1$ means the unique distribution on $1$), which gives rise to a number $F(!_p) \in \mathbb{R}^+$. So, among other things, $F$ assigns to each probability distribution a real number. Let’s write $I(p) = F(!_p)$.

But $F$ has to be a structure-preserving functor. Here “structure-preserving” refers to the $\Delta$-algebra structure. Crucial observation: any measure-preserving map $\theta \colon (X, p) \to (Y, q)$ between finite probability spaces can be written as a convex combination (over $y \in Y$) of maps to the one-point space. Since $F$ is required to preserve that convex combination, $F$ is entirely determined by $I$. In other words, $F$ is really just a way of assigning a number to each probability distribution — satisfying axioms, which we’re not finished with yet.

The one requirement on $F$ that we have left to consider is actual functoriality: preservation of composition. Rather than consider the general case, let me take just the example you mention. Take a probability distribution with rational probabilities,

$$p = \Bigl( \frac{k_1}{k}, \ldots, \frac{k_n}{k} \Bigr)$$

where $k_i \in \mathbb{Z}$ and $\sum k_i = k$. This gives rise to a composable pair of arrows in $FinProb$:

$$(k, u_k) \stackrel{\pi}{\to} (n, p) \stackrel{\psi}{\to} (1, u_1)$$

where $k$ means the set $\{1, \ldots, k\}$, where $u_k$ is the uniform distribution on $k$ elements, where $\pi$ is the map that partitions $k$ into pieces of size $k_1, \ldots, k_n$, and where $\psi$ is the only thing it could possibly be. Let’s apply $F$ to this composite $\psi \circ \pi$.

By what I just said about convex combinations, $\pi$ is a convex combination of maps into the terminal space:

$$\pi = \bigoplus_{i = 1}^n p_i \Bigl( (k_i, u_{k_i}) \to (1, u_1) \Bigr).$$

Since $F$ is structure-preserving,

$$F(\pi) = \sum_{i = 1}^n p_i I(u_{k_i}).$$

Now looking at the second map in our composable pair, $\psi$, we have $F(\psi) = I(p)$ simply by definition of $I$. Hence

$$F(\psi) + F(\pi) = I(p) + \sum_{i = 1}^n p_i I(u_{k_i}).$$

But $F: FinProb \to \mathbb{R}^+$ is a functor, and $+$ is composition in $\mathbb{R}^+$, so

$$F(\psi) + F(\pi) = F(\psi \circ \pi).$$

And $F(\psi \circ \pi) = I(u_k)$, again by definition of $I$. So

$$I(p) + \sum_{i = 1}^n p_i I(u_{k_i}) = I(u_k).$$

That’s exactly the chain rule! At least, it’s the chain rule for this particular example of an operadic composite,

$$u_k = p \circ (u_{k_1}, \ldots, u_{k_n}).$$

But everything I just said works equally well for any other composite.

So at last, we’ve seen how the chain rule expresses the fact that some functor preserves composition.