I have blogged a number of times in the past about the relationship between finitary (or “hard”, or “quantitative”) analysis, and infinitary (or “soft”, or “qualitative”) analysis. One way to connect the two types of analysis is via compactness arguments (and more specifically, contradiction and compactness arguments); such arguments can convert qualitative properties (such as continuity) to quantitative properties (such as bounded), basically because of the fundamental fact that continuous functions on a compact space are bounded (or the closely related fact that sequentially continuous functions on a sequentially compact space are bounded).

A key stage in any such compactness argument is the following: one has a sequence {X_n} of “quantitative” or “finitary” objects or spaces, and one has to somehow end up with a “qualitative” or “infinitary” limit object {X} or limit space. One common way to achieve this is to embed everything inside some universal space and then use some weak compactness property of that space, such as the Banach-Alaoglu theorem (or its sequential counterpart). This is for instance the idea behind the Furstenberg correspondence principle relating ergodic theory to combinatorics; see for instance this post of mine on this topic.

However, there is a slightly different approach, which I will call ultralimit analysis, which proceeds via the machinery of ultrafilters and ultraproducts; typically, the limit objects {X} one constructs are now the ultraproducts (or ultralimits) of the original objects {X_\alpha}. There are two main facts that make ultralimit analysis powerful. The first is that one can take ultralimits of arbitrary sequences of objects, as opposed to more traditional tools such as metric completions, which only allow one to take limits of Cauchy sequences of objects. The second fact is Los’s theorem, which tells us that {X} is an elementary limit of the {X_\alpha} (i.e. every sentence in first-order logic which is true for the {X_\alpha} for {\alpha} large enough, is true for {X}). This existence of elementary limits is a manifestation of the compactness theorem in logic; see this earlier blog post for more discussion. So we see that compactness methods and ultrafilter methods are closely intertwined. (See also my earlier class notes for a related connection between ultrafilters and compactness.)

Ultralimit analysis is very closely related to nonstandard analysis. I already discussed some aspects of this relationship in an earlier post, and will expand upon it at the bottom of this post. Roughly speaking, the relationship between ultralimit analysis and nonstandard analysis is analogous to the relationship between measure theory and probability theory.

To illustrate how ultralimit analysis is actually used in practice, I will show later in this post how to take a qualitative infinitary theory – in this case, basic algebraic geometry – and apply ultralimit analysis to then deduce a quantitative version of this theory, in which the complexity of the various algebraic sets and varieties that appear as outputs are controlled uniformly by the complexity of the inputs. The point of this exercise is to show how ultralimit analysis allows for a relatively painless conversion back and forth between the quantitative and qualitative worlds, though in some cases the quantitative translation of a qualitative result (or vice versa) may be somewhat unexpected. In an upcoming paper of myself, Ben Green, and Emmanuel Breuillard (announced in the previous blog post), we will rely on ultralimit analysis to reduce the messiness of various quantitative arguments by replacing them with a qualitative setting in which the theory becomes significantly cleaner.

For sake of completeness, I also redo some earlier instances of the correspondence principle via ultralimit analysis, namely the deduction of the quantitative Gromov theorem from the qualitative one, and of Szemerédi’s theorem from the Furstenberg recurrence theorem, to illustrate how close the two techniques are to each other.

— 1. Ultralimit analysis —

In order to perform ultralimit analysis, we need to prepare the scene by deciding on three things in advance:

  • The standard universe {{\mathcal U}} of standard objects and spaces.
  • A distinction between ordinary objects, and spaces.
  • A choice of non-principal ultrafilter {\alpha_\infty \in \beta {\mathbb N} \backslash {\mathbb N}}.

We now discuss each of these three preparatory ingredients in turn.

We assume that we have a standard universe or superstructure {{\mathcal U}} which contains all the “standard” sets, objects, and structures that we ordinarily care about, such as the natural numbers, the real numbers, the power set of real numbers, the power set of the power set of real numbers, and so forth. For technical reasons, we have to limit the size of this universe by requiring that it be a set, rather than a class; thus (by Russell’s paradox), not all sets will be standard (e.g. {{\mathcal U}} itself will not be a standard set). However, in many areas of mathematics (particularly those of a “finitary” or at most “countable” flavour, or those based on finite-dimensional spaces such as {{\mathbb R}^d}), the type of objects considered in a field of mathematics can often be contained inside a single set {{\mathcal U}}. For instance, the class of all groups is too large to be a set. But in practice, one is only interested in, say, groups with an at most countable number of generators, and if one then enumerates these generators and considers their relations, one can identify each such group (up to isomorphism) to one in some fixed set of model groups. One can then take {{\mathcal U}} to be the collection of these groups, and the various objects one can form from these groups (e.g. power sets, maps from one group to another, etc.). Thus, in practice, the requirement that we limit the scope of objects to care about is not a significant limitation. (If one does not want to limit one’s scope in this fashion, one can proceed instead using the machinery of Grothendieck universes.)

It is important to note that while we primarily care about objects inside the standard universe {{\mathcal U}}, we allow ourselves to use objects outside the standard universe (but still inside the ambient set theory) whenever it is convenient to do so. The situation is analogous to that of using complex analysis to solve real analysis problems; one may only care about statements that have to do with real numbers, but sometimes it is convenient to introduce complex numbers within the proofs of such statements. (More generally, the trick of passing to some completion {\overline{{\mathcal U}}} of one’s original structure {{\mathcal U}} in order to more easily perform certain mathematical arguments is a common theme throughout modern mathematics.)

We will also assume that there is a distinction between two types of objects in this universe: spaces, which are sets that can contain other objects, and ordinary objects, which are all the objects that are not spaces. Thus, for instance, a group element would typically be considered an ordinary object, whereas a group itself would be a space that group elements can live in. It is also convenient to view functions {f: X \rightarrow Y} between two spaces as itself a type of ordinary object (namely, an element of a space {\hbox{Hom}(X,Y)} of maps from {X} to {Y}). The precise concept of what constitutes a space, and what constitutes an ordinary object, is somewhat hard to formalise, but the basic rule of thumb to decide whether an object {X} should be a space or not is to ask whether mathematical phrases such as {x \in X}, {f: X \rightarrow Y}, or {A \subset X} are likely to make useful sense. If so, then {X} is a space; otherwise, {X} is an ordinary object.

Examples of spaces include sets, groups, rings, fields, graphs, vector spaces, topological spaces, metric spaces, function spaces, measure spaces, dynamical systems, and operator algebras. Examples of ordinary objects include points, numbers, functions, matrices, strings, and equations.

Remark 1 Note that in some cases, a single object may seem to be both an ordinary object and a space, but one can often separate the two roles that this object is playing by making a sufficiently fine distinction. For instance, in Euclidean geometry, a line {\ell} in is both an ordinary object (it is one of the primitive concepts in that geometry), but it can also be viewed as a space of points. In such cases, it becomes useful to distinguish between the abstract line {\ell}, which is the primitive object, and its realisation {\ell[{\mathbb R}]} as a space of points in the Euclidean plane. This type of distinction is quite common in algebraic geometry, thus, for instance, the imaginary circle {C := \{ (x,y): x^2 + y^2 = -1 \}} has an empty realisation {C[{\mathbb R}] = \emptyset} in the real plane {{\mathbb R}^2}, but has a non-trivial realisation {C[{\mathbb C}]} in the complex plane {{\mathbb C}^2} (or over finite fields), and so we do not consider {C} (as an abstract algebraic variety) to be empty. Similarly, given a function {f}, we distinguish between the function {f} itself (as an abstract object) and the graph {f[X] := \{ (x,f(x)): x \in X \}} of that function over some given domain {X}.

We also fix a nonprincipal ultrafilter {\alpha_\infty} on the natural numbers. Recall that this is a collection of subsets of {{\mathbb N}} with the following properties:

  • No finite set lies in {\alpha_\infty}.
  • If {A \subset {\mathbb N}} is in {\alpha_\infty}, then any subset of {{\mathbb N}} containing {A} is in {\alpha_\infty}.
  • If {A, B} lie in {\alpha_\infty}, then {A \cap B} also lies in {\alpha_\infty}.
  • If {A \subset {\mathbb N}}, then exactly one of {A} and {{\mathbb N} \backslash A} lies in {\alpha_\infty}.

Given a property {P(\alpha)} which may be true or false for each natural number {\alpha}, we say that {P} is true for {\alpha} sufficiently close to {\alpha_\infty} if the set {\{ \alpha \in {\mathbb N}: P(\alpha) \hbox{ holds}\}} lies in {\alpha_\infty}. The existence of a non-principal ultrafilter {\alpha_\infty} is guaranteed by the ultrafilter lemma, which can be proven using the axiom of choice.

Remark 2 One can view {\alpha_\infty} as a point in the Stone-Čech compactification, in which case “for {\alpha} sufficiently close to {\alpha_\infty}” acquires the familiar topological meaning “for all {\alpha} in a neighbourhood of {\alpha_\infty}“.

We can use this ultrafilter to take limits of standard objects and spaces. Indeed, given any two sequences {(x_\alpha)_{\alpha \in {\mathbb N}}}, {(y_\alpha)_{\alpha \in {\mathbb N}}} of standard ordinary objects, we say that such sequences are equivalent if we have {x_\alpha = y_\alpha} for all {\alpha} sufficiently close to {\alpha_\infty}. We then define the ultralimit {\lim_{\alpha \rightarrow \alpha_\infty} x_\alpha} of a sequence {(x_\alpha)_{\alpha \in {\mathbb N}}} to be the equivalence class of {(x_\alpha)_{\alpha \in {\mathbb N}}} (in the space {{\mathcal U}^{\mathbb N}} of all sequences in the universe). In other words, we have

\displaystyle \lim_{\alpha \rightarrow \alpha_\infty} x_\alpha = \lim_{\alpha \rightarrow \alpha_\infty} y_\alpha

if and only if {x_\alpha = y_\alpha} for all {\alpha} sufficiently close to {\alpha_\infty}.

The ultralimit {\lim_{\alpha \rightarrow \alpha_\infty} x_\alpha} lies outside the standard universe {{\mathcal U}}, but is still constructible as an object in the ambient set theory (because {{\mathcal U}} was assumed to be a set). Note that we do not need {x_\alpha} to be well-defined for all {\alpha} for the limit {(x_\alpha)_{\alpha \in {\mathbb N}}} to make sense; it is enough that {x_\alpha} is well-defined for all {\alpha} sufficiently close to {\alpha_\infty}.

If {x = \lim_{\alpha \rightarrow \alpha_\infty} x_\alpha}, we refer to the sequence {x_\alpha} of ordinary objects as a model for the limit {x}. Thus, any two models for the same limit object {x} will agree in a sufficiently small neighbourhood of {\alpha_\infty}.

Similarly, given a sequence of standard spaces {(X_\alpha)_{\alpha \in {\mathbb N}}}, one can form the ultralimit (or ultraproduct) {\lim_{\alpha \rightarrow \alpha_\infty} X_\alpha}, defined as the collection of all ultralimits {\lim_{\alpha \rightarrow \alpha_\infty} x_\alpha} of sequences {x_\alpha}, where {x_\alpha \in X_\alpha} for all {\alpha \in {\mathbb N}} (or for all {\alpha} sufficiently close to {\alpha_\infty}). Again, this space will lie outside the standard universe, but is still a set. (This will not conflict with the notion of ultralimits for ordinary objects, so long as one always takes care to keep spaces and ordinary objects separate.) If {X = \lim_{\alpha \rightarrow \alpha_\infty} X_\alpha}, we refer to the sequence {X_\alpha} of spaces as a model for {X}.

As a special case of an ultralimit, given a single space {X}, its ultralimit {\lim_{\alpha \rightarrow \alpha_\infty} X} is known as the ultrapower of {X} and will be denoted {{}^* X}.

Remark 3 One can view {{}^* X} as a type of completion of {X}, much as the reals are the metric completion of the rationals. Indeed, just as the reals encompass all limits {\lim_{n \rightarrow \infty} x_n} of Cauchy sequences {x_1,x_2,\ldots} in the rationals, up to equivalence, the ultrapower {{}^* X} encompass all limits of arbitrary sequences in {X}, up to agreement sufficiently close to {\alpha_\infty}. The ability to take limits of arbitrary sequences, and not merely Cauchy sequences or convergent sequences, is the underlying source of power of ultralimit analysis. (This ability ultimately arises from the universal nature of the Stone-Čech compactification {\beta {\mathbb N}}, as well as the discrete nature of {{\mathbb N}}, which makes all sequences {n \mapsto x_n} continuous.)

Of course, we embed the rationals into the reals by identifying each rational {x} with its limit {\lim_{n \rightarrow \infty} x}. In a similar spirit, we identify every standard ordinary object {x} with its ultralimit {\lim_{\alpha \rightarrow \alpha_\infty} x}. In particular, a standard space {X} is now identified with a subspace of {{}^* X}. When {X} is finite, it is easy to see that this embedding of {X} to {{}^* X} is surjective; but for infinite {X}, the ultrapower is significantly larger than {X} itself.

Remark 4 One could collect the ultralimits of all the ordinary objects and spaces in the standard universe {{\mathcal U}} and form a new structure, the nonstandard universe {\overline{{\mathcal U}}_{\alpha_\infty}}, which one can view as a completion of the standard universe, in much the same way that the reals are a completion of the rationals. However, we will not have to explicitly deal with this nonstandard universe and will not discuss it again in this post.

In nonstandard analysis, an ultralimit of standard ordinary object in a given class is referred to as (or more precisely, models) a nonstandard object in that class. To emphasise the slightly different philosophy of ultralimit analysis, however, I would like to call these objects limit objects in that class instead. Thus, for instance:

  • An ultralimit {n = \lim_{\alpha \rightarrow \alpha_\infty} n_\alpha} of standard natural numbers is a limit natural number (or a nonstandard natural number, or an element of {{}^* {\mathbb N}});
  • An ultralimit {x = \lim_{\alpha \rightarrow \alpha_\infty} x_\alpha} of standard real numbers is a limit real number (or a nonstandard real number, or a hyperreal, or an element of {{}^* {\mathbb R}});
  • An ultralimit {\phi = \lim_{\alpha \rightarrow \alpha_\infty} \phi_\alpha} of standard functions {\phi_\alpha: X_\alpha \rightarrow Y_\alpha} between two sets {X_\alpha,Y_\alpha} is a limit function (also known as an internal function, or a nonstandard function);
  • An ultralimit {\phi = \lim_{\alpha \rightarrow \alpha_\infty} \phi_\alpha} of standard continuous functions {\phi_\alpha: X_\alpha \rightarrow Y_\alpha} between two topological spaces {X_\alpha,Y_\alpha} is a limit continuous function (or internal continuous function, or nonstandard continuous function);
  • etc.

Clearly, all standard ordinary objects are limit objects of the same class, but not conversely.

Similarly, ultralimits of spaces in a given class will be referred to limit spaces in that class (in nonstandard analysis, they would be called nonstandard spaces or internal spaces instead). For instance:

  • An ultralimit {X = \lim_{\alpha \rightarrow \alpha_\infty} X_\alpha} of standard sets is a limit set (or internal set, or nonstandard set);
  • An ultralimit {G = \lim_{\alpha \rightarrow \alpha_\infty} G_\alpha} of standard groups is a limit group (or internal group, or nonstandard group);
  • An ultralimit {(X,{\mathcal B},\mu) = \lim_{\alpha \rightarrow \alpha_\infty} (X_\alpha,{\mathcal B}_\alpha,\mu_\alpha)} of standard measure spaces is a limit measure space (or internal measure space, or nonstandard measure space);
  • etc.

Note that finite standard spaces will also be limit spaces of the same class, but infinite standard spaces will not. For instance, {{\mathbb Z}} is a standard group, but is not a limit group, basically because it does not contain limit integers such as {\lim_{\alpha \rightarrow \alpha_\infty} \alpha}. However, {{\mathbb Z}} is contained in the limit group {{}^* {\mathbb Z}}. The relationship between standard spaces and limit spaces is analogous to that between incomplete spaces and complete spaces in various fields of mathematics (e.g. in metric space theory or field theory).

Any operation or result involving finitely many standard objects, spaces, and first-order quantifiers carries over to their nonstandard or limit counterparts (the formal statement of this is Los’s theorem). For instance, the addition operation on standard natural numbers gives an addition operation on limit natural numbers, defined by the formula

\displaystyle \lim_{\alpha \rightarrow \alpha_\infty} n_\alpha + \lim_{\alpha \rightarrow \alpha_\infty} m_\alpha := \lim_{\alpha \rightarrow \alpha_\infty} (n_\alpha + m_\alpha).

It is easy to see that this is a well-defined operation on the limit natural numbers {{}^* {\mathbb N}}, and that the usual properties of addition (e.g. the associative and commutative laws) carry over to this limit (much as how the associativity and commutativity of addition on the rationals automatically implies the same laws of arithmetic for the reals). Similarly, we can define the other arithmetic and order relations on limit numbers: for instance we have

\displaystyle \lim_{\alpha \rightarrow \alpha_\infty} n_\alpha \geq \lim_{\alpha \rightarrow \alpha_\infty} m_\alpha

if and only if {n_\alpha \geq m_\alpha} for all {\alpha} sufficiently close to {\alpha_0}, and similarly define {\leq, >, <}, etc. Note from the definition of an ultrafilter that we still have the usual order trichotomy: given any two limit numbers {n, m}, exactly one of {n < m}, {n=m}, and {n>m} is true.

Example 1 The limit natural number {\omega := \lim_{\alpha \rightarrow \alpha_\infty} \alpha} is larger than all standard natural numbers, but {\omega^2 = \lim_{\alpha \rightarrow \alpha_\infty} \alpha^2} is even larger still.

The following two exercises should give some intuition of how Los’s theorem is proved, and what it could be useful for:

Exercise 1 Show that the following two formulations of Goldbach’s conjecture are equivalent:

  • Every even natural number greater than two is the sum of two primes.
  • Every even limit natural number greater than two is the sum of two prime limit natural numbers.

Here, we define a limit natural number {n} to be even if we have {n=2m} for some limit natural number {m}, and a limit natural number {n} to be prime if it is greater than {1} but cannot be written as the product of two limit natural numbers greater than {1}.

Exercise 2 Let {k_\alpha} be a sequence of algebraically closed fields. Show that the ultralimit {k := \lim_{\alpha \rightarrow \alpha_\infty} k_\alpha} is also an algebraically closed field. In other words, every limit algebraically closed field is an algebraically closed field.

Given an ultralimit {\phi := \lim_{\alpha \rightarrow \alpha_\infty} \phi_\alpha} of functions {\phi_\alpha: X_\alpha \rightarrow Y_\alpha}, we can view {\phi} as a function from the limit space {X := \prod_{\alpha \rightarrow \alpha_\infty} X_\alpha} to the limit space {Y := \prod_{\alpha \rightarrow \alpha_\infty} Y_\alpha} by the formula

\displaystyle \phi( \lim_{\alpha \rightarrow \alpha_\infty} x_\alpha ) := \lim_{\alpha \rightarrow \alpha_\infty} \phi_\alpha(x_\alpha).

Again, it is easy to check that this is well-defined. Thus every limit function from a limit space {X} to a limit space {Y} is a function from {X} to {Y}, but the converse is not true in general.

One can easily show that limit sets behave well with respect to finitely many boolean operations; for instance, the intersection of two limit sets {X = \lim_{\alpha \rightarrow \alpha_\infty} X_\alpha} and {Y = \lim_{\alpha \rightarrow \alpha_\infty} Y_\alpha} is another limit set, namely {X \cap Y = \lim_{\alpha \rightarrow \alpha_\infty} X_\alpha \cap Y_\alpha}. However, we caution that the same is not necessarily true for infinite boolean operations; the countable union or intersection of limit sets need not be a limit set. (For instance, each individual standard integer in {{\mathbb Z}} is a limit set, but their union {{\mathbb Z}} is not.) Indeed, there is an analogy between the limit subsets of a limit set, and the clopen subsets of a topological space (or the constructible sets in an algebraic variety).

By the same type of arguments used to show Exercise 2, one can check that every limit group is a group (albeit one that usually lies outside the standard universe {{\mathcal U}}), every limit ring is a ring, every limit field is a field, etc.

The situation with vector spaces is a little more interesting. The ultraproduct {V = \lim_{\alpha \rightarrow \alpha_\infty} V_\alpha} of a collection of standard vector spaces {V_\alpha} over {{\mathbb R}} is a vector space over the larger field {{}^* {\mathbb R}}, because the various scalar multiplication operations {\cdot_\alpha: {\mathbb R} \times V_\alpha \rightarrow V_\alpha} over the standard reals become a scalar multiplication operation {\cdot: {}^* {\mathbb R} \times V \rightarrow V} over the limit reals. Of course, as the standard reals {{\mathbb R}} are a subfield of the limit reals {{}^* {\mathbb R}}, {V} is also a vector space over the standard reals {{\mathbb R}}; but when viewed this way, the properties of the {V_\alpha} are not automatically inherited by {V}. For instance, if each of the {V_\alpha} are {d}-dimensional over {{\mathbb R}} for some fixed finite {d}, then {V} is {d}-dimensional over the limit reals {{}^* {\mathbb R}}, but is infinite dimensional over the reals {{\mathbb R}}.

Now let {A = \lim_{\alpha \rightarrow \alpha_\infty} A_\alpha} be a limit finite set, i.e. a limit of finite sets {A_\alpha}. Every finite set is a limit finite set, but not conversely; for instance, {\lim_{\alpha \rightarrow \alpha_\infty} \{1,\ldots,\alpha\}} is a limit finite set which has infinite cardinality. On the other hand, because every finite set {A_\alpha} has a cardinality {|A_\alpha| \in {\mathbb N}} which is a standard natural number, we can assign to every limit finite set {A = \lim_{\alpha \rightarrow \alpha_\infty} A_\alpha} a limit cardinality {|A| \in {}^* {\mathbb N}} which is a limit natural number, by the formula

\displaystyle |\lim_{\alpha \rightarrow \alpha_\infty} A_\alpha| := \lim_{\alpha \rightarrow \alpha_\infty} |A_\alpha|.

This limit cardinality inherits all of the first-order properties of ordinary cardinality. For instance, we have the inclusion-exclusion formula

\displaystyle |A \cup B| + |A \cap B| = |A| + |B|

for any two limit finite sets; this follows from the inclusion-exclusion formula for standard finite sets by an easy limiting argument.

It is not hard to show that {\lim_{\alpha \rightarrow \alpha_\infty} A_\alpha} is finite if and only if the {|A_\alpha|} are bounded for {\alpha} sufficiently close to {\alpha_\infty}. Thus, we see that one feature of passage to ultralimits is that it converts the term “bounded” to “finite”, while the term “finite” becomes “limit finite”. This makes ultralimit analysis useful for deducing facts about bounded quantities from facts about finite quantities. We give some examples of this in the next section.

In a similar vein, an ultralimit {(X,d) = \lim_{\alpha \rightarrow \alpha_\infty} (X_\alpha,d_\alpha)} of standard metric spaces {(X_\alpha,d_\alpha)} yields a limit metric space, thus for instance {d: X \times X \rightarrow {}^* {\mathbb R}} is now a metric taking values in the limit reals. Now, if the spaces {(X_\alpha,d_\alpha)} were uniformly bounded, then the limit space {(X,d)} would be bounded by some (standard) real diameter. From the Bolzano-Weierstrass theorem we see that every bounded limit real number {x} has a unique standard part {\hbox{st}(x)} which differs from {x} by an infinitesimal, i.e. a limit real number of the form {\lim_{\alpha \rightarrow \alpha_\infty} x_\alpha} where {x_\alpha} converges to zero in the classical sense. As a consequence, the standard part {\hbox{st}(d)} of the limit metric function {d: X \times X \rightarrow {}^* {\mathbb R}} is a genuine metric function {\hbox{st}(d): X \times X \rightarrow {\mathbb R}}. The resulting metric space {(X, \hbox{st}(d))} is often referred to as an ultralimit of the original metric spaces {(X_\alpha,d_\alpha)}, although strictly speaking this conflicts slightly with the notation here, because we consider {(X,d)} to be the ultralimit instead.

— 2. Application: quantitative algebraic geometry —

As a sample application of the above machinery, we shall use ultrafilter analysis to quickly deduce some quantitative (but not explicitly effective) algebraic geometry results from their more well-known qualitative counterparts. Significantly stronger results than the ones given here can be provided by the field of effective algebraic geometry, but that theory is somewhat more complicated than the classical qualitative theory, and the point I want to stress here is that one can obtain a “cheap” version of this effective algebraic geometry from the qualitative theory by a straightforward ultrafilter argument. I do not know of a comparably easy way to get such ineffective quantitative results without the use of ultrafilters or closely related tools (e.g. nonstandard analysis or elementary limits).

We first recall a basic definition:

Definition 1 (Algebraic set) An (affine) algebraic set over an algebraically closed field {k} is a subset of {k^n}, where {n} is a positive integer, of the form

\displaystyle \{ x \in k^n: P_1(x) = \ldots = P_m(x) = 0 \} \ \ \ \ \ (1)

where {P_1,\ldots,P_m: k^n \rightarrow k} are a finite collection of polynomials.

Now we turn to the quantitative theory, in which we try to control the complexity of various objects. Let us say that an algebraic set in {k^n} has complexity at most {M} if {n \leq M}, and one can express the set in the form (1) where {m \leq M}, and each of the polynomials {P_1,\ldots,P_m} has degree at most {M}. We can then ask the question of to what extent one can make the above qualitative algebraic statements quantitative. For instance, it is known that a dimension {0} algebraic set is finite; but can we bound how finite it is in terms of the complexity {M} of that set? We are particularly interested in obtaining bounds here which are uniform in the underlying field {k}.

One way to do so is to open up an algebraic geometry textbook and carefully go through the proofs of all the relevant qualitative facts, and carefully track the dependence on the complexity. For instance, one could bound the cardinality of a dimension {0} algebraic set using Bézout’s theorem. But here, we will use ultralimit analysis to obtain such quantitative analogues “for free” from their qualitative counterparts. The catch, though, is that the bounds we obtain are ineffective; they use the qualitative facts as a “black box”, and one would have to go through the proof of these facts in order to extract anything better.

To begin the application of ultrafilter analysis, we use the following simple lemma.

Lemma 2 (Ultralimits of bounded complexity algebraic sets are algebraic) Let {n} be a dimension. Suppose we have a sequence of algebraic sets {A_\alpha \subset k_\alpha^n} over algebraically closed fields {k_\alpha}, whose complexity is bounded by a quantity {M} which is uniform in {\alpha}. Then if we set {k := \lim_{\alpha \rightarrow \alpha_\infty} k_\alpha} and {A :=\lim_{\alpha \rightarrow \alpha_\infty} A_\alpha}, then {k} is an algebraically closed field and {A \subset k^n} is an algebraic set (also of complexity at most {M}).

Conversely, every algebraic set in {k^n} is the ultralimit of algebraic sets in {k_\alpha^n} of bounded complexity.

Proof: The fact that {k} is algebraically closed comes from Exercise 2. Now we look at the algebraic sets {A_\alpha}. By adding dummy polynomials if necessary, we can write

\displaystyle A_\alpha = \{ x \in k_\alpha^n: P_{\alpha,1}(x) = \ldots = P_{\alpha,M}(x) = 0 \}

where the {P_{\alpha,1},\ldots,P_{\alpha,M}: k_\alpha^n \rightarrow k_\alpha} of degree at most {M}.

We can then take ultralimits of the {P_{\alpha,i}} to create polynomials {P_{1},\ldots,P_{M}: k^n \rightarrow k} of degree at most {M}. One easily verifies on taking ultralimits that

\displaystyle A = \{ x \in k^n: P_{1}(x) = \ldots = P_{M}(x) = 0 \}

and the first claim follows. The converse claim is proven similarly. \Box

Ultralimits preserve a number of key algebraic concepts (basically because such concepts are definable in first-order logic). We first illustrate this with the algebraic geometry concept of dimension. It is known that every non-empty algebraic set {V} in {k^n} has a dimension {\dim(V)}, which is an integer between {0} and {n}, with the convention that the empty set has dimension {-1}. There are many ways to define this dimension, but one way is to proceed by induction on the dimension {n} as follows. A non-empty algebraic subset of {k^0} has dimension {0}. Now if {n \geq 1}, we say that an algebraic set {V} has dimension {d} for some {0 \leq d \leq n} if the following statements hold:

  • For all but finitely many {t \in k}, the slice {V_t := \{ x \in k^{n-1}: (x,t) \in V \}} either all have dimension {d-1}, or are all empty.
  • For the remaining {t \in k}, the slice {V_t} has dimension at most {d}. If the generic slices {V_t} were all empty, then one of the exceptional {V_t} has to have dimension exactly {d}.

Informally, {A} has dimension {d} iff a generic slice of {A} has dimension {d-1}.

It is a non-trivial fact to show that every algebraic set in {k^n} does indeed have a well-defined dimension between {-1} and {n}.

Now we see how dimension behaves under ultralimits.

Lemma 3 (Continuity of dimension) Suppose that {A_\alpha \subset k_\alpha^n} are algebraic sets over various algebraically closed fields {k_\alpha} of uniformly bounded complexity, and let {A := \lim_{\alpha \rightarrow \alpha_\infty} A_\alpha} be the limiting algebraic set given by Lemma 2. Then {\dim(A) = \lim_{\alpha \rightarrow \alpha_\infty} \dim(A_\alpha)}. In other words, we have {\dim(A) = \dim(A_\alpha)} for all {\alpha} sufficiently close to {\alpha_\infty}.

Proof: One could obtain this directly from Los’s theorem, but it is instructive to do this from first principles.

We induct on dimension {n}. The case {n=0} is trivial, so suppose that {n \geq 1} and the claim has already been shown for {n-1}. Write {d} for the dimension of {A}. If {d=-1}, then {A} is empty and so {A_\alpha} must be empty for all {\alpha} sufficiently close to {\alpha_\infty}, so suppose that {d \geq 0}. By the construction of dimension, the slice {A_t} all have dimension {d-1} (or are all empty) for all but finitely many values {t_1,\ldots,t_r} of {t \in k}. Let us assume that these generic slices {A_t} all have dimension {d-1}; the other case is treated similarly and is left to the reader. As {k} is the ultralimit of the {k_\alpha}, we can write {t_i = \lim_{\alpha \rightarrow \alpha_\infty} t_{\alpha,i}} for each {1 \leq i \leq r}. We claim that for {\alpha} sufficiently close to {\alpha_\infty}, the slices {(A_\alpha)_{t_{\alpha}}} have dimension {d-1} whenever {t_{\alpha} \neq t_{\alpha,1},\ldots,t_{\alpha,r}}. Indeed, suppose that this were not the case. Carefully negating the quantifiers (and using the ultrafilter property), we see that for {\alpha} sufficiently close to {\alpha_\infty}, we can find {t_{\alpha} \neq t_{\alpha,1},\ldots,t_{\alpha,r}} such that {(A_\alpha)_{t_{\alpha}}} has dimension different from {d-1}. Taking ultralimits and writing {t := \lim_{\alpha \rightarrow \alpha_\infty} t_\alpha}, we see from the induction hypothesis that {A_t} has dimension different from {d-1}, contradiction.

We have shown that for {\alpha} sufficiently close to {\alpha_\infty}, all but finitely many slices of {A_\alpha} have dimension {d-1}, and thus by the definition of dimension, {A_\alpha} has dimension {d}, and the claim follows. \Box

We can use this to deduce quantitative algebraic geometry results from qualitative analogues. For instance, from the definition of dimension we have

Lemma 4 (Qualitative Bezout-type theorem) Every dimension {0} algebraic variety is finite.

Using ultrafilter analysis, we immediately obtain the following quantitative analogue:

Lemma 5 (Quantitative Bezout-type theorem) Let {A \subset k^n} be an algebraic set of dimension {0} and complexity at most {M} over a field {k}. Then the cardinality {A} is bounded by a quantity {C_M} depending only on {M} (in particular, it is independent of {k}).

Proof: By passing to the algebraic closure, we may assume that {k} is algebraically closed.

Suppose this were not the case. Carefully negating the quantifiers (and using the axiom of choice), we may find a sequence {A_\alpha \subset k_\alpha^n} of dimension {0} algebraic sets and uniformly bounded complexity over algebraically closed fields {k_\alpha}, such that {|A_\alpha| \rightarrow \infty} as {\alpha \rightarrow \infty}. We pass to an ultralimit to obtain a limit algebraic set {A := \lim_{\alpha \rightarrow \alpha_\infty} A_\alpha}, which by Lemma 3 has dimension {0}, and is thus finite by Lemma 4. But then this forces {A_\alpha} to be bounded for {\alpha} sufficiently close to {\alpha_\infty} (indeed we have {|A_\alpha| = |A|} in such a neighbourhood), contradiction. \Box

Remark 5 Note that this proof gives absolutely no bound on {C_M} in terms of {M}! One can get such a bound by using more effective tools, such as the actual Bezout theorem, but this requires more actual knowledge of how the qualitative algebraic results are proved. If one only knows the qualitative results as a black box, then the ineffective quantitative result is the best one can do.

Now we give another illustration of the method. The following fundamental result in algebraic geometry is known:

Lemma 6 (Qualitative Noetherian condition) There does not exist an infinite decreasing sequence of algebraic sets in a affine space {k^n}, in which each set is a proper subset of the previous one.

Using ultralimit analysis, one can convert this qualitative result into an ostensibly stronger quantitative version:

Lemma 7 (Quantitative Noetherian condition) Let {F: {\mathbb N} \rightarrow {\mathbb N}} be a function. Let {A_1 \supsetneq A_2 \supsetneq \ldots \supsetneq A_R} be a sequence of properly nested algebraic sets in {k^n} for some algebraically closed field {k}, such that each {A_i} has complexity at most {F(i)}. Then {R} is bounded by {C_F} for some {C_F} depending only on {F} (in particular, it is independent of {k}).

Remark 6 Specialising to the case when {F} is a constant {M}, we see that there is an upper bound on proper nested sequences of algebraic sets of bounded complexity; but the statement is more powerful than this because we allow {F} to be non-constant. Note that one can easily use this strong form of the quantitative Noetherian condition to recover Lemma 6 (why?), but if one only knew Lemma 7 in the constant case {F=M} then this does not obviously recover Lemma 6.

Proof: Note that {n} is bounded by {F(1)}, so it will suffice to prove this claim for a fixed {n}.

Fix {n}. Suppose the claim failed. Carefully negating all the quantifiers (and using the axiom of choice), we see that there exists an {F}, a sequence {k_\alpha} of algebraically closed fields, a sequence {R_\alpha} going to infinity, and sequences

\displaystyle A_{\alpha,1} \supsetneq \ldots \supsetneq A_{\alpha,R_\alpha}

of properly nested algebraic sets in {k_\alpha^n}, with each {A_{\alpha,i}} having complexity at most {F(i)}.

We take an ultralimit of everything that depends on {\alpha}, creating an algebraically closed field {k = \lim_{\alpha \rightarrow \alpha_\infty} k_\alpha}, and an infinite sequence

\displaystyle A_1 \supsetneq A_2 \supsetneq \ldots

of properly nested algebraic sets in {k^n}. (In fact, we could continue this sequence into a limit sequence up to the unbounded limit number {\lim_{\alpha \rightarrow \alpha_\infty} R_\alpha}, but we will not need this overspill here.) But this contradicts Lemma 6. \Box

Again, this argument gives absolutely no clue as to how {C_F} is going to depend on {F}. (Indeed, I would be curious to know what this dependence is exactly.)

Let us give one last illustration of the ultralimit analysis method, which contains an additional subtlety. Define an algebraic variety to be an algebraic set which is irreducible, which means that it cannot be expressed as the union of two proper subalgebraic sets. This notation is stable under ultralimits:

Lemma 8 (Continuity of irreducibility) Suppose that {A_\alpha \subset k_\alpha^n} are algebraic sets over various algebraically closed fields {k_\alpha} of uniformly bounded complexity, and let {A := \lim_{\alpha \rightarrow \alpha_\infty} A_\alpha} be the limiting algebraic set given by Lemma 2. Then {A} is an algebraic variety if and only if {A_\alpha} is an algebraic variety for all {\alpha} sufficiently close to {\alpha_\infty}.

However, this lemma is somewhat harder to prove than previous ones, because the notion of irreducibility is not quite a first order statement. The following exercises show the limit of what one can do without using some serious algebraic geometry:

Exercise 3 Let the notation and assumptions be as in Lemma 8. Show that if {A} is not an algebraic variety, then {A_\alpha} is a not algebraic variety for all {\alpha} sufficiently close to {\alpha_\infty}.

Exercise 4 Let the notation and assumptions be as in Lemma 8. Call an algebraic set {M}-irreducible if it cannot be expressed as the union of two proper algebraic sets of complexity at most {M}. Show that if {A} is an algebraic variety, then for every {M \geq 1}, {A_\alpha} is {M}-irreducible for all {\alpha} sufficiently close to {\alpha_\infty}.

These exercises are not quite strong enough to give Lemma 8, because {M}-irreducibility is a weaker concept than irreducibility. However, one can do better by applying some further facts in algebraic geometry. Given an algebraic set {A} of dimension {d \geq 0} in an affine space {k^n}, one can assign a degree {\deg(A)}, which is a positive integer such that {|A \cap V| = \deg(A)} for generic {n-d}-dimensional affine subspaces of {k^n}, which means that {V} belongs to the affine Grassmannian {Gr} of {n-d}-dimensional affine subspaces of {k^n}, after removing an algebraic subset of {Gr} of dimension strictly less than that of {Gr}. It is a standard fact of algebraic geometry that every algebraic set can be assigned a degree. Somewhat less trivially, the degree controls the complexity:

Theorem 9 (Degree controls complexity) Let {A} be an algebraic variety of {k^n} of degree {D}. Then {A} has complexity at most {C_{n,D}} for some constants {n, D} depending only on {n, D}.

Proof: (We thank Jordan Ellenberg and Ania Otwinowska for this argument.) It suffices to show that {A} can be cut out by polynomials of degree {D}, since the space of polynomials of degree {D} that vanish on {A} is a vector space of dimension bounded only by {n} and {D}.

Let {A} have dimension {d}. We pick a generic affine subspace {V} of {k^n} of dimension {n-d-2}, and consider the cone {C(V,A)} formed by taking all the union of all the lines joining a point in {V} to a point in {A}. This is an algebraic image of {V \times A \times {\mathbb R}} and is thus generically an algebraic set of dimension {n-1}, i.e. a hypersurface. Furthermore, as {A} has degree {D}, it is not hard to see that {C(V,A)} has degree {D} as well. Since a hypersurface is necessarily cut out by a single polynomial, this polynomial must have degree {D}.

To finish the claim, it suffices to show that the intersection of the {C(V,A)} as {V} varies is exactly {A}. Clearly, this intersection contains {A}. Now let {p} be any point not in {A}. The cone of {A} over {p} can be viewed as an algebraic subset of the projective space {P^{n-1}} of dimension {d}; meanwhile, the cone of a generic subspace {V} of dimension {n-d-2} is a generic subspace of {P^{n-1}} of the same dimension. Thus, for generic {V}, these two cones do not intersect, and thus {p} lies outside {C(V,A)}, and the claim follows. \Box

Remark 7 There is a stronger theorem that asserts that if the degree of a scheme in {k^n} is bounded, then the complexity of that scheme is bounded as well. The main difference between a variety and a scheme here is that for a scheme, we not only specify the set of points cut out by the scheme, but also the ideal of functions that we want to think of as vanishing on that set. This theorem is significantly more difficult than the above result; it is Corollary 6.11 of Kleiman’s SGA6 article.

Given this theorem, we can now prove Lemma 8.

Proof: In view of Exercise 3, it suffices to show that if {A} is irreducible, then the {A_\alpha} are irreducible for {\alpha} sufficiently close to {\alpha_0}.

The algebraic set {A} has some dimension {d} and degree {D}, thus {|A \cap V| = D} for generic affine {n-d}-dimensional subspaces {V} of {k^n}. Undoing the limit using Lemma 2 and Lemma 3 (adapted to the Grassmannian {Gr} rather than to affine space), we see that for {\alpha} sufficiently close to {\alpha_0}, {|A_\alpha \cap V_\alpha| = D} for generic affine {n-d}-dimensional subspaces {V_\alpha} of {k_\alpha^n}. In other words, {A_\alpha} has degree {D}, and thus by Theorem 9, any algebraic variety of {A_\alpha} of the same dimension {d} as {A_\alpha} will have complexity bounded by {C_{n,D}} uniformly in {\alpha}. Let {B_\alpha} be a {d}-dimensional algebraic subvariety of {A_\alpha}, and let {B} be the ultralimit of the {B_\alpha}. Then by Lemma 2, Lemma 3 and the uniform complexity bound, {B} is a {d}-dimensional algebraic subset of {A}, and thus must equal all of {A} by irreducibility of {A}. But this implies that {B_\alpha=A_\alpha} for all {\alpha} sufficiently close to {\alpha_0}, and the claim follows. \Box

We give a sample application of this result. From the Noetherian condition we easily obtain

Lemma 10 (Qualitative decomposition into varieties) Every algebraic set can be expressed as a union of finitely many algebraic varieties.

Using ultralimit analysis, we can make this quantitative:

Lemma 11 (Quantitative decomposition into varieties) Let {A \subset k^n} be an algebraic set of complexity at most {M} over an algebraically closed field {k}. Then {A} can be expressed as the union of at most {C_M} algebraic varieties of complexity at most {C_M}, where {C_M} depends only on {M}.

Proof: As {n} is bounded by {M}, it suffices to prove the claim for a fixed {n}.

Fix {n} and {M}. Suppose the claim failed. Carefully negating all the quantifiers (and using the axiom of choice), we see that there exists a sequence {A_\alpha\subset k_\alpha^n} of uniformly bounded complexity, such that {A_\alpha} cannot be expressed as the union of at most {\alpha} algebraic varieties of complexity at most {\alpha}. Now we pass to an ultralimit, obtaining a limit algebraic set {A \subset k^n}. As discussed earlier, {A} is an algebraic set over an algebraically closed field and is thus expressible as the union of a finite number of algebraic varieties {A_1,\ldots,A_m}. By Lemma 2 and Lemma 8, each {A_i} is an ultralimit of algebraic varieties {A_{\alpha,i}} of bounded complexity. The claim follows. \Box

— 3. Application: Quantitative Gromov theorem —

As a further illustration, I’ll redo an application of the correspondence principle from a previous post of mine. The starting point is the following famous theorem of Gromov:

Theorem 12 (Qualitative Gromov theorem) Every finitely generated group of polynomial growth is virtually nilpotent.

Let us now make the observation (already observed in Gromov’s original paper) that this theorem implies (and is in fact equivalent to) a quantitative version:

Theorem 13 (Quantitative Gromov theorem) For every {C, d} there exists {R} such that if {G} is generated by a finite set {S} with the growth condition {|B_S(r)| \leq Cr^d} for all {1 \leq r \leq R}, then {G} is virtually nilpotent, and furthermore it has a nilpotent subgroup of step and index at most {M_{C,d}} for some {M_{C,d}} depending only on {C,d}. Here {B_S(r)} is the ball of radius {r} generated by the set {S}.

Proof: We use ultralimit analysis. Suppose this theorem failed. Carefully negating the quantifiers, we find that there exists {C, d}, as well as a sequence {G_\alpha} of groups generated by a finite set {S_\alpha} such that {|B_{S_\alpha}(r)| \leq C r^d} for all {1 \leq r \leq \alpha}, and such that {G_\alpha} does not contain any nilpotent subgroup of step and index at most {\alpha}.

Now we take ultralimits, setting {G := \lim_{\alpha \rightarrow \alpha_\infty} G_\alpha} and {S := \lim_{\alpha \rightarrow \alpha_\infty} S_\alpha}. As the {S_\alpha} have cardinality uniformly bounded (by {Cr^1}), {S} is finite. The set {S} need not generate {G}, but it certainly generates some subgroup {\langle S \rangle} of this group. Since {|B_{S_\alpha}(r)| \leq C r^d} for all {\alpha} and all {1 \leq r \leq \alpha}, we see on taking ultralimits that {|B_S(r)| \leq Cr^d} for all {r}. Thus {\langle S \rangle} is of polynomial growth, and is thus virtually nilpotent.

Now we need to undo the ultralimit, but this requires a certain amount of preparation. We know that {\langle S \rangle} contains a finite index nilpotent subgroup {G'}. As {\langle S \rangle} is finitely generated, the finite index subgroup {G'} is also. (Proof: for {R} large enough, {B_S(R)} will intersect every coset of {G'}. As a consequence, one can describe the action of {\langle S\rangle} on the finite set {\langle S \rangle/G'} using only knowledge of {B_S(2R+1) \cap G'}. In particular, {B_S(2R+1) \cap G'} generates a finite index subgroup. Increasing {R}, the index of this subgroup is non-increasing, and thus must eventually stabilise. At that point, we generate all of {G'}.) Let {S'} be a set of generators for {G'}. Since {G'} is nilpotent of some step {s}, all commutators of {S'} of length at least {s+1} vanish.

Writing {S'} as an ultralimit of {S'_\alpha}, we see that the {S'_\alpha} are finite subsets of {G_\alpha} which generate some subgroup {G'_\alpha}. Since all commutators of {S'} of length at least {s+1} vanish, the same is true for {S'_\alpha} for {\alpha} close enough to {\alpha_\infty}, and so {G'_\alpha} is nilpotent for such {\alpha} with step bounded uniformly in {\alpha}.

Finally, if we let {R} be large enough that {B_S(R)} intersects every coset of {G'}, then we can cover {B_S(R+1)} by a product of {B_S(R)} and some elements of {G'} (which are of course finite products of elements in {S'} and their inverses). Undoing the ultralimit, we see that for {\alpha} sufficiently close to {\alpha_\infty}, we can cover {B_{S_\alpha}(R+1)} by the product of {B_{S_\alpha}(R)} and some elements of {G'_\alpha}. Iterating this we see that we can cover all of {G_\alpha} by {B_{S_\alpha}(R)} times {G'_\alpha}, and so {G'_\alpha} has finite index bounded uniformly in {\alpha}. But this contradicts the construction of {G_\alpha}. \Box

Remark 8 As usual, the argument gives no effective bound on {M_{C,d}}. Obtaining such an effective bound is in fact rather non-trivial; see this paper of Yehuda Shalom and myself for further discussion.

— 4. Application: Furstenberg correspondence principle —

Let me now redo another application of the correspondence principle via ultralimit analysis. We will begin with the following famous result of Furstenberg:

Theorem 14 (Furstenberg recurrence theorem) Let {(X, {\mathcal B}, \mu, T)} be a measure-preserving system, and let {A \subset X} have positive measure. Let {k \geq 1}. Then there exists {r > 0} such that {A \cap T^r A \cap \ldots \cap T^{(k-1)r} A} is non-empty.

We then use this theorem and ultralimit analysis to derive the following well-known result of Szemerédi:

Theorem 15 (Szemerédi’s theorem) Every set of integers of positive upper density contains arbitrarily long arithmetic progressions.

Proof: Suppose this were not the case. Then there exists {k \geq 1} and a set {A} of positive upper density with no progressions of length {k}. Unpacking the definition of positive upper density, this means that there exists {\delta > 0} and a sequence {N_\alpha \rightarrow \infty} such that

\displaystyle |A \cap [-N_\alpha, N_\alpha]| \geq \delta |[-N_\alpha, N_\alpha]|

for all {\alpha}. We pass to an ultralimit, introducing the limit natural number {N := \lim_{\alpha \rightarrow \alpha_\infty} N_\alpha} and using the ultrapower {{}^* A =\lim_{\alpha \rightarrow \alpha_\infty} A} (note that {A} is a space, not an ordinary object). Then we have

\displaystyle |{}^*A \cap [-N, N]| \geq \delta |[-N, N]|

where the cardinalities are in the limit sense. Note also that {{}^*A} has no progressins of length {k}.

Consider the space of all boolean combinations of shifts {{}^* A + r} of {{}^* A}, where {r} ranges over (standard) integers, thus for instance

\displaystyle ({}^* A + 3) \cap ({}^* A + 5) \backslash ({}^* A - 7)

would be such a set. We call such sets definable sets. We give each such definable set {B} a limit measure

\displaystyle \mu(B) := |B \cap [-N,N]| / [-N,N].

This measure takes values in the limit interval {{}^*[0,1]} and is clearly a finitely additive probability measure. It is also nearly translation invariant in the sense that

\displaystyle \mu(B+k) = \mu(B) + o(1)

for any standard integer {k}, where {o(1)} is an infinitesimal (i.e. a limit real number which is smaller in magnitude than any positive standard real number). In particular, the standard part {st(\mu)} of {\mu} is a finitely additive standard probability measure. Note from construction that {st(\mu)(A) \geq \delta}.

Now we convert this finitely additive measure into a countably additive one. Let {2^{\mathbb Z}} be the set of all subsets {B} of the integers. This is a compact metrisable space, which we endow with the Borel {\sigma}-algebra {{\mathcal B}} and the standard shift {T: B \mapsto B+1}. The Borel {\sigma}-algebra is generated by the clopen sets in this space, which are boolean combinations of {T^r E}, where {E} is the basic cylinder set {E := \{ B \in 2^{\mathbb Z}: 0 \in B \}}. Each clopen set can be assigned a definable set in {{}^* {\mathbb Z}} by mapping {T^r E} to {{}^* A + r} and then extending by boolean combinations. The finitely additive probability measure {st(\mu)} on definable sets then pulls back to a finitely additive probability measure {\nu} on clopen sets in {2^{\mathbb Z}}. Applying the Carathéodory extension theorem (taking advantage of the compactness of {2^{\mathbb Z}}), we can extend this finitely additive measure to a countably additive Borel probability measure.

By construction, {\nu(E) \geq \delta > 0}. Applying Theorem 14, we can find {r > 0} such that {E \cap T^r E \cap \ldots \cap T^{(k-1)r} E} is non-empty. This implies that {{}^* A \cap ({}^* A + r) \cap \ldots \cap ({}^* A + (k-1)r)} is non-empty, and so {{}^* A} contains an arithmetic progression of length {k}, a contradiction. \Box

Note that the above argument is nearly identical to the usual proof of the correspondence principle, which uses Prokhorov’s theorem instead of ultrafilters. The measure constructed above is essentially the Loeb measure for the ultraproduct.

— 5. Relationship with nonstandard analysis —

Ultralimit analysis is extremely close to, but subtly different from, nonstandard analysis, because of a shift of emphasis and philosophy. The relationship can be illustrated by the following table of analogies:

Digits Strings of digits Numbers
Symbols Strings of symbols Sentences
Set theory Finite von Neumann ordinals Peano arithmetic
Rational numbers {{\mathbb Q}} {\overline{{\mathbb Q}}} Real numbers {{\mathbb R}}
Real analysis Analysis on {\overline{{\mathbb R}}} Complex analysis
{{\mathbb R}} {{\mathbb R}^2} Euclidean plane geometry
{{\mathbb R}} Coordinate chart atlases Manifolds
{{\mathbb R}} Matrices Linear transformations
Algebra Sheaves of rings Schemes
Deterministic theory Measure theory Probability theory
Probability theory Von Neumann algebras Noncommutative probability theory
Classical mechanics Hilbert space mechanics Quantum mechanics
Finitary analysis Asymptotic analysis Infinitary analysis
Combinatorics Correspondence principle Ergodic theory
Quantitative analysis Compactness arguments Qualitative analysis
Standard analysis Ultralimit analysis Nonstandard analysis

(Here {\overline{{\mathbb R}}} is the algebraic completion of the reals, but {\overline{{\mathbb Q}}} is the metric completion of the rationals.)

In the first column one has a “base” theory or concept, which implicitly carries with it a certain ontology and way of thinking, regarding what objects one really cares to study, and what objects really “exist” in some mathematical sense. In the second column one has a fancier theory than the base theory (typically a “limiting case”, a “generalisation”, or a “completion” of the base theory), but one which still shares a close relationship with the base theory, in particular largely retaining the ontological and conceptual mindset of that theory. In the third column one has a new theory, which is modeled by the theories in the middle column, but which is not tied to that model, or to the implicit ontology and viewpoint carried by that model. For instance, one can think of a complex number as an element of the algebraic completion of the reals, but one does not have to, and indeed in many parts of complex analysis or complex geometry one wants to ignore the role of the reals as much as possible. Similarly for other rows of the above table. See for instance these lecture notes of mine for further discussion of the distinction between measure theory and probability theory.

[The relationship between the second and third columns of the above table is also known as the map-territory relation.]

Returning to ultralimit analysis, this is a type of analysis which still shares close ties with its base theory, standard analysis, in that all the objects one considers are either standard objects, or ultralimits of such objects (and similarly for all the spaces one considers). But more importantly, one continues to think of nonstandard objects as being ultralimits of standard objects, rather than having an existence which is largely independent of the concept of base theory of standard analysis. This perspective is reversed in nonstandard analysis: one views the nonstandard universe as existing in its own right, and the fact that the standard universe can be embedded inside it is a secondary feature (albeit one which is absolutely essential if one is to use nonstandard analysis in any nontrivial manner to say something new about standard analysis). In nonstandard analysis, ultrafilters are viewed as one tool in which one can construct the nonstandard universe from the standard one, but their role in the subject is otherwise minimised. In contrast, the ultrafilter {\alpha_\infty} plays a prominent role in ultralimit analysis.

In my opinion, none of the three columns here are inherently “better” than the other two; but they do work together quite well. In particular, the middle column serves as a very useful bridge to carry results back and forth between the worlds of the left and right columns.