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.

September 14, 2011

Universal Measures

Posted by Tom Leinster

 

There is much that is odd about motivic measure if it is judged by measure theory in the sense of twentieth century analysis […] The first peculiarity is that the measure is not real-valued.

Thomas Hales, What is motivic measure?, Bulletin of the AMS 42 (2005), 119–135.

This post isn’t about motivic measure, though you should definitely take a look at Hales’s excellent article (especially to find out what the second peculiarity is). This post will, however, share something of the spirit of motivic measure, including a flexible attitude towards where measure takes its values.

Suppose that we have some set, and a collection of “subsets” that we want to be able to “measure”. I’ll keep this very vague and general for the moment, though when I make it precise it genuinely will be quite general. The word “measure” isn’t used here with its standard meaning: we’re just assigning a “quantity” to each of our sets in some plausible way.

The crucial point is that whatever “quantity” means, it needn’t mean “real number”. And all I ask of a “measure” ϕ\phi is that it satisfies the inclusion-exclusion principle: ϕ(A 1A n)= iϕ(A i) i<jϕ(A iA j)+ \phi(A_1 \cup \cdots \cup A_n) = \sum_i \phi(A_i) - \sum_{i \lt j} \phi(A_i \cap A_j) + \cdots whenever n0n \geq 0 and A 1,,A nA_1, \ldots, A_n are sets for which this makes sense.

What is the universal way to measure a collection of sets?

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 iA_i concerned. For that to make any kind of sense, these “sets” had better all be subsets of one big set SS, say. So we’ve got a distinguished collection MM of subsets of SS, and each A iA_i is supposed to be an element of MM. Here MM 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 MM 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 1A nMA_1 \cup \cdots \cup A_n \in M (and, of course, A iMA_i \in M for each ii).

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

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

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

Fix a set SS and a collection MM of subsets of SS, closed under binary intersection.

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

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

ϕ(A 1A n)= iϕ(A i) i<jϕ(A iA j)+ i<j<kϕ(A iA jA k) \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 n0n \geq 0 and A 1,,A nMA_1, \ldots, A_n \in M with A 1A nMA_1 \cup \cdots \cup A_n \in M.

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

There’s an obvious notion of map of measures: a map (Y,ψ)(X,ϕ)(Y, \psi) \to (X, \phi) is a homomorphism α:YX\alpha: Y \to X such that αψ=ϕ\alpha \circ \psi = \phi. So there’s a category of measures on MM. Let’s call it Meas(M)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)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 —

Photo 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 AA of our big set SS has an indicator function, or characteristic function, I A:SI_A: S \to \mathbb{Z}. It takes value 11 inside AA and 00 outside AA. A function f:Sf: S \to \mathbb{Z} is simple if it’s a finite \mathbb{Z}-linear combination of indicator functions of measurable sets:

f= i=1 nα iI A i f = \sum_{i = 1}^n \alpha_i I_{A_i}

(α i\alpha_i \in \mathbb{Z}, A iMA_i \in M). The simple functions form an abelian group Simp(M)Simp(M) under addition.

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

I :MSimp(M). I_\bullet: M \to Simp(M).

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

I AB=I A+I BI AB. I_{A \cup B} = I_A + I_B - I_{A \cap B}.

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

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

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

M I Simp(M) ϕ !ϕ¯ X. \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 AA, we have

ϕ¯(I A)=ϕ(A). \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 dϕ\int - d\phi. Then the diagram asserts that

I Adϕ=ϕ(A) \int I_A d\phi = \phi(A)

for all AMA \in M.

Since every simple function is a \mathbb{Z}-linear combination of indicator functions, and since dϕ\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

( iα iI A i)dϕ= iα iϕ(A i). \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 kk. Then an object of Meas(M)Meas(M) is a pair (X,ϕ)(X, \phi) where XX is a kk-module and ϕ\phi is exactly as before; a simple function is a kk-linear combination of indicator functions; and so on. It all works.

The traditional choice is k=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.

Posted at September 14, 2011 1:47 AM UTC

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

17 Comments & 0 Trackbacks

Re: Universal Measures

Very nice!

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

I don’t suppose it helps that by the Yoneda lemma, every poset MM is isomorphic to a sub-poset of (𝒫(M),)(\mathcal{P}(M),\subseteq) — namely the sub-poset consisting of the “principal ideals” (= representable functors) (a)={bM|ba}\downarrow(a) = \{ b\in M | b \le a \}. I guess the problem is that the Yoneda embedding doesn’t preserve unions. Makes me feel like there’s some sheafy sort of thing that wants to be going on.

Posted by: Mike Shulman on September 14, 2011 5:18 AM | Permalink | PGP Sig | Reply to this

Re: Universal Measures

I’m glad you picked up on that point, Mike, because I was dimly aware that I was being lazy there. Klain and Rota state Groemer’s theorem in the generality of a sub-poset of a power set, and I just followed their lead. (I only read the proof 24 hours ago.)

I did get as far as realizing that not every lattice is a sublattice of a power set, since (for instance) not every lattice is distributive. But I didn’t start thinking about Yoneda: that’s a good point.

A crucial step in the proof of initiality is this: if A,A 1,,A nA, A_1, \ldots, A_n are subsets of our set SS, and

I ASpan{I A 1,,I A n}, I_A \in Span\{I_{A_1}, \ldots, I_{A_n}\},

then

AA 1A n. A \subseteq A_1 \cup \cdots \cup A_n.

If I were going to try to generalize the result beyond sub-posets of power sets, I might begin by thinking about this step.

Posted by: Tom Leinster on September 14, 2011 5:43 AM | Permalink | Reply to this

Re: Universal Measures

Elsewhere you have

…once we have the concept of Banach space, then with a tiny amount more input …, the concept of integrability just pops out.

Here you have integration popping out through a universal property. Any connection?

Posted by: David Corfield on September 14, 2011 10:42 AM | Permalink | Reply to this

Re: Universal Measures

Thanks for remembering that, David!

I have another one up my sleeve. The universal property formulation of Groemer’s theorem resembles this other one even more strongly, though I haven’t got further yet than thinking “hmm, those seem awfully similar”. I’ll save this other result for another time: it wants its own post.

Right now I’m off to Cambridge to coincide with the visit of Steve Lack. It seems that he’s getting off the plane from Sydney, getting on a bus to Cambridge, and promptly giving a talk. This is impressive.

Posted by: Tom Leinster on September 14, 2011 11:28 AM | Permalink | Reply to this

Re: Universal Measures

Yes, a real jetsetter. Earlier today I emailed him just as he was leaving the office in Sydney, replied, and then got a reply from him from the airport, about to leave. I have been wondering where to…

Posted by: David Roberts on September 14, 2011 12:50 PM | Permalink | Reply to this

Re: Universal Measures

Live blogging on Twisting Structures?

Posted by: David Corfield on September 14, 2011 12:55 PM | Permalink | Reply to this

Re: Universal Measures

It crossed my mind to attempt live blogging, but only briefly… I’ll just summarize the event as “Steve’s talk was great”.

Posted by: Tom Leinster on September 16, 2011 12:49 AM | Permalink | Reply to this

Re: Universal Measures

the lifting from sets to “data-over-sets” motivates thinking in terms of sheaves. for example, the “simple” integer-valued functions are, in the sheaf world, called “constructible” functions. various tools and ideas from the theory of constructible sheaves (going back to macpherson, kashiwara, schapira, …) lead to integration with respect to euler characteristic and a host of other interesting constructs.

one of the nice things about the sheaf-theoretic perspective on measure is that one does not have to limit to convex sets or “polyconvex” sets, etc.: a “tame” stratification suffices. perhaps the best way to deal with such “simple” or “tame” sets is to invoke o-minimal structures (see the excellent book by van den dries on “tame topology and o-minimal structures”).

Posted by: Robert Ghrist on September 14, 2011 11:48 AM | Permalink | Reply to this

Re: Universal Measures

Thanks; that’s very interesting. It keeps happening that people refer me to Van den Dries’s book. I have had it out of the library a couple of times, but somehow I still haven’t managed to get “the point” (if that makes any sense). Maybe I’ll give it another go.

Posted by: Tom Leinster on September 16, 2011 12:53 AM | Permalink | Reply to this

Re: Universal Measures

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 kk.

In fact, some convex geometers define valuations to take their values in an abelian semigroup. (Just rewrite the definition by rearranging terms so you don’t need minus signs.) The main example in which this additional generality comes into play is valuations on convex bodies whose values are themselves convex bodies, equipped with Minkowski addition.

Posted by: Mark Meckes on September 14, 2011 2:23 PM | Permalink | Reply to this

Re: Universal Measures

Using a semigroup (the upper reals) is precisely what one needs to do in a topos.

The construction of an integral on simple functions that Tom describes is closely related to the one by Tarski and Horn. We described it here, a more categorical presentation can be found in a recent paper by Steve Vickers. Steve’s paper gives a presentation of the Giry monad on the category of locales. The construction uses (only) geometric mathematics.

Posted by: Bas Spitters on September 14, 2011 9:24 PM | Permalink | Reply to this

Re: Universal Measures

So Mark, do you happen to know whether Groemer’s theorem holds with valuations taking values in an abelian semigroup? I would think it does, simply because right now I can’t see why the whole proof couldn’t be rearranged in the kind of way you suggest, but perhaps you already know.

Bas, thanks for the references. By the “upper reals”, I take it you mean either [0,)[0, \infty) or (0,)(0, \infty)?

Posted by: Tom Leinster on September 16, 2011 12:59 AM | Permalink | Reply to this

Re: Universal Measures

Or some other form of constructive real numbers

Posted by: David Roberts on September 16, 2011 1:19 AM | Permalink | Reply to this

Re: Universal Measures

David: Thanks for providing the link.
Indeed, [0,∞) with the upper topology.

Posted by: Bas Spitters on September 16, 2011 8:01 AM | Permalink | Reply to this

Re: Universal Measures

So Mark, do you happen to know whether Groemer’s theorem holds with valuations taking values in an abelian semigroup?

No, I only know Groemer’s theorem from Klain and Rota’s book, and I don’t have access to it now to see what the proof really needs.

Posted by: Mark Meckes on September 17, 2011 2:23 PM | Permalink | Reply to this

Re: Universal Measures

I never got round to checking this out. But this morning I saw a talk by Christoph Haberl about body-valued valuations, so I thought he’d be the perfect person to ask. I did ask, and he said that the answer was yes.

Posted by: Tom Leinster on September 28, 2011 3:18 PM | Permalink | Reply to this

Re: Universal Measures

To elaborate on Bas’s posting:

I found myself using similar arguments in my draft paper
A monad of valuation locales”,
prompted by techniques in a paper by Coquand and Spitters.

I used Simp(M) in the special situation where M has unions too, but with two differences from Tom’s article.

(1) I did not use subtraction. This is not a problem with inclusion and exclusion, since the negative terms can be moved to the other side of the equation, and Mark Meckes mentioned the possibility of using semigroups (I actually used monoids) rather than groups. However, this was essential because for constructivist reasons I had to use the lower reals rather than the Dedekind reals, and for them subtraction is not available. I used inclusion and exclusion in proving uniqueness of product valuations.

(2) I was in a point-free setting of locales, so I could not assume that the elements of M were concretely subsets of some given set. It was just a distributive lattice. I then had to define Simp(M) directly by universal algebra (as did Coquand and Spitters).

Although I was dealing abstractly with distributive lattices, I’m not sure how well the techniques generalize to meet semilattices as emphasized in the article. The property “behaves properly for existing joins” can be covered by the universal algebra, but I don’t know how to get at the underlying distributivity that in the concrete setting is intrinsic.

From this point of view Groemer’s result is a representation theorem, representing the universal gadget as a function space. I proved something more combinatorical, that the universal gadget is isomorphic to the (join) semilattice tensor of M and the natural numbers. Amongst other things, this shows that the structure is both monoid and lattice. Integration is available, and I got a Riesz theorem which, I think, may be somehow capturing the spirit of Groemer in the lattice situation.

Posted by: Steve Vickers on September 16, 2011 10:54 AM | Permalink | Reply to this

Post a New Comment