Many structures in mathematics are incomplete in one or more ways. For instance, the field of rationals or the reals are algebraically incomplete, because there are some non-trivial algebraic equations (such as in the case of the rationals, or in the case of the reals) which could potentially have solutions (because they do not imply a necessarily false statement, such as , just using the laws of algebra), but do not actually have solutions in the specified field.
Similarly, the rationals , when viewed now as a metric space rather than as a field, are also metrically incomplete, beause there exist sequences in the rationals (e.g. the decimal approximations of the irrational number ) which could potentially converge to a limit (because they form a Cauchy sequence), but do not actually converge in the specified metric space.
A third type of incompleteness is that of logical incompleteness, which applies now to formal theories rather than to fields or metric spaces. For instance, Zermelo-Frankel-Choice (ZFC) set theory is logically incomplete, because there exist statements (such as the consistency of ZFC) which could potentially be provable by the theory (because it does not lead to a contradiction, or at least so we believe, just from the axioms and deductive rules of the theory), but is not actually provable in this theory.
A fourth type of incompleteness, which is slightly less well known than the above three, is what I will call elementary incompleteness (and which model theorists call the failure of the countable saturation property). It applies to any structure that is describable by a first-order language, such as a field, a metric space, or a universe of sets. For instance, in the language of ordered real fields, the real line is elementarily incomplete, because there exists a sequence of statements (such as the statements for natural numbers ) in this language which are potentially simultaneously satisfiable (in the sense that any finite number of these statements can be satisfied by some real number ) but are not actually simultaneously satisfiable in this theory.
In each of these cases, though, it is possible to start with an incomplete structure and complete it to a much larger structure to eliminate the incompleteness. For instance, starting with an arbitrary field , one can take its algebraic completion (or algebraic closure) ; for instance, can be viewed as the algebraic completion of . This field is usually significantly larger than the original field , but contains as a subfield, and every element of can be described as the solution to some polynomial equation with coefficients in . Furthermore, is now algebraically complete (or algebraically closed): every polynomial equation in which is potentially satisfiable (in the sense that it does not lead to a contradiction such as from the laws of algebra), is actually satisfiable in .
Similarly, starting with an arbitrary metric space , one can take its metric completion ; for instance, can be viewed as the metric completion of . Again, the completion is usually much larger than the original metric space , but contains as a subspace, and every element of can be described as the limit of some Cauchy sequence in . Furthermore, is now a complete metric space: every sequence in which is potentially convergent (in the sense of being a Cauchy sequence), is now actually convegent in .
In a similar vein, we have the Gödel completeness theorem, which implies (among other things) that for any consistent first-order theory for a first-order language , there exists at least one completion of that theory , which is a consistent theory in which every sentence in which is potentially true in (because it does not lead to a contradiction in ) is actually true in . Indeed, the completeness theorem provides at least one model (or structure) of the consistent theory , and then the completion can be formed by interpreting every sentence in using to determine its truth value. Note, in contrast to the previous two examples, that the completion is usually not unique in any way; a theory can have multiple inequivalent models , giving rise to distinct completions of the same theory.
Finally, if one starts with an arbitrary structure , one can form an elementary completion of it, which is a significantly larger structure which contains as a substructure, and such that every element of is an elementary limit of a sequence of elements in (I will define this term shortly). Furthermore, is elementarily complete; any sequence of statements that are potentially simultaneously satisfiable in (in the sense that any finite number of statements in this collection are simultaneously satisfiable), will actually be simultaneously satisfiable. As we shall see, one can form such an elementary completion by taking an ultrapower of the original structure . If is the standard universe of all the standard objects one considers in mathematics, then its elementary completion is known as the nonstandard universe, and is the setting for nonstandard analysis.
As mentioned earlier, completion tends to make a space much larger and more complicated. If one algebraically completes a finite field, for instance, one necessarily obtains an infinite field as a consequence. If one metrically completes a countable metric space with no isolated points, such as , then one necessarily obtains an uncountable metric space (thanks to the Baire category theorem). If one takes a logical completion of a consistent first-order theory that can model true arithmetic, then this completion is no longer describable by a recursively enumerable schema of axioms, thanks to Gödel’s incompleteness theorem. And if one takes the elementary completion of a countable structure, such as the integers , then the resulting completion will necessarily be uncountable.
However, there are substantial benefits to working in the completed structure which can make it well worth the massive increase in size. For instance, by working in the algebraic completion of a field, one gains access to the full power of algebraic geometry. By working in the metric completion of a metric space, one gains access to powerful tools of real analysis, such as the Baire category theorem, the Heine-Borel theorem, and (in the case of Euclidean completions) the Bolzano-Weierstrass theorem. By working in a logically and elementarily completed theory (aka a saturated model) of a first-order theory, one gains access to the branch of model theory known as definability theory, which allows one to analyse the structure of definable sets in much the same way that algebraic geometry allows one to analyse the structure of algebraic sets. Finally, when working in an elementary completion of a structure, one gains a sequential compactness property, analogous to the Bolzano-Weierstrass theorem, which can be interpreted as the foundation for much of nonstandard analysis, as well as providing a unifying framework to describe various correspondence principles between finitary and infinitary mathematics.
In this post, I wish to expand upon these above points with regard to elementary completion, and to present nonstandard analysis as a completion of standard analysis in much the same way as, say, complex algebra is a completion of real algebra, or real metric geometry is a completion of rational metric geometry.
— 1. Elementary convergence —
In order to understand the concept of a metric completion of a metric space , one needs to know about the distinction between a Cauchy sequence and a convergent sequence. Similarly, to talk about the elementary completion of a structure , one needs the notion of an elementarily Cauchy sequence and an elementarily convergent sequence.
Let us set out some notation. We assume that we have some first-order language , which allows one to form sentences involving the first-order logical symbols (, , , , , , etc.), variables of one or more types, the equality symbol , some constant symbols, and some operations and relations. For instance:
- could be the language of multiplicative groups, in which there is only one type of object (a group element), a constant symbol , a binary operation from pairs of group elements to group elements, and a unary operation from group elements to group elements.
- could be the language of real ordered fields, in which there is one type of object (a field element), constant symbols , binary operations , and unary operations (with the latter only being defined for non-zero elements), and the order relation .
- could be the language of (formal) metric spaces, in which there are two types of objects (points in the space, and real numbers), the constants, operations and relations of a real ordered field, and a metric operation from pairs of points in the space to real numbers.
- could be the language of sets, in which there is one type of object (a set) and one relation .
- etc., etc.
We assume that the language has at most countably many types, constants, operations, and relations. In particular, there are at most countably many sentences in .
A structure for a language is a way of interpreting each of the object classes in as a set, and each of the constants, operations, and relations as an elements, functions, and relations on those sets respectively. For instance, a structure for the language of groups would be a set , together with a constant symbol , a binary function , and a unary operation . In particular, groups are structures for the language of groups, but so are many non-groups. Each structure can be used to interpret any given sentence in , giving it a truth value of true or false. We write if is interpreted to be true by . For instance, the axioms of a group can be expressed as a single sentence , and a structure for the language of groups is a group if and only if .
Now we introduce the notion of elementary convergence.
Definition 1 (Elementary convergence) Let be a structure for a language , and let be a sequence of objects in (all of the same type). Let be another object in of the same type as the .
- We say that the sequence is elementarily Cauchy if, for every predicate that takes one variable of the same type as the as input, the truth value of becomes eventually constant (i.e. either is true for all sufficiently large , or is false for all sufficiently large ). We write this eventual truth value as .
- We say that the sequence is elementarily convergent to if we have for every predicate that takes one variable of the same type as the or as input.
Remark 1 One can view the predicates (or more precisely, the sets ) as generating a topology on (or more precisely, on the domain of one of the object types of in ), in which case elementary convergence can be interpreted as convergence in this topology. Indeed, as there are only countably many predicates, this topology is metrisable.
To give an example, let us use the language of ordered fields , with the model , and pick a transcendental number , e.g. . Then the sequence is elementarily convergent to . The reason for this is that the language is fairly limited in nature, and as such it can only define a fairly small number of sets; in particular, if is a predicate of one variable, then the Tarski-Seidenberg theorem tells us that the set cut out by that set has to be a semi-algebraic set over the algebraic reals, i.e. a finite union of (possibly unbounded) intervals (which can be open, closed, or half-open) whose endpoints are algebraic reals. In particular, a transcendental number , if it lies in such a set, lies in the interior of such a set, and so will also lie in such a set for large enough, and similarly if lies outside such a set.
In contrast, if one picks an algebraic number for , such as , then does not converge in an elementary sense to , because one can find a predicate such as which is true for but not true for any of the . So the language has sufficiently “poor vision” that it cannot easily distinguish a transcendental number such as from nearby numbers such as , but its vision is significantly better at algebraic numbers, and in particular can distinguish from easily. So we see that elementary convergence is, in this case, a slightly stronger concept than the usual topological or metric notion of convergence on .
In the case of the real model of ordered fields, elementary limits are unique, but this is not the case in general. For instance, in the language of fields, and using the complex model , any given complex number is elementarily indistinguishable from its complex conjugate , and so any sequence of complex numbers that would converge elementarily to , would also converge elementarily to . (In fact, there is an enormous Galois group , the action of which is completely undetectable with regards to elementary convergence.)
A related problem is that the operations on a structure are not necessarily continuous with respect to these elementary limits. For instance, if are sequences of real numbers that converge elementarily to respectively, it is not necessarily the case that converge to (consider for instance the case when and ).
One way to partially resolve these problem is to consider the convergence not just of sequences of individual objects , but of sequences of families of objects:
Definition 2 (Joint elementary convergence) Let be a structure a language , let be a set, and for each natural number , let be a tuple of of elements in , and let be another tuple in , with each having the same type as .
- We say that the tuples are jointly elementarily Cauchy if, for every natural number , every predicate of variables in of the appropriate type, and every , the truth value of is eventually constant.
- We say that the tuples are jointly elementarily convergent to if, for every natural number , every predicate of variables in of the appropriate type, and every , the truth value of converges to the truth value of as .
For instance, using the complex model of the language of fields, if converges elementarily to (say) , then we cannot prevent from also converging elementarily to . (Indeed, it is not hard to see that converges elementarily to if and only for all sufficiently large .) But if we ask that jointly converges to , then will not also jointly converge to (though it does jointly converge to ).
In a similar fashion, if are reals that converge jointly elementarily to , then will converge elemntarily to also.
Now we give a more sophisticated example. Here, is the language of set theory, and is a model of ZFC. In ZFC set theory, we can of course construct most of the objects we are used to in modern mathematics, such as a copy of the real line, a copy of the natural numbers, and so forth. Note that ‘s interpretation of the natural numbers may be different from the “true” natural numbers ; in particular, in non-standard models of set theory, may be much larger than (e.g. it may be an ultrapower of ). Because of this, we will be careful to subscript ‘s copies of such objects in order to distinguish them from their true counterparts, though it will not make much difference for this immediate example.
We can also define in all the formal apparatus needed for probability theory, such as a probability space and a real-valued random variable on that space.
Now suppose that inside we have a sequence of probability spaces, and a sequence of random variables on these probability spaces. Now suppose the quintuple is jointly elementarily convergent to a limit . The axioms of being a probability space can be encoded inside the first order language of set theory, so the limit is also a probability space (as viewed inside ). Similarly, is a random variable on this probability space.
Now let be rational numbers. If , then by the definition of elementary convergence (and the fact that rational numbers can be defined using an expression of finite length in the language ), we see that holds for all sufficiently large . From this, one can deduce that the converge in distribution to . Thus we see that in this case, joint elementary convergence is at least as strong as convergence in distribution, though (much as with the example with elementary convergence in using the language of ordered fields) the two notions of convergence are not equivalent.
We included in the quintuple due to the use of real numbers such as in the above discussion, but it is not strictly necessary, because one can construct uniquely in from the axioms of set theory by using one of the standard constructions of the real numbers. But note that while we may use the set of real numbers in the above elementary convergence, one cannot invoke specific real numbers unless they are “constructible” in the sense that they can be uniquely specified in the language . If one wished to be able to use arbitrary real numbers as constants, one would not only place into the quintuple, but also place in every element of into the tuple (thus making the tuple quite large, and most likely uncountable, though note from Skolem’s paradox that it is possible for to be (externally) countable even as it is uncountable from the internal perspective of ).
As we see from the above discussion, joint elementary convergence is a useful notion even when some of the elements in the tuple are constant. We isolate this case with another definition:
Definition 3 (Joint relative elementary convergence) Let be a structure for a language , let be sets, and for each natural number , let be a tuple of of elements in , and let and be further tuples in . We say that the tuples are jointly elementarily convergent to relative to the constants if the disjoint union is jointly elementarily convergent to .
We define the notion of are jointly elementarily Cauchy relative to the constants similarly.
Informally, if is jointly elementarily convergent to relative to if the language is unable to asymptotically distinguish the from the , even if it “knows” about the constants .
— 2. Elementary completion —
Not every sequence in a structure is elementarily Cauchy or elementarily convergent. However, we have the following simple fact:
Proof: There are at most countably many predicates of a single variable of the right type in . By the infinite pigeonhole principle, we can find a subsequence of the such that is eventually constant. We can find a further subsequence of that sequence for which is eventually constant. We continue extracting subsequences of this nature for each , and then the diagonal sequence is elementarily Cauchy, as desired.
The same argument works when considering countably many variables and countably many constants (as there are still only countably many predicates to deal with):
Proposition 5 (Arzelá-Ascoli) Let be a structure for a language , let be at most countable sets, and for each natural number , let be a tuple of of elements in , and let be another tuple in . Then there is a subsequence which is jointly elementarily Cauchy relative to .
As in the metric case, not every elementarily Cauchy sequence is elementarily convergent, and not every sequence has an elementarily convergent subsequence. For instance, in the language of ordered fields, using the structure , the sequence has no elementarily convergent subsequence (because any limit of such a subsequence would be positive but also less than for arbitrarily large , contradicting the Archimedean property of the reals). From Proposition 4, we conclude that the reals are elementarily incomplete; there must exist some subsequence of that is elementarily Cauchy, but not elementarily convergent.
However, we can always complete any structure by passing to the ultrapower . This concept has been discussed in previous blog posts, so we give only a quick review here.
For the rest of this post, we fix a single non-principal ultrafilter on the (standard) natural numbers . (See this previous blog post for some basic discussion of what non-principal ultrafilters are, and how they are used in non-standard analysis.) A property of a natural number is said to hold for all sufficiently close to if the set of for which holds lies in the ultrafilter .
Definition 6 (Ultrapower) Let be a structure for some language . Given two sequences and of objects in , we say that the sequences are equivalent if one has for all sufficiently close to . The equivalence class associated to a given sequence will be called the ultralimit of the and denoted . The ultrapower of is the collection of all ultralimits of sequences of objects in . By identifying with for every object in , we see that every object in can be identified with an object in . We refer to elements of as standard objects, and elements of as non-standard objects.
Every relation and operation in can be extended to by taking ultralimits. For instance, given a -ary relation , and non-standard objects for , we say that holds in if and only if holds in for all sufficiently close to . Similarly, given a -ary operation and non-standard objects , we define the non-standard object to be the ultralimit of the standard objects .
Ultrapowers are also discussed in more detail in this previous blog post. A fundamental theorem of Los asserts that the ultrapower is elementarily equivalent to : any sentence in which is true in , is also true in , and vice versa; this fact is also known as the transfer principle for nonstandard analysis. For instance, the ultrapower of an ordered field is an ordered field, the ultrapower of an algebraically closed field is an algebraically closed field, and so forth. One must be slightly careful, though, with models that involve standard objects such as a copy of the natural numbers, or a copy of the real numbers; the ultrapower will have their own non-standard copy and of these objects, which are considerably larger than their standard counterparts, in the sense that they contain many more elements. Thus, for instance, if one is taking the ultrapower of a standard probability space , in which the probability measure takes values in the standard reals, the ultrapower is a non-standard probability space, in which the non-standard probability measure now takes values in the non-standard reals.
One can view the ultrapower as the completion of , in much the same way as the reals are a completion of the rationals:
This property is also known as countable saturation.
Proof: We can write for each natural number and a sequence of standard objects in . As before, we enumerate the predicates of one variable. For each natural number , the truth value of becomes eventually constant; we will call this constant .
Now let be a standard natural number. By construction, there exists an such that
for all . As is the ultralimit of the , there thus exists a set such that
for all . By replacing each with if necessary, we may assume that the are decreasing: .
For each , let be the largest integer in such that , or if no such integer exists. By construction, we see that for any , we haved
whenever and . If we then set to be the non-standard object , we thus have
for each , and thus converges elementarily to as required.
Combining this theorem with Proposition 4 we conclude an analogue of the Bolzano-Weierstrass theorem for ultrapowers:
Corollary 8 (Bolzano-Weierstrass for ultrapowers) In an ultrapower , every sequence of non-standard objects in has an elementarily convergent subsequence .
The same argument works (but with more complicated notation) for countable families of objects, and with countably many constants:
Theorem 9 (Bolzano-Weierstrass for ultrapowers, II) Let be an ultrapower, let be at most countable, let be a sequence of tuples of nonstandard objects in , and let be another sequence of tuples of nonstandard objects. Then there is a subsequence which converges jointly elementarily to a limit relative to the constants .
The proof of this theorem proceeds almost exactly as in the single variable case, the key point being that the number of predicates that one has to stabilise remains countable.
Remark 2 If one took the ultrafilter over a larger set than the natural numbers , then one could make the sets larger as well. Such larger saturation properties, beyond countable saturation, are useful in model theory (particularly when combined with the use of large cardinals, such as inaccessible cardinals), but we will not need them here.
Conversely, every nonstandard object can be viewed as the elementary limit of standard objects:
Proof: Let be an enumeration of the predicates of one variable. For any natural number , there exists a nonstandard object such that has the same truth value as for all , namely . By transfer, there must therefore exist a standard object such that has the same truth value as . Thus converges elementarily to , and the claim follows.
Exercise 1 If is the ultralimit of a sequence of standard objects, show that there is a subsequence that converges elementarily to .
Exercise 2 (Heine-Borel theorem for structures) Given any structure , show that the following four statements are equivalent:
- (Countable saturation) If are a countable family of predicates, such that if any finite number of are simultaneously satisfiable in (i.e. for each there exists such that holds for all ), then the entire family of are simultaneously satisfiable (i.e. there exists such that holds for all ).
- (Countable compactness) Every countable cover of by sets of the form for some predicate , has a finite subcover.
- (Elementary completeness) Every elementarily Cauchy sequence in has an elementarily convergent subsequence.
- (Bolzano-Weierstrass property) Every elementary sequence in has an elementarily convergent subsequence.
The Bolzano-Weierstrass theorem for ultrapowers can then be used to derive the foundational properties of nonstandard analysis. For instance, consider the standard natural numbers in , and hence in . Applying the Bolzano-Weierstrass theorem for ultraproducts, we conclude that some subsequence of natural numbers will converge elementarily to a non-standard natural number . For any standard natural number , we have for all sufficiently large , and hence on taking elementary limits we have (since is constructible). Thus we have constructed an unbounded nonstandard natural number, i.e. a number which is larger than all standard natural numbers.
In a similar spirit, we can also use the Bolzano-Weierstrass theorem construct infinitesimal nonstandard real numbers which are positive, but less than every standard positive real number (and in particular less than for any standard ).
More generally, we have the overspill principle: if is a predicate involving some non-standard constants , such that is true for arbitrarily large standard natural numbers , then it must also be true for at least one unbounded nonstandard natural number . Indeed, one simply takes a sequence of standard natural numbers for which , and extracts a subsequence of these which converges elementarily to a non-standard limit (relative to ), which must then be unbounded. Contrapositively, if holds for all unbounded , then it must also hold for all sufficiently large standard .
Similarly, we have the underspill principle: if a predicate is true for arbitrarily small positive standard real , then it must also be true for at least one infinitesimal positive non-standard real ; and contrapositively, if it is true for all infinitesimal positive non-standard real , then it is also true for all sufficiently small standard real .
A typical application of these principles is in the nonstandard formulation of continuity:
Proposition 11 (Nonstandard formulation of continuity) Let be a standard function, which can then be extended by ultralimits to the nonstandard completion . Let . Then the following are equivalent:
- is continuous at .
- One has whenever is a nonstandard real such that .
Proof: If is continuous, then the “epsilon-delta” definition implies that whenever (so that for every standard ), one has for every standard (by transfer), and thus . Conversely, if is discontinuous at , then there exists a sequence of standard reals converging to such that for some standard ; taking ultralimits using Bolzano-Weierstrass to extract a subsequence that is elementarily convergent relative to , we thus have a non-standard with , so that .
Exercise 3 With the notation as above, show that is uniformly continuous if and only if whenever are such that .
Exercise 4 With the notation as above, show that is differentiable at a standard real with derivative if and only if for all nonstandard reals .
— 3. The correspondence principle —
One can use the Bolzano-Weierstrass theorem for ultrapowers to establish various versions of the correspondence principle, as discussed previously on this blog. A simple example occurs when demonstrating the equivalence of colouring theorems, such as the following:
It is clear that Theorem 13 implies Theorem 12. To deduce Theorem 12 from Theorem 13, we can argue as follows. Suppose Theorem 13 fails, then there exists and , and arbitrarily large standard natural number for which there exists a -colouring of without any monochromatic arithmetic progressions of length . Applying the overspill principle (or the Bolzano-Weierstrass theorem), there must then also exist an unbounded nonstandard natural number for which there exists a -colouring of without any monochromatic arithmetic progressions of length . But the nonstandard interval contains the standard integers as a subset, thus the integers can now also be -coloured without any monochromatic arithmetic progressions of length , contradicting Theorem 12.
As another example, we can relate qualitative and quantitative results in algebraic geometry. For instance, as noted previously on this blog, the following basic result in algebraic geometry,
is equivalent to the following more quantitative version:
Theorem 15 (Quantitative decomposition into varieties) Every algebraic set of complexity at most over an algebraically closed field can be decomposed at most algebraic varieties, each of complexity at most , where depends only on .
(For a definition of complexity see the previous blog post.)
Clearly Theorem 15 implies Theorem 14. To show the converse implication, suppose that Theorem 15 failed, then there exists such that for every standard natural number there exists an algebraic set of complexity at most over some field that cannot be decomposed into fewer than algebraic varieties. We use the Bolzano-Weierstrass theorem for ultrapowers to extract a subsequence that converges jointly elementarily to some limit . As each of the are algebraically closed fields, the elementary limit is also. As the were algebraic sets over of uniformly bounded complexity, is an algebraic set over , and thus by Theorem 14 is decomposable into at most algebraic varieties for some finite . The property of being decomposable into at most algebraic varieties can be phrased in an elementarily open manner, i.e. as the disjunction of sentences in first-order logic; this is essentially established in the previous blog post, with the key point being that any top-dimensional component of an algebraic set has a lesser degree than that of the original set, and so has a uniform bound on complexity. Thus, we see that for all sufficiently large , must also be decomposable into at most algebraic varieties, a contradiction.
Our final example, namely the Furstenberg correspondence principle, is a bit more sophisticated. Here, we are demonstrating the equivalence of the following two statements:
It is easy to use Theorem 17 to show Theorem 16, so we focus on the reverse inclusion. Suppose that Theorem 17 failed, then there exists a standard integer , a standard real , and a standard set of integers of positive upper density at least that has no arithmetic progressions of length . In particular, for arbitrarily large standard , there exists a subset of of density at least without any progressions of length . Applying the overspill principle, there thus exists an unbounded nonstandard and a nonstandard subset of of density at least without any progressions of length .
Let be the collection of all nonstandard subsets of . (Note that not every subset of a nonstandard set remains nonstandard; it may instead merely be an external subset. See this previous blog post for further discussion.) This is a Boolean algebra. From countable saturation we see that this Boolean algebra has the following special property: if any set in this Boolean algebra is partitioned into an (externally) countable family of further elements in this Boolean algebra, then all but finitely many of the are empty. For if this were not the case, then by the axiom of choice, one could find a subsequence and a set of elements of . Passing to a further subsequence, we can assume that the converge elementarily to a limit . But then this limit lies in but not in any of the , a contradiction.
From the above property, we see that any (external) finitely additive measure on is automatically a premeasure, and thus by the Hahn-Kolmogorov extension theorem, can be extended to a countably additive measure on the measure-theoretic completion of the (external) -algebra generated by .
In particular, if we consider the nonstandard normalised counting measure
on and take its standard part,
this is a finitely additive probability measure on , and hence extends to a probability measure in , which we will continue to call . This measure is known as the Loeb measure on the nonstandard set . Observe that any nonstandard subset of of infinitesimal density will have Loeb measure zero. On the other hand, the set had density at least , and so will have Loeb measure at least also.
Next, we define the shift by , leaving undefined for . But observe that has an infinitesimal density, hence has Loeb measure zero. So is defined almost everywhere, and is easily seen to be measurable and measure-preserving; it has an (almost everywhere defined) inverse that is also measurable and measure-preserving. Thus with Loeb measure and the shift becomes a measure-preserving system. Applying Theorem 16, we can thus find a standard such that has positive Loeb measure, so contains a -term arithmetic progression, a contradiction.
Remark 3 As stated, the measure space structure on is not separable (i.e. countably generated) or regular (coming from a metric space). However, this can be fixed by restricting attention to the much smaller -algebra generated by and its shifts (after dealing with the null sets on which is not defined, e.g. by cutting out the neighbourhood of ). We omit the details.
— 4. The Szemerédi regularity lemma —
Finally, we use nonstandard analysis to give a proof of the Szemerédi regularity lemma, which we phrase as follows:
for all and , where , viewing as a symmetric subset of .
Here we do not make the cells in the partition of equal size, as is customary, but it is not too difficult to obtain this additional property from the above formulation of the lemma. The ability of nonstandard analysis to establish regularity lemmas was first observed by Elek and Szegedy.
An application of the Bolzano-Weierstrass theorem for ultraproducts shows that this lemma is equivalent to the following nonstandard version:
Lemma 19 (Szemerédi regularity lemma, nonstandard formulation) Let be a nonstandard finite graph, and let . Then there exists a vertex partition , where is a standard natural number and are nonstandard subsets of such that for all pairs outside of a bad set with , there exists a standard density such that
for all and .
To see why Lemma 19 implies Lemma 18, suppose that Lemma 18 failed. Then there is a standard such that for every standard one could find a standard finite graph which could not be regularised into or fewer cells as required by the lemma. Applying the Bolzano-Weierstrass theorem for ultraproducts, we can assume that converges elementarily (relative to ) to a limit , which is then a nonstandard finite graph which cannot be regularised into any standard finite number of cells. But this contradicts Lemma 19.
It remains to prove Lemma 19. Let be Loeb measure on (as constructed in the previous section), and be Loeb measure on . It is easy to see that contains the product -algebra as a subalgebra, and that the product measure is the restriction of to . The edge set , viewed as a symmetric nonstandard subset of , is measurable in , but is not necessarily measurable in . One can then form the conditional expectation , which is a -measurable function that is defined up to -almost everywhere equivalence, and takes values in .
The -algebra is generated by product sets of -measurable functions, which in turn can be approximated in measure to arbitrary accuracy by product sets of nonstandard sets. As is -measurable, we can approximate it to less than in norm by a finite linear combination of indicator functions of products of nonstandard sets. Organising these products, we thus see that
for some finite partition of into nonstandard sets and some standard real numbers . By Markov’s inequality, we thus see that
for all outside of a bad set with
Now let and be nonstandard sets, with outside of . Then
On the other hand, is orthogonal to all functions, and in particular to , and thus
we thus see that
Thus has been regularised using a finite number of cells, as required.