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.

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 XX is a set UU of subsets with the following property: for all partitions X=X 1⨿⨿X n X = X_1 \amalg \cdots \amalg X_n of XX into a finite number n0n \geq 0 of subsets, there is precisely one ii such that X iUX_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 XX be a set. I’ll write P(X)P(X) for its power set.

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

This is the same as the first definition except that nn is constrained to be equal to 33. You can do the same with 4,5,4, 5, \ldots, but not 22.

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

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

So an ultrafilter is almost the same thing as a {0,1}\{0, 1\}-valued valuation. The only difference is the extra condition that ϕ(X)=1\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 kk. I’ll assume that your favourite rig has the property that there are no natural numbers n1n \neq 1 satisfying n.1=1n.1 = 1 in kk. For example, kk might be a field of characteristic zero, or \mathbb{N}, or \mathbb{Z}.

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

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 XX is a collection FF of subsets that is upwards closed (YZFY \supseteq Z \in F implies YFY \in F) and closed under finite intersections (or equivalently (i) Y,ZFY, Z \in F implies YZFY \cap Z \in F, and (ii) XFX \in F).

Definition 5  An ultrafilter on XX is a filter UU such that the only filters containing UU are P(X)P(X) and UU 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 XX is a filter UU such that for all YXY \subseteq X, either YUY \in U or XYUX \setminus Y \in U, but not both.

This is ripe for restating order-theoretically. We’ll use the inclusion ordering on P(X)P(X), and we’ll use the two-element totally ordered set 22. A filter on XX is nothing but a map P(X)2P(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 XX is a map P(X)2P(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 XX is a point of the Stone–Čech compactification of XX.

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

Definition 9  An ultrafilter on XX is a set UU of subsets such that for all YXY \subseteq X, YU  n0,Z 1,,Z nU, YZ 1Z n. 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

25 Comments & 0 Trackbacks

Re: Definitions of Ultrafilter

Can you give me an example of an ultrafilter UU on a set XX that isn’t of the form xX\exists x \in X such that SUxSS \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 xx 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 XX to be an upwards-closed collection of “large subsets” of XX 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 XX be a set and 𝔽\mathbb{F} a field with |𝔽|<|X||\mathbb{F} |\lt |X |. Then there are maximal ideals in the ring 𝔽 X\mathbb{F}^X with residue field 𝔽\mathbb{F} but that do not correspond to evaluating at any point in XX. (It is always true, regardless of cardinality, that the maximal ideals of 𝔽 X\mathbb{F}^X are in natural bijection with points in the Stone-Cech completion of XX; 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 𝔽 X𝔽\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 𝔽 X\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 XX, if you are me you think of X=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 XX 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=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 FF with the property that for any subset YXY \subseteq X, either YY or its complement ¬Y\neg Y belong FF. 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 YY nor ¬Y\neg Y belong to a proper filter FF. I claim that the empty set can belong to at most one of the collections

{YA:AF},{¬YA:AF}.\{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,BFA, B \in F such that =YA\emptyset = Y \cap A and =¬yB\emptyset = \neg y \cap B. It follows that

=YAB,=¬YAB\emptyset = Y \cap A \cap B, \qquad \emptyset = \neg Y \cap A \cap B

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

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

this would be a proper filter that properly extends FF. Therefore, FF 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 FF is closed under countable intersections, then so is this FF' 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 1C 2C_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 iA_i belongs to the union, if we take each A iA_i to belong to the difference C i+1C iC_{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 FF' should instead be the upward-closed collection generated by {YA:AF}\{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 XX 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 XX is essentially the same thing as a map

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

which preserves the canonical action of the monoid hom([n],[n])\hom([n], [n]) of endofunctions on a (finite) nn-element set [n][n], and that is a reformulation of condition (1) that you wrote down. Here n3n \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 UU on XX as a map

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

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

I’ll explain both this comment and how Lawvere’s characterization works. An ultrafilter UU on XX is usually construed as a set of subsets of XX. We can think of the subsets that belong to UU as “large”, or “measure 1”, and the subsets that don’t belong to UU 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 kk where the integrable functions are going to take their values, and where the integrals themselves will also live. Our integral should certainly satisfy

χ Adϕ=ϕ(A) \int \chi_A \;d\phi = \phi(A)

for all AXA \subseteq X, where χ A\chi_A is the characteristic function of AA. 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 dϕ\int -\;d\phi, without any “extend by linearity” business. It’s simply this: given f:Xkf: X \to k with finite image, fdϕ\int f\;d\phi is the unique element of kk such that

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

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

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

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

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

uniquely determined by

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

whenever f[n] Xf \in [n]^X. It’s End([n])End([n])-invariant, that is, θfdU=θ(fdU)\int \theta\circ f\;d U = \theta(\int f\; d U) whenever θ:[n][n]\theta: [n] \to [n]. That’s how an ultrafilter gives rise to an End([n])End([n])-invariant map [n] XX[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 n3n\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 opTop opF^{op} \to Top^{op}—here FF 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][F, Set] and Top opTop^{op}, even an idempotent adjunction, whose fixpoints on the left, and on the right, are, respectively, the finite limit preserving functors FSetF \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 FF 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 FSetF \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 TT, there is an equivalence of categories

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

where T-Alg fpT\text{-}Alg_{fp} is the full subcategory of T-AlgT\text{-}Alg consisting of just the finitely presentable TT-algebras, and FinLim(,)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 TT-algebra AA, you get a finite limit preserving functor

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

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

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

Bool fpF op Bool_{fp} \simeq F^{op}

where Bool fpBool_{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

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

where BoolBool 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 FSetF \to Set, where FF 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 +SetF_+ \to Set, where F +F_+ is the category of nonempty finite sets.

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

Without thinking about it, I lazily assume that the equivalence

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

is restriction. If so, this tells us that a functor FSetF \to Set preserves finite limits just as long as its restriction to F +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 TT, general algebras can be identified with finite-limit-preserving functors

Alg fp opSetAlg_{fp}^{op} \to Set

and in the case where TT is the theory of Boolean algebras, Alg fpAlg_{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)(1_B, e) where e:BBe: B \to B is an idempotent on a f.g. free Boolean algebra) give you all the objects of Alg fpAlg_{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.freeAlg fpi: Alg_{f.g.free} \to Alg_{fp} induces an equivalence

FinLim(Alg fp op,Set)FinProd(Alg f.g.free op,Set)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)FinProd(Alg f.g.free¯ op,Set)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 opAlg_{f.g.free}^{op} is the free finite product category containing an algebra, a.k.a. the Lawvere theory. Alg fp opAlg_{fp}^{op} is the free finite limit category containing an algebra. Hence both the categories

FinLim(Alg fp op,Set),FinProd(Alg f.g.free op,Set) 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 FSetF \to Set, if the restriction to F +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 f.g.free op,Set)=Alg FinProd(T, Set) = FinProd(Alg^{op}_{f.g.free}, Set) = Alg

and

𝒢(Alg,Set)=Alg f.g.free op=T, \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

(Alg,Set)=Alg fp op? \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 AlgSetAlg \to Set which preserve limits are representable functors Alg(A,):AlgSetAlg(A, -): Alg \to Set, and representable functors which preserve filtered colimits here will be those where AA 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 +SetF_+ \to Set (in particular, one that preserves finite products) to a functor FSetF \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 ϕ:F +Set\phi: F_+ \to Set to a functor ϕ:FSet\phi': F \to Set, all you need is to define ϕ(0)\phi'(0) and maps ϕ(! n):ϕ(0)ϕ(n)\phi'(!_n): \phi'(0) \to \phi(n) so that ϕ(! n)=ϕ(g)ϕ(! m)\phi'(!_n) = \phi(g) \circ \phi'(!_m) for every g:mng: m \to n in F +F_+. (That’s enough because you only have to worry about maps going out of 00, never maps going in to 00, because 00 is a strict initial object.) But that data is the same as a set ϕ(0)\phi'(0) together with a function

ϕ(0)lim mϕ(m)\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 mBool(2 m,B)\lim_m Bool(2^m, B)

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

Bool(colim m2 m,B)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 mF +m\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 tt. Unwinding some more,

Bool(t,B)Bool(t, B)

is empty, unless BB is itself tt.

Summarizing, we’re in the following funny situation:

  • If BB 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 ϕ:F +Set\phi: F_+ \to Set to a functor ϕ:FSet\phi': F \to Set. Here ϕ(0)\phi'(0) is forced to be the empty set.
  • But if BB is a terminal Boolean algebra, then I was right: the functor ϕ:F +Set\phi: F_+ \to Set is the terminal functor, and there are lots of ways to extend to a functor ϕ:FSet\phi': F \to Set. The only one of these that will be finite-limit-preserving will be the one where ϕ(0)\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 BB 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