Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 30, 2012

Where Do Ultraproducts Come From?

Posted by Tom Leinster

I move jobs tomorrow: from Glasgow to Edinburgh, city of James Clerk Maxwell, Arthur Conan Doyle, Robert Louis Stevenson and Dolly the Sheep. But before I go, I want to give you the fourth and final post on my new paper, Codensity and the ultrafilter monad.

It’s not like the first three. There, I explained some definite facts: what codensity monads are, and how they naturally throw up various interesting mathematical structures. But this post contains nothing new except speculation. Specifically, I’ll speculate that codensity monads naturally throw up the notion of ultraproduct — though at present, I can’t see how.

Introduction to ultraproducts

Before I speculate about the connection with codensity, I’ll explain what ultraproducts are. If you already know, skip to the next heading, near the end of the post.

Ultraproducts are probably most associated with logic, but the definition is, in fact, purely set-theoretic.

Let XX be a set, Ω\Omega an ultrafilter on XX, and S =(S x) xXS_\bullet = (S_x)_{x \in X} a family of sets. Since Ω\Omega is a set of subsets of XX, it’s ordered by inclusion. There’s a functor (Ω,) opSet(\Omega, \subseteq)^{op} \to \mathbf{Set} defined on objects by Y yYS yY \mapsto \prod_{y \in Y} S_y, and on morphisms by projection. The ultraproduct

ΩS \prod_\Omega S_\bullet

is the colimit of this functor.

Explicitly, an element of ΩS \prod_\Omega S_\bullet is an equivalence class of pairs (Y,(s y) yY)(Y, (s_y)_{y \in Y}) where YΩY \in \Omega, s yS ys_y \in S_y, and the equivalence relation \sim is defined by

(s y) yY(t z) zZ{xYZ:s x=t x}Ω. (s_y)_{y \in Y} \sim (t_z)_{z \in Z} \iff \{ x \in Y \cap Z : s_x = t_x \} \in \Omega.

Let’s agree to call a subset of XX large if it belongs to the ultrafilter Ω\Omega, and small otherwise. Then an element of the ultraproduct is an equivalence class of families (s y) yY yYS y(s_y)_{y \in Y} \in \prod_{y \in Y} S_y indexed over some large subset YY of XX, with two such families identified if they agree in a large number of coordinates.

(If all the sets S xS_x are nonempty then there’s a slightly simpler explicit description, but that won’t be relevant here.)

 

Trivial example  The only easy examples of ultrafilters are the principal ultrafilters. In that case, ultraproducts are really trivial: when Ω\Omega is the principal ultrafilter on an element xx of XX, the ultraproduct ΩS \prod_\Omega S_\bullet is simply S xS_x.

 

A few of us discussed ultraproducts in response to David’s post a few weeks ago. Moshe Kamensky expressed the opinion that in model theory, ultraproducts are mostly a technical tool, and one can find similar opinions expressed in the well-known book Model Theory by Wilfrid Hodges. On the other hand, the equally well-known book Model Theory by Chang and Keisler devotes one entire chapter out of seven to ultraproducts.

So, I don’t know whether there’s a consensus among model theorists as to the importance of ultraproducts. But I’ll try to explain what I understand to be their importance, using a bit of categorical language.

As the definition above shows, ultraproducts are constructed using two kinds of (co)limit in Set\mathbf{Set}: products, and colimits over (Ω,) op(\Omega, \subseteq)^{op}. This latter category is filtered, because Ω\Omega is a filter. So, ultraproducts are constructed out of products and filtered colimits. It follows that the functor

Ω:Set XSet \prod_\Omega \colon \mathbf{Set}^X \to \mathbf{Set}

preserves finite limits.

Actually, everything so far is true if Ω\Omega is a mere filter, not necessarily an ultrafilter. (I know I haven’t defined filters, only ultrafilters. If you don’t know what filters are, it doesn’t really matter — all you need to know is that they’re more general than ultrafilters.) Now using the fact that Ω\Omega is an ultrafilter, we can show that the functor

Ω:Set XSet \prod_\Omega \colon \mathbf{Set}^X \to \mathbf{Set}

also preserves finite coproducts. It has other exactness properties too (e.g. it preserves image factorizations), but I think they all follow quite easily from the fact that it preserves finite limits and finite coproducts.

I’ll now explain the kind of thing that ultraproducts can do, by means of an extended example.

 

Extended example  This is all about fields. Fix an ultrafilter Ω\Omega on a set XX. As noted above, this determines a functor Ω:Set XSet\prod_\Omega \colon \mathbf{Set}^X \to \mathbf{Set}, which preserves, among other things, finite products. Since the theory of (commutative) rings is a finite product theory, there’s an induced functor

Ω:Ring XRing. \prod_\Omega \colon \mathbf{Ring}^X \to \mathbf{Ring}.

If (R x) xX(R_x)_{x \in X} is a family of rings then the ring structure on the set ΩR \prod_\Omega R_\bullet is the obvious, pointwise, structure.

This in turn restricts to a functor

Ω:Field XField. \prod_\Omega \colon \mathbf{Field}^X \to \mathbf{Field}.

Why? There’s probably a nice abstract argument, but — mainly for the sake of practising with the definition — here’s an explicit one. (Skip this paragraph if you’re not in the mood for details.) The claim is that if (k x) xX(k_x)_{x \in X} is an XX-indexed family of fields then the ring Ωk \prod_\Omega k_\bullet is also a field. So, take a nonzero element of Ωk \prod_\Omega k_\bullet. Such an element is the equivalence class of some family (c y) yY(c_y)_{y \in Y} where c yk yc_y \in k_y and YXY \subseteq X is large. Since it’s nonzero, a large number of the elements c yk yc_y \in k_y are nonzero and therefore invertible. Their inverses c y 1c_y^{-1} then determine an element of Ωk \prod_\Omega k_\bullet, and it’s easy to show that it’s the inverse of our original element. That does it.

We’ve just shown that ultraproducts have a nice preservation property that ordinary products don’t. The product of fields is most definitely not a field!

Next, let’s think about the characteristics of the fields involved. I won’t prove a systematic result on the characteristic of the ultraproduct Ωk \prod_\Omega k_\bullet in terms of the characteristics of the individual fields k xk_x; I’ll just do a single example.

Suppose that X={1,2,3,}X = \{1, 2, 3, \ldots\}, and that the fields k 1,k 2,k 3,k_1, k_2, k_3, \ldots have respective characteristics 2,3,5,2, 3, 5, \ldots — so we’ve got one field of each prime characteristic.

Also assume that our ultrafilter Ω\Omega on XX is nonprincipal. This means that every singleton {x}\{x\} is small. But in an ultrafilter, a finite union of small sets is always small, so it’s equivalent to say that every finite subset of XX is small.

Now, what’s the characteristic of the field Ωk \prod_\Omega k_\bullet?

Well, the multiplicative unit of Ωk \prod_\Omega k_\bullet is

[(1,1,1,)] [(1, 1, 1, \ldots)]

where (1,1,)k 1×k 2×(1, 1, \ldots) \in k_1 \times k_2 \times \cdots and the square brackets mean equivalence class. So, when nn is a positive integer, the element “n1n\cdot 1” of Ωk \prod_\Omega k_\bullet is

[(n1,n1,n1,)] [(n\cdot 1, n\cdot 1, n\cdot 1, \ldots)]

where the iith term n1n \cdot 1 is an element of k ik_i. On the other hand, the zero of Ωk \prod_\Omega k_\bullet is

[(0,0,0,)]. [(0, 0, 0, \ldots)].

So n1=0n \cdot 1 = 0 in Ωk \prod_\Omega k_\bullet if and only if n1=0n \cdot 1 = 0 in a large number of the fields k 1k_1, k 2k_2, k 3k_3, …. But that’s never the case: if n1n\cdot 1 in k ik_i then the iith prime divides nn, so there are only finitely many such ii, and finite subsets of XX are small.

So, Ωk \prod_\Omega k_\bullet has characteristic zero.

Here’s a dramatic way to think about it. Imagine, implausibly, that we know no examples of fields of characteristic zero. Maybe the only fields we know are those of the form /p\mathbb{Z}/p\mathbb{Z} for prime pp. Then the ultraproduct construction automatically provides us with an example — in fact, many examples — of a field of characteristic zero.

 

That’s the end of the extended example. Those who know about these things will have recognized, barely concealed beneath its surface, two important theorems:

  • Łoś’s theorem, also known as the fundamental theorem of ultraproducts. If each of the sets S xS_x is a structure (of a given signature) in the sense of model theory, then so too is ΩS \prod_\Omega S_\bullet, in a natural way. (For example, if each of the sets S xS_x is a ring then so is ΩS \prod_\Omega S_\bullet.) Łoś’s theorem states that a first-order statement is true in ΩS \prod_\Omega S_\bullet if and only if it is true in a large number of the structures S xS_x.
  • The compactness theorem, which states that if Γ\Gamma is a set of first-order statements and each finite subset of Γ\Gamma has a model, then Γ\Gamma itself has a model. For example, let Δ\Delta be the set of axioms for a field. Just knowing about the fields /p\mathbb{Z}/p\mathbb{Z} tells us that each finite subset of Δ{210,310,510,} \Delta \cup \{ 2\cdot 1 \neq 0, 3 \cdot 1 \neq 0, 5 \cdot 1 \neq 0, \ldots \} has a model. Using ultraproducts, we constructed from these fields of positive characteristic a field of characteristic zero. That’s hardly an impressive achievement, but it points to a general fact: the compactness theorem can easily be proved by following the same pattern, using ultraproducts. And the compactness theorem can be used to prove much more startling results than the trivial one about characteristic zero: see Wikipedia, for instance.

Speculation on ultraproducts and codensity

Suppose, once more, that we have an ultrafilter Ω\Omega on a set XX.

Back here, I described integration against an ultrafilter. Integration against Ω\Omega defines, for each finite set BB, a function

dΩ:B XB. \int - \, d \Omega \colon B^X \to B.

It’s natural in BB, meaning that given any map BCB \to C of finite sets, the evident square commutes.

Just now, I reviewed the definition of ultraproduct with respect to an ultrafilter. I only described ultraproducts of families of sets, but the definition works just as well when Set\mathbf{Set} is replaced by any other category with products and filtered colimits. Taking ultraproducts with respect to Ω\Omega defines, for each such category B\mathbf{B}, a functor

Ω:B XB. \prod_\Omega \colon \mathbf{B}^X \to \mathbf{B}.

It’s natural in B\mathbf{B}, meaning that given any functor BC\mathbf{B} \to \mathbf{C} preserving products and filtered colimits, the evident square commutes up to canonical isomorphism.

This suggests that the process of taking ultraproducts is a categorification of the process of integrating against an ultrafilter. Can we make that precise? I don’t know.

Ordered sets sometimes provide a stepping stone between sets (0-categories) and categories (1-categories). Let BB be a finite lattice. As a set, BB is finite, and as a category, BB has products and filtered colimits. It’s easy to see that the processes of integration and ultraproduct coincide in BB: whenever (b x) xX(b_x)_{x \in X} is a family of elements of BB,

Ωb = Ωb . \int_\Omega b_\bullet = \prod_\Omega b_\bullet.

That’s encouraging.

Back here, we saw that ultrafilters on XX not only give rise to, but actually correspond one-to-one with, natural families of functions

(B XB) BFinSet. \Bigl( B^X \to B \Bigr)_{B \in \mathbf{FinSet}}.

In other language, this says that the ultrafilter monad is the codensity monad of the inclusion functor FinSetSet\mathbf{FinSet} \hookrightarrow \mathbf{Set}.

Are there similar statements for ultraproducts? That is, do ultrafilters on XX not only give rise to, but actually correspond one-to-one with, natural families of maps

(B XB) \Bigl( \mathbf{B}^X \to \mathbf{B} \Bigr)

indexed over ‘nice’ categories B\mathbf{B}? And can we rephrase this correspondence as a neat assertion about a codensity monad? Again, I don’t know.

It’s not obvious to me how to see this idea through. Among other things, the question arises of distinguishing between ultrafilters and general filters, which suggests that something’s wrong. Perhaps I haven’t got the right level of generality. But given the close formal resemblance between ultraproducts and integration against an ultrafilter, it’s hard to resist speculating. I hope someone will be able to see a clear path through.

Posted at September 30, 2012 5:11 AM UTC

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

36 Comments & 1 Trackback

Re: Where Do Ultraproducts Come From?

I’m not sure how this ties into the codensity monad story, but the following observation about the connection between filters and functors Set/κSet\mathbf{Set}/\kappa \to\mathbf{Set} may be helpful.

A functor F:Set/κSetF:\mathbf{Set}/\kappa \to\mathbf{Set} induced by a filter has the fibration-like property that every map XFYX\to F Y has a lifting XYX'\to Y. This weak lifting property requires the axiom of choice and there may be no terminal lifting, so the functor is not always actually a fibration.

Every left exact functor induces a filter: the filter of subterminal that are mapped to the terminal object. If a left exact functor F:Set/κSetF:\mathbf{Set}/\kappa \to\mathbf{Set} has the weak lifting property, it is isomorphic to the left exact functor induced by its filter.

Posted by: Wouter Stekelenburg on September 30, 2012 2:32 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

That could be a start — thanks a lot. I’ll need to think about that.

(Incidentally, I fixed your Latex, which originally came out raw — lots of visible dollar signs etc. If you want to use Latex in a comment, you have to select a suitable option from the dropdown menu marked “Text Filter” in the comment window. Any option containing the word “itex” will do. I use “itex to MathML with parbreaks”.)

Posted by: Tom Leinster on September 30, 2012 2:37 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

I guess the result in your last sentence implies that ultrafilters on a set KK correspond one-to-one with functors Set KSet\mathbf{Set}^K \to \mathbf{Set} that (i) preserve finite limits, (ii) preserve finite coproducts, and (iii) have the weak lifting property that you describe. The correspondence is given by ultraproducts: an ultrafilter Ω\Omega on KK corresponds to the functor Ω:Set KSet\prod_\Omega \colon \mathbf{Set}^K \to \mathbf{Set}.

That’s good, but I have two reservations. First, I don’t like this weak lifting property — it just seems ad hoc. Second, we’re not taking advantage of the fact that ultraproducts are defined on lots of categories, not just Set\mathbf{Set}. But maybe this is one of those nice situations where two problems cancel each other out?

Posted by: Tom Leinster on September 30, 2012 3:18 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

So what is, say, the codensity monad of the forgetful functor from ‘categories with finite limits and filtered colimits’ to ‘categories with finite limits’?

Posted by: Mike Shulman on September 30, 2012 4:37 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Does this functor have a left adjoint? (Or at least, a left adjoint in a suitable 2-dimensional sense?) If so, the codensity monad is the monad induced by the adjunction.

Let’s see. The forgetful functor from (categories with filtered colimits) to (categories) does have a left adjoint, at least on small categories, and it sends A\mathbf{A} to Flat(A op,Set)Flat(\mathbf{A}^{op}, Set). If A\mathbf{A} has finite limits, does Flat(A op,Set)Flat(\mathbf{A}^{op}, Set)? Without thinking about it too hard, I suppose it does.

The answer to your question must depend on whether “categories with finite limits and filtered colimits” secretly includes the condition that they commute.

Wait — isn’t it true on general principles that the forgetful functor you mention is 2-monadic?

Posted by: Tom Leinster on September 30, 2012 8:17 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

I haven’t thought about this very much, but the direction of your questions suggests that maybe we ought to impose some sort of finiteness condition on our “categories with finite limits and filtered colimits” (in addition to a commutativity). Maybe they should be locally finitely presentable.

Posted by: Mike Shulman on October 1, 2012 12:41 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

One tiny bit evidence that ultraproducts are not the most natural way for category theoretic model theory is that Awodey and Forssell avoid them in their duality theorem for first-order logic in First-Order Logical Duality.

Just like the Boolean Algebra (syntax for propositional logic)-Stone space (of models of propositional theories) duality, they develop a duality between the syntactic categories for first-order theories (Boolean coherent categories) and topological groupoids (of models).

…the categories of models of coherent theories can not, in general, be expected to have more structure than those for classical first-order theories. What they do have are ultra-products. Although ultra-products are not an intrinsic feature of categories of models (for coherent theories), in the sense that they are not a categorical invariant, Makkai [7] shows that model categories and the category of sets can be equipped with a notion of ultra-product structure—turning them into so-called ultra-categories—which allows for the characterization of definable set functors as those functors that preserve this additional structure.

By contrast, they

…present a ‘syntax-semantics’ duality which shows how to recover a coherent decidable or a classical first-order theory from its models. Compared with the duality theory of Makkai [7, 8], we give an alternative notion of external structure with which to equip the models, which in our case is topological instead of based on ultra-products. This permits the use of topos theory in establishing the main results, and in particular results in a semantic construction of the classifying topos of the theory.

But who knows maybe you need ultraproducts for things other than reconstructing a theory from its models. I wonder how compactness arguments work in their set-up. Presumably adding sentences to a theory is a process of quotienting on the syntax side dualized to an inclusion of models on the semantics side. So, there’s something about quotienting by finite subtheories on the syntax side and non-empty inclusions on the semantics side.

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

Re: Where Do Ultraproducts Come From?

Thanks for this, David. Of course, I’m not remotely competent to comment on the place of ultraproducts in model theory. They might be important in other contexts, though: for example, there’s a book by Hans Schoutens called The Use of Ultraproducts in Commutative Algebra.

I like thinking about topological compactness in terms of ultrafilter convergence. (For example, I like the fact that a space is compact if and only if every ultrafilter on it converges to at least one point.) I wonder whether it’s coincidence that I also like thinking about logical compactness in terms of ultraproducts. I’ll explain why I like this with a standard example.

Let’s say that an element ε\varepsilon of an ordered field kk is infinitesimal if ε>0\varepsilon \gt 0 and nε<1n \cdot \varepsilon \lt 1 for all nn \in \mathbb{N}.

Question: is there some ordered field containing an infinitesimal element?

Classic answer: yes. Add a constant symbol ε\varepsilon to the first-order language of ordered fields, write OFOF for the set of (first-order) axioms for ordered fields, and consider the set of axioms

Γ=OF{ε>0}{ε<1, ε+ε<1, ε+ε+ε<1, }. \Gamma = OF \cup \{ \varepsilon \gt 0 \} \cup \{ \varepsilon \lt 1, &nbsp; \varepsilon + \varepsilon \lt 1, &nbsp; \varepsilon + \varepsilon + \varepsilon \lt 1, &nbsp; \ldots \}.

Every finite subset of Γ\Gamma has a model, e.g. \mathbb{R} equipped with a suitably small positive ε\varepsilon. So by the compactness theorem, Γ\Gamma itself has a model, as required.

Not-quite-so-classic answer: yes. Choose a nonprincipal ultrafilter Ω\Omega on \mathbb{N}. The ultrapower Ω\prod_\Omega \mathbb{R} has the structure of an ordered field, and contains an element

ε=[(1,1/2,1/3,)]. \varepsilon = [(1, 1/2, 1/3, \ldots)].

This ε\varepsilon is infinitesimal. Indeed, it’s >0\gt 0 since each term 1/n1/n is >0\gt 0. Also, given nn \in \mathbb{N}, we have

nε=[(n,n/2,n/3,)] n \cdot \varepsilon = [(n, n/2, n/3, \ldots)]

and all but finitely many of the terms n,n/2,n/3,n, n/2, n/3, \ldots are <1\lt 1, so nεn\cdot \varepsilon itself is <1\lt 1.

Comparison of the two answers The two answers are essentially the same: if you take the proof of the compactness theorem via ultraproducts and unwind it in the case at hand, the first answer becomes the second. Nevertheless, one can point to some aesthetic differences.

The first answer has the advantage that it makes no obtrusively arbitrary choices (unlike the second, where I chose arbitrarily not only an ultrafilter on \mathbb{N} but also a real sequence converging to 00). There is some arbitrariness there, though, since the compactness theorem merely asserts that there exists a model for Γ\Gamma, and it’s certainly not unique.

The second answer has the advantage that it exhibits in an unmysterious way an ordered field with an infinitesimal element. (Well: maybe you think there’s some mystery involved in the existence of nonprincipal ultrafilters. If so, at least you can say that all the mystery is parcelled up there.) Moreover, the proof that the constructed ε\varepsilon really is infinitesimal evokes the familiar idea that the first finite chunk of a sequence is unimportant.

The second answer also has the advantage — at least, it’s an advantage if you’re uncomfortable with logical terms — that it doesn’t use words like “model”, “language” and “first order”. It’s closer to the mainstream of structural mathematics. All you need to know is something about ultraproducts, and that doesn’t require a course on logic either.

I’m not trying to argue that one thing is better than the other; I’m just thinking aloud.

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

Re: Where Do Ultraproducts Come From?

It may be worth remarking that not only can you prove the compactness theorem using ultraproducts, but in fact the compactness theorem is logically equivalent to the ultrafilter theorem (every proper filter is contained in an ultrafilter), as a weak form of the axiom of choice.

Posted by: Mike Shulman on October 1, 2012 12:40 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Interesting — I didn’t know that.

Posted by: Tom Leinster on October 1, 2012 12:51 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

The Wikipedia entry has

…the compactness theorem is equivalent to Gödel’s completeness theorem, and both are equivalent to the Boolean prime ideal theorem, a weak form of the axiom of choice.

and the Boolean prime ideal theorem states that

… ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma.

Johnstone has notes on the prime ideal theorem in ‘Stone Spaces’, if memory serves.

I wonder if there’s an interesting take on compactness in the Awodey-Forssell picture.

Posted by: David Corfield on October 1, 2012 9:00 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Were we to study category theoretic takes on completeness, we might look at:

  • S. Awodey. Continuity and logical completeness: an application of sheaf theory and topoi. In The Age of Alternative Logics, pages 139-149. Springer, 2006.

  • S. Awodey and C. Butz, Topological completeness for higher-order logic. Journal of Symbolic Logic 65(3), (2000) pp. 1168–82.

  • M. Makkai. Generalized sketches as a framework for completeness theorems. Part I, Journal of Pure and Applied Algebra, 115(1):49-79, 1997.

  • M. Makkai. Generalized sketches as a framework for completeness theorems. Part II, Journal of Pure and Applied Algebra, 115(2):179–212, 1997.

  • M. Makkai and G.E. Reyes. Completeness results for intuitionistic and modal logic in a categorical setting. Annals of Pure and Applied Logic, 72(1):25-101, 1995.

A good resource for categorical logic is the bibliography provided by Hans Halvorson.

Posted by: David Corfield on October 1, 2012 11:23 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Constructions of infinitesimals come in various shapes and sizes; this is a topic considered by G.H. Hardy and many others, long before Abraham Robinson came on the scene.

About the simplest ordered field which contains an infinitesimal is the field of germs of rational functions \mathbb{R} \to \mathbb{R} “at infinity”, where functions are ordered by saying fgf \leq g if f(x)g(x)f(x) \leq g(x) for all sufficiently large xx. It’s not too hard to see that for any two rational f,gf, g, either f(x)<g(x)f(x) \lt g(x) or f(x)=g(x)f(x) = g(x) or g(x)<f(x)g(x) \lt f(x) for all sufficiently large xx (because if that weren’t true, then the graphs of ff and gg would intersect infinitely often, and we know that can’t happen for rational functions unless they are identically equal). Thus, germs of such functions do give an ordered field.

In this setting, ordinary reals are identified with germs of constant functions. The germ of f(x)=xf(x) = x, being greater than any constant, is an “infinite” element, and similarly any function of the form f(x)=n/xf(x) = n/x is an infinitesimal element.

Ordered fields gotten by taking germs at infinity of suitable classes of functions are called “Hardy fields”. Hardy himself was interested in the asymptotics of functions that can be obtained by taking rational functions, the exponential and logarithmic functions, and closing under the four arithmetic operations and under composition. Germs of functions in this class give a very rich supply of infinite and infinitesimal quantities.

As I understand it, the idea of taking an ultraproduct is sort of an ultimate extrapolation of this idea of taking germs of functions “at infinity” to get infinitesimals.

First, the Stone-Cech compactification is a universal way of adding “ideal points at infinity” to complete the discrete space \mathbb{N} to a compact space β()\beta(\mathbb{N}). Note that the inclusion {}\mathbb{N} \hookrightarrow \mathbb{N} \cup \{\infty\} into the one-point compactification has a unique extension to a continuous map β(){}\beta(\mathbb{N}) \to \mathbb{N} \cup \{\infty\}, where the points in the fiber over \infty are exactly the non-principal ultrafilters; in that sense, we can think of each non-principal ultrafilter as a “point at infinity”.

Let Uβ()U \in \beta(\mathbb{N}) be a point at infinity. We say that two functions f,g:f, g: \mathbb{N} \to \mathbb{R} have the same germ at UU if they are equal on all “sufficiently small” neighborhoods of UU in the Stone space β()\beta(\mathbb{N}). A basis of such neighborhoods is parametrized by subsets SP()S \in P(\mathbb{N}), i.e., sets of the form

S^={xβ():Sx}\hat{S} = \{x \in \beta(\mathbb{N}): S \in x\}

form a basis of (cl)open sets for β()\beta(\mathbb{N}). To say two functions f,g:f, g: \mathbb{N} \to \mathbb{R} agree on some neighborhood of UU therefore means that for some SUS \in U, we have f(n)=g(n)f(n) = g(n) for all nSn \in S. Just as in the definition of ultraproduct.

Such ultraproducts are obviously quite enormous ordered field extensions of the reals, since the f:f: \mathbb{N} \to \mathbb{R} we are considering don’t have to be particularly nice functions (like rational functions, or the sorts of functions considered by Hardy). It’s nice (although easy to see) that we indeed have an ordered field (i.e., the trichotomy law is satisfied), and there are enough elements in the field that it’s real closed and we can perform analytic operations on them – an advantage that Robinson infinitesimals have over your general run-of-the-mill Hardy fields.

Posted by: Todd Trimble on October 1, 2012 2:14 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

The germs-of-rational-functions example of an ordered field is really nice — thanks!

Posted by: Tom Leinster on October 2, 2012 10:17 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

By the way, Tom, what’s the move to Edinburgh?

Posted by: David Corfield on September 30, 2012 4:54 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

It’s a Chancellor’s fellowship, with a twist that’s too boring to go into here. In practice, it will involve similar commitments to my current job, but with reduced teaching and rain. (There’s 40% less rain in Edinburgh than Glasgow. Can you believe that? The two cities are less than an hour apart by train, but one has nearly twice the rainfall of the other.)

Posted by: Tom Leinster on September 30, 2012 8:28 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

So that’s at least two cheers and probably three, as I suspect you’re being modest.

These are prestigious awards aimed at high potential academics in the early stages of their careers who have begun to establish a reputation for top quality research.

Posted by: David Corfield on October 1, 2012 9:05 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

The twist is that I’m not really in the early stage of my “career”… Anyway, thanks. I’m writing this now from a sunny office in Edinburgh.

Posted by: Tom Leinster on October 1, 2012 1:15 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Sorry for not having anything more constructive to say, but the correct spelling is “Łoś”, not “Łoš”.

Posted by: Karol Szumiło on October 1, 2012 7:32 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Oops. Thanks for letting me know. Fixed now.

Posted by: Tom Leinster on October 1, 2012 7:43 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

I just want to throw in a couple of historical references on ultraproducts in categorical context which haven’t yet come up in the discussions on the blog:

The oldest source is probably

T. Okhuma, Ultrapowers in categories, Yokohama Math. J. 14
(1966), pp. 17-37.

The definition of ultraproducts as filtered colimits seems to originate from here

S. Fakir and L. Haddad, Objets coherents et ultraproduits dans les
catégories, Journal of Algebra, Vol. 21, No. 3, pp. 410-421, June 1972.

Sabah Fakir expanded on this in his dissertation under J. Bénabou which contains a good deal of model theory in locally presentable cats and is online at numdat:

S.Fakir: Objets algèbriquement clos et injectifs dans les catégories localement présentables, Mémoires de la S.M.F tome 42 (1975) 5-75

In the following epoch two articles in the Can.J.Math. deal with categorical closure properties of ultraproducts:

G.Matthiessen: Regular and strongly finitary structures
over strongly algebroidal categories, Vol. XXX, No. 2, 1978, pp. 250-261

P.Bankston: Some obstacles to duality in topological algebra, Vol.XXXIV, No. 1, 1982, pp. 80-90

In the meantime in eastern Europe H.Andréka and I.Németi among others also studied categorical ultraproducts. The following online paper might serve as a pointer to this strang:

H.H.Bui, I.Németi: Problems with the category theoretic notions of ultraproducts, Bulletin of the Section of Logic Volume 10/3 (1981), pp. 122-126

In the context of the codensity monad where profinite structures show up naturally the following more recent paper might be interesting:
H.L.Mariano: Profinite structures are retracts of ultraproducts of finite structures, (arxiv math/0401095).

And finally, somewhat off the categorical track to ultraproducts, i would like to mention the classical and eminently readable source on what can be done with ultraproducts in model theory:

Bell,Slomson: Models and ultraproducts, North-Holland 1969 (reprint available from Dover).

This list is not meant to be exhaustive but intends to supplement the references already mentioned with some other articles I am aware of. Further references can be found in the references of the above listed or in the notes of R.Diaconescu ‘Institution-independent model theory’, Birkhäuser 2008.

—-

By the way, Tom, as you mention Kelly’s book in the historical section of your paper, you might as well refer to Dubuc, ‘Kan extensions in enriched category theory’, LNM 145, 1970. Dubuc does quite a bit of work with the codensity monad e.g. you find a version of prop.6.5 on p.74, which is, I guess, a translation to the enriched context of Linton’s generalisation of the syntax-semantics adjunction from Lawvere’s dissertation.

Posted by: thomas holder on October 2, 2012 2:50 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Wow, that’s impressive!

At the very least, I should look up Okhuma and Dubuc. I should also look up Fakir and Haddad’s paper — the construction of ultraproducts as filtered colimits maybe isn’t such a big deal, but I’m curious to know what else is in there.

Posted by: Tom Leinster on October 2, 2012 10:53 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

The categorical definition of ultraproducts might be somewhat tricky though as Bui-Németi mention that in the cat of totally ordered sets categorical ultraproducts fail to exist in cases where the model theoretic ultraproducts do exist.
Before ending up with the list I had merely the intention to promote Fakir’s dissertation as he even treats model completions and model companions which I have never seen coming up in categorical discussions anywhere else. There is a fair deal of model-theoretic algebra and its translation into category theory which at the time must have been really innovative.
I haven’t actually seen the first two papers. If you happen to come across the Okhuma paper please correct me if I have been wrong with the attribution of the definition to Fakir-Haddad. There is some confusion about this in the literature: Bui-Németi refer to Okhuma and as Fakir does not cite him in his dissertation he was probably simply not aware of the reference.

Posted by: thomas holder on October 3, 2012 10:50 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Right, I’ll add Bui–Németi to my list. Do you know the paper of Barr cited in my own paper? It has a short appendix on ultraproducts, which is kind of a little rant, but an interesting one. I think he makes the point there that ultraproducts can exist in categories that don’t have all products (though I might not be remembering correctly).

Here’s a simple example. Take a finite set BB, seen as a discrete category. Also take a set XX, an ultrafilter Ω\Omega on XX, and an XX-indexed family (b x) xX(b_x)_{x \in X} of elements of BB. What should we take the ultraproduct Ωb \prod_\Omega b_\bullet to be?

Obviously the category BB is very far from having all products. Yet, we can make sense of the ultraproduct. For since BB is finite, there’s some ZΩZ \in \Omega such that (b z) zZ(b_z)_{z \in Z} is a constant family — the constant being Xb dΩ\int_X b_\bullet \, d\Omega. It follows that for any YΩY \in \Omega, all but a small number of the elements b yb_y (yYy \in Y) are equal to Xb dΩ\int_X b_\bullet \, d\Omega.

Usually when constructing the ultraproduct we’d take the filtered colimit of yYb y\prod_{y \in Y} b_y over all YΩY \in \Omega. But it’s in the spirit of things to let YY range over only the large subsets of ZZ (since in any case, YZY \cap Z is a large subset of YY that’s also a subset of ZZ). The product of a constant family in a discrete category is just that constant, so the filtered colimit of yYb y\prod_{y \in Y} b_y over all large YZY \subseteq Z is simply Xb dΩ\int_X b_\bullet \, d\Omega again. So that’s the right thing to take the ultraproduct to be.

Posted by: Tom Leinster on October 3, 2012 11:42 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Thanks for the example, I’ll have a look at the Barr paper.
I kind of pushed the Bui-Németi paper also because Diaconescu mentions that the Hungarian school uses an entirely different approach to ultraproducts and their paper refers to the following one with a rather interesting title:

H. Andréka and I. Németi, Los lemma holds in every category,
Studia Sci. Math. Hungar., Vol. 13 (1978), pp. 361-376.

(sorry for the inadequate spelling of Los due to my lack of typographical sophistication!)

Posted by: thomas holder on October 3, 2012 2:43 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

After taking a look at the Fakir-Haddad paper I must correct myself: they credit Okhuma with the categorical definition of ultraproducts.

I keep bumping into other online-papers on the subject:

D.Ellerman: Sheaves of structures and generalized ultraproducts, Ann.Math.Logic 7, 1974

J.Kennison: Triples and compact sheaf representations, J.Pure.Appl.Alg. 20, 1981

As Tom mentions in the paper, the ultraproduct A_U of a family (A_i,i in X) arises as the stalk at the ultrafilter U of a sheaf on the set ßX of ultrafilters on X. The process is functorial. There is even an adjunction between the functor mapping a discrete sheaf on X to this so called ultrasheaf on ßX and the forgetful functor mapping a compact sheaf to its underlying discrete sheaf. Kennison shows that the forgetful functor is monadic so the ultrasheaf monad ressembles the ultrafilter monad.
I am not sure how far analogical thinking goes in a digital era but this suggests: finite sets relate to ultrafilters like finite families relate to sheaves of ultraproducts!

Before I stop let me mention two more papers that are available online:

Lawvere considers generalized ultraproducts in

‘Quantifiers and Sheaves’, Actes du congrès international des mathématiciens, Nice 1970, Tome I, Gauthier-Villars

Awodey, Steve and Eliasson, Jonas, “Ultrasheaves and Double Negation” (2003). Department of Philosophy. Paper 68.

Posted by: thomas holder on October 16, 2012 7:02 PM | Permalink | Reply to this

less set theory please

You are bringing together ideas from a very wide range of disciplines that have hitherto not had much categorical attention, so we can hope to see lots of useful comments from outside our subject. On the other hand, you have started from categorical principles and I know that you have good categorical intuition, so I am looking forward to a nice piece of category theory at the end of it that will not rely so heavily on set theory as the traditional material that you have described.

I take issue with your statement that “ultrafilters are inevitable”, because it is uninformative and loaded. What you might say instead is that they are “complementary” to finite sets, but (linguistically) implicit in that is an idea of what the “complete” things are. I had previously thought of directed or filtered diagrams as the “purely infinite” ones, but that was when the “complete” things were complete semilattices: in your case they are perhaps complete Boolean algebras or toposes.

So you have obtained ultrafilters by subtracting finite sets from all sets, and the set-theoretic ideas come from the latter, even if you replace sets by an elementary topos.

What do you actually require of an inclusion of categories in this role in order to reproduce mathematical phenomena similar to those that you have described?

Can you find examples of such inclusions where (meaningful parts of your development still go through but) this “difference” is much smaller?

For example, for me finite sets are compact Hausdorff overt discrete spaces. So I might consider them as a subcategory of a model of Abstract Stone Duality (or the category of locally compact sober spaces) or some other constructive formulation of topology.

Posted by: Paul Taylor on October 1, 2012 2:20 PM | Permalink | Reply to this

Re: less set theory please

Thanks for the interesting thoughts. It’s funny that you say “less set theory”, because where this paper started for me wasn’t set theory at all: it was measure theory.

I’d been wondering whether (in some nebulous sense) measure spaces could be completely understood by chopping them into a finite number of pieces. For example, entropy for measures on a finite set is very easy, and I thought this chopping idea might help me to get a grip on entropy for general measure spaces. (I really mean probability spaces here, not measure spaces, but that’s beside the point.) I expressed this thought to Mark Meckes, who instinctively guessed that it wouldn’t work.

When I tried to make my question precise, I ended up with this: is the category of measure spaces with finite underlying set codense in the category of all measure spaces? After a while I realized that I didn’t even know whether the category of finite sets was codense in the category of sets. Once I’d figured out that the answer to that was no, it was fairly easy to deduce that the answer to the question about measure spaces was also no. The reason is the same: the existence of nonprincipal ultrafilters.

(So Mark was right.)

In the end I decided that the measure space question wasn’t that interesting — it’s just the FinSetSet\mathbf{FinSet} \hookrightarrow \mathbf{Set} example with a bit of window-dressing. So, disloyally, I dropped it from the paper that it had brought into existence.

What do you actually require of an inclusion of categories in this role in order to reproduce mathematical phenomena similar to those that you have described?

I don’t know. I suppose I only have a hazy idea of what would count as similar phenomena, so it’s hard to say. I did go through lots of examples of codensity monads, in my head or on paper. In a lot of cases, something trivial or semi-trivial came out. (Under “semi-trivial” I’d put the examples that come from inclusions of ordered sets.) In other cases, I couldn’t see what the codensity monad was or whether it existed. (For example, I don’t know whether the free group functor from sets to groups has a codensity monad.) I probably included in the paper all the interesting ones I thought of.

By the way, would you count the vector space example, FDVectVect\mathbf{FDVect} \hookrightarrow \mathbf{Vect}, as inherently set-theoretic?

Can you find examples of such inclusions where (meaningful parts of your development still go through but) this “difference” is much smaller?

I just now tried things like the inclusion of the category of nonempty sets into Set\mathbf{Set}, or the inclusion of a category into the same category with a terminal object freely adjoined, thus aiming for something where the difference is really small. But the answers seem to be trivial (which is maybe inevitable). I can’t think of any interesting example in the middle.

Posted by: Tom Leinster on October 2, 2012 10:43 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

So what might Set\mathbf{Set}, Ring\mathbf{Ring}, Field\mathbf{Field} belong to that we can integrate functions valued in them against an ultrafilter? Presumably the category of models of any first-order theory would do.

How to characterise the model categories (or groupoids) of first-order theories? Makkai speaks of ultra-categories or groupoids, e.g., ones equipped with a notion of ultraproduct structure.

Would we then be looking to include ultra-groupoids, or whatever, in some larger (2-)category and forming a codensity monad?

Hmm, I can’t get hold of any of Makkai’s writings on this

  • Michael Makkai. Stone duality for first order logic. Advances in Mathematics, 65(2):97-170, 1987.
  • Michael Makkai. Strong conceptual completeness for first order logic. Annals of Pure and Applied Logic, 40:167-215, 1988.
  • Michael Makkai. Duality and Definability in First Order Logic. Number 503 in Memoirs of the American Mathematical Society. American Mathematical Society, 1993.

Forssell’s thesis says

An ultra-groupoid is a groupoid with ultraproducts and limit ultrapowers, as well as additional ultraproduct and limit ultrapower related structure, including certain relations on arrows and a notion of ultra-morphism, see [19]. Together with structure preserving (up to specified transition isomorphisms) groupoid functors (ultra-functors) and certain invertible natural transformations between them (ultra-transformations), these form the groupoid-enriched category of ultra groupoids.

Then you can set up a duality with the 2-category of

Boolean pretopoi, coherent functors between the pretopoi, and invertible natural transformation between functors.

But maybe good category theorists as we are, we should prefer Awodey and Forssell’s Stone groupoids of models.

Hmm, do you know of any codensity 2-monads from the inclusion of 2-categories? Shouldn’t the XX of the ‘voters’ be generalised to something more than a possibly infinite set?

Posted by: David Corfield on October 1, 2012 3:08 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

To answer just one bit:

Shouldn’t the XX of the ‘voters’ be generalised to something more than a possibly infinite set?

Yes, quite possibly. I’d had the same thought, but I don’t have much of an idea what the answer might be.

Posted by: Tom Leinster on October 2, 2012 11:04 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

I guess one thing going on is that voting over Fields works like this. For a set XX of voters, we have

XFields, X \to Fields,

which is

XSets Th(Field). X \to Sets^{Th(Field)}.

If I could say this is equivalent to a map

Th(Field)Sets X, Th(Field) \to Sets^X,

then the latter can be postcomposed with ultrafilter integration

Sets XSets, Sets^X \to Sets,

giving a map Th(Field)SetTh(Field) \to Set, i.e., a field.

But what world do all these objects live in? All the people I mentioned before would have Th(Field)Th(Field) as a Boolean pretopos. SetsSets is an ambimorphic, dualizing object, living in the syntactic and semantic worlds.

Posted by: David Corfield on October 3, 2012 10:00 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

I’m not sure I understand what you mean, David. Given an ultrafilter Ω\Omega on a set XX, integration against Ω\Omega defines a map B XBB^X \to B for any finite set BB. It doesn’t define a functor Set XSetSet^X \to Set. Or when you wrote “ultrafilter integration Sets XSetsSets^X \to Sets”, did you actually mean “ultraproduct Sets XSetsSets^X \to Sets”?

Posted by: Tom Leinster on October 5, 2012 2:49 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Whoops, yes, I meant ultraproduct. Presumably models of classical theories are inheriting the capacity of sets to form ultraproducts.

Posted by: David Corfield on October 5, 2012 9:32 PM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

The articles published by Elsevier, at least, should be available:

Michael Makkai. Stone duality for first order logic. Advances in Mathematics, 65(2):97-170, 1987.

Michael Makkai. Strong conceptual completeness for first order logic. Annals of Pure and Applied Logic, 40:167-215, 1988.

Posted by: David Roberts on October 4, 2012 2:53 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

Ah good, thanks. It seemed that via one route our library only had these journals in limited time ranges.

Anyway, let’s see, from the second

The essence of the main result of [14] is that the functors commuting with ultraproducts and ultramorphisms are exactly the definable functors of (the pretopos completion of) TT.

So, given the set of models of a first-order theory TT, we can reconstruct the theory (or its pretopos completion) by locating those functors commuting as said. These are definable functors, i.e., of the kind which sends objects in the category of models to their interpretations of a specific formula.

However,

…the objection was made by some that the notion of ultramorphism is too complicated to be of real interest.

In [15], I reformulated the result in the form of a structure theorem on (part of) the (meta-) 2-category PRETOP of all pretoposes in which theorem Set plays a distinguished role. The result now took the form of a construction of a 2-functor into PRETOP taking values that are Set and some iterated small limits formed Strong conceptual completeness out of Set, which could be shown to be codense at all small pretoposes. The point of the paper was that, apparently, the mere existence of such a functor was non-trivial, and it represented a more conceptual version of the result of [14].

The main result of the present paper is a two fold improvement on [15]. On the one hand, it shows the codensity of an appropriate functor at each member of a class of pretoposes not only including all small pretoposes but also containing Set and its iterated small limits. This allows one to talk about the codensity of a functor into a natural 2-category of pretoposes in the full sense, not just at certain objects of it. On the other hand, by a general lifting lemma, one is now able to conclude the codensity of a simply defined full inclusion.

Good to see codensity looming large.

Posted by: David Corfield on October 4, 2012 8:47 AM | Permalink | Reply to this

Re: Where Do Ultraproducts Come From?

I was trying to be subtle, but oh well:

Free access to archived articles of primary mathematics journals from Elsevier.

Posted by: David Roberts on October 5, 2012 3:03 AM | Permalink | Reply to this
Read the post Whitney Twists
Weblog: The n-Category Café
Excerpt: Q. Is the magnitude of a graph invariant under Whitney twists? A. Sometimes.
Tracked: July 7, 2013 7:37 AM

Post a New Comment