Roughly speaking, mathematical analysis can be divided into two major styles, namely hard analysis and soft analysis. The precise distinction between the two types of analysis is imprecise (and in some cases one may use a blend the two styles), but some key differences can be listed as follows.

  • Hard analysis tends to be concerned with quantitative or effective properties such as estimates, upper and lower bounds, convergence rates, and growth rates or decay rates. In contrast, soft analysis tends to be concerned with qualitative or ineffective properties such as existence and uniqueness, finiteness, measurability, continuity, differentiability, connectedness, or compactness.
  • Hard analysis tends to be focused on finitary, finite-dimensional or discrete objects, such as finite sets, finitely generated groups, finite Boolean combination of boxes or balls, or “finite-complexity” functions, such as polynomials or functions on a finite set. In contrast, soft analysis tends to be focused on infinitary, infinite-dimensional, or continuous objects, such as arbitrary measurable sets or measurable functions, or abstract locally compact groups.
  • Hard analysis tends to involve explicit use of many parameters such as {\epsilon}, {\delta}, {N}, etc. In contrast, soft analysis tends to rely instead on properties such as continuity, differentiability, compactness, etc., which implicitly are defined using a similar set of parameters, but whose parameters often do not make an explicit appearance in arguments.
  • In hard analysis, it is often the case that a key lemma in the literature is not quite optimised for the application at hand, and one has to reprove a slight variant of that lemma (using a variant of the proof of the original lemma) in order for it to be suitable for applications. In contrast, in soft analysis, key results can often be used as “black boxes”, without need of further modification or inspection of the proof.
  • The properties in soft analysis tend to enjoy precise closure properties; for instance, the composition or linear combination of continuous functions is again continuous, and similarly for measurability, differentiability, etc. In contrast, the closure properties in hard analysis tend to be fuzzier, in that the parameters in the conclusion are often different from the parameters in the hypotheses. For instance, the composition of two Lipschitz functions with Lipschitz constant {K} is still Lipschitz, but now with Lipschitz constant {K^2} instead of {K}. These changes in parameters mean that hard analysis arguments often require more “bookkeeping” than their soft analysis counterparts, and are less able to utilise algebraic constructions (e.g. quotient space constructions) that rely heavily on precise closure properties.

In the lectures so far, focusing on the theory surrounding Hilbert’s fifth problem, the results and techniques have fallen well inside the category of soft analysis. However, we will now turn to the theory of approximate groups, which is a topic which is traditionally studied using the methods of hard analysis. (Later we will also study groups of polynomial growth, which lies on an intermediate position in the spectrum between hard and soft analysis, and which can be profitably analysed using both styles of analysis.)

Despite the superficial differences between hard and soft analysis, though, there are a number of important correspondences between results in hard analysis and results in soft analysis. For instance, if one has some sort of uniform quantitative bound on some expression relating to finitary objects, one can often use limiting arguments to then conclude a qualitative bound on analogous expressions on infinitary objects, by viewing the latter objects as some sort of “limit” of the former objects. Conversely, if one has a qualitative bound on infinitary objects, one can often use compactness and contradiction arguments to recover uniform quantitative bounds on finitary objects as a corollary.

Remark 1 Another type of correspondence between hard analysis and soft analysis, which is “syntactical” rather than “semantical” in nature, arises by taking the proofs of a soft analysis result, and translating such a qualitative proof somehow (e.g. by carefully manipulating quantifiers) into a quantitative proof of an analogous hard analysis result. This type of technique is sometimes referred to as proof mining in the proof theory literature, and is discussed in this previous blog post (and its comments). We will however not employ systematic proof mining techniques here, although in later posts we will informally borrow arguments from infinitary settings (such as the methods used to construct Gleason metrics) and adapt them to finitary ones.

Let us illustrate the correspondence between hard and soft analysis results with a simple example.

Proposition 1 Let {X} be a sequentially compact topological space, let {S} be a dense subset of {X}, and let {f: X \rightarrow [0,+\infty]} be a continuous function (giving the extended half-line {[0,+\infty]} the usual order topology). Then the following statements are equivalent:

  • (i) (Qualitative bound on infinitary objects) For all {x \in X}, one has {f(x) < +\infty}.
  • (ii) (Quantitative bound on finitary objects) There exists {M < +\infty} such that {f(x) \leq M} for all {x \in S}.

In applications, {S} is typically a (non-compact) set of “finitary” (or “finite complexity”) objects of a certain class, and {X} is some sort of “completion” or “compactification” of {S} which admits additional “infinitary” objects that may be viewed as limits of finitary objects.

Proof: To see that (ii) implies (i), observe from density that every point {x} in {X} is adherent to {S}, and so given any neighbourhood {U} of {x}, there exists {y \in S \cap U}. Since {f(y) \leq M}, we conclude from the continuity of {f} that {f(x) \leq M} also, and the claim follows.

Conversely, to show that (i) implies (ii), we use the “compactness and contradiction” argument. Suppose for sake of contradiction that (ii) failed. Then for any natural number {n}, there exists {x_n \in S} such that {f(x_n) \geq n}. (Here we have used the axiom of choice, which we will assume throughout this course.) Using sequential compactness, and passing to a subsequence if necessary, we may assume that the {x_n} converge to a limit {x \in X}. By continuity of {f}, this implies that {f(x) = +\infty}, contradicting (i). \Box

Remark 2 Note that the above deduction of (ii) from (i) is ineffective in that it gives no explicit bound on the uniform bound {M} in (ii). Without any further information on how the qualitative bound (i) is proven, this is the best one can do in general (and this is one of the most significant weaknesses of infinitary methods when used to solve finitary problems); but if one has access to the proof of (i), one can often finitise or proof mine that argument to extract an effective bound for {M}, although often the bound one obtains in the process is quite poor (particularly if the proof of (i) relied extensively on infinitary tools, such as limits). See this blog post for some related discussion.

The above simple example illustrates that in order to get from an “infinitary” statement such as (i) to a “finitary” statement such as (ii), a key step is to be able to take a sequence {(x_n)_{n \in {\bf N}}} (or in some cases, a more general net {(x_\alpha)_{\alpha \in A}}) of finitary objects and extract a suitable infinitary limit object {x}. In the literature, there are three main ways in which one can extract such a limit:

  • (Topological limit) If the {x_n} are all elements of some topological space {S} (e.g. an incomplete function space) which has a suitable “compactification” or “completion” {X} (e.g. a Banach space), then (after passing to a subsequence if necessary) one can often ensure the {x_n} converge in a topological sense (or in a metrical sense) to a limit {x}. The use of this type of limit to pass between quantitative/finitary and qualitative/infinitary results is particularly common in the more analytical areas of mathematics (such as ergodic theory, asymptotic combinatorics, or PDE), due to the abundance of useful compactness results in analysis such as the (sequential) Banach-Alaoglu theorem, Prokhorov’s theorem, the Helly selection theorem, the Arzelá-Ascoli theorem, or even the humble Bolzano-Weierstrass theorem. However, one often has to take care with the nature of convergence, as many compactness theorems only guarantee convergence in a weak sense rather than in a strong one.
  • (Categorical limit) If the {x_n} are all objects in some category (e.g. metric spaces, groups, fields, etc.) with a number of morphisms between the {x_n} (e.g. morphisms from {x_{n+1}} to {x_n}, or vice versa), then one can often form a direct limit {\lim_{\rightarrow} x_n} or inverse limit {\lim_{\leftarrow} x_n} of these objects to form a limiting object {x}. The use of these types of limits to connect quantitative and qualitative results is common in subjects such as algebraic geometry that are particularly amenable to categorical ways of thinking. (We have seen inverse limits appear in the discussion of Hilbert’s fifth problem, although in that context they were not really used to connect quantitative and qualitative results together.)
  • (Logical limit) If the {x_n} are all distinct spaces (or elements or subsets of distinct spaces), with few morphisms connecting them together, then topological and categorical limits are often unavailable or unhelpful. In such cases, however, one can still tie together such objects using an ultraproduct construction (or similar device) to create a limiting object {\lim_{n \rightarrow \alpha} x_n} or limiting space {\prod_{n \rightarrow \alpha} x_n} that is a logical limit of the {x_n}, in the sense that various properties of the {x_n} (particularly those that can be phrased using the language of first-order logic) are preserved in the limit. As such, logical limits are often very well suited for the task of connecting finitary and infinitary mathematics together. Ultralimit type constructions are of course used extensively in logic (particularly in model theory), but are also popular in metric geometry. They can also be used in many of the previously mentioned areas of mathematics, such as algebraic geometry (as discussed in this previous post).

The three types of limits are analogous in many ways, with a number of connections between them. For instance, in the study of groups of polynomial growth, both topological limits (using the metric notion of Gromov-Hausdorff convergence) and logical limits (using the ultralimit construction) are commonly used, and to some extent the two constructions are at least partially interchangeable in this setting. (See also these previous posts for the use of ultralimits as a substitute for topological limits.) In the theory of approximate groups, though, it was observed by Hrushovski that logical limits (and in particular, ultraproducts) are the most useful type of limit to connect finitary approximate groups to their infinitary counterparts. One reason for this is that one is often interested in obtaining results on approximate groups {A} that are uniform in the choice of ambient group {G}. As such, one often seeks to take a limit of approximate groups {A_n} that lie in completely unrelated ambient groups {G_n}, with no obvious morphisms or metrics tying the {G_n} to each other. As such, the topological and categorical limits are not easily usable, whereas the logical limits can still be employed without much difficulty.

Logical limits are closely tied with non-standard analysis. Indeed, by applying an ultraproduct construction to standard number systems such as the natural numbers {{\bf N}} or the reals {{\bf R}}, one can obtain nonstandard number systems such as the nonstandard natural numbers {{}^* {\bf N}} or the nonstandard real numbers (or hyperreals) {{}^* {\bf R}}. These nonstandard number systems behave very similarly to their standard counterparts, but also enjoy the advantage of containing the standard number systems as proper subsystems (e.g. {{\bf R}} is a subring of {{}^* {\bf R}}), which allows for some convenient algebraic manipulations (such as the quotient space construction to create spaces such as {{}^* {\bf R} / {\bf R}}) which are not easily accessible in the purely standard universe. Nonstandard spaces also enjoy a useful completeness property, known as countable saturation, which is analogous to metric completeness (as discussed in this previous blog post) and which will be particularly useful for us in tying together the theory of approximate groups with the theory of Hilbert’s fifth problem. See this previous post for more discussion on ultrafilters and nonstandard analysis.

In these notes, we lay out the basic theory of ultraproducts and ultralimits (in particular, proving Los’s theorem, which roughly speaking asserts that ultralimits are limits in a logical sense, as well as the countable saturation property alluded to earlier). We also lay out some of the basic foundations of nonstandard analysis, although we will not rely too heavily on nonstandard tools in this course. Finally, we apply this general theory to approximate groups, to connect finite approximate groups to an infinitary type of approximate group which we will call an ultra approximate group. We will then study these ultra approximate groups (and models of such groups) in more detail in the next set of notes.

Remark 3 Throughout these notes (and in the rest of the course), we will assume the axiom of choice, in order to easily use ultrafilter-based tools. If one really wanted to expend the effort, though, one could eliminate the axiom of choice from the proofs of the final “finitary” results that one is ultimately interested in proving, at the cost of making the proofs significantly lengthier. Indeed, there is a general result of Gödel that any result which can be stated in the language of Peano arithmetic (which, roughly speaking, means that the result is “finitary” in nature), and can be proven in set theory using the axiom of choice (or more precisely, in the ZFC axiom system), can also be proven in set theory without the axiom of choice (i.e. in the ZF system). As this course is not focused on foundations, we shall simply assume the axiom of choice henceforth to avoid further distraction by such issues.

— 1. Ultrafilters —

The concept of an ultrafilter will be fundamental. We will only need to consider ultrafilters on the natural numbers {{\bf N}}, although one can certainly consider ultrafilters on more general sets.

Definition 2 (Ultrafilter) An filter {\alpha} on the natural numbers is a collection of sets of natural numbers obeying the following axioms:

  • (Monotonicity) If {E \subset F \subset {\bf N}}, and {E \in \alpha}, then {F \in \alpha}.
  • (Intersection) If {E, F \in \alpha}, then {E \cap F \in \alpha}.
  • (Properness) {\emptyset \not \in \alpha}.

An ultrafilter {\alpha} on the natural numbers is a filter which obeys an additional axiom:

  • (Maximality) If {E \subset {\bf N}}, then exactly one of {E} and {{\bf N} \backslash E} lies in {\alpha}.

A nonprincipal ultrafilter is an ultrafilter {\alpha} that obeys one final axiom:

  • (Nonprincipality) No finite set belongs to {\alpha}. (Equivalently: any cofinite set will belong to {\alpha}.)

Given a nonprincipal ultrafilter {\alpha}, we say that a set {E \subset {\bf N}} is {\alpha}-large if it is contained in {\alpha}, and {\alpha}-small otherwise. A property {P(n)} of the natural numbers {n \in {\bf N}} is said to hold for all {n} sufficiently close to {\alpha} if it holds in an {\alpha}-large set.

The most basic fact about nonprincipal ultrafilters is that they exist – a result due to Tarski, and known as the ultrafilter lemma:

Exercise 1 (Ultrafilter lemma) Show that there exists at least one nonprincipal ultrafilter. (Hint: first construct a nonprincipal filter, and then use Zorn’s lemma to place it inside a maximal nonprincipal filter.)

Exercise 2 Call an ultrafilter principal if it is not nonprincipal. Show that for any natural number {n_0}, the set {\{ E \subset {\bf N}: n_0 \in E \}} is a principal ultrafilter, and conversely every principal ultrafilter is of this form. Thus, the space of principal ultrafilters can be identified with {{\bf N}}.

The space of all ultrafilters is denoted {\beta {\bf N}}, and so by the preceding exercise one can view {{\bf N}} as a subset of {\beta {\bf N}}, with {\beta {\bf N} \backslash {\bf N}} denoting the nonprincipal ultrafilters.

Ultrafilters can be interpreted in a number of different ways, as indicated by the exercises below.

Exercise 3 (Ultrafilters as finitely additive probability measures) If {\alpha} is an ultrafilter, show that the map {\mu: 2^{\bf N} \rightarrow \{0,1\}} that maps {\alpha}-large subsets of {{\bf N}} to {1} and {\alpha}-small subsets of {{\bf N}} to {0}, is a finitely additive probability measure (thus {\mu(E)+\mu(F)=\mu(E \cup F)} whenever {E, F \subset {\bf N}} are disjoint). Conversely, show that every finitely additive probability measure {\mu: 2^{\bf N} \rightarrow \{0,1\}} that takes values in {\{0,1\}} arises in this manner.

In view of the above exercise, one may view “{\alpha}-large” as analogous to “full measure”, and “holding for all {n} sufficiently close to {\alpha}” as analogous to “holding for almost all {n}“, except that the measure is only finitely additive instead of countably additive, and so concepts such as {\alpha}-largeness are only stable under finitely many intersections, rather than countably many intersections.

Exercise 4 (Ultrafilters as Stone-Cech compactification of {{\bf N}}) We view {\beta {\bf N}} as a subset of the power set {2^{2^{\bf N}}}, and give it the induced topology from the product topology on {2^{2^{\bf N}}}.

  • (i) If {\alpha} is a nonprincipal ultrafilter, show that every neighbourhood of {\alpha} in {\beta {\bf N}} intersects {{\bf N}} in an {\alpha}-large set, and that every {\alpha}-large set arises in this manner. (This explains the notation “{n} sufficiently close to {\alpha}“.)
  • (ii) Show that this makes {\beta {\bf N}} a compactification of {{\bf N}} in the sense that it is compact Hausdorff and contains {{\bf N}} as a dense subset.
  • (iii) Show that {\beta {\bf N}} is a universal compactification (or Stone-Cech compactification), thus if {X} is any other compactification of {{\bf N}}, then there is a unique continuous map {f: \beta {\bf N} \rightarrow X} that is the identity on {{\bf N}}.
  • (iv) If {Y} is any compact Hausdorff space, show that every function {f: {\bf N} \rightarrow Y} has a unique continuous extension {\beta f: \beta {\bf N} \rightarrow Y} to the space {\beta {\bf N}}.

Remark 4 More discussion on the Stone-Cech compactification can be found in this previous blog post. The compact space {\beta {\bf N}} can also be endowed with an interesting semigroup structure, which is of importance in Ramsey theory and ergodic theory; see this previous post for more details.

Exercise 5 (Ultrafilters as Banach limits) Recall that a functional {\lambda: \ell^\infty({\bf N}) \rightarrow {\bf C}} from the *-algebra {\ell^\infty({\bf N})} of bounded complex sequences {(a_n)_{n \in {\bf N}}} to the complex numbers is a *-homomorphism if it is complex-linear and obeys the conjugation law

\displaystyle \lambda(( \overline{a_n} )_{n \in {\bf N}}) = \overline{\lambda(( a_n )_{n \in {\bf N}})}

and the homomorphism law

\displaystyle \lambda(( a_n b_n )_{n \in {\bf N}}) = \lambda(( a_n )_{n \in {\bf N}}) \lambda(( b_n )_{n \in {\bf N}})

for all bounded sequences {a_n, b_n}, while mapping the constant sequence {(1)_{n \in {\bf N}}} to {1}.

  • (i) Show that if {\alpha} is a ultrafilter, show that there exists a unique *-homomorphism {\alpha\!-\!\lim: \ell^\infty({\bf N}) \rightarrow {\bf C}} with the property that for every {E \subset {\bf N}}, one has {\alpha\!-\!\lim 1_E(n) = 1} if and only if {E} is {\alpha}-large.
  • (ii) Conversely, show that all *-homomorphisms {\lambda} from {\ell^\infty({\bf N})} to {{\bf C}} arise in this fashion, and that a *-homomorphism arises from a nonprincipal ultrafilter if and only if it extends the limit functional (thus {\lambda( (a_n)_{n \in {\bf N}} ) = \lim_{n \rightarrow \infty} a_n} whenever {a_n} is convergent).

From the above exercise we see that {\beta {\bf N}} can be viewed as the Gelfand spectrum of {\ell^\infty({\bf N})}.

Exercise 6 (Ultrafilters and Arrow’s theorem) Let {S} be a finite set consisting of at least three elements (representing “candidates”). Let {O(S)} denote the space of all total orderings {<} on {S}. Define a voting system to be a function {V: O(S)^{\bf N} \rightarrow O(S)} from a sequence {(<_n)_{n \in {\bf N}}} of orderings on {S} (representing the preferences of an infinite number of “voters”) to an ordering {V((<_n)_{n \in {\bf N}})} on {S}. If {\alpha} is a nonprincipal ultrafilter, show that there is a unique voting system {V_\alpha: O(S)^{\bf N} \rightarrow O(S)} with the property that for any distinct {A, B \in S}, one has {A V((<_n)_{n \in {\bf N}}) B} if and only if {A <_n B} for all {n} sufficiently close to {\alpha}. Show furthermore that this voting system obeys the following axioms for all distinct candidates {A,B} and all orderings {<_n \in O(S)}:

  • (Consensus) If {A <_n B} for all {n}, then {A V((<_n)_{n \in {\bf N}}) B}.
  • (Non-dictatorship) There is no {n_0} with the property that {A V((<_n)_{n \in {\bf N}}) B} holds if and only if {A <_{n_0} B} holds for all choices of {A, B, <_n}.
  • (Independence of irrelevant alternatives) The truth value of {A V((<_n)_{n \in {\bf N}}) B} depends only on the truth values of {A <_n B} for all {n}. Thus, if {(<'_n)_{n\in {\bf N}}} is another sequence of orderings such that {A <_n B} if and only if {A <'_n B}, then {A V((<_n)_{n \in {\bf N}}) B} holds if and only if {A V((<'_n)_{n \in {\bf N}}) B} holds.

Conversely, show that any voting system obeying the above axioms arises from an nonprincipal ultrafilter in this fashion. Thus we see that Arrow’s theorem does not hold for infinite sets due to the existence of nonprincipal ultrafilters in this setting; or to put it another way, Arrow’s theorem is equivalent to the assertion that finite sets have no nonprincipal ultrafilters. (This connection between ultrafilters and Arrow’s theorem was first observed by Kirman and Sondermann. See this previous blog post for more discussion of the voting interpretation of an ultrafilter.)

As the above examples indicate, there are many different ways to view ultrafilters. My personal preference (at least from the perspective of forming ultraproducts and doing nonstandard analysis) is to view a nonprincipal ultrafilter as a consistent way to take limits of sequences that do not necessarily converge in the classical sense, as per Exercise 5; but other readers may prefer to use one of the other interpretations of an ultrafilter instead.

— 2. Ultrapowers and ultralimits —

We now turn to the formal definition of an ultrapower and ultralimit. In order to define these two terms, we must first fix two objects:

  • A non-principal ultrafilter {\alpha \in \beta {\bf N} \backslash {\bf N}}; and
  • A standard universe {{\mathfrak U}}, which is some some set of objects, the elements of which we refer to as standard objects. We refer to subsets of the standard universe (i.e. sets of standard objects) as standard spaces (or standard sets).

Informally, the standard universe is going to contain all the objects that we are initially interested in studying. For instance, if we are doing arithmetic, the standard universe might be the natural numbers {{\bf N}}. If we are doing analysis, the standard universe might include the real numbers {{\bf R}}, as well as the set of subsets of {{\bf R}}, the set of functions from {{\bf R}} to {{\bf R}}, and so forth. If we are studying approximate groups in an ambient group {G}, the standard universe might include the elements of {G}, subsets of {G}, and similar such objects. We will place some more constraints on the standard universe later, but for now, the only requirement we have is that this universe forms a set. (In particular, the standard universe cannot be so huge to be a proper class, such as the class of all sets, or the class of all groups, etc., although in most applications outside of set theory, this is hardly a restriction.)

In practice, the standard universe will contain many familiar mathematical spaces, such as the natural numbers, the real numbers, and so forth. To emphasise this, we will sometimes refer to the natural numbers {{\bf N}} as the standard natural numbers, the real numbers {{\bf R}} as the standard real numbers {{\bf R}}, and so forth. This is in order to distinguish such spaces from the nonstandard natural numbers {{}^* {\bf N}}, the nonstandard real numbers {{}^* {\bf R}}, etc., which we now define.

Remark 5 For the applications in this course, the precise choice of nonprincipal ultrafilter {\alpha} will be completely irrelevant; one such ultrafilter will be just as good for our purposes as another. Basically, we only use the ultrafilter {\alpha} in order to fix a consistent way to make choices amongst any sequence of options indexed by the natural numbers; but the precise way in which these choices are made will not be important, so long as it is consistent (in the sense that the ultrafilter axioms are obeyed). There are other applications of ultrafilters, however, in which some nonprincipal ultrafilters are decidedly superior to others; see this previous post for an example of this in dynamical systems.

Definition 3 (Ultralimits and ultraproducts) Two sequences {(x_n)_{n \in {\bf N}}}, {(y_n)_{n \in {\bf N}}} of standard objects {x_n, y_n \in {\mathfrak U}} are said to be equivalent if one has {x_n = y_n} for all {n} sufficiently close to {\alpha}. This is easily seen to be an equivalence relation. We define the ultralimit {\lim_{n \rightarrow \alpha} x_n} to be the equivalence class of a sequence {(x_n)_{n \in {\bf N}}}; thus {\lim_{n \rightarrow \alpha} x_n = \lim_{n \rightarrow \alpha} y_n} if and only if {x_n=y_n} for all {n} sufficiently close to {\alpha}. Such ultralimits will be called nonstandard objects.

Given a sequence {(X_n)_{n \in {\bf N}}} of standard spaces {X_n \subset {\mathfrak U}}, we define the ultraproduct {\prod_{n \rightarrow \alpha} X_n} to be the space of all ultralimits {\lim_{n \rightarrow \alpha} x_n}, where {x_n \in X_n} for each {n}. Such spaces will be called nonstandard spaces (also known as nonstandard sets or internal sets).

If {X} is a standard space, we define the ultrapower {{}^* X} of {X} to be the ultraproduct {{}^* X := \prod_{n \rightarrow \alpha} X} of the constant sequence {X}. We embed {X} inside {{}^* X} by identifying each element {x} of {X} with the ultralimit {\lim_{n \rightarrow \alpha} x}. If {X} is the standard elements of some type, we refer to elements of {{}^* X} (i.e. ultralimits of sequences in {X}) as nonstandard elements of the same type. Thus, for instance, elements of {{}^* {\bf N}} are nonstandard natural numbers, elements of {{}^* {\bf R}} are nonstandard real numbers (also known as hyperreals), and so forth. The ultrapower {{}^* {\mathfrak U}} of the standard universe will be called the nonstandard universe.

Note that one can define an ultralimit {\lim_{n \rightarrow \alpha} x_n} for sequences {x_n} of standard objects that are only defined for an {\alpha}-large set of {n}, and similarly one can define ultraproducts {\prod_{n \rightarrow \alpha} X_n} on spaces {X_n} that are only defined for an {\alpha}-large set of {n}. From the nonprincipal nature of {\alpha} we observe that we can modify {x_n} or {X_n} for finitely many {n} without affecting the ultralimit {\lim_{n \rightarrow \alpha} x_n} or ultraproduct {\prod_{n \rightarrow \alpha} X_n}.

Remark 6 The relation between a standard space {X} and its ultrapower {{}^* X} is analogous in some ways to the relationship between the rationals {{\bf Q}} and its metric completion, namely the real line {{\bf R}}. Indeed, using the usual metric completion construction, one can interpret a real number as an equivalence class of Cauchy sequences of rationals (or as a formal limit {\lim_{n \rightarrow \infty} q_n} of one of the Cauchy sequences in this class), and then one identifies each rational {q} with its formal limit {\lim_{n \rightarrow \infty} q} in order to keep the rationals embedded inside the reals. Note however that whilst in the metric completion, one is only allowed to take (formal) limits of Cauchy sequences, in the ultrapower construction one may take limits of arbitrary sequences. This makes the ultrapower construction more “powerful” than the metric completion construction in that no a priori convergence (or even boundedness) hypotheses are needed in order to take limits. See this previous blog post for more discussion of ultrapowers as a completion.

Remark 7 With our conventions, we have the slightly unfortunate consequence that every standard object is also a nonstandard object; for instance, every standard natural number is also a nonstandard natural number, every standard real is also a nonstandard real, and so forth. We will occasionally use the terminology strictly nonstandard to denote a nonstandard object that is not standard. For instance, an element of {{}^* {\bf N} \backslash {\bf N}} would be a strictly nonstandard natural number.

Exercise 7 If {X} is a standard space, show that {X = {}^* X} if and only if {X} is finite. In particular, if {x_n \in X} is a sequence with finite (standard) range {X}, then {\lim_{n \rightarrow \alpha} x_n} also lives in the same range {X}.

The above exercise shows that for finite spaces, there is no distinction between a standard space {X} and its nonstandard counterpart {{}^* X}. However, for infinite spaces, the nonstandard version of the space is usually much larger:

Exercise 8 Show that {{}^* {\bf N}} is uncountable. (Hint: adapt the Cantor diagonal argument.) The precise cardinality of an ultrapower is actually quite difficult to determine in general, as it can depend on the choice of ultrafilter and even on the choice of additional set theory axioms such as the continuum hypothesis.

Exercise 9 (Ultrapowers preserve Boolean operations) Let {X, Y} be standard spaces. Show that {(X \cup Y)^* = X^* \cup Y^*}, {(X \cap Y)^* = X^* \cap Y^*}, and {(X \backslash Y)^* = X^* \backslash Y^*}. Also show that {X \subset Y} if and only if {X^* \subset Y^*}.

Strictly speaking, ultrapowers do not preserve Cartesian products: from the definitions, {(X \times Y)^*} and {X^* \times Y^*} are slightly different spaces. However, there is an obvious bijection between the two sets, and we shall abuse notation and implicitly make the identification {(X \times Y)^* = X^* \times Y^*} throughout the rest of this post. More generally, given sequences {X_n, Y_n} of standard spaces, we make the identification {\prod_{n \rightarrow \alpha} (X_n \times Y_n) = (\prod_{n \rightarrow \alpha} X_n) \times (\prod_{n \rightarrow \alpha} Y_n)}.

Remark 8 Just as standard spaces {X} are subsets of the standard universe {{\mathfrak U}}, nonstandard spaces {\prod_{n \rightarrow \alpha} X_n} are subsets of the nonstandard universe {{}^* {\mathfrak U}}. However, the converse is not true in general; not every subset of the nonstandard universe is necessarily a nonstandard space. For instance, we will show later that {{\bf N}} is not a nonstandard subset of {{}^* {\bf N}} (and as such, is sometimes referred to as an external subset of {{}^* {\bf N}}). Very roughly speaking, internal spaces in the nonstandard universe play a role similar to that of elementary sets (i.e. finite boolean combinations of intervals) in the real line; they are closed under various operations, but fall well short of exhausting all possible subsets of the ambient space. (Actually, an even better analogy would be the clopen subsets of a Cantor space.)

Now we record an important property of nonstandard spaces, analogous to the finite intersection property formulation of (countable) compactness.

Lemma 4 (Countable saturation) Let {F_1, F_2, \ldots} be a sequence of nonstandard spaces such that any finite collection of these spaces has non-empty intersection (thus {\bigcap_{m=1}^M F_m \neq \emptyset} for all {M \geq 1}). Then the entire sequence has non-empty intersection (thus {\bigcap_{m=1}^\infty F_m \neq \emptyset}).

Proof: Write {F_m = \prod_{n \rightarrow \alpha} F_{n,m}}, then for each {m}, {\bigcap_{m=1}^M F_m} is the ultraproduct of {\bigcap_{m=1}^M F_{m,n}} (cf. Exercise 9). In particular, {\bigcap_{m=1}^M F_{m,n}} is non-empty for all {n} in an {\alpha}-large subset {E_M} of the natural numbers. By shrinking the {E_M} as necessary we may assume that they are monotone, thus {E_1 \supset E_2 \supset \ldots}, and such that {E_M} does not contain any natural number less than {M}; in particular, {\bigcap_{M=1}^\infty E_M = \emptyset}. For any {n \in E_1}, let {M_n} denote the largest natural number {M} such that {n \in E_M}, and then let {x_n} denote an element of {\bigcap_{m=1}^{M_n} F_{m,n}}. Then by construction, for each {m \geq 1}, we have {x_n \in F_{m,n}} for all {n \in E_m}, and thus the nonstandard object {x := \lim_{n \rightarrow \alpha} x_n} lies in {F_m} for all {m}, and thus {\bigcap_{m=1}^\infty F_m} is non-empty as required. \Box

Exercise 10 (Countable compactness) Show that any countable cover of a nonstandard space by other nonstandard spaces has a finite subcover.

Exercise 11 (Bolzano-Weierstrass type theorem) Let {X_1,\ldots,X_k} be a finite collection of nonstandard spaces, and let {P_i: X_1 \times \ldots \times X_k \rightarrow \{ \hbox{true},\hbox{false}\}} be an at most countable collection of nonstandard {k}-ary predicates on these spaces. Let {x_{1,m}, \ldots, x_{k,m}} for {m \in {\bf N}} be sequences of nonstandard objects in {X_1,\ldots,X_k} respectively (indexed by the standard natural numbers {{\bf N}}). Show that there are subsequences {x_{1,m_j},\ldots,x_{k,m_j}} which converge elementarily to some elements {x_1,\ldots,x_k} of {X_1,\ldots,X_k} in the sense that for each predicate {P_i}, one has {P_i(x_{1,{m_j}},\ldots,x_{k,{m_j}}) = P_i(x_1,\ldots,x_k)} for all sufficiently large {j}. (See this previous post for more discussion on these sorts of completeness properties on nonstandard spaces.)

Remark 9 By replacing the ultraproduct construction with more sophisticated set-theoretic constructions, one can strengthen the countable saturation property by replacing “countable” by “at most cardinality {\kappa}” for any given cardinal {\kappa}; however, as one increases {\kappa}, the size of the ultraproduct-type object must also necessarily increase (although one can make the size of the model only slightly larger than {\kappa}, if one is willing to use inaccessible cardinals). Such (huge) saturated models are of importance in model theory, but for our applications we will only need to work with the countably saturated models provided by the ultraproduct construction.

We have taken ultralimits and ultraproducts of standard objects and standard spaces; now we perform a similar construction to standard functions and relations.

Definition 5 (Ultralimits of functions and relations) A standard function is a function {f: X \rightarrow Y} between two standard spaces {X, Y}. Given a sequence {f_n: X_n \rightarrow Y_n} of standard functions, we define the ultralimit {\lim_{n \rightarrow \alpha} f_n: \prod_{n \rightarrow \alpha} X_n \rightarrow \prod_{n \rightarrow \alpha} Y_n} to be the function defined by the formula

\displaystyle (\lim_{n \rightarrow \alpha} f_n) (\lim_{n \rightarrow \alpha} x_n) := \lim_{n \rightarrow\alpha} f_n(x_n)

whenever {x_n \in X_n}. One can easily verify that this does indeed define a function, which we refer to as a nonstandard function (also called an internal function in the literature). The ultralimit {{}^* f := \lim_{n \rightarrow \alpha} f} of a single standard function is thus a nonstandard function from {{}^* X} to {{}^* Y} that extends {f}; by abuse of notation we shall also refer to {{}^* f} as {f} (analogously to how we identify {\lim_{n \rightarrow \alpha} x} with {x} rather than giving it a different name such as {{}^* x}).

Similarly, for a (standard) natural number {k \in {\bf N}}, define a standard {k}-ary relation (or standard {k}-ary predicate) to be a standard function {R: X_1 \times \ldots \times X_k \rightarrow \{ \hbox{true}, \hbox{false}\}} from the product of {k} standard spaces to the Boolean space {\{ \hbox{true}, \hbox{false}\}} (which we will treat as part of the standard universe {{\mathfrak U}}). By the preceding construction (and Exercise 7), the ultralimit {\lim_{n \rightarrow \alpha} R_n} of a sequence of standard {k}-ary relations {R_n: X_{1,n} \times \ldots \times X_{k,n} \rightarrow \{ \hbox{true}, \hbox{false}\}} (with {k} independent of {n}) is another {k}-ary relation

\displaystyle \lim_{n \rightarrow \alpha} R_n: \lim_{n \rightarrow \alpha} X_{1,n} \times \lim_{n \rightarrow \alpha} X_{k,n} \rightarrow \{ \hbox{true}, \hbox{false}\},

which we will call a nonstandard {k}-ary relation (also known as an internal {k}-ary relation). Thus {\lim_{n \rightarrow \alpha} R_n( \lim_{n \rightarrow \alpha} x_{1,n},\ldots,\lim_{n \rightarrow \alpha} x_{k,n})} is true if and only if {R_n(x_{1,n},\ldots,x_{k,n})} is true for all {n} sufficiently close to {\alpha}. Again, we identify each relation {R} with its nonstandard extension {{}^* R := \lim_{n\rightarrow \alpha} R}.

In a very similar spirit, given a sequence {O_n: X_{1,n} \times \ldots \times X_{k,n} \rightarrow Y_n} of standard {k}-ary operators, one can define the ultralimit

\displaystyle \lim_{n \rightarrow \alpha} O_n: \lim_{n \rightarrow \alpha} X_{1,n} \times \lim_{n \rightarrow \alpha} X_{k,n} \rightarrow \lim_{n \rightarrow \alpha} Y_n

which we will call a nonstandard {k}-ary operator (also known as an internal {k}-ary operator). Again, we identify each standard operator {O} with its nonstandard extension {{}^* O := \lim_{n \rightarrow \alpha} O}.

Example 1 Let {a = \lim_{n \rightarrow \alpha} a_n} and {b = \lim_{n \rightarrow \alpha} b_n} be two nonstandard natural numbers (thus {a_n, b_n} are sequences of standard natural numbers). Then, by definition,

  • {a+b} is the nonstandard natural number {a+b := \lim_{n \rightarrow \alpha} a_n + b_n}.
  • {ab} is the nonstandard natural number {ab := \lim_{n \rightarrow \alpha} a_n b_n}.
  • One has {a < b} if {a_n < b_n} for all {n} sufficiently close to {\alpha}.
  • {a} is even if {a_n} is even for all {n} sufficiently close to {\alpha}.
  • {a} is prime if {a_n} is prime for all {n} sufficiently close to {\alpha}.

A basic fact about the ultraproduct construction is that any elementary (or more precisely, first-order) statement that is true for a standard space (or a sequence of such standard spaces) is also true for the associated nonstandard space (either an ultrapower or an ultraproduct). We will formalise this assertion shortly, but let us first illustrate it with some examples.

Exercise 12

  • (i) Show that addition on the nonstandard natural numbers is both commutative and associative.
  • (ii) Show that a nonstandard natural number {a} is even if and only if it is of the form {a = 2b} for some nonstandard natural number {b}.
  • (iii) Show that a nonstandard natural number {a} is prime if and only if it is greater than {1}, but cannot be factored as {a=bc} for some nonstandard natural numbers {b,c > 1}.
  • (iv) Show that the standard Goldbach conjecture (every even standard natural number larger than {2} is the sum of two standard primes) is logically equivalent to the nonstandard Goldbach conjecture (every even nonstandard natural number larger than {2} is the sum of two nonstandard primes).
  • (v) Show that the standard twin prime conjecture (for any standard natural number {a}, there exists a standard prime {p>a} such that {p+2} is also prime) is logically equivalent to the nonstandard twin prime conjecture (for any nonstandard natural number {a}, there exists a nonstandard prime {p>a} such that {p+2} is also a nonstandard prime).

Now we generalise the above examples.

Exercise 13 Let {k \geq 0}, and let {P_n, Q_n: X_{1,n} \times \ldots \times X_{k,n} \rightarrow \{ \hbox{true}, \hbox{false}\}} be two sequences of {k}-ary predicates. For each {1 \leq i \leq k}, let {X_i := \prod_{n\rightarrow \alpha} X_{i,n}}, and write {P := \lim_{n \rightarrow \alpha} P_n} and {Q := \lim_{n \rightarrow \alpha} Q_n}.

  • (i) (Continuity of Boolean operations) Show that {\lim_{n \rightarrow\alpha} (P_n \wedge Q_n) = P \wedge Q}, {\lim_{n \rightarrow\alpha} (P_n \vee Q_n) = P \vee Q}, and {\lim_{n \rightarrow \alpha} (\neg P_n) = \neg P}.
  • (ii) (Continuity of existential quantifier) If {1 \leq i \leq k}, {\exists_i P_n} denotes the {k-1}-ary predicate {\exists x_i \in X_{i,n}: P_n(x_{1,n},\ldots,x_{k,n})} in the remaining {k-1} variables {x_{j,n} \in X_{j,n}} for {j \neq i}, and {\exists_i P} denotes the {k-1}-ary predicate {\exists x_i \in X_i: P(x_1,\ldots,x_k)} in the remaining {k-1} variables {x_j \in X_j} for {j \neq i}, show that {\lim_{n \rightarrow \alpha} \exists_i P_n = \exists_i P}.
  • (iii) (Continuity of universal quantifier) If {1 \leq i \leq k}, {\forall_i P_n} denotes the {k-1}-ary predicate {\forall x_i \in X_{i,n}: P_n(x_{1,n},\ldots,x_{k,n})} in the remaining {k-1} variables {x_{j,n} \in X_{j,n}} for {j \neq i}, and {\exists_i P} denotes the {k-1}-ary predicate {\forall x_i \in X_i: P(x_1,\ldots,x_k)} in the remaining {k-1} variables {x_j \in X_j} for {j \neq i}, show that {\lim_{n \rightarrow \alpha} \forall_i P_n = \forall_i P}.

By iterating the above exercise, we can obtain Los’s theorem, which we first state informally as follows.

Theorem 6 (Los’s theorem, informal version) Let {k, m} be natural numbers. For each natural number {n}, suppose one has a collection {a_{1,n},\ldots,a_{m,n}} of standard objects, spaces, operators, and relations (of various arities), and let {a_1,\ldots,a_m} be the corresponding nonstandard objects, spaces, operators, and relations formed via the ultralimit or ultraproduct construction. Let {P} be a formal {k}-ary predicate expressible in first-order logic using {m} objects, spaces, operators, and relations. Then {P}, when quantified over {a_1,\ldots,a_m}, is the ultralimit of {P} quantified over {a_{1,n},\ldots,a_{m,n}}. (In particular, {P} quantified over {a_1,\ldots,a_m} is a nonstandard predicate.)

Specialising to the case {k=0}, (so {P} is a first-order sentence involving {m} objects, spaces, operators, and relations), we see that {P} is true when quantified over {a_1,\ldots,a_m} if and only if {P} is true when quantified over {a_{1,n},\ldots,a_{m,n}} for all {n} sufficiently close to {\alpha}.

Corollary 7 (Special case of Los’s theorem, informal version) Any first-order sentence that holds for a finite collection of standard objects, spaces, operators, and relations, also holds for their corresponding nonstandard counterparts (using the ultralimit or ultrapower construction).

Before we state the theorem more formally, let is illustrate it with some more examples.

  • {{\bf R}} is an ordered field when given the usual constants {0, 1}, field operations {+, -, \cdot, ()^{-1}}, and order relation {<}. (Technically, {()^{-1}} is not an operation on {{\bf R}} because it is undefined at {0}, but this can easily be fixed by artificial means, e.g. by arbitrarily defining {()^{-1}} at {0}.). The assertion that {{\bf R}} is an ordered field can be expressed as a (rather lengthy) sentence in first-order logic using the indicated spaces, objects, operations, and relations. As a consequence, the ultrapower {{}^* {\bf R}} (with the same constants {0, 1} and the nonstandard extensions of the field operations and order relation) is also an ordered field.
  • Let {G_n= (G_n,\cdot_n)} be a sequence of groups; then the ultraproduct {G := \prod_{n \rightarrow \alpha} G_n} (with the ultralimit group operation {\cdot := \lim_{n \rightarrow \alpha} \cdot_n}, and similarly for the group identity and inverse operations) is also a group, because the group axioms can be phrased in first-order logic using the indicated structures. If, for each {n}, {g_n} is an element of {G_n}, then the ultralimit {\lim_{n \rightarrow \alpha} g_n} is a central element of {G} if and only if {g_n} is a central element of {G_n} for all {n} sufficiently close to {\alpha}. Similarly, if for each {n}, {H_n} is a subset of {G_n}, then the ultraproduct {\prod_{n \rightarrow \alpha} H_n} is a normal subgroup of {G} if and only if {H_n} is a normal subgroup of {G_n} for all {n} sufficiently close to {\alpha}.
  • The standard natural numbers {{\bf N}} obey the axiom of induction: if {P(n)} is a predicate definable in the language of Peano arithmetic, and {P(0)} is true, and {P(n)} implies {P(n+1)} for all {n \in {\bf N}}, then {P(n)} is true for all {n \in {\bf N}}. As a consequence, the same axiom of induction also holds for the nonstandard natural numbers {{}^*{\bf N}}. Note however it is important for the nonstandard axiom of induction that the predicate be definable in the language of Peano arithmetic. For instance, the following argument is fallacious: “{0 \in {\bf N}}, and for any nonstandard natural number {n}, {n \in {\bf N}} implies {n+1 \in {\bf N}}. Hence, by induction, {n \in {\bf N}} for all nonstandard natural numbers {n}“. The reason is that the predicate “{n \in {\bf N}}” is not formalisable in the language of Peano arithmetic.
  • Exercise 9 can be interpreted as a special case of Corollary 7.

Exercise 14

  • (i) Show that {{\bf N}} (viewed as a subset of {{}^* {\bf N}}) is not a nonstandard space. (Hint: if it were, the fallacious induction mentioned earlier could now be made valid.)
  • (ii) Establish the overspill principle: if a nonstandard predicate {P(n)} on the nonstandard natural numbers is true for all standard natural numbers, then it is true for at least one strictly nonstandard natural number as well.
  • (iii) Show that if a nonstandard subset of {{}^* {\bf N}} consists only of standard natural numbers, then it is finite.
  • (iv) Show that the nonstandard natural numbers {{}^* {\bf N}} are not well-ordered. Why does this not contradict Los’s theorem?

Exercise 15 For each {n}, let {G_n} be a group, and let {S_n} be a subset of {G_n}. Write {G := \prod_{n \rightarrow \alpha} G_n} and {S := \prod_{n \rightarrow\alpha} S_n}.

  • (i) Give an example in which each {S_n} generates {G_n} as a group, but {S} does not generate {G} as a group.
  • (ii) Show that {S} generates {G} as a group if and only if there exists a (standard) natural number {M} such that {(S_n \cup \{1\} \cup S^{-1}_n)^M = G_n} for all {n} sufficiently close to {\alpha}. (Hint: apply countable saturation (Exercise 10) to the sets {(S \cup \{1\} \cup S^{-1})^M}.)

Now we make Los’s theorem more precise, by defining a formal language for first-order logic. (This section is optional and may be safely omitted by the reader.)

Suppose we are given a collection {{\mathcal L}} of formal objects, spaces, operators, and relations, with each object (formally) belonging to one of the spaces, and with each of the operators and relations formally defined on some collection of these spaces (and in the case of operators, taking values in one of the spaces) as well. We will refer to elements of {{\mathcal L}} as primitive terms. Initially, we do not actually identify these formal terms with concrete counterparts, whether they be standard or nonstandard. A well-formed formula involving {{\mathcal L}} and one or more formal free variables {x_1,\ldots,x_n}, each of which belonging to one of the formal spaces, is formed by a finite number of applications of the following rules:

  • Each free variable {x_1,\ldots,x_n} is a well-formed formula (belonging to the associated formal space).
  • Each object in {{\mathcal C}} is a well-formed formula (belonging to the associated formal space).
  • If {a_1,\ldots,a_k} are well-formed formulae, and {O} is a {k}-ary operator, then {O(a_1,\ldots,a_k)} will be a well-formed formula if the {a_1,\ldots,a_k} belong to the formal spaces indicated by the domain of {O}. Of course, {O(a_1,\ldots,a_k)} then belongs to the formal space indicated by the range of {O}.

A formal predicate {P = P(x_1,\ldots,x_k)} involving {{\mathcal L}} and one or more free variables {x_1,\ldots,x_k} is then formed by a finite number of applications of the following rules:

  • If {X}, {Y} are well-formed formulae belonging to the same formal space, then {X=Y} is a predicate.
  • If {X_1,\ldots,X_k} are well-formed formulae, and {R} is a {k}-ary relation in {{\mathcal L}}, then {R(X_1,\ldots,X_k)} is a predicate if the {X_1,\ldots,X_k} belong to the formal spaces indicated by the domain of {R}.
  • If {P} and {Q} are predicates, then so are {(P \vee Q)}, {(P \wedge Q)}, {(\neg P)}, {(P \implies Q)}, and {(P \iff Q)}.
  • If {P(x_1,\ldots,x_k,x)} is a predicate in {x_1,\ldots,x_k} and an additional free variable {x} in some formal space {X}, then {(\exists x \in X: P(x_1,\ldots,x_k,x))} and {(\forall x \in X: P(x_1,\ldots,x_k,x))} are predicates in {x_1,\ldots,x_k}. (Similarly for any permutation in the ordering of {x_1,\ldots,x_k,x}.)

Given a formal predicate involving {{\mathcal L}} and one or more free variables {x_1,\ldots,x_n}, we may quantify (or interpret) the predicate by associating each formal object in {{\mathcal L}} to an actual object, which may be a standard object, a nonstandard object, or something else entirely, and similarly associating an actual space, relation, or operator to each formal space, relation, or operator, making sure that all the relevant domains and ranges are respected. When one does so, the formal predicate {P} becomes a concrete predicate {P: X_1 \times \ldots \times X_k \rightarrow \{ \hbox{true}, \hbox{false}\}} on the appropriate quantified spaces by interpreting all the symbols in {P} in the obvious fashion. For instance, if the primitive terms consist of a formal space {X} and a formal binary operation {\cdot: X \times X \rightarrow X}, then {P(x) := ``\forall y \in X: xy = yx''} is a formal unary predicate, and if one quantifies this predicate over a concrete group {G=(G,\cdot)} (which may be standard, nonstandard, or neither), then one obtains a concrete unary predicate {P: G \rightarrow \{\hbox{true}, \hbox{false}\}}, with {P(g)} true precisely when {g} is a central element of {G}.

Exercise 16 With the above definitions, prove Theorem 6.

Exercise 17 (Compactness theorem) Let {{\mathcal L}} be an at most countable collection of formal objects, spaces, operators and relations. Let {S_1, S_2, S_3, \ldots} be a sequence of sentences involving the symbols in {{\mathcal L}}. Suppose that any finite collection {S_1,\ldots,S_n} of these sentences is satisfiable in the standard universe, thus there exists an assignment of standard objects, spaces, operators, or relations to each element of {{\mathcal L}} for which {S_1,\ldots,S_n} are all true when quantified over these assignments. Show that the entire collection {S_1,S_2,\ldots} are then satisfiable in the nonstandard universe, thus there exists an assignment of nonstandard objects. (This is the countable case of the compactness theorem in logic. One can also use ultraproducts over larger sets than {{\bf N}} to prove the general case of the compactness theorem, but we will not do so here.)

— 3. Nonstandard finite sets and nonstandard finite sums —

It will be convenient to extend the standard machinery of finite sets and finite sums to the nonstandard setting. Define a nonstandard finite set to be an ultraproduct {A = \prod_{n \rightarrow \alpha} A_n} of finite sets, and a nonstandard finite sequence of reals {(x_m)_{m \in A}} to be a nonstandard function {m \mapsto x_m} from a nonstandard finite set {A} to the nonstandard reals, or equivalently an ultralimit of standard finite sequences {(x_{m,n})_{m \in A_n}} of reals. We can define the (nonstandard) cardinality {|A|} of a nonstandard finite set in the usual manner:

\displaystyle |\prod_{n \rightarrow \alpha} A_n| := \lim_{n \rightarrow \alpha} |A_n|.

Thus, for instance, if {N} is a nonstandard natural number, then the nonstandard finite set {\{ n \in {}^* {\bf N}: 1 \leq n \leq N\}} has nonstandard cardinality {N}.

Similarly, if {(x_m)_{m \in A} = \lim_{n \rightarrow \alpha} (x_{m,n})_{m \in A_n}} is a nonstandard finite sequence of reals, we define the nonstandard sum {\sum_{m \in A} x_m} as

\displaystyle \sum_{m \in A} x_m := \lim_{n \rightarrow \alpha} \sum_{m \in A_n} x_{m,n}.

Thus for instance {\sum_{m \in A} 1 = |A|}. By using Los’s theorem, all the basic laws of algebra for manipulating standard finite sums carry over to nonstandard finite sums. For instance, we may interchange summations

\displaystyle \sum_{m_1 \in A_1} \sum_{m_2 \in A_2} x_{m_1,m_2} = \sum_{m_2 \in A_2} \sum_{m_1 \in A_1} x_{m_1,m_2} = \sum_{(m_1,m_2) \in A_1 \times A_2} x_{m_1,m_2}

for any nonstandard finite sequence {(x_{m_1,m_2})_{(m_1,m_2) \in A_1 \times A_2}} of reals indexed by a product set, simply because the same assertion is obviously true for standard finite sequences.

— 4. Asymptotic notation —

The ultrapower and ultralimit constructions are extremely general, being basically applicable to any collection of standard objects, spaces, objects, and relations. However, when one applies these constructions to standard number systems, such as the natural numbers {{\bf N}}, the integers {{\bf Z}}, the real numbers {{\bf R}}, or the complex numbers {{\bf C}} to obtain nonstandard number systems such as {{}^* {\bf N}}, {{}^* {\bf Z}}, {{}^* {\bf R}}, {{}^* {\bf C}}, then one can gain an additional tool of use in analysis, namely a clean asymptotic notation which is closely related to standard asymptotic notation, but has a slightly different arrangement of quantifiers that make the nonstandard asymptotic notation better suited to algebraic constructions (such as the quotient space construction) than standard asymptotic notation.

Definition 8 (Asymptotic notation) Let {R} be one of the standard number systems ({{\bf N}}, {{\bf Z}}, {{\bf Q}}, {{\bf R}}, {{\bf C}}). A nonstandard number {x} in {{}^* R} is said to be bounded if one has {|x| \leq C} for some standard real number {C} (or equivalently, {|x| \leq n} some standard natural number {n}), and unbounded otherwise. If {y} is a non-negative nonstandard real, we write {x = O(y)} if {|x| \leq Cy} for some standard real number {C}, thus a nonstandard number is bounded if and only if it is {O(1)}. We say that {x} is infinitesimal if {|x| \leq \epsilon} for every standard real number {\epsilon>0} (or equivalently, if {|x| \leq \frac{1}{n}} for all standard positive natural numbers {n}), and write {x=o(y)} if {|x| \leq \epsilon y} for all standard real numbers {\epsilon>0}, thus {x} is infinitesimal if and only if it is {o(1)}.

Example 2 All standard numbers are bounded, and all non-zero standard numbers are non-infinitesimal. The nonstandard natural number {N := \lim_{n \rightarrow \alpha} n} is unbounded, and the nonstandard real number {\frac{1}{N} = \lim_{n\rightarrow \alpha} \frac{1}{n}} is non-zero but infinitesimal.

Remark 10 One can also develop analogous nonstandard asymptotic notation on other spaces, such as normed vector spaces or locally compact groups; see for instance this previous blog post for an example of the former, and this paper of Hirschfeld on a nonstandard proof of Hilbert’s fifth problem for an example of the latter. We will however not need to deploy nonstandard asymptotic notation in such generality here.

Note that we can apply asymptotic notation to individual nonstandard numbers, in contrast to standard asymptotic notation in which one needs to have the numbers involved to depend on some additional parameter if one wishes to prevent the notation from degenerating into triviality. In particular, we can form well-defined sets such as the bounded nonstandard reals

\displaystyle O({\bf R}) := \{ x \in {}^* {\bf R}: x = O(1) \}

and the infinitesimal nonstandard reals

\displaystyle o({\bf R}) := \{ x \in {}^* {\bf R}: x = o(1) \}.

Exercise 18 (Standard part) Show that {o({\bf R})} is an ideal of the commutative ring {O({\bf R})}, and one has the decomposition {O({\bf R}) = {\bf R} \oplus o({\bf R})}, thus every bounded real {x = O({\bf R})} has a unique decomposition {x = \hbox{st}(x) + (x-\hbox{st}(x))} into a standard part {\hbox{st}(x) \in {\bf R}} and an infinitesimal part {x - \hbox{st}(x) \in o({\bf R})}. Show that the map {x \mapsto \hbox{st}(x)} is a ring homomorphism from {O({\bf R})} to {{\bf R}}.

Exercise 19 Let {N} be an unbounded nonstandard natural number. Write {O_{\bf Z}(N) := \{ n \in {}^* {\bf Z}: n = O(N)\}} and {o_{\bf Z}(N) := \{ n \in {}^* {\bf Z}: n = o(N)\}}. Show that {o_{\bf Z}(N)} is a subgroup of the additive group {O_{\bf Z}(N)}, and that the quotient group {O_{\bf Z}(N)/o_{\bf Z}(N)} is isomorphic (as an additive group) to the standard real numbers {{\bf R}}. (One could in fact use this construction as a definition of the real number system, although this would be a rather idiosyncratic choice of construction.)

The following exercise should be compared with Proposition 1. Note the absence of a continuity hypothesis on the function {f}.

Exercise 20 Let {f: X \rightarrow {\bf R}} be a standard function, which we extend to a nonstandard function {f: {}^* X \rightarrow {}^* {\bf R}} in the usual manner. Show that the following statements are equivalent:

  • (i) (Qualitative bound on nonstandard objects) For all {x \in {}^* X}, one has {f(x) = O(1)}.
  • (ii) (Quantitative bound on standard objects) There exists a standard real {M < +\infty} such that {|f(x)| \leq M} for all {x \in X}.

(Hint: use some version of the countable saturation property.)

One of the first motivations of nonstandard analysis was to obtain a rigorous theory of infinitesimals that could be used as an alternate (though logically equivalent) foundation for real analysis. We will not need to use this foundation here, but the following exercises are intended to give some indication of one might start setting up such foundations.

Exercise 21 Let {E} be a standard subset of the reals {{\bf R}}.

  • Show that {E} is open if and only if {E + o({\bf R}) \subset {}^* E}, or equivalently if {\hbox{st}^{-1}(E) \subset {}^* E}. (Here, {A+B := \{a+b: a \in A, b \in B \}} denotes the sumset of {A} and {B}.)
  • Show that {E} is closed if and only if {{}^* E \cap O({\bf R}) \subset E + o({\bf R})}, or equivalently if {\hbox{st}({}^* E \cap O({\bf R})) \subset E}.
  • Show that {E} is bounded if and only if {{}^* E \subset O({\bf R})}.
  • Show that {E} is compact if and only if {{}^* E \subset E + o({\bf R})}.

Exercise 22 Let {(x_n)_{n \in {\bf N}}} be a standard sequence of reals, and let {(x_n)_{n \in {}^* {\bf N}}} be its nonstandard extension. Let {L} be a real number.

  • Show that {x_n} converges to {L} as {n \rightarrow \infty} if and only if {x_N = L+o(1)} for all unbounded natural numbers {N}.
  • Show that {\sum_{n=1}^\infty x_n} is conditionally convergent to {L} if and only if {\sum_{n=1}^N x_N = L + o(1)} for all unbounded natural numbers {N}.

Exercise 23 Let {f: {\bf R} \rightarrow {\bf R}} be a standard function, and let {f: {}^* {\bf R} \rightarrow {}^* {\bf R}} be its nonstandard extension. Show that the following are equivalent:

  • {f} is a continuous function.
  • One has {f(y) = f(x)+o(1)} whenever {x \in {\bf R}}, {y \in {}^* {\bf R}}, and {y = x+o(1)}.
  • One has {f(\hbox{st}(x)) = \hbox{st}(f(x))} for all {x \in O({\bf R})}.

Exercise 24 Let {f: {\bf R} \rightarrow {\bf R}} be a standard function, and let {f: {}^* {\bf R} \rightarrow {}^* {\bf R}} be its nonstandard extension. Show that the following are equivalent:

  • {f} is a uniformly continuous function.
  • One has {f(y) = f(x) + o(1)} whenever {x, y \in {}^* {\bf R}} and {y=x+o(1)}.

Exercise 25 Let {f: {\bf R} \rightarrow {\bf R}} be a standard function, and let {f: {}^* {\bf R} \rightarrow {}^* {\bf R}} be its nonstandard extension. Show that the following are equivalent:

  • {f} is a differentiable function.
  • There exists a standard function {f': {\bf R} \rightarrow {\bf R}} such that {f(x+h) = f(x) + f'(x) h + o(|h|)} for all {x \in {\bf R}} and {h = o(1)}, or equivalently if {f'(x) = \hbox{st} \frac{f(x+h)-f(x)}{h}} for all {x \in {\bf R}} and non-zero {h = o(1)}.

Exercise 26 Let {f: {\bf R} \rightarrow {\bf R}} be a standard continuous function, and let {f: {}^* {\bf R} \rightarrow {}^* {\bf R}} be its nonstandard extension. Show that for any standard reals {a<b} and any unbounded natural number {N}, one has

\displaystyle \int_a^b f(x)\ dx = \hbox{st} \frac{1}{N} \sum_{n=1}^N f(a + \frac{b-a}{N} n)

(note that {\sum_{n=1}^N f(a + \frac{b-a}{N} n)} is a nonstandard finite sum). More generally, show that

\displaystyle \int_a^b f(x)\ dx = \hbox{st} \frac{1}{N} \sum_{n=1}^N f(x_n^*) (x_n - x_{n-1})

whenever {(x_n)_{0 \leq n \leq N}} and {(x_n^*)_{1 \leq n \leq N}} are nonstandard finite sequences with {a \leq x_{n-1} \leq x_n^* \leq x_n \leq b} and {x_n = x_{n-1} + o(1)} for all {1 \leq n \leq N}.

— 5. Ultra approximate groups —

In this section we specialise the above ultraproduct machinery to the concept of a finite approximate group, to link such objects with a type of infinite approximate group which we call an ultra approximate group. These objects will be studied much more intensively in the next two lectures, but for now we focus on the correspondence between ultra approximate groups and their finitary counterparts.

We first recall the notion of an approximate group. For simplicity, we work for now in the global group setting, although later on we will also need to generalise to local groups.

Definition 9 (Approximate group) Let {K \geq 1} be a standard real number. A (global) approximate group is a subset {A} of a global group {G = (G,\cdot)} which is symmetric, contains the identity, and is such that {A \cdot A} can be covered by at most {K} left-translates of {A}.

Definition 10 (Ultra approximate group) An ultra approximate group is an ultraproduct {A = \prod_{n \rightarrow \alpha} A_n}, where each {A_n \subset G_n} is a standard finite {K}-approximate group for some {K} independent of {n}.

Example 3 If {N = \prod_{n \rightarrow \alpha} N_n} is a nonstandard natural number, then the nonstandard arithmetic progression {\{ m \in {}^* {\bf N}: -N \leq m \leq N \}} is an ultra approximate group, because it is an ultraproduct of standard finite {2}-approximate groups {\{ m \in {\bf N}: -N_n \leq m \leq N_n\}}.

Example 4 If {N = \prod_{n \rightarrow \alpha} N_n} is a nonstandard natural number, then the nonstandard cyclic group {{\bf Z}/N{\bf Z} = \prod_{n \rightarrow \alpha} {\bf Z}/N_n{\bf Z}} is an ultra approximate group, because it is an ultraproduct of standard cyclic groups. More generally, any nonstandard finite group (i.e. an ultraproduct of standard finite groups) is an ultra approximate group.

For any fixed {K}, the statement of a set {A} in a group {G} being a {K}-approximate group can be phrased in first-order logic quantified over {G} using the group operations and the predicate {x \in A} of membership in {A}. From this and Los’s theorem, we see that any ultraproduct of {K}-approximate groups is again a {K}-approximate group. In particular, an ultra approximate group is a {K}-approximate group for some (standard) finite {K}.

We will be able to make a correspondence between various assertions about {K}-approximate groups and about ultra approximate groups, so that problems about the former can be translated to problems about the latter. By itself, this correspondence is not particularly deep or substantial; but the point will be that by moving from the finitary category of finite {K}-approximate groups to the infinitary category of ultra approximate groups, we will be able to deploy tools from infinitary mathematics, and in particular the topological group theory results (such as the Gleason-Yamabe theorem) from previous notes, to bear on the problem. We will execute this strategy in the next few notes, but for now, let us just see how the correspondence works. We begin with a simple example, in the bounded torsion case. For a standard natural number {r}, we say that a group {G} is {r}-torsion if every element has order at most {r}, thus for each {g \in G} one has {g^n = 1} for some {1 \leq n \leq r}.

Proposition 11 (Correspondence in the torsion case) Let {r \geq 1}. The following two statements are equivalent:

  • (i) (Finitary statement) For all {K \geq 1}, there exists {C_{K,r} \geq 1} such that, given a finite {K}-approximate group {A} in an {r}-torsion group {G}, one can find a finite (genuine) subgroup {H} of {G} such that {A^4} contains {H}, and {A} can be covered by at most {C_{K,r}} left-translates of {H}.
  • (ii) (Infinitary statement) For any ultra approximate group {A} in a {r}-torsion nonstandard group {G}, one can find a nonstandard finite subgroup {H} of {G} such that {A^4} contains {H}, and {A} can be covered by finitely many left-translates of {H}.

Proof: Let us first assume (i) and establish (ii). Let {A = \prod_{n \rightarrow \alpha} A_n} be an ultra approximate group in an {r}-torsion nonstandard group {G = \prod_{n \rightarrow \alpha} G_n}. Since {G} is {r}-torsion, and the property of being {r}-torsion is a first-order statement in the language of groups, we see from Los’s theorem that {G_n} is a {r}-torsion group for all {n} sufficiently close to {\alpha}. Since the {A_n} are all finite {K}-approximate groups for some {K} independent of {n}, we conclude from (i) that for all {n} sufficiently close to {\alpha}, we can find a finite subgroup {H_n} of {G_n} such that {A_n^4} contains {H_n}, and {A_n} can be covered by at most {C_{K,r}} left-translates of {H_n}. Taking {H := \prod_{n \rightarrow \alpha} H_n} and applying Los’s theorem again, we cnoclude that {H} is a nonstandard finite subgroup of {G}, that {A^4} contains {H}, and {A} can be covered by at most {C_{K,r}} left-translates of {H}, giving (ii) as desired.

Now we assume (ii) and establish (i). Suppose for contradiction that (i) failed. Carefully negating the quantifiers, we conclude that there exists {K \geq } such that for each natural number {n}, one can find a finite {K}-approximate group {A_n} in an {r}-torsion group {G_n} for which there does not exist any finite subgroup {H_n} of {G_n} such that {A_n^4} contains {H_n} and {A_n} can be covered by at most {n} left-translates of {H_n}. We then form the ultraproducts {A := \prod_{n \rightarrow \alpha} A_n} and {G := \prod_{n \rightarrow \alpha} G_n}. By Los’s theorem, {G} is an {r}-torsion nonstandard group, and {A} is an ultra approximate group in {G}. Thus, by (ii), there is a nonstandard finite subgroup {H = \prod_{n \rightarrow \alpha} H_n} of {G} such that {A^4} contains {H} and {A} is covered by {M} left-translates of {H} for some (standard) natural number {M}. By Los’s theorem, we conclude that for all {n} sufficiently close to {\alpha}, {H_n} is a finite subgroup of {G_n}, {A_n^4} contains {H_n}, and {A_n} is covered by {M} left-translates of {H_n}. In particular, as {\alpha} is nonprincipal, this assertion holds for at least one {n > M}. But this contradicts the construction of {A_n}. \Box

Note how the infinitary statement in the above proposition is a qualitative version of the more quantitative finitary statement. In particular, parameters such as {K} and {C_{K,r}} have been efficiently concealed in the infinitary formulation, whereas they must be made explicit in the finitary formulation. As such, the infinitary approach leads to a reduction in the amount of “epsilon management” that one often has to perform in finitary settings.

In the next section we will use the Gleason-Yamabe theorem to establish (ii) and hence conclude (i) as a corollary (this argument is essentially due to Hrushovski). Interestingly, no purely finitary proof of (i) in full generality is currently known (other than by finitising the infinitary proof, which is in principle possible, but would create an extremely long and messy proof as a consequence). We move from the bounded torsion setting to another special case, namely the abelian setting. Here, the finite subgroups need to be replaced by the more general concept of a coset progression.

Definition 12 A (standard symmetric) generalised arithmetic progression {P} of rank {r} in a (standard) additive group {G = (G,+)} is a set of the form

\displaystyle P = P(v_1,\ldots,v_r;N_1,\ldots,N_r) := \{ a_1 v_1 + \ldots + a_r v_r: |a_1| \leq N_1, \ldots, |a_r| \leq N_r \}

where {v_1,\ldots,v_r \in G}, {N_1,\ldots,N_r > 0}, and the {a_1,\ldots,a_r} are constrained to be integers. An ultra generalised arithmetic progression is an ultraproduct {P := \prod_{n \rightarrow \alpha} P_n} of standard generalised arithmetic progressions {P_n} of fixed rank {r}.

A (standard) coset progression {Q} of rank {r} in a (standard) additive group {G = (G,+)} is a set of the form {Q=H+P}, where {H} is a finite subgroup of {G} and {P} is a generalised arithmetic progression of rank {r}. An ultra coset progression is an ultraproduct {Q := \prod_{n \rightarrow \alpha} Q_n} of standard coset progressions {Q_n} of fixed rank {r}; equivalently, it is a set of the form {H+P}, where {H} is a nonstandard finite group in a nonstandard group {G}, and {P} is an ultra generalised arithmetic progression in {G}.

Exercise 27 Show that the following two statements are equivalent:

  • (i) (Finitary abelian Freiman theorem) For all {K \geq 1}, there exists {C_{K}, r_K \geq 1} such that, given a finite {K}-approximate group {A} in an abelian group {G = (G,+)}, one can find a coset progression {Q} in {G} of rank at most {r_K} such that {A^4} contains {Q}, and {A} can be covered by at most {C_{K}} left-translates of {Q}.
  • (ii) (Infinitary abelian Freiman theorem) For any ultra approximate group {A} in a abelian nonstandard group {G = (G,+)}, one can find an ultra coset progression {Q} of {G} such that {A^4} contains {Q}, and {A} can be covered by finitely many left-translates of {Q}.

The statement (i) was established by Green and Ruzsa by finitary means (such as the finite Fourier transform). In later notes we will give an alternate proof of (i) that proceeds via (ii) and the structure theory of locally compact abelian groups.

Finally, we can give the correspondence in the full nonabelian setting.

Definition 13 Given a (standard) finite number of generators {v_1,\ldots,v_r} in a (standard) group {G = (G,\cdot)}, and (standard) real numbers {N_1,\ldots,N_r>0}, define the noncommutative progression {P( v_1,\ldots,v_r; N_1,\ldots,N_r)} to be the set of all words in {v_1^{\pm 1},\ldots,v_r^{\pm 1}} involving at most {N_i} copies of {v_i^{\pm 1}} for each {1 \leq i \leq r}. We refer to {r} as the rank of the noncommutative progression. A nilprogression of rank {r} and step at most {s} is a noncommutative progression that lies in a nilpotent group of step at most {s}. A \epmh{coset nilprogression} in {G} of rank {r} and step at most {s} is a set of the form {\pi^{-1}(P)}, where {H} is a finite group in {G}, {N(H)} is the normaliser of {H}, {\pi: N(H) \rightarrow N(H)/H} is the quotient map, and {P} is a nilprogression of rank {r} in {N(H)/H}.

An ultra coset nilprogression is an ultraproduct {Q = \prod_{n \rightarrow \alpha} Q_n} of coset nilprogressions of rank {r} and step at most {s}, for some standard natural numbers {r, s} independent of {n}.

Exercise 28 Show that the following two statements are equivalent:

  • (i) (Finitary nonabelian Freiman theorem) For all {K \geq 1}, there exists {C_{K}, s_K, r_K \geq 1} such that, given a finite {K}-approximate group {A} in a group {G = (G,\cdot)}, one can find a coset nilprogression {Q} in {G} of rank at most {r_K} and step at most {s_K} such that {A^4} contains {Q}, and {A} can be covered by at most {C_{K}} left-translates of {Q}.
  • (ii) (Infinitary nonabelian Freiman theorem) For any ultra approximate group {A} in a nonstandard group {G = (G,\cdot)}, one can find an ultra coset nilprogression {Q} in {G} such that {A^4} contains {Q}, and {A} can be covered by finitely many left-translates of {Q}.

In later notes we will establish (ii), and hence (i), thus giving a (qualitatively) satisfactory description of finite approximate groups in arbitrary groups.

Exercise 29 Let {n} be a standard natural number. Show that every nonstandard finite subgroup of {{}^* GL_n({\bf C})} is virtually abelian.