The n-Category Café

The inclusion-exclusion formula tells us the cardinality of a union, which in categorical terms is a pushout. The set of orbits of a free action of a group $G$ on a finite set is the colimit of the associated functor $B G \to FinSet$. (Here $B G$ is the one-object category whose maps are the elements of $G$.) Generally, we’re going to think about the cardinality of the colimit of a functor $X: A \to FinSet$, where $A$ is a finite category.

In both the examples I just mentioned, the cardinality $|colim X|$ of the colimit is a $\mathbb{Q}$-linear combination of the cardinalities $|X(a)|$ of the individual sets $X(a)$, taken over all objects $a \in A$. For inclusion-exclusion, we take

$$A = (0 \leftarrow 1 \rightarrow 2)$$

and get

$$|colim(X)| = |X(0)| - |X(1)| + |X(2)|.$$

For a free action of a group $G$, we take $A = B G$. If the single object of $A$ is called $a$, then

$$|colim(X)| = |X(a)|/o(G)$$

— the cardinality of the set $X(a)$ being acted on, divided by the order of $G$.

Generally, there’s no hope of computing the cardinality of the colimit of a functor $X: A \to FinSet$ in terms of the cardinalities of the sets $X(a)$ alone. The colimit usually depends on what the functor $X$ does to morphisms, as well as objects. So in order to pull this off, we’re going to have to confine ourselves to only those functors $X$ that are especially convenient. The hope is that for any $A$, there are rational numbers $w_A(a)$ ($a \in A$) such that for all “convenient” functors $X: A \to FinSet$,

$$|colim(X)| = \sum_{a \in A} w_A(a) |X(a)|.$$

Here’s how to simultaneously figure out what the coefficients $w_A(a)$ in this weighted sum must be and what “convenient” should mean.

The starting thought is that most notions of “nice enough” for set-valued functors include the representables. Since the colimit of any representable is the one-element set, for the last equation to hold for all representables $A(b, -)$ means that

$$1 = \sum_{a \in A} w_A(a) |A(b, a)|$$

for all $b \in A$.

And now we’re getting somewhere! This is a system of equations with the same number of equations as unknowns $w_A(a)$, namely, the number of objects of $A$. And in this situation, there’s typically a unique solution, at least if we work over the field $\mathbb{Q}$.

A family $(w_A(a))_{a \in A}$ of rational numbers satisfying

$$\sum_{a \in A} |A(b, a)| w_A(a) = 1$$

for all $b \in A$ is called a weighting on $A$, and $w_A(a)$ is called the weight of $a$. For the purposes of this post, I’ll assume there’s always exactly one weighting on $A$. That’s not entirely justified: there are examples of finite categories with no weighting or finitely many. (See Examples 1.11 of my paper The Euler characteristic of a category, where all the stuff I’m talking about right now is worked out.) But it’s safe enough.

So, take the weighting $w_A$ on $A$. By defintion, the class of functors $X: A \to FinSet$ satisfying

$$|colim(X)| = \sum_{a \in A} w_A(a) |X(a)|$$

contains the representables. But it’s easy to see that it’s also closed under coproducts. So, this equation — which I’ll call the colimit formula — holds for all coproducts of representables!

Which functors $A \to Set$ are coproducts of representables? They’re sometimes called the “familially representable” functors, the idea being that a coproduct of representables $\sum_{i \in I} A(a_i, -)$ is represented by a family of objects $(a_i)_{i \in I}$. But in my last post, I called them the “free functors”. The way I put it there was that the forgetful functor

$$Set^A \to Set^{ob\ A}$$

has both a left and a right adjoint, and a functor $X \in Set^A$ is free if and only if it’s in the image of the left adjoint. That means

$$X \cong \sum_{a \in A} S(a) \times A(a, -)$$

for some family of sets $(S(a))_{a \in A}$.

Examples

• When $A$ is the discrete two-object category $\{0, 1\}$, both weights are $1$, and the general colimit formula

  $$|colim(X)| = \sum_a w_A(a) |X(a)|$$

  reduces to something very basic:

  $$|X(0) + X(1)| = |X(0)| + |X(1)|$$

  — the cardinality of a coproduct is the sum of the individual cardinalities. When $A$ is a discrete category, all functors $A \to Set$ are coproducts of representables.

• When $A$ is the shape $(0 \leftarrow 1 \rightarrow 2)$ for pushouts, a functor $X: A \to FinSet$ is a diagram

  $$(X(0) \leftarrow X(1) \rightarrow X(2))$$

  of finite sets, and $X$ is a coproduct of representables if and only if both these maps are injections. Assume $X$ is a coproduct of representables. The weighting on $A$ is $(1, -1, 1)$, so the colimit formula says that the cardinality of a pushout is

  $$|X(0)| - |X(1)| + |X(2)|$$

  — the inclusion-exclusion formula.

• For a group $G$ (or more generally, a monoid), the weight of the unique object of $B G$ is $1/o(G)$, the reciprocal of the order. Given an action of $G$ on a a finite set, the corresponding functor $B G \to FinSet$ is a coproduct of representables if and only if the action is free. In that case, the colimit formula says that the number of orbits is the cardinality of the set divided by $o(G)$.

• Finally, when $A = (0 \rightrightarrows 1)$, the colimit formula says that the coequalizer of $X(0) \rightrightarrows X(1)$ has $|X(1)| - |X(0)|$ elements, provided that the two functions from $X(0)$ to $X(1)$ are injective with disjoint images.

Aside for category theorists   Under finiteness conditions, and assuming that $A$ is Cauchy complete, a functor $X: A \to Set$ is a coproduct of representables if and only if it is flat with respect to the class of finite connected limits. This might seem more abstract than the original condition, but it actually gives a concrete, testable condition for $X$ to be a coproduct of representables. (See Lemma 5.2 and Definition 3.2 here.) This result enables one to see rather quickly that in all the examples above, the functors arising as coproducts of representables are exactly what I said they are.

 

Summary so far  We’ve seen that a finite category $A$ typically has a unique weighting $w_A$ — meaning a family $(w_A(a))_{a \in A}$ of rational numbers satisfying

$$\sum_a |A(a, b)| w_A(a) = 1$$

for all $b \in A$. And we’ve seen that when $X: A \to FinSet$ is a coproduct of representables, the “colimit formula” holds:

$$|colim(X)| = \sum_a w_A(a) |X(a)|.$$

Now, what if $X$ isn’t a coproduct of representables? The colimit formula won’t usually hold. But the right-hand side of this non-equation still calculates something. What is it?

Let me define the magnitude $|X|$ of a functor $X: A \to FinSet$ by

$$|X| = \sum_{a \in A} w_A(a) |X(a)| \in \mathbb{Q}.$$

This is equal to $|colim(X)|$ if $X$ is a coproduct of representables, but not in general.

For example, if we take a monoid $M$ acting on a finite set, the magnitude of the corresponding functor $B M \to FinSet$ is the cardinality of the set divided by the order of $M$. Unless the action is free, this isn’t usually the number of orbits, and it might not even be an integer.

The functor $\Delta 1: A \to FinSet$ sending everything in $A$ to the one-element set has magnitude

$$|\Delta 1| = \sum_{a \in A} w_A(a),$$

which is called the magnitude or Euler characteristic of $A$. (Under finiteness hypothesis, it’s equal to the topological Euler characteristic of the classifying space in $A$.) Hence the magnitude of a category is a special case of the magnitude of a set-valued functor. Conversely, one can show that the magnitude of a functor $X: A \to FinSet$ is equal to the magnitude of its category of elements.

So, the concepts of magnitude of a category (already studied extensively) and the magnitude of a set-valued functor (a term I think I’m introducing for the first time here) are each special cases of the other. But in these posts, unlike everything I’ve written about magnitude before, I’m going to give prime position to magnitude of set-valued functors rather than of categories.

 

Does this definition of the magnitude of a set-valued functor have sensible properties? It does!

First, if $X, Y: A \to FinSet$ are isomorphic then certainly $|X| = |Y|$. Second, and a bit less trivially, magnitude is invariant under equivalence in the following sense: if we compose $X: A \to FinSet$ with an equivalence of categories $G: B \to A$ then

$$|X \circ G| = |X|.$$

In fact, this holds just as long as $G$ has a left adjoint.

The term “magnitude” suggests it should behave in a cardinality-like way, and it does that too. For example, given functors $X, Y: A \to FinSet$,

$$|X + Y| = |X| + |Y|,$$

where the left-hand side is the magnitude of the coproduct of our two functors. A bit more generally, suppose we have a diagram of functors and natural transformations

$$X \leftarrow Y \rightarrow Z$$

such that for each $a \in A$, the functions

$$X(a) \leftarrow Y(a) \rightarrow Z(a)$$

are injective with disjoint images (or more abstractly, the corresponding functor from $(0 \leftarrow 1 \rightarrow 2)$ to $FinSet$ is a coproduct of representables). Then one can show that the magnitude of the pushout $X +_Y Z$ is given by

$$|X +_Y Z| = |X| - |Y| + |Z|.$$

So magnitude in this sense obeys the inclusion-exclusion formula. More generally still, there’s a similar result for any shape of colimit, but I won’t write it out here. It’s exactly what the pushout case suggests.

 

I hope I’ve driven home the message that although the colimit formula

$$|colim(X)| = |X|$$

for functors $X: A \to FinSet$ holds when $X$ is a coproduct of representables, it doesn’t hold for arbitrary $X$. So perhaps it’s interesting to see how much the two sides of the equation differ when $X$ isn’t a coproduct of representables. In other words, let’s look at the difference

$$|colim(X)| - |X| = |colim(X)| - \sum_a w_A(a) |X(a)| \in \mathbb{Q}.$$

It seems to me that this quantity could be interesting. However, I don’t have a strong feel for what it means yet, so for now I’ll give it a bland name: the discrepancy of $X$.

Example  The discrepancy of a coequalizer

$$X_0 \rightrightarrows X_1 \to C$$

is

$$|C| - (|X_1| - |X_0|) = |X_0| - |X_1| + |C|.$$

We’ve already seen that this is $0$ if our two functions $f, g: X_0 \rightrightarrows X_1$ are injective with disjoint images. But in general, it looks rather like an Euler characteristic. In fact, from our coequalizer we can form a chain complex of free abelian groups

$$0 \to \mathbb{Z} X_0 \stackrel{\mathbb{Z}g - \mathbb{Z}f}{\to} \mathbb{Z} X_1 \stackrel{\mathbb{Z}h}{\to} \mathbb{Z} C \to 0$$

where $h$ is the original function $X_1 \to C$. Then the discrepancy of our coequalizer is equal to the Euler characteristic of this complex.

This complex is exact except maybe at $\mathbb{Z} X_0$. Let’s do a little check: if $f$ and $g$ are injective with disjoint images then $\mathbb{Z}g - \mathbb{Z}f$ is injective too, so the complex is exact everywhere, which implies that the Euler characteristic is $0$. Since the discrepancy is also $0$ in this case, we’ve just confirmed one case of the result that the discrepancy of the coequalizer is the Euler characteristic of the resulting complex.

Example  For a pushout square

$$\begin{array}{ccc} X_1 &\rightarrow &X_0 \\ \downarrow & &\downarrow \\ X_2 &\rightarrow &P, \end{array}$$

the discrepancy is

$$|P| - (|X_0| - |X_1| + |X_2|) = |X_1| - |X_0| - |X_2| + |P|.$$

I don’t know what to do with this formula, but it has a certain symmetry. Has anyone come across it before?

 

I’ll finish by explaining the entropy connection I promised at the start. Here we go!

 

Ordinary Shannon entropy  For this, we need to think about the Shannon entropy not just of probability measures — the usual setting — but of arbitrary measures. The sets we’re considering measures on will always be finite.

A probability measure $p$ on a finite set $\{1, \ldots, n\}$ is just an $n$-tuple $(p_1, \ldots, p_n)$ of nonnegative reals summing to $1$, and its entropy $H(p)$ is defined by

$$H(p) = -\sum_i p_i \log p_i,$$

with the convention that $0\ \log\ 0 = 0$. A measure $a = (a_1, \ldots, a_n)$ on $\{1, \ldots, n\}$ is any $n$-tuple of nonnegative reals, and the definition of entropy is extended from probability measures to arbitrary measures by homogeneity. That is, writing $\|a\| = \sum a_i$, the tuple $a/\|a\|$ is a probability measure, and we define

$$H(a) = \|a\| H(a/\|a\|)$$

(or $H(a) = 0$ if $\|a\| = 0$). This is the unique way of extending the definition so that

$$H(\lambda a) = \lambda H(a)$$

for all measures $a$ and real $\lambda \geq 0$.

Let’s now consider measures $a = (a_1, \ldots, a_n)$ where each $a_i$ is an integer. Such a thing amounts to a map

$$A \stackrel{\pi}{\to} I$$

of finite sets. To see this, take $I = \{1, \ldots, n\}$, and take $A \stackrel{\pi}{\to} I$ to be a function into $I$ whose $i$-fibre has cardinality $a_i$.

This categorification manoeuvre — upgrading from numbers to sets — brings maps into play. In particular, we get the monoid $End(A)$ of all functions $A \to A$, and its submonoid $End_I(A)$ consisting of the endomorphisms of $A$ over $I$. That is, the elements of $End_I(A)$ are the functions $f: A \to A$ such that $\pi \circ f = \pi$.

The inclusion of monoids

$$End_I(A) \hookrightarrow End(A),$$

like any other monoid homomorphism, induces an action of the domain on the underlying set of the codomain: applying an element $f \in End_I(A)$ to an element $g \in End(A)$ gives a new element $f \circ g \in End(A)$. And this monoid action corresponds to a functor

$$End_I(A) \to FinSet.$$

(Or “$B End_I(A) \to FinSet$” if you want to be fussy, but I’ll drop the $B$s.)

Question: what’s the magnitude of this functor?

Answer: it’s

$$\frac{|End(A)|}{|End_I(A)|} = \frac{\|a\|^{\|a\|}}{\prod_i a_i^{a_i}} = \prod_i \biggl( \frac{\|a\|}{a_i} \biggr)^{a_i}.$$

This is nothing but $\exp(H(a))$, the exponential of the entropy of our measure! So:

The exponential of entropy is a special case of magnitude.

(Sometimes it seems that the exponential of entropy is a more fundamental quantity than the entropy itself. Apart from anything else, it doesn’t depend on a choice of base. I like to call the exponential of entropy the diversity.)

At least, that’s true when the measure of each point is an integer. But from knowing the entropy of such measures, we can easily obtain the entropy of those where the entropy of each point is rational, assuming the homogeneity property $H(\lambda a) = \lambda H(a)$. And then one can get the completely general case of real measures by extending by continuity.

The basic calculation above was described in an earlier post of mine, but at that time I didn’t see clearly what it meant.

 

Relative entropy  Given two probability measures $p$ and $r$ on the same finite set, you can calculate their relative entropy. It’s a measure of how surprised you’d be to observe a distribution of $p$ in a sample drawn from a population with distribution $r$. (I think of $r$ as the “reference” distribution.) The formula for $H(p\|r)$, the entropy of $p$ relative to $r$, is

$$H(p\|r) = \sum_i p_i \log(p_i/r_i) \in [0, \infty].$$

Just as for ordinary entropy, we can extend it from probability measures to arbitrary measures. We’re now dealing with two measures $a$ and $b$ on the same finite set, and I’ll assume they have the same total mass: $\|a\| = \|b\|$. Again, we extend homogeneously, so that

$$H(\lambda a \| \lambda b) = \lambda H(a\|b)$$

whenever $\lambda \geq 0$.

And as before, we’ll focus on measures taking integer values. A pair of measures on a finite set $I$, both taking integer values and with the same total mass, amounts to a diagram

$$A \rightrightarrows I$$

in $FinSet$. The idea is that if we take $I = \{1, \ldots, n\}$ and write $a_i$ and $b_i$ for the cardinalities of the fibres of the $i$-fibres of these two maps, then one of our measures is $(a_1, \ldots, a_n)$ and the other is $(b_1, \ldots, b_n)$. They have the same total mass because

$$a_1 + \cdots + a_n = |A| = b_1 + \cdots + b_n.$$

Calling our two maps $\pi, \rho: A \to I$, we can consider the set

$$Hom_I(A \stackrel{\pi}{\to} I, A \stackrel{\rho}{\to} I)$$

of functions $g : A \to A$ such that $\rho \circ g = \pi$. This set is acted on by the monoid

$$End_I(A \stackrel{\pi}{\to} I)$$

of functions $f : A \to A$ such that $\pi \circ f = \pi$, by composition.

As we keep seeing, a monoid action corresponds to a functor from that monoid to $Set$, whose magnitude we can compute. In this case, the magnitude is

$$\frac{|Hom_I(A \stackrel{\pi}{\to} I, A \stackrel{\rho}{\to} I)|}{|End_I(A \stackrel{\pi}{\to} I)|} = \frac{\prod b_i^{a_i}}{\prod a_i} = \prod \biggl( \frac{a_i}{b_i} \biggr)^{a_i},$$

which is equal to

$$\exp(-H(a \| b))$$

—the negative exponential of relative entropy.

(We’re never going to be able to get rid of that negative and get $\exp(H(a \| b))$ itself as a magnitude, since $H(a\|b)$ can be infinite but that the magnitude of a functor can’t be, at least in the context at hand.)

As for ordinary entropy, if we know relative entropy for integer-valued measures then it’s only two short steps to the definition for arbitrary measures.

 

Conditional entropy  Whereas relative entropy takes as its input a pair of measures on the same set, conditional entropy takes as its input two measures on different sets.

It’s usually presented in terms of random variables: we have random variables $X$ and $Y$ taking values in sets $I$ and $J$ respectively (which for us will be finite), and the conditional entropy $H(X | Y)$ is defined by

$$H(X | Y) = \sum_{i \in I, j \in J} P(X = i, Y = j) \log \frac{1}{P(X = i | Y = j)}.$$

If we write $(p_{i j})_{i \in I, j \in J}$ for the joint distribution — so that the $p_{i j}$ are nonnegative reals summing to $1$ — then

$$H(X | Y) = \sum_{i, j} p_{i j} \log \biggl( \frac{p_j}{p_{i j}} \biggr).$$

Here $p$ is a probability measure on $I \times J$. But just as for ordinary and relative entropy, this definition extends to arbitrary measures $a$ on $I \times J$, by scaling homogeneously.

To see how conditional entropy is a special case of magnitude, we follow a path that should be familiar by now.

An integer-valued measure on $I \times J$ amounts to a map $A \to I \times J$ of finite sets, or equivalently a diagram

$$I \leftarrow A \rightarrow J$$

in $FinSet$. In the monoid of all endomorphisms of $A$, we can consider the endomorphisms over $I$, or over $J$, or most restrictively of all, over $I \times J$. In particular, there is an inclusion of monoids

$$End_{I \times J}(A) \hookrightarrow End_J(A).$$

As for ordinary entropy, this homomorphism induces an action of the domain on the underlying set of the codomain, giving a functor $End_{I \times J}(A) \to FinSet$ whose magnitude we can calculate. It’s

$$\frac{|End_J(A)|}{|End_{I \times J}(A)|} = \frac{\prod_j a_j^{a_j}}{\prod_{i, j} a_{i j}^{a_{i j}}} = \prod_{i, j} \biggl( \frac{a_j}{a_{i j}} \biggr)^{a_{i j}},$$

where I’m using $a_{i j}$ to mean the cardinality of the $(i, j)$-fibre of $A \to I \times J$ and $a_j$ to mean the cardinality of the $j$-fibre of $A \to J$. This is exactly the exponential of the conditional entropy.

 

Conclusion   The exponentials of

• ordinary entropy
• the negative of relative entropy
• conditional entropy

all arise as special cases of magnitude — at least for integer-valued measures, but it’s routine to derive the definition for general measures from that special case.

 

If you know lots about entropy, you might be wondering now: what about mutual information? Is that the magnitude of some set-valued functor too?

I don’t know! Given $A \to I \times J$, the quantity we’d like to obtain as a magnitude is

$$\frac{|End(A)| |End_{I \times J}(A)|}{|End_I(A)| |End_J(A)|}.$$

I can’t see how to do that in any natural way.

Maybe I’ll come back to this point next time, when I’ll start on the topic that’s actually the title of these posts: comagnitude.