The n-Category Café

No one can, really; the existence of such a nonprincipal ultrafilter comes down to a highly nonconstructive (weak) form of the axiom of choice.

A principal ultrafilter is one generated by a single element $x$ in the sense you wrote down. Being a nonprincipal ultrafilter is equivalent (in Zermelo set theory, say, without assuming choice) to being an ultrafilter that contains the filter of cofinite sets i.e., complements of finite sets. In particular, a nonprincipal ultrafilter exists only on an infinite set.

The usual way to prove existence of nonprincipal ultrafilters is to prove a more general lemma, the ultrafilter lemma, which proves that any filter can be extended to an ultrafilter. The standard proof uses the axiom of choice. While it is not quite as strong as the axiom of choice, there are certainly models of ZF where the ultrafilter lemma fails.

The ultrafilter lemma is quite a handy thing; it is at the bottom of, for example, the compactness theorem for propositional and first-order logic, the construction of ultrapowers and nonstandard reals, and many other things.

Incidentally, Definition 4 suggests that if we join Lawvere in thinking of an ultrafilter $U$ on $X$ as a map

$$[n]^X \to [n]$$

of $End([n])$-sets, then this map should be thought of as integration against $U$. (Here $n \geq 3$ is a fixed natural number.)

I’ll explain both this comment and how Lawvere’s characterization works. An ultrafilter $U$ on $X$ is usually construed as a set of subsets of $X$. We can think of the subsets that belong to $U$ as “large”, or “measure 1”, and the subsets that don’t belong to $U$ as “small”, or “measure zero”. The “measure” idea is made precise in Definition 3, where the measure (really, valuation) is called $\phi$.

Now let’s try to build some kind of integral from this measure $\phi$. We choose a rig $k$ where the integrable functions are going to take their values, and where the integrals themselves will also live. Our integral should certainly satisfy

$$\int \chi_A \;d\phi = \phi(A)$$

for all $A \subseteq X$, where $\chi_A$ is the characteristic function of $A$. And it turns out that, in the normal way of things, we can extend linearly to get an integral defined on a reasonably large class of functions (Definition 5).

But what I didn’t say before is that there’s also a direct way of defining $\int -\;d\phi$, without any “extend by linearity” business. It’s simply this: given $f: X \to k$ with finite image, $\int f\;d\phi$ is the unique element of $k$ such that

$$f^{-1}\Bigl(\int f\;d\phi\Bigr) \in U.$$

(Definition 1 guarantees that there is a unique element of $k$ with this property.) And this makes no reference to the rig structure of $k$!

The measure $\phi$ was derived from the ultrafilter $U$ in a very simple way: it’s just the characteristic function of $U$, in fact. So we could reasonably write $\int -\;d U$ instead of $\int -\; d\phi$.

Finally, let’s come back to Lawvere’s characterization of ultrafilters. We’ve fixed a natural number $n \geq 3$. Starting from an ultrafilter $U$ on $X$, we get a map

$$\int - \;d U: [n]^X \to [n]$$

uniquely determined by

$$f^{-1}\Bigl(\int f\; d U\Bigr) \in U$$

whenever $f \in [n]^X$. It’s $End([n])$-invariant, that is, $\int \theta\circ f\;d U = \theta(\int f\; d U)$ whenever $\theta: [n] \to [n]$. That’s how an ultrafilter gives rise to an $End([n])$-invariant map $[n]^X \to X$.

For the converse, you’re trying to turn an “integral” into a “measure”. As usual, the idea is to define the measure of a subset as the integral of its characteristic function. I’ll skip the details, but here’s where you need the assumption $n\geq 3$: it’s to prove that the resulting “measure” really is an ultrafilter, which you can do by applying Definition 2.

and applying to it the construction with which we associate the name of Kan.

Ah, Richard. Every sentence is golden.

I like your way of looking at Stone duality. But maybe it would be kind to expand on this part:

the finite limit preserving functors $F \to Set$ (i.e., the boolean algebras)

Let me try to guess what you had in mind when you wrote this. For any finitary algebraic theory $T$, there is an equivalence of categories

$$T\text{-}Alg \simeq FinLim(T\text{-}Alg_{fp}^{op}, Set)$$

where $T\text{-}Alg_{fp}$ is the full subcategory of $T\text{-}Alg$ consisting of just the finitely presentable $T$-algebras, and $FinLim(-, -)$ is the full subcategory of the functor category consisting of just the finite limit preserving functors.

(In fact, this equivalence is also obtained by applying the construction with which we associate the name of Kan. Explicitly, given an arbitrary $T$-algebra $A$, you get a finite limit preserving functor

$$Hom(-, A): T\text{-}Alg_{fp}^{op} \to Set.$$

This process $A \mapsto Hom(-, A)$ turns out to define an equivalence between $T$-algebras and finite limit preserving presheaves on $T\text{-}Alg_{fp}$.)

That’s one half of what I assume you had in mind. The other half is that

$$Bool_{fp} \simeq F^{op}$$

where $Bool_{fp}$ is the category of finitely presentable Boolean algebras. It’s fairly easy to see that a Boolean algebra is finitely presentable if and only if it’s finite, so what this says is that the category of finite Boolean algebras is dual to the category of finite sets: “baby Stone duality”.

Putting the two halves together, we get equivalences

$$Bool \simeq FinLim(Bool_{fp}^{op}, Set) \simeq FinLim(F, Set)$$

where $Bool$ is the category of Boolean algebras.

Have I guessed your thinking right?

so I would be minded to go hunting for the equivalence of this with the usual definition in the Stone duality literature

Thanks. That’s a good idea.

Here’s a thing. Richard used the fact that a Boolean algebra amounts to a finite limit preserving functor $F \to Set$, where $F$ is the category of finite sets. But Todd has been writing about the fact that a Boolean algebra amounts to a finite product preserving functor $F_+ \to Set$, where $F_+$ is the category of nonempty finite sets.

So, a finite limit preserving functor $F \to Set$ is the same thing as a finite product preserving functor $F_+ \to Set$.

Without thinking about it, I lazily assume that the equivalence

$$FinLim(F, Set) \simeq FinProd(F_+, Set)$$

is restriction. If so, this tells us that a functor $F \to Set$ preserves finite limits just as long as its restriction to $F_+$ preserves finite products. Is that obvious from first principles?