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 , , , 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 is still Lipschitz, but now with Lipschitz constant instead of . 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 1Another type of correspondence between hard analysis and soft analysis, which is “syntactical” rather than “semantical” in nature, arises by taking theproofsof 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 asproof miningin 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 1Let be a sequentially compact topological space, let be a dense subset of , and let be a continuous function (giving the extended half-line the usual order topology). Then the following statements are equivalent:

- (i) (Qualitative bound on infinitary objects) For all , one has .
- (ii) (Quantitative bound on finitary objects) There exists such that for all .

In applications, is typically a (non-compact) set of “finitary” (or “finite complexity”) objects of a certain class, and is some sort of “completion” or “compactification” of 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 in is adherent to , and so given any neighbourhood of , there exists . Since , we conclude from the continuity of that 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 , there exists such that . (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 converge to a limit . By continuity of , this implies that , contradicting (i).

Remark 2Note that the above deduction of (ii) from (i) isineffectivein that it gives no explicit bound on the uniform bound in (ii). Without any further information onhowthe 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 oftenfinitiseorproof minethat argument to extract an effective bound for , 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 (or in some cases, a more general net ) of finitary objects and extract a suitable infinitary limit object . In the literature, there are three main ways in which one can extract such a limit:

- (Topological limit) If the are all elements of some topological space (e.g. an incomplete function space) which has a suitable “compactification” or “completion” (e.g. a Banach space), then (after passing to a subsequence if necessary) one can often ensure the converge in a topological sense (or in a metrical sense) to a limit . 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 are all objects in some category (e.g. metric spaces, groups, fields, etc.) with a number of morphisms between the (e.g. morphisms from to , or vice versa), then one can often form a direct limit or inverse limit of these objects to form a limiting object . 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 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 or limiting space that is a
*logical limit*of the , in the sense that various properties of the (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 that are uniform in the choice of ambient group . As such, one often seeks to take a limit of approximate groups that lie in completely unrelated ambient groups , with no obvious morphisms or metrics tying the 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 or the reals , one can obtain nonstandard number systems such as the nonstandard natural numbers or the nonstandard real numbers (or hyperreals) . 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. is a subring of ), which allows for some convenient algebraic manipulations (such as the quotient space construction to create spaces such as ) 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 3Throughout 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 , although one can certainly consider ultrafilters on more general sets.

Definition 2 (Ultrafilter)Anfilteron the natural numbers is a collection of sets of natural numbers obeying the following axioms:

- (Monotonicity) If , and , then .
- (Intersection) If , then .
- (Properness) .
An

ultrafilteron the natural numbers is a filter which obeys an additional axiom:

- (Maximality) If , then exactly one of and lies in .
A

nonprincipal ultrafilteris an ultrafilter that obeys one final axiom:

- (Nonprincipality) No finite set belongs to . (Equivalently: any cofinite set will belong to .)
Given a nonprincipal ultrafilter , we say that a set is

-largeif it is contained in , and-smallotherwise. A property of the natural numbers is saidto hold for all sufficiently close toif it holds in an -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 2Call an ultrafilterprincipalif it is not nonprincipal. Show that for any natural number , the set is a principal ultrafilter, and conversely every principal ultrafilter is of this form. Thus, the space of principal ultrafilters can be identified with .

The space of all ultrafilters is denoted , and so by the preceding exercise one can view as a subset of , with 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 is an ultrafilter, show that the map that maps -large subsets of to and -small subsets of to , is a finitely additive probability measure (thus whenever are disjoint). Conversely, show that every finitely additive probability measure that takes values in arises in this manner.

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

Exercise 4 (Ultrafilters as Stone-Cech compactification of )We view as a subset of the power set , and give it the induced topology from the product topology on .

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

Remark 4More discussion on the Stone-Cech compactification can be found in this previous blog post. The compact space 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 from the *-algebra of bounded complex sequences to the complex numbers is a*-homomorphismif it is complex-linear and obeys the conjugation lawand the homomorphism law

for all bounded sequences , while mapping the constant sequence to .

- (i) Show that if is a ultrafilter, show that there exists a unique *-homomorphism with the property that for every , one has if and only if is -large.
- (ii) Conversely, show that all *-homomorphisms from to arise in this fashion, and that a *-homomorphism arises from a nonprincipal ultrafilter if and only if it extends the limit functional (thus whenever is convergent).

From the above exercise we see that can be viewed as the Gelfand spectrum of .

Exercise 6 (Ultrafilters and Arrow’s theorem)Let be a finite set consisting of at least three elements (representing “candidates”). Let denote the space of all total orderings on . Define avoting systemto be a function from a sequence of orderings on (representing the preferences of an infinite number of “voters”) to an ordering on . If is a nonprincipal ultrafilter, show that there is a unique voting system with the property that for any distinct , one has if and only if for all sufficiently close to . Show furthermore that this voting system obeys the following axioms for all distinct candidates and all orderings :

- (Consensus) If for all , then .
- (Non-dictatorship) There is no with the property that holds if and only if holds for all choices of .
- (Independence of irrelevant alternatives) The truth value of depends only on the truth values of for all . Thus, if is another sequence of orderings such that if and only if , then holds if and only if 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*; and - A
*standard universe*, 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 . If we are doing analysis, the standard universe might include the real numbers , as well as the set of subsets of , the set of functions from to , and so forth. If we are studying approximate groups in an ambient group , the standard universe might include the elements of , subsets of , 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 as the *standard* natural numbers, the real numbers as the *standard* real numbers , and so forth. This is in order to distinguish such spaces from the *nonstandard* natural numbers , the *nonstandard* real numbers , etc., which we now define.

Remark 5For the applications in this course, the precise choice of nonprincipal ultrafilter will be completely irrelevant; one such ultrafilter will be just as good for our purposes as another. Basically, we only use the ultrafilter 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 , of standard objects are said to beequivalentif one has for all sufficiently close to . This is easily seen to be an equivalence relation. We define theultralimitto be the equivalence class of a sequence ; thus if and only if for all sufficiently close to . Such ultralimits will be callednonstandard objects.Given a sequence of standard spaces , we define the ultraproduct to be the space of all ultralimits , where for each . Such spaces will be called

nonstandard spaces(also known asnonstandard setsorinternal sets).If is a standard space, we define the

ultrapowerof to be the ultraproduct of the constant sequence . We embed inside by identifying each element of with the ultralimit . If is the standard elements of some type, we refer to elements of (i.e. ultralimits of sequences in ) as nonstandard elements of the same type. Thus, for instance, elements of are nonstandard natural numbers, elements of are nonstandard real numbers (also known as hyperreals), and so forth. The ultrapower of the standard universe will be called thenonstandard universe.

Note that one can define an ultralimit for sequences of standard objects that are only defined for an -large set of , and similarly one can define ultraproducts on spaces that are only defined for an -large set of . From the nonprincipal nature of we observe that we can modify or for finitely many without affecting the ultralimit or ultraproduct .

Remark 6The relation between a standard space and its ultrapower is analogous in some ways to the relationship between the rationals and its metric completion, namely the real line . 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 of one of the Cauchy sequences in this class), and then one identifies each rational with its formal limit 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 ofarbitrarysequences. This makes the ultrapower construction more “powerful” than the metric completion construction in that noa prioriconvergence (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 7With 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 terminologystrictly nonstandardto denote a nonstandard object that is not standard. For instance, an element of would be a strictly nonstandard natural number.

Exercise 7If is a standard space, show that if and only if is finite. In particular, if is a sequence with finite (standard) range , then also lives in the same range .

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

Exercise 8Show that 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 be standard spaces. Show that , , and . Also show that if and only if .

Strictly speaking, ultrapowers do not preserve Cartesian products: from the definitions, and are slightly different spaces. However, there is an obvious bijection between the two sets, and we shall abuse notation and implicitly make the identification throughout the rest of this post. More generally, given sequences of standard spaces, we make the identification .

Remark 8Just as standard spaces are subsets of the standard universe , nonstandard spaces are subsets of the nonstandard universe . 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 is not a nonstandard subset of (and as such, is sometimes referred to as anexternal subsetof ). 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 be a sequence of nonstandard spaces such that any finite collection of these spaces has non-empty intersection (thus for all ). Then the entire sequence has non-empty intersection (thus ).

*Proof:* Write , then for each , is the ultraproduct of (cf. Exercise 9). In particular, is non-empty for all in an -large subset of the natural numbers. By shrinking the as necessary we may assume that they are monotone, thus , and such that does not contain any natural number less than ; in particular, . For any , let denote the largest natural number such that , and then let denote an element of . Then by construction, for each , we have for all , and thus the nonstandard object lies in for all , and thus is non-empty as required.

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 be a finite collection of nonstandard spaces, and let be an at most countable collection of nonstandard -ary predicates on these spaces. Let for be sequences of nonstandard objects in respectively (indexed by the standard natural numbers ). Show that there are subsequences whichconverge elementarilyto some elements of in the sense that for each predicate , one has for all sufficiently large . (See this previous post for more discussion on these sorts of completeness properties on nonstandard spaces.)

Remark 9By replacing the ultraproduct construction with more sophisticated set-theoretic constructions, one can strengthen the countable saturation property by replacing “countable” by “at most cardinality ” for any given cardinal ; however, as one increases , the size of the ultraproduct-type object must also necessarily increase (although one can make the size of the model only slightly larger than , 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)Astandard functionis a function between two standard spaces . Given a sequence of standard functions, we define theultralimitto be the function defined by the formulawhenever . One can easily verify that this does indeed define a function, which we refer to as a

nonstandard function(also called aninternal functionin the literature). The ultralimit of a single standard function is thus a nonstandard function from to that extends ; by abuse of notation we shall also refer to as (analogously to how we identify with rather than giving it a different name such as ).Similarly, for a (standard) natural number , define a

standard -ary relation(orstandard -ary predicate) to be a standard function from the product of standard spaces to the Boolean space (which we will treat as part of the standard universe ). By the preceding construction (and Exercise 7), the ultralimit of a sequence of standard -ary relations (with independent of ) is another -ary relationwhich we will call a

nonstandard -ary relation(also known as aninternal -ary relation). Thus is true if and only if is true for all sufficiently close to . Again, we identify each relation with its nonstandard extension .In a very similar spirit, given a sequence of standard -ary operators, one can define the ultralimit

which we will call a

nonstandard -ary operator(also known as aninternal -ary operator). Again, we identify each standard operator with its nonstandard extension .

Example 1Let and be two nonstandard natural numbers (thus are sequences of standard natural numbers). Then, by definition,

- is the nonstandard natural number .
- is the nonstandard natural number .
- One has if for all sufficiently close to .
- is even if is even for all sufficiently close to .
- is prime if is prime for all sufficiently close to .

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 is even if and only if it is of the form for some nonstandard natural number .
- (iii) Show that a nonstandard natural number is prime if and only if it is greater than , but cannot be factored as for some nonstandard natural numbers .
- (iv) Show that the standard Goldbach conjecture (every even standard natural number larger than is the sum of two standard primes) is logically equivalent to the nonstandard Goldbach conjecture (every even nonstandard natural number larger than is the sum of two nonstandard primes).
- (v) Show that the standard twin prime conjecture (for any standard natural number , there exists a standard prime such that is also prime) is logically equivalent to the nonstandard twin prime conjecture (for any nonstandard natural number , there exists a nonstandard prime such that is also a nonstandard prime).

Now we generalise the above examples.

Exercise 13Let , and let be two sequences of -ary predicates. For each , let , and write and .

- (i) (Continuity of Boolean operations) Show that , , and .
- (ii) (Continuity of existential quantifier) If , denotes the -ary predicate in the remaining variables for , and denotes the -ary predicate in the remaining variables for , show that .
- (iii) (Continuity of universal quantifier) If , denotes the -ary predicate in the remaining variables for , and denotes the -ary predicate in the remaining variables for , show that .

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 be natural numbers. For each natural number , suppose one has a collection of standard objects, spaces, operators, and relations (of various arities), and let be the corresponding nonstandard objects, spaces, operators, and relations formed via the ultralimit or ultraproduct construction. Let be a formal -ary predicate expressible in first-order logic using objects, spaces, operators, and relations. Then , when quantified over , is the ultralimit of quantified over . (In particular, quantified over is a nonstandard predicate.)Specialising to the case , (so is a first-order sentence involving objects, spaces, operators, and relations), we see that is true when quantified over if and only if is true when quantified over for all sufficiently close to .

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.

- is an ordered field when given the usual constants , field operations , and order relation . (Technically, is not an operation on because it is undefined at , but this can easily be fixed by artificial means, e.g. by arbitrarily defining at .). The assertion that 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 (with the same constants and the nonstandard extensions of the field operations and order relation) is also an ordered field.
- Let be a sequence of groups; then the ultraproduct (with the ultralimit group operation , 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 , is an element of , then the ultralimit is a central element of if and only if is a central element of for all sufficiently close to . Similarly, if for each , is a subset of , then the ultraproduct is a normal subgroup of if and only if is a normal subgroup of for all sufficiently close to .
- The standard natural numbers obey the axiom of induction: if is a predicate definable in the language of Peano arithmetic, and is true, and implies for all , then is true for all . As a consequence, the same axiom of induction also holds for the nonstandard natural numbers . 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: “, and for any nonstandard natural number , implies . Hence, by induction, for all nonstandard natural numbers “. The reason is that the predicate “” 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 (viewed as a subset of ) 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 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 consists only of standard natural numbers, then it is finite.
- (iv) Show that the nonstandard natural numbers are not well-ordered. Why does this not contradict Los’s theorem?

Exercise 15For each , let be a group, and let be a subset of . Write and .

- (i) Give an example in which each generates as a group, but does not generate as a group.
- (ii) Show that generates as a group if and only if there exists a (standard) natural number such that for all sufficiently close to . (
Hint:apply countable saturation (Exercise 10) to the sets .)

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 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 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 and one or more formal free variables , 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 is a well-formed formula (belonging to the associated formal space).
- Each object in is a well-formed formula (belonging to the associated formal space).
- If are well-formed formulae, and is a -ary operator, then will be a well-formed formula if the belong to the formal spaces indicated by the domain of . Of course, then belongs to the formal space indicated by the range of .

A *formal predicate* involving and one or more free variables is then formed by a finite number of applications of the following rules:

- If , are well-formed formulae belonging to the same formal space, then is a predicate.
- If are well-formed formulae, and is a -ary relation in , then is a predicate if the belong to the formal spaces indicated by the domain of .
- If and are predicates, then so are , , , , and .
- If is a predicate in and an additional free variable in some formal space , then and are predicates in . (Similarly for any permutation in the ordering of .)

Given a formal predicate involving and one or more free variables , we may *quantify* (or *interpret*) the predicate by associating each formal object in 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 becomes a concrete predicate on the appropriate quantified spaces by interpreting all the symbols in in the obvious fashion. For instance, if the primitive terms consist of a formal space and a formal binary operation , then is a formal unary predicate, and if one quantifies this predicate over a concrete group (which may be standard, nonstandard, or neither), then one obtains a concrete unary predicate , with true precisely when is a central element of .

Exercise 16With the above definitions, prove Theorem 6.

Exercise 17 (Compactness theorem)Let be an at most countable collection of formal objects, spaces, operators and relations. Let be a sequence of sentences involving the symbols in . Suppose that any finite collection 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 for which are all true when quantified over these assignments. Show that the entire collection 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 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 of finite sets, and a *nonstandard finite sequence of reals* to be a nonstandard function from a nonstandard finite set to the nonstandard reals, or equivalently an ultralimit of standard finite sequences of reals. We can define the (nonstandard) cardinality of a nonstandard finite set in the usual manner:

Thus, for instance, if is a nonstandard natural number, then the nonstandard finite set has nonstandard cardinality .

Similarly, if is a nonstandard finite sequence of reals, we define the nonstandard sum as

Thus for instance . 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

for any nonstandard finite sequence 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 , the integers , the real numbers , or the complex numbers to obtain nonstandard number systems such as , , , , 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 be one of the standard number systems (, , , , ). A nonstandard number in is said to beboundedif one has for some standard real number (or equivalently, some standard natural number ), andunboundedotherwise. If is a non-negative nonstandard real, we write if for some standard real number , thus a nonstandard number is bounded if and only if it is . We say that isinfinitesimalif for every standard real number (or equivalently, if for all standard positive natural numbers ), and write if for all standard real numbers , thus is infinitesimal if and only if it is .

Example 2All standard numbers are bounded, and all non-zero standard numbers are non-infinitesimal. The nonstandard natural number is unbounded, and the nonstandard real number is non-zero but infinitesimal.

Remark 10One 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*

and the *infinitesimal nonstandard reals*

Exercise 18 (Standard part)Show that is an ideal of the commutative ring , and one has the decomposition , thus every bounded real has a unique decomposition into astandard partand aninfinitesimal part. Show that the map is a ring homomorphism from to .

Exercise 19Let be an unbounded nonstandard natural number. Write and . Show that is a subgroup of the additive group , and that the quotient group is isomorphic (as an additive group) to the standard real numbers . (One could in fact use this construction as adefinitionof 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 .

Exercise 20Let be a standard function, which we extend to a nonstandard function in the usual manner. Show that the following statements are equivalent:

- (i) (Qualitative bound on nonstandard objects) For all , one has .
- (ii) (Quantitative bound on standard objects) There exists a standard real such that for all .
(

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 21Let be a standard subset of the reals .

- Show that is open if and only if , or equivalently if . (Here, denotes the sumset of and .)
- Show that is closed if and only if , or equivalently if .
- Show that is bounded if and only if .
- Show that is compact if and only if .

Exercise 22Let be a standard sequence of reals, and let be its nonstandard extension. Let be a real number.

- Show that converges to as if and only if for all unbounded natural numbers .
- Show that is conditionally convergent to if and only if for all unbounded natural numbers .

Exercise 23Let be a standard function, and let be its nonstandard extension. Show that the following are equivalent:

- is a continuous function.
- One has whenever , , and .
- One has for all .

Exercise 24Let be a standard function, and let be its nonstandard extension. Show that the following are equivalent:

- is a uniformly continuous function.
- One has whenever and .

Exercise 25Let be a standard function, and let be its nonstandard extension. Show that the following are equivalent:

- is a differentiable function.
- There exists a standard function such that for all and , or equivalently if for all and non-zero .

Exercise 26Let be a standard continuous function, and let be its nonstandard extension. Show that for any standard reals and any unbounded natural number , one has(note that is a nonstandard finite sum). More generally, show that

whenever and are nonstandard finite sequences with and for all .

** — 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 be a standard real number. A (global)approximate groupis a subset of a global group which is symmetric, contains the identity, and is such that can be covered by at most left-translates of .

Definition 10 (Ultra approximate group)Anultra approximate groupis an ultraproduct , where each is a standard finite -approximate group for some independent of .

Example 3If is a nonstandard natural number, then the nonstandard arithmetic progression is an ultra approximate group, because it is an ultraproduct of standard finite -approximate groups .

Example 4If is a nonstandard natural number, then the nonstandard cyclic group 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 , the statement of a set in a group being a -approximate group can be phrased in first-order logic quantified over using the group operations and the predicate of membership in . From this and Los’s theorem, we see that any ultraproduct of -approximate groups is again a -approximate group. In particular, an ultra approximate group is a -approximate group for some (standard) finite .

We will be able to make a correspondence between various assertions about -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 -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 , we say that a group is *-torsion* if every element has order at most , thus for each one has for some .

Proposition 11 (Correspondence in the torsion case)Let . The following two statements are equivalent:

- (i) (Finitary statement) For all , there exists such that, given a finite -approximate group in an -torsion group , one can find a finite (genuine) subgroup of such that contains , and can be covered by at most left-translates of .
- (ii) (Infinitary statement) For any ultra approximate group in a -torsion nonstandard group , one can find a nonstandard finite subgroup of such that contains , and can be covered by finitely many left-translates of .

*Proof:* Let us first assume (i) and establish (ii). Let be an ultra approximate group in an -torsion nonstandard group . Since is -torsion, and the property of being -torsion is a first-order statement in the language of groups, we see from Los’s theorem that is a -torsion group for all sufficiently close to . Since the are all finite -approximate groups for some independent of , we conclude from (i) that for all sufficiently close to , we can find a finite subgroup of such that contains , and can be covered by at most left-translates of . Taking and applying Los’s theorem again, we cnoclude that is a nonstandard finite subgroup of , that contains , and can be covered by at most left-translates of , 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 such that for each natural number , one can find a finite -approximate group in an -torsion group for which there does *not* exist any finite subgroup of such that contains *and* can be covered by at most left-translates of . We then form the ultraproducts and . By Los’s theorem, is an -torsion nonstandard group, and is an ultra approximate group in . Thus, by (ii), there is a nonstandard finite subgroup of such that contains and is covered by left-translates of for some (standard) natural number . By Los’s theorem, we conclude that for all sufficiently close to , is a finite subgroup of , contains , and is covered by left-translates of . In particular, as is nonprincipal, this assertion holds for at least one . But this contradicts the construction of .

Note how the infinitary statement in the above proposition is a qualitative version of the more quantitative finitary statement. In particular, parameters such as and 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 12A (standard symmetric)generalised arithmetic progressionof rank in a (standard) additive group is a set of the formwhere , , and the are constrained to be integers. An

ultra generalised arithmetic progressionis an ultraproduct of standard generalised arithmetic progressions of fixed rank .A (standard)

coset progressionof rank in a (standard) additive group is a set of the form , where is a finite subgroup of and is a generalised arithmetic progression of rank . Anultra coset progressionis an ultraproduct of standard coset progressions of fixed rank ; equivalently, it is a set of the form , where is a nonstandard finite group in a nonstandard group , and is an ultra generalised arithmetic progression in .

Exercise 27Show that the following two statements are equivalent:

- (i) (Finitary abelian Freiman theorem) For all , there exists such that, given a finite -approximate group in an abelian group , one can find a coset progression in of rank at most such that contains , and can be covered by at most left-translates of .
- (ii) (Infinitary abelian Freiman theorem) For any ultra approximate group in a abelian nonstandard group , one can find an ultra coset progression of such that contains , and can be covered by finitely many left-translates of .

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 13Given a (standard) finite number of generators in a (standard) group , and (standard) real numbers , define thenoncommutative progressionto be the set of all words in involving at most copies of for each . We refer to as therankof the noncommutative progression. Anilprogressionof rank and step at most is a noncommutative progression that lies in a nilpotent group of step at most . A \epmh{coset nilprogression} in of rank and step at most is a set of the form , where is a finite group in , is the normaliser of , is the quotient map, and is a nilprogression of rank in .An

ultra coset nilprogressionis an ultraproduct of coset nilprogressions of rank and step at most , for some standard natural numbers independent of .

Exercise 28Show that the following two statements are equivalent:

- (i) (Finitary nonabelian Freiman theorem) For all , there exists such that, given a finite -approximate group in a group , one can find a coset nilprogression in of rank at most and step at most such that contains , and can be covered by at most left-translates of .
- (ii) (Infinitary nonabelian Freiman theorem) For any ultra approximate group in a nonstandard group , one can find an ultra coset nilprogression in such that contains , and can be covered by finitely many left-translates of .

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

Exercise 29Let be a standard natural number. Show that every nonstandard finite subgroup of is virtually abelian.

## 18 comments

Comments feed for this article

16 October, 2011 at 3:56 pm

David RobertsHi Terry,

I’m a bit confused by the link provided to Goedel’s paper in Remark 3. What you say is that adding the axiom of choice to ZF is _conservative_ for statements in the language of PA, but you are linking to the paper about the _relative consistency_ of adding AC to ZF. I know this course is ‘not focused on foundations’, but could you clarify?

16 October, 2011 at 4:14 pm

Terence TaoThe way Godel proves the relative consistency of AC in that paper is by starting with an arbitrary model of ZF and showing that inside it one can obtain a model of ZFC (namely, the constructible universe L). This universe has the same model of the natural numbers as the original model of ZF (basically because all natural numbers in the original model are constructible in that model), and in particular assigns the same truth value to any sentence in the language of PA as the original model (i.e. arithmetic is absolute between the original model and the constructible universe). Thus, if one can prove a sentence in the language of PA in ZFC, then that sentence is also true in all models of ZF, and hence is provable in ZF by completeness.

16 October, 2011 at 10:37 pm

David RobertsAh, thanks. Just that the paper you linked to is a one-page research announcement and has no proofs. Makes sense now.

24 October, 2011 at 10:40 am

Proof mining and approximate groups, announcement | chorasimilarity[…] http://terrytao.wordpress.com/2011/10/15/254a-notes-6-ultraproducts-as-a-bridge-between-hard-analysi… […]

24 October, 2011 at 6:46 pm

The structure of approximate groups « What’s new[…] faithful representation” is a good first approximation.) As discussed in the previous lecture notes, we use an ultralimit for this purpose; the paper of Hrushovski where this strategy was first […]

27 October, 2011 at 8:37 pm

254A, Notes 7: Models of ultra approximate groups « What’s new[…] the previous set of notes, we introduced the notion of an ultra approximate group – an ultraproduct of finite […]

6 November, 2011 at 9:23 am

254A, Notes 8: The microstructure of approximate groups « What’s new[…] fact, a stronger statement is true, involving the nilprogressions defined in Notes 6: Proposition […]

11 November, 2011 at 9:32 am

Machfudzough…

I still confused..

XD

11 November, 2011 at 3:33 pm

Ben HayesIn Exercise 19, should $N$ be strictly non-standard? I think in the case $N=1,$ then the quotient group is just $Z.$

[Corrected, thanks – T.]11 November, 2011 at 6:28 pm

AnonymousIn definition 5, in the definition of a standard k-ary relation, the R_k should be replaced with X_k.

[Corrected, thanks – T.]5 February, 2012 at 11:33 am

254B, Notes 5: Product theorems, pivot arguments, and the Larsen-Pink non-concentration inequality « What’s new[…] use the tool of ultraproducts (which we will phrase in the language of nonstandard analysis). See this previous blog post for a discussion of ultraproducts and how they can be used to turn quantitative (or […]

2 April, 2012 at 4:55 pm

A cheap version of nonstandard analysis « What’s new[…] an ultrapower of with respect to some non-principal ultrafilter over the natural numbers; see e.g. this blog post for details. Once one is comfortable with ultrafilters and ultrapowers, this becomes quite a simple […]

12 September, 2012 at 3:36 pm

Definable subsets over (nonstandard) finite fields, and almost quantifier elimination « What’s new[…] this ultraproduct. (We will be using the notation of ultraproducts and nonstandard analysis from this previous blog post.) This approach is equivalent to the more finitary approach mentioned in the previous paragraph, at […]

28 October, 2012 at 12:24 pm

Walsh’s ergodic theorem, metastability, and external Cauchy convergence « What’s new[…] will assume some familiarity with nonstandard analysis, as covered for instance in these previous blog […]

14 November, 2012 at 9:42 am

Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets « What’s new[…] into equivalent qualitative, infinitary problems in zero characteristic (in the spirit of this blog post). This allows one to use several tools from those fields as “black boxes”; not just the […]

28 November, 2012 at 5:32 pm

Multiple recurrence in quasirandom groups « What’s new[…] this mixing theorem. Instead, we had to first use the machinery of ultraproducts (as discussed in this previous post) to convert the finitary statement about a quasirandom group to an infinitary statement about a […]

14 March, 2013 at 1:17 pm

Rectification and the Lefschetz principle | What's new[…] can be used as a bridge to connect quantitative and qualitative results (as discussed in these previous blog posts), we will deduce Theorem 3 from the following (well-known) qualitative […]

7 December, 2013 at 4:05 pm

Ultraproducts as a Bridge Between Discrete and Continuous Analysis | What's new[…] analysis“. Some of the material here is drawn from previous blog posts, notably “Ultraproducts as a bridge between hard analysis and soft analysis” and “Ultralimit analysis and quantitative algebraic geometry“‘. The text […]