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 23, 2012

Where Do Ultrafilters Come From?

Posted by Tom Leinster

Here’s the central point of my new paper:

There is a standard piece of categorical machinery which, when fed the notion of finiteness of a set, produces as output the notion of ultrafilter.

More snappily:

Ultrafilters are inevitable.

The categorical machine I’m referring to is the one that makes codensity monads (which I explained last time). The result isn’t mine: it seems to have first appeared in a paper published the year I was born. But it deserves to be better known.

I’ll tell you roughly how the theorem works — and, perhaps more importantly, I’ll tell you what it means to integrate against an ultrafilter.

First a technological remark: usually I’d use a fancy-font capital letter U to denote an ultrafilter, something like 𝒰\mathcal{U}. But I’m not sure how many people will be able to read that. (I know that until I installed some extra fonts, I wasn’t able to read all the symbols here.) So instead, I’ll use a capital omega: Ω\Omega.

(Out of interest: how many readers can’t see the wedding-invitation U here: 𝒰\mathcal{U}?)

What’s an ultrafilter?

Definition  Let XX be a set. An ultrafilter on XX is a set Ω\Omega of subsets such that whenever XX is expressed as a disjoint union of three subsets, exactly one belongs to Ω\Omega.

This isn’t the usual definition, but it’s equivalent (Proposition 1.5 of my paper). You can change “three” to any larger integer, but not to “two” — that gives a strictly weaker condition.

An equivalent definition is:

Definition  Let XX be a set. An ultrafilter on XX is a set Ω\Omega of subsets such that whenever XX is expressed as a disjoint union of a finite number of subsets, exactly one belongs to Ω\Omega.

The first thing anyone needs to know about ultrafilters is that there are some rather trivial examples. Given any set XX and element xXx \in X, the principal ultrafilter on xx is the set of all subsets containing xx.

The second thing anyone needs to know is that there are other examples, but it’s impossible to describe them explicitly. If XX is finite then the principal ultrafilters are the only ultrafilters on XX. If XX is infinite, however, there are nonprincipal ultrafilters on XX — but proving this makes essential use of the axiom of choice.

Suppose now that we have an ultrafilter Ω\Omega on XX. Let ff be a function from XX to a finite set BB. By the second definition above, there is a unique bBb \in B whose fibre f 1(b)f^{-1}(b) belongs to Ω\Omega. I claim that bb deserves to be called

XfdΩ. \int_X f \, d\Omega.

In other words, I claim that XfdΩ\int_X f\, d\Omega is the correct notation for the unique element of BB satisfying

f 1( XfdΩ)Ω. f^{-1} \biggl( \int_X f\, d\Omega \biggr) \in \Omega.

This integral notation imitates the standard notation from measure theory. There, if μ\mu is a measure on a space XX and ff is a function on XX, the integral of ff against μ\mu is written as Xfdμ\int_X f \, d\mu.

So, we’re thinking of an ultrafilter on XX as something like a measure on XX. If probability indicates your degree of belief, an ultrafilter is a probability measure for fundamentalists: everything has probability 00 or 11. The subsets of XX with measure 11 are exactly the elements of the ultrafilter; every other subset has measure 00. A more precise statement is that the ultrafilters on a set XX correspond one-to-one with the finitely additive probability measures on XX, as noted in Lemma 3.1 of my paper (and many times before).

But what could it mean to integrate against an ultrafilter?

Take a set XX equipped with an ultrafilter Ω\Omega. Given a “nice” function ff on XX, say f:XBf\colon X \to B, the integral of ff against Ω\Omega should be an element of BB. Here I’ll interpret “nice” as meaning simply that BB is finite. Whatever integration is, it should at the very least satisfy the following two conditions:

  • Since Ω\Omega is a kind of probability measure (meaning that the measure of the whole of XX is 11), the integral of a constant function should be that constant.
  • If two functions ff and gg are equal almost everywhere (that is, the set of points of XX where they agree belongs to Ω\Omega), then their integrals should be equal.

And the fact is: the unique “integration” rule satisfying these two conditions is XdΩ\int_X - \, d\Omega, as defined above.

This tells us we’ve got the right definition of integration. Further confirmation comes from the fact that there’s a formula for integration under a change of variables, exactly analogous to the classical one. There are also nice things to say when the codomain BB carries some algebraic structure, which is what we’re used to — classically, integrands take values in \mathbb{R} or \mathbb{C}. You can find all this in sections 3 and 4 of my paper.

Aside  A function is like an election. When you have a function f:XBf\colon X \to B, you can imagine each “voter” xXx \in X choosing a single element f(x)f(x) from the set BB of all possible “options”. Any ultrafilter Ω\Omega on XX thinks that there’s one option chosen by almost all of the voters, namely, XfdΩ\int_X f \, d\Omega.

Before the election, you could decide to use Ω\Omega as your voting system, so that the final outcome of the election is XfdΩB\int_X f \, d\Omega \in B. This is always unfair, but if Ω\Omega is the principal ultrafilter on some xXx \in X, it’s spectacularly unfair: the outcome of the election is simply the option chosen by the privileged voter xx.

There’s more on the voting/ultrafilter connection in a couple of blog posts: one of Terry Tao’s, and one of mine.

Let’s take stock. Let XX be any set. Whenever we have an ultrafilter Ω\Omega on XX, we can integrate against Ω\Omega. The operation of integration turns functions from XX to a finite set BB into elements of BB:

XdΩ:[X,B]B. \int_X - \, d\Omega \colon [X, B] \to B.

Here [X,B][X, B] is the set of functions from XX to BB.

Everything about integration against ultrafilters works nicely. In particular, integration against an ultrafilter is natural in the codomain BB. Categorically, this says that XdΩ\int_X - \, d\Omega is an element of the end

BFinSet[[X,B],B]. \int_{B \in \mathbf{FinSet}} [[X, B], B].

It’s unfortunate that the integral sign is being used in two different ways here, but there we are: they’re both standard notation, and it shouldn’t cause confusion. Anyway, if you know about codensity monads — for instance, if you read my last post — that end formula should look familiar. It’s the codensity monad of the inclusion functor FinSetSet\mathbf{FinSet} \hookrightarrow \mathbf{Set}, evaluated at XX. That is: let GG be the inclusion functor FinSetSet\mathbf{FinSet} \hookrightarrow \mathbf{Set}, and let T GT^G be the codensity monad of GG. Then (by definition, if you like)

T G(X)= BFinSet[[X,B],B]. T^G(X) = \int_{B \in \mathbf{FinSet}} [[X, B], B].

So, given an ultrafilter Ω\Omega on a set XX, you get an element XdΩ\int_X - \, d\Omega of T G(X)T^G(X). You can think of T G(X)T^G(X) as the set of “integrals”, or integration operators, on XX.

We can bundle this up into a neat categorical statement. The ultrafilters on a set XX form another set, U(X)U(X), and this defines a functor U:SetSetU \colon \mathbf{Set} \to \mathbf{Set}. Since everything works nicely, integrating against an ultrafilter defines a natural transformation UT GU \to T^G,

Ω XdΩ. \Omega \mapsto \int_X - \, d\Omega.

In fact, UU is a monad in a unique way; I won’t say how, but you can read about it in my paper. It’s called the ultrafilter monad. As you might hope, our natural transformation UT GU \to T^G respects the monad structures.

But best of all, this transformation UT GU \to T^G is actually an isomorphism:

Theorem  The codensity monad of the inclusion FinSetSet\mathbf{FinSet} \hookrightarrow \mathbf{Set} is isomorphic to the ultrafilter monad.

So if ultrafilters are regarded as measures, this says that there’s a one-to-one correspondence between measures and integrals.

In my paper, I attribute this result to Ernie Manes, who included it as a guided exercise in his 1976 book Algebraic Theories. But in my last post, Tim Porter pointed out an earlier text in which the result appeared (thanks, Tim!):

  • J. F. Kennison, Dion Gildenhuys, Equational completion, model induced triples and pro-objects, Journal of Pure and Applied Algebra 1 (1971), 317–346.

(Neither they nor Manes use the language of integration.)

The theorem justifies my claim at the beginning of this post: that if you take general categorical constructions for granted, the notion of ultrafilter is inherent in the notion of finitness of a set.

This isn’t the only way to conclude that “ultrafilters are inevitable”: for instance, you can view an ultrafilter on a set XX as a lattice homomorphism from the power set of XX to the two-element lattice. But perhaps the notion of lattice is slightly less primitive than the notion of finite set.

Actually, Kennison and Gildenhuys’s theorem can be strengthened. Theorem 3.5 of my paper states:

Theorem  Let B\mathbf{B} be a full subcategory of FinSet\mathbf{FinSet} containing at least one set with at least 3 elements. Then the codensity monad of the inclusion BSet\mathbf{B} \hookrightarrow \mathbf{Set} is isomorphic to the ultrafilter monad.

The isomorphism is, again, a version of the one-to-one correspondence between integrals and measures. The number 3 here is the same 3 as appears in the definition of ultrafilter given at the start. Again, it can’t be lowered to 22.

One extreme case of this theorem is Kennison and Gildenhuys’s, where B\mathbf{B} is the whole of FinSet\mathbf{FinSet}.

The other extreme case is where B\mathbf{B} consists of a single finite set BB with three or more elements. In that case, the codensity monad T GT^G of BSet\mathbf{B} \hookrightarrow \mathbf{Set} is particularly easy to describe. For any set XX, the set [X,B]=B X[X, B] = B^X has a natural action by the monoid End(B)End(B) of endomorphisms of BB. Of course, BB itself has a natural action by End(B)End(B) too. Then T G(X)T^G(X) is simply the set of maps [X,B]B[X, B] \to B preserving the End(B)End(B)-action. Hence:

Theorem  Let BB be a finite set with at least three elements. Then for any set XX, the set of End(B)End(B)-equivariant maps [X,B]B[X, B] \to B is canonically isomorphic to the set of ultrafilters on XX.

This result seems to be due to Lawvere, though he also seems not to have published it. Todd Trimble told me about it, and has written about it at the nLab.

Posted at September 23, 2012 3:13 PM UTC

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

32 Comments & 0 Trackbacks

Re: Where Do Ultrafilters Come From?

The fact that you need a form of the axiom of choice to produce nonprincipal ultrafilters means that in constructive mathematics, ultrafilters are not usually very useful. So I wonder, how constructive is Kennison and Gildenhuys’s theorem? On the one hand, if it is not constructive, then maybe elements of T G(X)T^G(X) could serve as a constructive substitute for ultrafilters in some contexts. But on the other hand, if it is constructive, then could there be models of set theory (with dramatic failures of AC) in which FinSetFinSet is actually codense in SetSet? What do T GT^G-algebras look like constructively?

Posted by: Mike Shulman on September 23, 2012 6:21 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

There is a constructive version of Manes theorem.
On compact space objects in topoi Harry J. Porta and Oswald Wyler.


Posted by: Bas Spitters on September 23, 2012 6:55 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

I haven’t read Kennison and Gildenhuys’s proof, but I’ve read mine, and I think it’s completely constructive. My explicit assumption in the paper is that Set\mathbf{Set} is a category of sets satisfying the axiom of choice, and that was also my implicit assumption in the post above. So yes, I think there are choiceless categories of sets in which the subcategory of finite sets is codense.

As I understand it (which is very little), this is something like the point of Lawvere’s mail to the categories list concerning topos theory and large cardinals: search for the word “large” in the nLab entry on ultrafilters.

Posted by: Tom Leinster on September 23, 2012 6:57 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Nice, thanks! Somehow I hadn’t read that post of Lawvere’s (although I did know the connection between measurable cardinals and codensity of infinite sets).

So yes, I think there are choiceless categories of sets in which the subcategory of finite sets is codense.

I know that the ultrafilter theorem (every filter can be extended to an ultrafilter) is implied by the axiom of choice, is not equivalent to it, but is not provable in ZF, and is equivalent to a bunch of other natural statements. But I don’t think I’ve ever heard the set-theoretic status of the statement “there exists a nonprincipal ultrafilter on some set” (which I guess is what would have to fail in order for FinSet to be codense in Set). Does anyone know?

Posted by: Mike Shulman on September 23, 2012 10:51 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

According to this mathoverflow answer, it is consistent with ZF that every ultrafilter on every set is principal. The refs given are a 1977 paper of Andreas Blass, A model without ultrafilters, which I’ve been quite unable to track down (according to the mathscinet review, even what’s published in the journal is just a summary), and a 1977 paper of Pincus and Solovay, Definability of measures and ultrafilters, which references the Blass. The proof given in Pincus and Solovay uses L, so I’m not sure whether or how it could be made constructive.

Posted by: Peter LeFanu Lumsdaine on September 24, 2012 5:22 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

I e-mailed Andreas about his 1977 paper. He did not have an electronic copy, but pointed out that the journal title changed through time and suggested looking for Polska Akademiia Nauk, Buletin.

Posted by: Tim Porter on September 26, 2012 6:40 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Awesome, thanks!

Posted by: Mike Shulman on September 25, 2012 2:44 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

The number 3 here is the same 3 as appears in the definition of ultrafilter given at the start.

Could there be a connection to the 3 of Arrow’s theorem, i.e., that there must be at least three choices to rank?

Posted by: David Corfield on September 23, 2012 8:49 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Interesting. I had briefly wondered whether Arrow’s theorem could be interpreted as saying that some functor is codense.

Let me remind myself of how Arrow’s theorem goes (using this post on means).

We have a finite set CC of candidates, and a finite set XX of voters.

Given a set SS, write O(S)O(S) for the set of total orders on SS. Any total order on a set induces a total order on each subset, giving a functor

O:P(C) opSet. O\colon P(C)^{op} \to \mathbf{Set}.

We also have a functor

[X,O]:P(C) opSet, [X, O] \colon P(C)^{op} \to \mathbf{Set},

sending DCD \subseteq C to [X,O(D)][X, O(D)].

For the purposes of Arrow’s theorem, a voting system is a natural transformation :[X,O]O\int \colon [X, O] \to O such that R=R\int R = R for any RO(C)R \in O(C). Here, the integrand “RR” is the constant function XO(C)X \to O(C) with value RR, and the meaning of the equation is that if all the voters order the candidates in the same way, then the outcome of the election is that same ordering.

Arrow’s theorem states that if the set XX of voters has at least one element and the set CC of candidates has at least three elements then the only voting systems are the trivial ones: those in which one privileged voter always gets their way. These trivial voting systems feel very like the principal ultrafilters, or the elements of a double dual vector space X **X^{**} of the form “evaluate at some particular xx”.

I think there’s got to be something in this connection, whether or not the two occurrences of “3” are really the same. It seems to me that the set BB in the last theorem of my post, required to have at least three elements, is more like the set O(C)O(C) than the set CC itself. Then again, saying that BB has more than two elements is equivalent to saying that O(C)O(C) has more than two elements…

This seems worth thinking about.

Posted by: Tom Leinster on September 23, 2012 9:39 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

It seems to me that the set BB in the last theorem of my post, required to have at least three elements, is more like the set O(C)O(C) than the set CC itself. Then again, saying that BB has more than two elements is equivalent to saying that O(C)O(C) has more than two elements…

So if the three candidates were placed on a circle, and voters were only allowed clockwise orderings, I wonder if the 3 choices for 3 candidates would be enough for Arrow’s theorem.

Posted by: David Corfield on September 24, 2012 8:56 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Lawvere and Rosebrugh place Isbell adequacy in the context of ‘social choice’ in section 8.4 of their set theory book. Piecing together their motivating examples and exercises one gets an ‘Arrow-style’ interpretation: given a set of candidates V and a set of voters X a social choice is a functional s: V^X -> V aggregating invidual choices such that for all endomorphisms e: V -> V and maps f:V^X->V, s(e f)=e(s f). Then such a ‘generalized point’ s satisfies a Pareto condition (‘is weakly averaging’ in their terminology): the social choice functional s respects univocal invidual choices (= constant maps v: X->V ) in the sense that s(v) = v . Every ordinary point x in X gives rise to a (generalized) point dx:V^X->V by evaluation at x, g |-> g(x). Exercise 8.25 says then that for X finite and |V|=3 every generalized point is already an ordinary point or ‘every social choice is dictatorial’ in economic parlance.
As Lawvere and Rosebrugh abandon the social choice interpretation soon after some initial discussion it is not clear whether they use this parallel only as a warm up for the discussion of generalised points and Isbell adequacy that is to follow, or if they have further worked out ideas on ‘social choice functionals’. They certainly perceived the similarity between the Isbell set up and ‘social choice’.

Posted by: thomas holder on September 25, 2012 2:39 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Thanks! I think I read that section once upon a time, but I’d forgotten about it, and I don’t think I ever noticed Exercise 8.25 or its connection with Arrow’s theorem.

I’ll stick in a reference to this when I revise the paper, and an acknowledgement to you. For the latter purpose, let me make sure I’ve got the spelling of your name right. The “o” of “Holder” doesn’t have an umlaut, does it? (You’ll understand why a mathematician would ask.)

Incidentally, Lawvere is the only contemporary writer I know who uses left/right adequate for dense/codense. Isbell’s terminology was first, but “dense” seems so much more evocative. It’s also what Mac Lane used in Categories for the Working Mathematician, and like so much of the terminology he used there, this is what has become standard.

Posted by: Tom Leinster on September 25, 2012 10:52 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

In this comment, I was hoping for a re-statement of Arrow’s theorem of the form “such-and-such a functor is codense”.

I haven’t found such a statement, and maybe there isn’t one. But I might as well record the less satisfying version that I have got.

Let CC be a finite set (thought of as the set of candidates in an election). Write P(C)P(C) for its power set, ordered by inclusion. Write FinSet \mathbf{FinSet}_{\neq\emptyset} for the category of nonempty finite sets. There is a functor

O:P(C) opFinSet O: P(C)^{op} \to \mathbf{FinSet}_{\neq\emptyset}

sending DCD \subseteq C to the set of total orders on DD, and OO has a codensity monad (T,η,μ)(T, \eta, \mu).

A statement equivalent to Arrow’s theorem is:

Theorem (Arrow)  If |C|3|C| \geq 3 then the natural transformation η\eta is cartesian.

I’m not really proud of that, as I can’t actually see any conceptual content.

Incidentally, Samson Abramsky was thinking along closely related lines a year or two ago. He gave a talk at the 2011 PSSL in Oxford called something like “Arrow’s theorem arrow-theoretically”. But as far as I can see, he hasn’t written anything up.

Posted by: Tom Leinster on September 25, 2012 11:05 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Lawvere and Rosebrugh pursue the ‘social choice’ example up to the point where they introduce the ‘generalized points’ in definition 8.19 and I guess this is precisely because they know that ‘generalized points’ are an inappropriate social choice mechanism ‘offending our sense of fairness’ as they write before definition 8.18, where they define a symmetry condition on social choice functionals s:V^X -> V namely to be invariant under permutations of the voters, which automatically excludes dictators. As they want to discuss Isbell adequacy they abandon the analogy to ‘social choice’ at this point.
I understand the claim of exercise 8.25 to be that the full subcategory on a set V with |V|=3 is left adequate (codense) in FinSet. I think they realise the relevance of this for social choice functionals, so in this sense an ‘Arrow theorem’ is implicit in their discussion.
The question is now the extent to which this ‘Arrow theorem’ is Arrow’s theorem.
Before tackling Arrow’s theorem it might be easier to try to reduce the Muller-Satterthwaite theorem (see Philip Reny’s online paper: ‘Arrow’s theorem and the Gibbard-Satterthwaite theorem: a unified approach’) to the adequacy statement for |V|>=3. Theirs is an ‘Arrow theorem’ saying that every monotonic, Pareto efficient social choice functional f:V^X->C (X finite set of voters, V set of linear orders on set of candidates C) is dictatorial for |C|>=3. Like in the case of Arrow’s theorem the functionals seem to have the ‘wrong’ codomain and the role of the monotonicity condition seems to be to ‘lift’ it to a generalized point f:V^X->V. There really should be a generalisation out there!

Posted by: thomas holder on September 26, 2012 9:34 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Thanks for all this information!

The “generalized points” in Lawvere and Rosebrugh’s Definition 8.19 are elements of a codensity monad, in the following sense. Let VV be a set, and write TT for the codensity monad of the full subcategory of Set\mathbf{Set} consisting of the object VV alone. Then a VV-generalized point of XX is precisely an element of T(X)T(X).

In this language, my Corollary 3.9 (which as far as I know is due to Lawvere) states that when VV is a finite set with three or more elements, the VV-generalized elements of a set XX correspond one-to-one with the ultrafilters on XX.

Exercise 8.25 then amounts to the statement that the only ultrafilters on a finite set are the principal ultrafilters. As you say, this states that the full subcategory on a three-element set is a codense (right adequate) subcategory of FinSet\mathbf{FinSet}. That’s quite a way from Arrow’s theorem, though, I’d say. In particular, it’s much easier to prove, as I’m sure you know.

Posted by: Tom Leinster on September 26, 2012 10:39 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

The parallelism principal filter-ultrafilter, point-generalized point, private opinion - public opinion is rather suggestive in this case. What’s funny is that in the categorical version the difference between private and public opinion is that the latter has a generalized domain but shares the codomain with the individual opinion (in this sense the public is merely a ‘more general’ individual) whereas in the economists’ theorems the ‘general will’ differs also in the codomain from the individuals’ wills: at the first sight the public will is not about the same thing as the individual will at all. I guess when one wants to find a bijection or a surjection between, let’s say, the generalized points f:V^X->V in T(X) and the monotonic, Pareto efficient social choice functions f:V^X->C in the Muller-Satterthwaite case one ends up giving the same kind of induction arguments as the economists do in the original proofs. So category theory would be no short cut here: all one can hope for is a gain in conceptual clarity.

Posted by: thomas holder on September 27, 2012 11:35 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

A reference in this context is

Hans Keiding:
The categorical approach to social choice theory,
Mathematical Social Sciences, Volume 1, Issue 2, January 1981, Pages 177-191

Posted by: thomas holder on October 5, 2012 9:48 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Abramsky’s paper ‘Arrow’s theorem by arrow theory’ is now available as arXiv:1401.4585 . Another paper for the aficionado is G.Segre ‘Quantum Democracy is possible’ (arXiv:0806.3667) that discusses a case with nonprincipal ultrafilters.

Posted by: thomas holder on January 22, 2014 5:34 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

… in the sense that Arrow’s Theorem can be read as identifying the decisive schemes (with finitely many voters) as those coming from (necessarily principal) ultrafilters on the electorate, … yes? In that context they are called “dictatorships”.

Posted by: Jesse C. McKeown on September 23, 2012 10:08 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Right, thanks. I know “dictatorship” is the standard term, but with the specific election metaphor I’m using, I prefer not to use it. That’s because “dictator” suggests a politician, whereas here it actually means a voter whose choice always prevails.

Posted by: Tom Leinster on September 23, 2012 10:12 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Out of interest: how many readers can’t see the wedding-invitation U here

As a negative response to the negative question, I can see it fine here. “Here” is Safari 5.0.6 on OSX 10.5.8 with no special fonts installed. So it’ll surely show up fine on any more modern versions of OSX; and I’d imagine it’s liable to come up fine on any other WebKit-based browsers (though they may be lacking fonts).

Posted by: wren ng thornton on September 23, 2012 9:51 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Thanks — that’s good to know.

Posted by: Tom Leinster on September 24, 2012 1:19 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

As to the 𝒰\mathcal{U}, out of interest I tried it on an old version of Safari (4.1.3) on my MacBook and there was initially nothing showing. I then went to see what version of Safari I was running and during that time the mathcal U had appeared.

Posted by: Tim Porter on September 24, 2012 10:23 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

The proof of existence of the codensity monad really looks constructive, which is to be expected since it’s just general category theory. So this is quite interesting because it does indeed suggest a constructive alternative to ultrafilters.

The other remaks I wanted to make was that the codensity monad for the inclusion of finite sets into sets reminds me very strongly of Martin Escardo’s selection monad. This is worth looking into.

Posted by: Andrej Bauer on September 23, 2012 11:57 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

The fancy 𝒰\mathcal{U} shows up as a gray rectangle in Firefox on my Android tablet. (Is it possible to install new fonts in Android?)

Posted by: Mike Shulman on September 24, 2012 3:23 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Another interesting fact mentioned on nLab is that an algebra over the ultrafilter monad is the same thing as a compact Hausdorff space. With the intuition that the codensity monad is the monad generated from a functor which does not necesserally have an adjoint, a compact Hausdorff space can be thought of as an arbitrary set with the structure of a finite set. This is interesting since it fits well with the intuition that a compact space is a topological space of finite size.

Posted by: Itai Bar-Natan on September 25, 2012 12:04 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Right! And this —

the intuition that a compact space is a topological space of finite size

— is exactly what my next post will be about. Stay tuned…

Posted by: Tom Leinster on September 25, 2012 12:12 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Your very nice talk at CT2013 today about this paper has inspired me to wonder about the codensity monads of other similar functors. For instance, the sort of person who believes that \infty-groupoids are better than sets may naturally wonder, what is the codensity (,1)(\infty,1)-monad of the inclusion of finitely presented \infty-groupoids into all \infty-groupoids?

That may be too much of a mouthful, but what about 1-groupoids? I’m not sure whether we should look at finitely presented groupoids or finitely generated free groupoids. In either case, what sort of structure on a groupoid would allow us to “integrate” a function into any such “finite” groupoid?

Posted by: Mike Shulman on July 13, 2013 6:54 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Thanks. Good questions… and I don’t know any of the answers. As I said in my talk, I have a PhD student currently looking at the situation for algebraic theories. This doesn’t quite cover the case of (1-)groupoids, of course.

Posted by: Tom Leinster on July 21, 2013 4:11 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

I'm coming late to this party, but I wonder why in justifying the notation XfdΩ\int_X f \,d\Omega you don't try just taking it literally, noting that Ω\Omega is a measure (in the finitely-additive sense). This seems crazy, because such an integral is a limit of linear combinations (with nonnegative real coefficients) of elements of the arbitrary finite set BB, yet we don't know how to multiply elements of BB by real numbers, we don't know how to add such products, and we don't know how to take limits of such sums. And yet …

The only measures provided by Ω\Omega are 00 and 11, and we know how to multiply anything (an element bb of BB or anything else whatsoever) by 00 or 11: the result is 00 or bb itself, respectively. And we know how to add 00 to any bb: the result is bb. And we know how to take a limit of an eventually constant net (with eventual value bb): the result is again bb. And these are the only operations that appear in this case!

So while BB does not have the structure of a topological vector space (or something a bit more general but still quite close) that would be necessary to define XfdΩ\int_X f \,d\Omega when Ω\Omega is an arbitrary measure on XX, it does have the structure necessary to define that integral when Ω\Omega is an ultrafilter. (That BB is finite is important to guarantee that the net whose limit we are taking is eventually constant.)

Incidentally, since I've just annoyed myself by (following the OP) writing ‘ XfdΩ\int_X f \,d\Omega’, I'll annoy all of you by pointing out that this should be written ‘ XfΩ\int_X f \Omega’, the ‘d’ being superfluous notation ultimately coming from mistakenly identifying the variable xx in the classical a bf(x)dx\int_a^b f(x) \,d{x} with Lebesgue measure when in fact it is dxd{x} (or really even |dx||d{x}|) that corresponds to Lebesgue measure. (See the explanation on the nLab.)

Posted by: Toby Bartels on August 24, 2016 11:13 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Couldn’t we just take the actual integral somewhere like B\mathbb{R}^B and then notice that the result happens to be the characteristic function of a singleton?

Posted by: Mike Shulman on August 24, 2016 4:35 PM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

I wonder why in justifying the notation XfdΩ\int_X f \,d\Omega you don’t try just taking it literally, noting that Ω\Omega is a measure (in the finitely-additive sense).

I thought I did take it literally. For instance, Proposition 4.3 of my paper states:

Let XX be a set, Ω\Omega an ultrafilter on XX, and RR a rig. Then XdΩ\int_X - d\Omega is the unique RR-linear map Simp(X,R)RSimp(X,R) \to R such that for all YXY \subseteq X, Xχ YdΩ={1 ifYΩ 0 otherwise. \int_X \chi_Y \,d\Omega = \begin{cases} 1 &\text{if}\,\,Y \in \Omega\\ 0 &\text{otherwise}. \end{cases} (Here Simp(X,R)Simp(X, R) is the set of simple functions from XX to RR.)

Is that different from what you meant?

I agree with you on the notation. Worse, I don’t understand why people write fdμf\,d\mu rather than fμf\mu for the measure defined by (fdμ)(A)= Afdμ. (f\,d\mu)(A) = \int_A f\,d\mu. I see no downside to calling it fμf\mu instead.

Posted by: Tom Leinster on August 25, 2016 1:00 AM | Permalink | Reply to this

Post a New Comment