The n-Category Café

I’ll answer that question, but first it needs making precise.

What kind of thing are the “quantities”? The inclusion-exclusion equation is an equation between two quantities, and involves only addition and subtraction, so all we need to ask of quantities is that they form an abelian group.

What kind of thing are the “sets”? The inclusion-exclusion equation involves unions and intersections of the sets $A_i$ concerned. For that to make any kind of sense, these “sets” had better all be subsets of one big set $S$, say. So we’ve got a distinguished collection $M$ of subsets of $S$, and each $A_i$ is supposed to be an element of $M$. Here $M$ should make you think of “measurable”.

More exactly, the equation involves one union and lots of intersections. It’s going to be a real pain if the collection $M$ of measurable sets isn’t closed under intersection, so let’s assume that it is. But we won’t assume that it’s closed under union: we just ask that the equation holds if $A_1 \cup \cdots \cup A_n \in M$ (and, of course, $A_i \in M$ for each $i$).

A good example to keep in mind is this: $M$ is the set of compact convex subsets of $S = \mathbb{R}^N$ (counting $\emptyset$ as convex). This is closed under binary intersection, but not union.

In other examples, $M$ might be closed under finite union. Then the inclusion-exclusion principle reduces to the cases $n = 0$ and $n = 2$. The usual terminology then is that $\phi$ is a valuation.

Aside  You could formulate it more generally, taking $M$ to be an abstract poset — not necessarily one represented as a sub-poset of $(\mathcal{P}(S), \subseteq)$. In that generality, I don’t know what the universal measure is.

Fix a set $S$ and a collection $M$ of subsets of $S$, closed under binary intersection.

With apologies for abusing an already-abused word, I’ll make the following definition.

Definition  A measure on $M$ is a pair $(X, \phi)$ where $X$ is an abelian group (of “quantities”) and $\phi: M \to X$ is a function satisfying the inclusion-exclusion principle:

$$\phi(A_1 \cup \cdots \cup A_n) = \sum_i \phi(A_i) - \sum_{i \lt j} \phi(A_i \cap A_j) + \sum_{i \lt j \lt k} \phi(A_i \cap A_j \cap A_k) - \cdots$$

whenever $n \geq 0$ and $A_1, \ldots, A_n \in M$ with $A_1 \cup \cdots \cup A_n \in M$.

For example, if $S = \mathbb{R}^2$ and $M$ is the set of compact convex subsets, then there is a measure $(\mathbb{R}, perimeter)$ on $M$.

There’s an obvious notion of map of measures: a map $(Y, \psi) \to (X, \phi)$ is a homomorphism $\alpha: Y \to X$ such that $\alpha \circ \psi = \phi$. So there’s a category of measures on $M$. Let’s call it $Meas(M)$.

Here’s the formal version of the question I originally posed, “what is the universal measure?”:

What is the initial object of  $Meas(M)$?

The answer can be found in a result called Groemer’s integral theorem. Actually, I don’t know how widely it’s called that. It’s the name used by Klain and Rota in their book (page 9), but I suspect they coined it. The original result of Helmut Groemer —

— was about convex sets. Klain and Rota gave a more general lattice-theoretic formulation. The current formulation as a universal property is new, as far as I’m aware.

In a slogan, the answer is:

The universal measure is indication.

And while I’m sloganeering:

The universal property asserts that simple functions can be integrated.

Let me explain those cryptic utterances.

Every subset $A$ of our big set $S$ has an indicator function, or characteristic function, $I_A: S \to \mathbb{Z}$. It takes value $1$ inside $A$ and $0$ outside $A$. A function $f: S \to \mathbb{Z}$ is simple if it’s a finite $\mathbb{Z}$-linear combination of indicator functions of measurable sets:

$$f = \sum_{i = 1}^n \alpha_i I_{A_i}$$

($\alpha_i \in \mathbb{Z}$, $A_i \in M$). The simple functions form an abelian group $Simp(M)$ under addition.

Every measurable set $A$ has an associated indicator function $I_A$, and this process — which I facetiously called “indication” — defines a map

$$I_\bullet: M \to Simp(M).$$

It’s easy to see that $I_\bullet$ satisfies the inclusion-exclusion principle. For example, the case $n = 2$ is that

$$I_{A \cup B} = I_A + I_B - I_{A \cap B}.$$

So $(Simp(M), I_\bullet)$ is a measure on $M$.

Theorem (Groemer)  The initial object of  $Meas(M)$ is $(Simp(M), I_\bullet)$.

Let’s unwind this universal property and see what it says. By definition of the category $Meas(M)$, it says that whenever $X$ is an abelian group and $\phi: M \to X$ satisfies the inclusion-exclusion principle, there is a unique homomorphism $\overline{\phi}: Simp(M) \to X$ such that $\overline{\phi} \circ I_\bullet = \phi$:

$$\begin{matrix} M &\stackrel{I_\bullet}{\to} &Simp(M) \\ &\phi\searrow &\downarrow \exists!\overline{\phi}\\ & &X. \end{matrix}$$

But the commutativity of this diagram just says that for any measurable set $A$, we have

$$\overline{\phi}(I_A) = \phi(A).$$

What usually turns the indicator function of a set into the measure of that set? Integration! So we should write $\overline{\phi}$ as $\int - d\phi$. Then the diagram asserts that

$$\int I_A d\phi = \phi(A)$$

for all $A \in M$.

Since every simple function is a $\mathbb{Z}$-linear combination of indicator functions, and since $\int - d\phi$ is supposed to be a $\mathbb{Z}$-linear map, the uniqueness part of the universal property is not in question. The substantial part is existence. What we have to prove here is that the integral of a simple function can be defined consistently by

$$\int \Bigl(\sum_i \alpha_i I_{A_i}\Bigr) d\phi = \sum_i \alpha_i \phi(A_i).$$

In other words, if we represent a simple function as a linear combination of indicator functions in two different ways, we get the same answer for the integral. Proving that is going to depend on $\phi$ having some nice property; and that nice property turns out to be exactly the inclusion-exclusion principle.

There’s a more general result, too. All of the above was in a stripped-down world where quantities are only assumed to form an abelian group. In other words, we worked over $\mathbb{Z}$. But everything works over an arbitrary ring $k$. Then an object of $Meas(M)$ is a pair $(X, \phi)$ where $X$ is a $k$-module and $\phi$ is exactly as before; a simple function is a $k$-linear combination of indicator functions; and so on. It all works.

The traditional choice is $k = \mathbb{R}$, so that we’re integrating real-valued functions. But the proof of Groemer’s theorem uses nothing about $\mathbb{R}$ beyond that it’s a ring.