## July 2, 2011

### Definitions of Ultrafilter

#### Posted by Tom Leinster

One of these days I want to explain a precise sense in which the notion of ultrafilter is inescapable. But first I want to do a bit of historical digging.

If you’re subscribed to Bob Rosebrugh’s categories mailing list, you might have seen one of my historical questions. Here’s another: have you ever seen the following definition of ultrafilter?

Definition 1  An ultrafilter on a set $X$ is a set $U$ of subsets with the following property: for all partitions $X = X_1 \amalg \cdots \amalg X_n$ of $X$ into a finite number $n \geq 0$ of subsets, there is precisely one $i$ such that $X_i \in U$.

This is equivalent to any of the usual definitions. It’s got to be in the literature somewhere, but I haven’t been able to find it. Can anyone help?

Just for fun, here’s a list of other equivalent definitions of ultrafilter. I wouldn’t be at all surprised if there’s some text where someone has compiled a similar list; but again, I haven’t found one.

Throughout, let $X$ be a set. I’ll write $P(X)$ for its power set.

Definition 2  An ultrafilter on $X$ is a set $U$ of subsets with the following property: for all partitions $X = X_1 \amalg X_2 \amalg X_3$ of $X$ into three subsets, there is precisely one $i \in \{1, 2, 3\}$ such that $X_i \in U$.

This is the same as the first definition except that $n$ is constrained to be equal to $3$. You can do the same with $4, 5, \ldots$, but not $2$.

Another way of defining ultrafilter is in the spirit of my recent post on Hadwiger’s theorem. The idea is that an ultrafilter is a way of measuring the “size” of subsets of $X$.

Definition 3  An ultrafilter on $X$ is a function $\phi: P(X) \to \{0, 1\}$ such that (i) $\phi$ is a valuation: $\phi(\emptyset) = 0$ and $\phi(Y \cup Z) = \phi(Y) + \phi(Z) - \phi(Y \cap Z)$ for all $Y, Z \subseteq X$, and (ii) $\phi(X) = 1$.

So an ultrafilter is almost the same thing as a $\{0, 1\}$-valued valuation. The only difference is the extra condition that $\phi(X) = 1$, which could equivalently be replaced with “$\phi$ is not identically zero”.

A valuation is something like a measure. Measures are closely related to integrals. So, we can try to come up with a way of defining ultrafilters so that they look like integrals. I had a go at that a year ago, but I think the following feels more authentically integral-esque.

Choose your favourite rig $k$. I’ll assume that your favourite rig has the property that there are no natural numbers $n \neq 1$ satisfying $n.1 = 1$ in $k$. For example, $k$ might be a field of characteristic zero, or $\mathbb{N}$, or $\mathbb{Z}$.

Definition 4  An ultrafilter on $X$ is a $k$-linear function $\int: \{functions  X \to k   with finite image\} \to k$ such that $\int \lambda = \lambda$ for all $\lambda \in k$ (where the integrand is a constant function) and $\int f \in image(f)$ for all $f$.

Let’s look now at the classic way of defining “ultrafilter”. In fact there are two classic ways, closely related to each other. Before stating either, we need a preliminary definition. A filter on $X$ is a collection $F$ of subsets that is upwards closed ($Y \supseteq Z \in F$ implies $Y \in F$) and closed under finite intersections (or equivalently (i) $Y, Z \in F$ implies $Y \cap Z \in F$, and (ii) $X \in F$).

Definition 5  An ultrafilter on $X$ is a filter $U$ such that the only filters containing $U$ are $P(X)$ and $U$ itself.

In other words, an ultrafilter is a maximal proper filter. There is an alternative way of framing the maximality, which gives the other classic definition:

Definition 6  An ultrafilter on $X$ is a filter $U$ such that for all $Y \subseteq X$, either $Y \in U$ or $X \setminus Y \in U$, but not both.

This is ripe for restating order-theoretically. We’ll use the inclusion ordering on $P(X)$, and we’ll use the two-element totally ordered set $2$. A filter on $X$ is nothing but a map $P(X) \to 2$ of meet-semilattices—that is, a map preserving finite meets ($=$ infs $=$ greatest lower bounds). An ultrafilter is a filter that, viewed as a map, also preserves complements.

Definition 7  An ultrafilter on $X$ is a map $P(X) \to 2$ of Boolean algebras (or equivalently, of lattices).

We’re now getting into the realm of Stone duality (the equivalence between the category of Boolean algebras and the opposite of the category of totally disconnected compact Hausdorff spaces). So it’s no surprise that accompanying the Boolean algebra definition, there’s a topological definition:

Definition 8  An ultrafilter on $X$ is a point of the Stone–Čech compactification of $X$.

Finally, here’s a definition I learned from the $n$Lab page on ultrafilters, but haven’t digested yet:

Definition 9  An ultrafilter on $X$ is a set $U$ of subsets such that for all $Y \subseteq X$, $Y \in U  \Leftrightarrow  \forall n \geq 0, \forall Z_1, \ldots, Z_n \in U,  Y \cap Z_1 \cap \cdots \cap Z_n \neq \emptyset.$

Anyway, the last eight of those nine were mostly for entertainment. What I’d most like is if someone can give me a reference for the first one. Thanks!

Posted at July 2, 2011 11:35 PM UTC

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

### Re: Definitions of Ultrafilter

Can you give me an example of an ultrafilter $U$ on a set $X$ that isn’t of the form $\exists x \in X$ such that $S \in U \Leftrightarrow x \in S$?

Posted by: Jamie Vicary on July 3, 2011 12:47 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

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.

Posted by: Todd Trimble on July 3, 2011 1:43 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

A strengthening of the ultrafilter lemma that I have used not too long ago is the following. For an (ADJECTIVES) cardinal $\kappa$, define a $\kappa$-filter on $X$ to be an upwards-closed collection of “large subsets” of $X$ such that any intersection of fewer than $\kappa$ “large” subsets is again “large”. Then the axiom of choice continues to assure that $\kappa$-ultrafilters (maximal $\kappa$-filters) exist.

With these, you can prove the following: Let $X$ be a set and $\mathbb{F}$ a field with $|\mathbb{F} |\lt |X |$. Then there are maximal ideals in the ring $\mathbb{F}^X$ with residue field $\mathbb{F}$ but that do not correspond to evaluating at any point in $X$. (It is always true, regardless of cardinality, that the maximal ideals of $\mathbb{F}^X$ are in natural bijection with points in the Stone-Cech completion of $X$; the question arose in a project of mine whether you could distinguish the “finite”=principal ones from the “infinite”=nonprincipal ones by looking at the residue field. Of course, when I say “the residue field is $\mathbb{F}$”, what I mean is that I’m asking to understand the $\mathbb{F}$-algebra homomorphisms $\mathbb{F}^X \to \mathbb{F}$.)

Posted by: Theo JF on July 7, 2011 12:15 AM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Incidentally, the fact about residue fields in $\mathbb{F}^X$ is not at all surprising if your first thought is to think of $\mathbb{F}$ as a finite field. But if you are me, then when you fear “let $\mathbb{F}$ be a field” you think “let $\mathbb{F}$ denote $\mathbb{C}$ the field of complex numbers”. And when you think of a set $X$, if you are me you think of $X = \mathbb{N}$ a countable set, or a second-countable topological space. So then it is very surprising that the non-principle residue fields in the Stone-Cech completion can be as small as $\mathbb{F}$. All such residue fields are necessarily models of the first-order theory of $\mathbb{F}$ (for any value of $\mathbb{F}$ — you can let $\mathbb{F}$ denote “Set Theory” if you want), but generically they are nonstandard models thereof. Whereas they can be “standard” when $X$ is very large; also bizarre is that the model becomes “nonstandard” upon sufficiently large base-change.

Of course, Todd knows more about all of this than I do; I mention it for others who might be reading.

Posted by: Theo JF on July 7, 2011 12:28 AM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Then the axiom of choice continues to assure that κ-ultrafilters exist.

Really? I thought that got you into measurable-cardinal territory. Is there some subtlety that I missed in what you said which keeps you in ZFC?

Posted by: Mike Shulman on July 7, 2011 2:51 AM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

I’m guessing some of those subtleties are packed into “ADJECTIVES” — maybe to make sure there are “enough” filters? The Zorn’s Lemma choice mirror would seem then to give you maximal filters… unless there are other subtleties?

Posted by: some guy on the street on July 8, 2011 5:44 AM | Permalink | Reply to this

### Countably complete ultrafilters?

I worried about the same thing that Mike worried about, but at the same time it wasn’t clear where the argument breaks down exactly. So this might be a good opportunity to work through some details. [Edit in hindsight: most of the following is fluff. If you want to cut to the chase, you can skip to the last three paragraphs.]

For example, take the set $X = \mathbb{R}$, and consider the filter of subsets whose complements are at most countable. This is closed under countable intersections. (I’m working in ZFC of course.) But there’s some reason now why this can’t extend to an ultrafilter closed under countable intersections. I “know” this by the following reasoning: (1) any such ultrafilter must be non-principal (since any singleton has empty intersection with some co-countable set); (2) the least uncountable measurable cardinal is the least cardinal that admits a nonprincipal ultrafilter closed under countable intersections; (3) therefore, the cardinality of $\mathbb{R}$ is greater than the first measurable cardinal; (4) this can’t be because uncountable measurable cardinals are strongly inaccessible.

So is that saying that a simple Zorn’s lemma argument breaks down somewhere? There’s one little subtlety that I want to look into first. An ultrafilter is sometimes described as a maximal element in the poset of all proper filters; this is equivalent to being a proper filter $F$ with the property that for any subset $Y \subseteq X$, either $Y$ or its complement $\neg Y$ belong $F$. Okay, the thing I want to check is whether this complementation property still holds for maximal elements in the poset of all proper filters that are closed under countable intersections.

Actually, before I do that, let me review how the proof goes for maximal elements in the poset of all proper filters. Suppose that neither $Y$ nor $\neg Y$ belong to a proper filter $F$. I claim that the empty set can belong to at most one of the collections

$\{Y \cap A: A \in F\}, \qquad \{\neg Y \cap A: A \in F\}.$

[For if the empty set belonged to both, then there exist $A, B \in F$ such that $\emptyset = Y \cap A$ and $\emptyset = \neg y \cap B$. It follows that

$\emptyset = Y \cap A \cap B, \qquad \emptyset = \neg Y \cap A \cap B$

so that by the distributive law, $\emptyset = (Y \cup \neg Y) \cap A \cap B = A \cap B$; this would contradict properness of the filter $F$.] Then, if say the empty set did not belong to the first collection

$F' = \{Y \cap A: A \in F\},$

this would be a proper filter that properly extends $F$. Therefore, $F$ is not a maximal proper filter. It follows that maximal proper filters have the complementation property.

It seems to me that the exact same argument would carry over proper countably complete filters, because if $F$ is closed under countable intersections, then so is this $F'$ we created.

So okay, maximal elements in the poset of countably complete proper filters indeed have the complementation property, and therefore they are ultrafilters that are countably complete.

So although it might seem strange, by my reckoning there must be something wrong specifically with the Zorn’s lemma argument. Can it be that chains in the poset of countably complete proper filters might not have upper bounds??

Oh! That’s obviously it. Or I think it’s “obvious”. Take a countable chain $C_1 \subset C_2 \subset \ldots$ of countably complete (proper) filters. Then the obvious thing to take for the upper bound, which is the union, doesn’t work. In other words, how would we prove that the intersection of sets $A_i$ belongs to the union, if we take each $A_i$ to belong to the difference $C_{i+1} - C_i$?

In different, more high-falutin’ language: filtered colimits along chains commute with the finite limits we need to prove closure of the colimit under finitary operations, but once we need to deal with infinitary operations like countable intersections, filtered colimits of general chains are out the window. Thus we should expect Zorn’s lemma arguments to generally fail where infinitary operations are involved.

Posted by: Todd Trimble on July 8, 2011 5:00 PM | Permalink | Reply to this

### Re: Countably complete ultrafilters?

I made a slight mistake in what I wrote down above: that $F'$ should instead be the upward-closed collection generated by $\{Y \cap A: A \in F\}$. Hopefully there aren’t any other significant errors.

Posted by: Todd Trimble on July 8, 2011 5:13 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

My understanding is that as soon as you have an ultrafilter that is closed under $\kappa$-ary intersections for any infinite cardinal $\kappa$, you have a measurable cardinal. In fact, if $X$ is the smallest set on which such an ultrafilter exists, then its cardinality is measurable.

Posted by: Mike Shulman on July 8, 2011 4:10 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

There’s a paper that touches on aspects of this (i.e. ultrafilters, categories and measurable cardinals):

Reinhard Börger, Coproducts and ultrafilters. Journal of Pure and Applied Algebra 46 (1987), 35–47.

Posted by: Tom Leinster on July 8, 2011 5:10 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Tom, the only lead I have for a reference is that post of Lawvere to the categories list that I mentioned to you in email. Lawvere was remarking that an ultrafilter on $X$ is essentially the same thing as a map

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

which preserves the canonical action of the monoid $\hom([n], [n])$ of endofunctions on a (finite) $n$-element set $[n]$, and that is a reformulation of condition (1) that you wrote down. Here $n \geq 3$.

So I’m guessing that if you can track down that 1960 article of Isbell that Lawvere mentions (but what is it?), you might find what you are looking for. (As an aside, I’ll bet this condition (1) is really ancient folklore.) I’m also guessing that if no one here comes up with a concrete reference, your best bet might be to write Lawvere directly.

Posted by: Todd Trimble on July 3, 2011 1:55 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Thanks, Todd. I suspected that the conversation might roam into the territory of what I wanted to talk about in that later post, but it did so quicker than I’d anticipated :-) Never mind! That fact of Lawvere’s is remarkable.

I’ll ask Lawvere about Definition 1 in a fortnight, at the CT meeting in Vancouver. I think the 1960 article of Isbell’s that he cites must be Adequate subcategories. (Lawvere mentions Ulam measures, which appear on p.548-9 of Isbell.) A discussion of ultrafilters would fit right into Isbell’s paper, but there isn’t one.

I’d bet a large sum against Definition 1 being new. It would seem a bit funny to me if it had the status of folklore, though: it’s so simple that you’d think it would quickly have made its way into the written literature. But stranger things have happened. (Perhaps filters are so important to logicians that they always want to view ultrafilters in that context.)

It occurred to me that I should probably ask this at MathOverflow. The trouble is that MO is too addictive… so I’ll hold off for a while.

Posted by: Tom Leinster on July 3, 2011 2:25 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

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.

Posted by: Tom Leinster on July 3, 2011 4:13 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

The, in my opinion, best way of proving Stone duality is by looking at the functor $F^{op} \to Top^{op}$—here $F$ is the category of finite sets—which views a finite set as a discrete topological space, and applying to it the construction with which we associate the name of Kan.

This yields an adjunction between $[F, Set]$ and $Top^{op}$, even an idempotent adjunction, whose fixpoints on the left, and on the right, are, respectively, the finite limit preserving functors $F \to Set$ (i.e., the boolean algebras), and the Stone spaces; with the equivalence between these categories of fixpoints proving Stone duality, and at the same time exhibiting the category of Stone spaces as the free completion of $F$ under cofiltered limits.

The details of this hinge in part on your Definition 1 and so I would be minded to go hunting for the equivalence of this with the usual definition in the Stone duality literature; probably you have already done so but there is my two penn’orth.

Posted by: Richard Garner on July 4, 2011 9:13 AM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

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.

Posted by: Tom Leinster on July 4, 2011 12:01 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

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?

Posted by: Tom Leinster on July 4, 2011 2:13 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Let’s see: for a finitary algebraic theory $T$, general algebras can be identified with finite-limit-preserving functors

$Alg_{fp}^{op} \to Set$

and in the case where $T$ is the theory of Boolean algebras, $Alg_{fp}$ can be identified with the category of finite Boolean algebras (including the terminal one). The opposite of that category is the category of all finite sets (including the empty one).

The mechanism I was using was to take the Cauchy completion of the category of finitely generated free Boolean algebras. It just so happens that the absolute colimits (coequalizers of pairs $(1_B, e)$ where $e: B \to B$ is an idempotent on a f.g. free Boolean algebra) give you all the objects of $Alg_{fp}$ but one: the terminal one. (It’s a little easier to see that in the dual picture, applying “baby” Stone duality.)

I think the first principle then is that restriction along the inclusion $i: Alg_{f.g.free} \to Alg_{fp}$ induces an equivalence

$FinLim(Alg_{fp}^{op}, Set) \to FinProd(Alg_{f.g.free}^{op}, Set)$

and the second is that that can be “improved” to

$FinLim(Alg_{fp}^{op}, Set) \to FinProd(\widebar{Alg_{f.g.free}}^{op}, Set)$

where the bar overhead denotes Cauchy completion.

Posted by: Todd Trimble on July 4, 2011 4:36 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

I see. Thanks very much.

So we’re shifting between doctrines. $Alg_{f.g.free}^{op}$ is the free finite product category containing an algebra, a.k.a. the Lawvere theory. $Alg_{fp}^{op}$ is the free finite limit category containing an algebra. Hence both the categories

$FinLim(Alg_{fp}^{op}, Set), \quad FinProd(Alg_{f.g.free}^{op}, Set)$

are equivalent to the category of algebras. In particular, they’re equivalent to each other.

I’m idly wondering how hard it would be to prove in a nuts and bolts way that, for functors $F \to Set$, if the restriction to $F_+$ preserves finite products then the original functor preserves finite limits. It’s much nicer to have the conceptual explanation that you’ve supplied, though.

Posted by: Tom Leinster on July 5, 2011 11:54 AM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

According to Forssell, we can think of the theory/model duality as

$FinProd(T, Set) = FinProd(Alg^{op}_{f.g.free}, Set) = Alg$

and

$\mathcal{G}(Alg, Set) = Alg^{op}_{f.g.free} = T,$

where $\mathcal{G}$ is the category of categories with all limits and colimits and with functors which preserve limits, filtered colimits, and regular epimorphisms.

Is there then a category, $\mathcal{H}$, such that

$\mathcal{H}(Alg, Set) = Alg^{op}_fp ?$

Posted by: David Corfield on July 5, 2011 1:14 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Yes, I think we take $\mathcal{H}$ to be the 2-category of locally finitely presentable categories and functors which preserve limits and filtered colimits. Functors $Alg \to Set$ which preserve limits are representable functors $Alg(A, -): Alg \to Set$, and representable functors which preserve filtered colimits here will be those where $A$ is a finitely presented algebra. This comes under the heading of Gabriel-Ulmer duality.

Posted by: Todd Trimble on July 5, 2011 2:56 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

I should have remembered, thanks. You’re probably feeling doomed to have to repeat this to me over and over (see here and here). I’ll get it one of these days.

Posted by: David Corfield on July 5, 2011 3:12 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

I see now that A Duality Relative to a Limit Doctrine deals with the general theory of which this situation is a special case, i.e., dualities for doctrines and what happens when there’s an injection from one to the other as with the finite product and finite limit doctrines (p. 9).

Posted by: David Corfield on July 5, 2011 4:35 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Wait, are you sure that what it’s saying? I got the idea there could be lots of ways of extending a functor $F_+ \to Set$ (in particular, one that preserves finite products) to a functor $F \to Set$, and the latter won’t necessarily preserve finite limits even if the former preserves finite products.

But let me try to do this more carefully. (When I say “carefully”, I mean I’m going to do a boring calculation, which can be cleaned up and made more elegant after the fact. You can skip to the end to see my conclusion.)

To extend a functor $\phi: F_+ \to Set$ to a functor $\phi': F \to Set$, all you need is to define $\phi'(0)$ and maps $\phi'(!_n): \phi'(0) \to \phi(n)$ so that $\phi'(!_n) = \phi(g) \circ \phi'(!_m)$ for every $g: m \to n$ in $F_+$. (That’s enough because you only have to worry about maps going out of $0$, never maps going in to $0$, because $0$ is a strict initial object.) But that data is the same as a set $\phi'(0)$ together with a function

$\phi'(0) \to \lim_m \phi(m)$

and so let’s compute that limit (in the case where $\phi$ preserves finite products). It will be of the form

$\lim_m Bool(2^m, B)$

where $B$ is some Boolean algebra. That’s the same as

$Bool(colim_m 2^m, B)$

where the colimit is computed in the category of Boolean algebras. Applying Stone duality, that colimit inside is the Boolean algebra attached to the Stone space limit $\lim_{m \in F_+} m$.

And that limit sure as heck looks like the empty space to me. Unwinding, that Boolean algebra colimit is the terminal Boolean algebra, which I’ll call $t$. Unwinding some more,

$Bool(t, B)$

is empty, unless $B$ is itself $t$.

Summarizing, we’re in the following funny situation:

• If $B$ is a non-terminal Boolean algebra, then by golly you were right Tom: there’s only one way to extend the corresponding product-preserving functor $\phi: F_+ \to Set$ to a functor $\phi': F \to Set$. Here $\phi'(0)$ is forced to be the empty set.
• But if $B$ is a terminal Boolean algebra, then I was right: the functor $\phi: F_+ \to Set$ is the terminal functor, and there are lots of ways to extend to a functor $\phi': F \to Set$. The only one of these that will be finite-limit-preserving will be the one where $\phi'(0)$ is terminal.
Posted by: Todd Trimble on July 5, 2011 1:18 PM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

Wait, are you sure that’s what it’s saying?

Oops: my mistake. Thanks for clearing it up.

If $B$ is a non-terminal Boolean algebra, then by golly you were right Tom

Pure fluke!

Posted by: Tom Leinster on July 8, 2011 12:07 AM | Permalink | Reply to this

### Re: Definitions of Ultrafilter

After nearly two years, a helpful MathOverflow user has pointed out a place in the literature where Definitions 1 and 2 of ultrafilter appear (and are proved to be equivalent to the usual definition):

Fred Galvin, Alfred Horn, Operations preserving all equivalence relations. Proceedings of the American Mathematical Society 24 (1970), 521–523.

Posted by: Tom Leinster on May 8, 2013 9:22 PM | Permalink | Reply to this

Post a New Comment