## 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 $X$ be a set. An ultrafilter on $X$ is a set $\Omega$ of subsets such that whenever $X$ 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 $X$ be a set. An ultrafilter on $X$ is a set $\Omega$ of subsets such that whenever $X$ 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 $X$ and element $x \in X$, the principal ultrafilter on $x$ is the set of all subsets containing $x$.

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

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

$\int_X f \, d\Omega.$

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

$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 $X$ and $f$ is a function on $X$, the integral of $f$ against $\mu$ is written as $\int_X f \, d\mu$.

So, we’re thinking of an ultrafilter on $X$ as something like a measure on $X$. If probability indicates your degree of belief, an ultrafilter is a probability measure for fundamentalists: everything has probability $0$ or $1$. The subsets of $X$ with measure $1$ are exactly the elements of the ultrafilter; every other subset has measure $0$. A more precise statement is that the ultrafilters on a set $X$ correspond one-to-one with the finitely additive probability measures on $X$, 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 $X$ equipped with an ultrafilter $\Omega$. Given a “nice” function $f$ on $X$, say $f\colon X \to B$, the integral of $f$ against $\Omega$ should be an element of $B$. Here I’ll interpret “nice” as meaning simply that $B$ 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 $X$ is $1$), the integral of a constant function should be that constant.
• If two functions $f$ and $g$ are equal almost everywhere (that is, the set of points of $X$ 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 $\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 $B$ 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\colon X \to B$, you can imagine each “voter” $x \in X$ choosing a single element $f(x)$ from the set $B$ of all possible “options”. Any ultrafilter $\Omega$ on $X$ thinks that there’s one option chosen by almost all of the voters, namely, $\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 $\int_X f \, d\Omega \in B$. This is always unfair, but if $\Omega$ is the principal ultrafilter on some $x \in X$, it’s spectacularly unfair: the outcome of the election is simply the option chosen by the privileged voter $x$.

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 $X$ be any set. Whenever we have an ultrafilter $\Omega$ on $X$, we can integrate against $\Omega$. The operation of integration turns functions from $X$ to a finite set $B$ into elements of $B$:

$\int_X - \, d\Omega \colon [X, B] \to B.$

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

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

$\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 $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$, evaluated at $X$. That is: let $G$ be the inclusion functor $\mathbf{FinSet} \hookrightarrow \mathbf{Set}$, and let $T^G$ be the codensity monad of $G$. Then (by definition, if you like)

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

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

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

$\Omega \mapsto \int_X - \, d\Omega.$

In fact, $U$ 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 $U \to T^G$ respects the monad structures.

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

Theorem  The codensity monad of the inclusion $\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 $X$ as a lattice homomorphism from the power set of $X$ 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 $\mathbf{B}$ be a full subcategory of $\mathbf{FinSet}$ containing at least one set with at least 3 elements. Then the codensity monad of the inclusion $\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 $2$.

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

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

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

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

### 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)$ 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 $FinSet$ is actually codense in $Set$? What do $T^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 $\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?

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 $C$ of candidates, and a finite set $X$ of voters.

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

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

We also have a functor

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

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

For the purposes of Arrow’s theorem, a voting system is a natural transformation $\int \colon [X, O] \to O$ such that $\int R = R$ for any $R \in O(C)$. Here, the integrand “$R$” is the constant function $X \to O(C)$ with value $R$, 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 $X$ of voters has at least one element and the set $C$ 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^{**}$ of the form “evaluate at some particular $x$”.

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 $B$ in the last theorem of my post, required to have at least three elements, is more like the set $O(C)$ than the set $C$ itself. Then again, saying that $B$ has more than two elements is equivalent to saying that $O(C)$ has more than two elements…

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 $B$ in the last theorem of my post, required to have at least three elements, is more like the set $O(C)$ than the set $C$ itself. Then again, saying that $B$ has more than two elements is equivalent to saying that $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 $C$ be a finite set (thought of as the set of candidates in an election). Write $P(C)$ for its power set, ordered by inclusion. Write $\mathbf{FinSet}_{\neq\emptyset}$ for the category of nonempty finite sets. There is a functor

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

sending $D \subseteq C$ to the set of total orders on $D$, and $O$ has a codensity monad $(T, \eta, \mu)$.

A statement equivalent to Arrow’s theorem is:

Theorem (Arrow)  If $|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 $V$ be a set, and write $T$ for the codensity monad of the full subcategory of $\mathbf{Set}$ consisting of the object $V$ alone. Then a $V$-generalized point of $X$ is precisely an element of $T(X)$.

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

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 $\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?

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 $(\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 $\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 $B$, yet we don't know how to multiply elements of $B$ 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 $0$ and $1$, and we know how to multiply anything (an element $b$ of $B$ or anything else whatsoever) by $0$ or $1$: the result is $0$ or $b$ itself, respectively. And we know how to add $0$ to any $b$: the result is $b$. And we know how to take a limit of an eventually constant net (with eventual value $b$): the result is again $b$. And these are the only operations that appear in this case!

So while $B$ 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 $\int_X f \,d\Omega$ when $\Omega$ is an arbitrary measure on $X$, it does have the structure necessary to define that integral when $\Omega$ is an ultrafilter. (That $B$ 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 ‘$\int_X f \,d\Omega$’, I'll annoy all of you by pointing out that this should be written ‘$\int_X f \Omega$’, the ‘d’ being superfluous notation ultimately coming from mistakenly identifying the variable $x$ in the classical $\int_a^b f(x) \,d{x}$ with Lebesgue measure when in fact it is $d{x}$ (or really even $|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 $\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 $\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 $X$ be a set, $\Omega$ an ultrafilter on $X$, and $R$ a rig. Then $\int_X - d\Omega$ is the unique $R$-linear map $Simp(X,R) \to R$ such that for all $Y \subseteq X$, $\int_X \chi_Y \,d\Omega = \begin{cases} 1 &\text{if}\,\,Y \in \Omega\\ 0 &\text{otherwise}. \end{cases}$ (Here $Simp(X, R)$ is the set of simple functions from $X$ to $R$.)

Is that different from what you meant?

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

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

Post a New Comment