Much as group theory is the study of groups, or graph theory is the study of graphs, model theory is the study of *models* (also known as structures) of some language (which, in this post, will always be a single-sorted, first-order language). A structure is a set , equipped with one or more operations, constants, and relations. This is of course an extremely general type of mathematical object, but (quite remarkably) one can still say a substantial number of interesting things about very broad classes of structures.

We will observe the common abuse of notation of using the set as a metonym for the entire structure, much as we usually refer to a group simply as , a vector space simply as , and so forth. Following another common bending of the rules, we also allow some operations on structures (such as the multiplicative inverse operation on a group or field) to only be partially defined, and we allow use of the usual simplifying conventions for mathematical formulas (e.g. writing instead of or , in cases where associativity is known). We will also deviate slightly from the usual practice in logic by emphasising individual structures, rather than the theory of general classes of structures; for instance, we will talk about the theory of a single field such as or , rather than the theory of all fields of a certain type (e.g. real closed fields or algebraically closed fields).

Once one has a structure , one can introduce the notion of a definable subset of , or more generally of a Cartesian power of , defined as a set of the form

for some formula in the language with free variables and any number of constants from (that is, is a well-formed formula built up from a finite number of constants in , the relations and operations on , logical connectives such as , , , and the quantifiers ). Thus, for instance, in the theory of the arithmetic of the natural numbers , the set of primes is a definable set, since we have

In the theory of the field of reals , the unit circle is an example of a definable set,

but so is the the complement of the circle,

and the interval :

Due to the unlimited use of constants, any finite subset of a power of any structure is, by our conventions, definable in that structure. (One can of course also consider definability without parameters (also known as -definability), in which arbitrary constants are not permitted, but we will not do so here.)

We can isolate some special subclasses of definable sets:

- An
*atomic definable set*is a set of the form (1) in which is an atomic formula (i.e. it does not contain any logical connectives or quantifiers). - A
*quantifier-free definable set*is a set of the form (1) in which is quantifier-free (i.e. it can contain logical connectives, but does not contain the quantifiers ).

Example 1In the theory of a field such as , an atomic definable set is the same thing as an affine algebraic set (also known as anaffine algebraic variety, with the understanding that varieties are not necessarily assumed to be irreducible), and a quantifier-free definable set is known as aconstructible set; thus we see that algebraic geometry can be viewed in some sense as a special case of model theory. (Conversely, it can in fact be quite profitable to think of model theory as an abstraction of algebraic geometry; for instance, the concepts of Morley rank and Morley degree in model theory (discussed in this previous blog post) directly generalises the concepts of dimension and degree in algebraic geometry.) Over , the interval is a definable set, but not a quantifier-free definable set (and certainly not an atomic definable set); and similarly for the primes over .

A quantifier-free definable set in is nothing more than a finite boolean combination of atomic definable sets; in other words, the class of quantifier-free definable sets over is the smallest class that contains the atomic definable sets and is closed under boolean operations such as complementation and union (which generate all the other boolean operations). Similarly, the class of definable sets over is the smallest class that contains the quantifier-free definable sets, and is also closed under the operation of *projection* from to for every natural number , where is the map .

Some structures have the property of enjoying quantifier elimination, which means that every definable set is in fact a quantifier-free definable set, or equivalently that the projection of a quantifier-free definable set is again quantifier-free. For instance, an algebraically closed field (with the field operations) has quantifier elimination (i.e. the projection of a constructible set is again constructible); this fact can be proven by the classical tool of resultants, and among other things can be used to give a proof of Hilbert’s nullstellensatz. (Note though that projection does not necessary preserve the property of being atomic; for instance, the projection of the atomic set is the non-atomic, but still quantifier-free definable, set .) In the converse direction, it is not difficult to use the nullstellensatz to deduce quantifier elimination. For theory of the real field , which is not algebraically closed, one does not have quantifier elimination, as one can see from the example of the unit circle (which is a quantifier-free definable set) projecting down to the interval (which is definable, but not quantifer-free definable). However, if one adds the additional operation of order to the reals, giving it the language of an ordered field rather than just a field, then quantifier elimination is recovered (the class of quantifier-free definable sets now enlarges to match the class of definable sets, which in this case is also the class of semi-algebraic sets); this is the famous Tarski-Seidenberg theorem.

On the other hand, many important structures do not have quantifier elimination; typically, the projection of a quantifier-free definable set is not, in general, quantifier-free definable. This failure of the projection property also shows up in many contexts outside of model theory; for instance, Lebesgue famously made the error of thinking that the projection of a Borel measurable set remained Borel measurable (it is merely an analytic set instead). Turing’s halting theorem can be viewed as an assertion that the projection of a decidable set (also known as a *computable* or *recursive* set) is not necessarily decidable (it is merely *semi-decidable* (or *recursively enumerable*) instead). The notorious P=NP problem can also be essentially viewed in this spirit; roughly speaking (and glossing over the placement of some quantifiers), it asks whether the projection of a polynomial-time decidable set is again polynomial-time decidable. And so forth. (See this blog post of Dick Lipton for further discussion of the subtleties of projections.)

Now we consider the status of quantifier elimination for the theory of a finite field . If interpreted naively, quantifier elimination is trivial for a finite field , since every subset of is finite and thus quantifier-free definable. However, we can recover an interesting question in one of two (essentially equivalent) ways. One is to work in the asymptotic regime in which the field is large, but the length of the formulae used to construct one’s definable sets stays bounded uniformly in the size of (where we view any constant in as contributing a unit amount to the length of a formula, no matter how large is). A simple counting argument then shows that only a small number of subsets of become definable in the asymptotic limit , since the number of definable sets clearly grows at most polynomially in for any fixed bound on the formula length, while the number of all subsets of grows exponentially in .

Another way to proceed is to work not with a single finite field , or even with a sequence of finite fields, but with the ultraproduct of a sequence of finite fields, and to study the properties of definable sets over 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 least if one does not care to track of the exact bounds on the length of the formulae involved. Indeed, thanks to Los’s theorem, a definable subset of is nothing more than the ultraproduct of definable subsets of for all sufficiently close to , with the length of the formulae used to define uniformly bounded in . In the language of nonstandard analysis, one can view as a nonstandard finite field.

The ultraproduct of finite fields is an important example of a *pseudo-finite field* – a field that obeys all the sentences in the languages of fields that finite fields do, but is not necessarily itself a finite field. The model theory of pseudo-finite fields was first studied systematically by Ax (in the same paper where the Ax-Grothendieck theorem, discussed previously on this blog, was established), with important further contributions by Kiefe, by Fried-Sacerdote, by two papers of Chatzidakis-van den Dries-Macintyre, and many other authors.

As mentioned before, quantifier elimination trivially holds for finite fields. But for infinite pseudo-finite fields, such as the ultraproduct of finite fields with going to infinity, quantifier elimination fails. For instance, in a finite field , the set of quadratic residues is a definable set, with a bounded formula length, and so in the ultraproduct , the set of nonstandard quadratic residues is also a definable set. However, in one dimension, we see from the factor theorem that the only atomic definable sets are either finite or the whole field , and so the only constructible sets (i.e. the only quantifier-free definable sets) are either finite or cofinite in . Since the quadratic residues have asymptotic density in a large finite field, they cannot form a quantifier-free definable set, despite being definable.

Nevertheless, there is a very nice *almost quantifier elimination* result for these fields, in characteristic zero at least, which we phrase here as follows:

Theorem 1 (Almost quantifier elimination)Let be a nonstandard finite field of characteristic zero, and let be a definable set over . Then is the union of finitely many sets of the formwhere is an atomic definable subset of (i.e. the -points of an algebraic variety defined over in ) and is a polynomial.

Results of this type were first obtained essentially due to Catarina Kiefe, although the formulation here is closer to that of Chatzidakis-van den Dries-Macintyre.

Informally, this theorem says that while we cannot quite eliminate *all* quantifiers from a definable set over a nonstandard finite field, we can eliminate all but one existential quantifier. Note that negation has also been eliminated in this theorem; for instance, the definable set uses a negation, but can also be described using a single existential quantifier as .) I believe that there are more complicated analogues of this result in positive characteristic, but I have not studied this case in detail (Kiefe’s result does not assume characteristic zero, but her conclusion is slightly different from the one given here). In the one-dimensional case , the only varieties are the affine line and finite sets, and we can simplify the above statement, namely that any definable subset of takes the form for some polynomial (i.e. definable sets in are nothing more than the projections of the -points of a plane curve).

There is an equivalent formulation of this theorem for standard finite fields, namely that if is a finite field and is definable using a formula of length at most , then can be expressed in the form (2) with the degree of bounded by some quantity depending on and , assuming that the characteristic of is sufficiently large depending on .

The theorem gives quite a satisfactory description of definable sets in either standard or nonstandard finite fields (at least if one does not care about effective bounds in some of the constants, and if one is willing to exclude the small characteristic case); for instance, in conjunction with the Lang-Weil bound discussed in this recent blog post, it shows that any non-empty definable subset of a nonstandard finite field has a nonstandard cardinality of for some positive standard rational and integer . Equivalently, any non-empty definable subset of for some standard finite field using a formula of length at most has a standard cardinality of for some positive rational of height and some natural number between and . (For instance, in the example of the quadratic residues given above, is equal to and equal to .) There is a more precise statement to this effect, namely that the Poincaré series of a definable set is rational; see Kiefe’s paper for details.

Below the fold I give a proof of Theorem 1, which relies primarily on the Lang-Weil bound mentioned above.

** — 1. Proof of theorem — **

Fix a nonstandard finite field of characteristic zero. Let us temporarily define a *basic set* to be a set (2) for some atomic definable set and some polynomial , and a *good set* to be a finite union of basic sets in some vector space . Our objective is thus to show that all definable sets are good.

Clearly, every atomic definable set is already a basic set, and is thus certainly good. Given the relationship between atomic definable sets and all definable sets, it thus suffices to show that the class of good sets are closed under boolean operations (e.g. union, intersection, negation) and projection. Closure under unions is automatic by definition; the interesting and difficult closure properties are projection and negation. (Closure under intersection is, strictly speaking, a consequence of closure under unions and negations, thanks to de Morgan’s laws; but it turns out to be convenient to obtain closure under intersection first as a stepping stone to closure under negation.)

We first observe that we may place good sets in a suitable “normal form”. Let be the algebraic closure of . This is an algebraically closed field that has a nonstandard Frobenius endomorphism , defined as the ultralimit of the Frobenius maps on each of the finite fields . This is a nonstandard automorphism of whose fixed points are precisely . An atomic definable set over is the same thing as the -points of an variety over which is invariant with resspect to the Frobenius automorphism (this can be established for instance by inspecting a reduced Grobner basis for the associated ideal). Such a variety can be decomposed over into absolutely irreducible components. Some of these components may remain Frobenius-invariant and will thus continue to be defined over . If a component is not Frobenius invariant, we may intersect it with all of its Frobenius conjugates without losing any of its -points; by the Noetherian property, this will reduce that component to an absolutely irreducible variety defined over . Thus, every variety defined over can be replaced with a union of finitely many absolutely irreducible varieties defined over , without losing or gaining any -points. From this, we see that any good set can be placed in a form in which all of the varieties involved are absolutely irreducible.

Now consider a basic set of the form

with absolutely irreducible. We consider the constant term of . If this term vanishes identically on , then this basic set is all of . Otherwise, observe that we may factorise

for some polynomial with , and then

From this, we see that any good set can be expressed as the union of the -points of a variety (i.e. an atomic definable set) and finitely many basic sets which have *unit constant term* in the sense that they have the form

with absolutely irreducible and .

This leads us to the following useful lemma:

Lemma 2 (Hypersurface removal)Let be a good set in , and let be a polynomial. Then is also good.

*Proof:* By replacing with its norm over the polynomials over , we may assume that takes coefficients in . By the preceding discussion, it suffices to establish this in the case when is either the -points an irreducible variety , or a basic set on such a variety with unit constant term. In the former case, we simply note that

In the latter case, we observe that

whenever has unit constant term.

This allows us to generalise to be constructible rather than algebraic:

Corollary 3Any set of the form , where is a quantifier-free definable set (i.e. the -points of a constructible set), and is a polynomial from to , is good.

*Proof:* Again, we may assume takes coefficients in . A constructible set can be expressed as the union of finitely many quasiprojective varieties (i.e. the set-theoretic difference of two affine varieties). A quasiprojective variety can be written as the finite union of sets of the form for various polynomials , and the claim then follows from the preceding lemma.

Now we can handle images of constructible sets with -dimensional fibres:

Proposition 4Let be constructible sets defined over with irreducible Zariski closures, and let be a regular map, also defined over , with the property that all fibres , are zero-dimensional. Then is good. (In particular, the set of -points of any constructible set is a good set.)

*Proof:* By restricting if necessary, we may assume that is dominant. The field of -valued rational functions on can then be viewed as a field extension of (using the pullback map by ); as the fibres are zero-dimensional, this extension has transcendence degree zero, i.e. it is algebraic. By the primitive element theorem (and it is here that we are using our hypothesis that has characteristic zero, to ensure that the field extension is separable), is generated by and a rational function on , which by clearing denominators one can assume to be integral with respect to the polynomial ring , thus

for some polynomial with coefficients in with monic as a polynomial over . Each of the coordinate functions on the affine variety can then be viewed (again after clearing denominators) as a polynomial (over ) in , divided by some non-trivial polynomial , thus

for all and all in , and some polynomials with coefficients in . From this, we see that for any with , has an -point if and only if has a root in . Thus we have

Using Corollary 3 and an induction hypothesis on the dimension of to deal with the residual term , we obtain the claim.

Next, we record an important property of infinite pseudofinite fields, known as the pseudo algebraically closed (PAC) axiom:

Lemma 5 (PAC axiom)Let be an absolutely irreducible variety defined over . Then is non-empty. Furthermore, for any Zariski-dense constructible subset of , is non-empty also.

*Proof:* We write as an ultralimit of varieties defined over . As is absolutely irreducible, we have absolutely irreducible with dimension for close to (see Lemma 3 and Lemma 8 of this previous blog post), and so by the Lang-Weil bound (see this previous blog post) we have

Since goes to infinity as , we conclude that is non-empty for sufficiently close to , and so is non-empty also by Los’s theorem. The same argument works for , using the Schwarz-Zippel bound from the previous post to handle the set removed from to form .

We can now establish closure with respect to projection:

*Proof:* It suffices to establish that

is a good set whenever is a constructible subset of . Let be the projection map from to , so our task is to show that is good. By decomposing , we may assume that has irreducible closure, and that all the fibres of in have the same dimension, which is either , , or . If the fibres have dimension , then by the PAC axiom , and the claim follows from Corollary 3. If the fibres have dimension , the claim follows instead from Proposition 4. So the only remaining case is when the fibres are one-dimensional curves.

We can work generically in , since the contribution of any subvariety of of strictly smaller dimension can be handled by an induction hypothesis. Generically, the fibre over a point is then given by a curve for some polynomial defined over . If is an -point of , then by the PAC axiom, this curve contains an -point in the plane if and only if , viewed as a polynomial of two variables, contains an absolutely irreducible factor defined over . If one fixes the degree of this factor, this is a definable constraint on coefficients, and by Proposition 4, the set of for which this constraint is obeyed is a good set. Letting vary from to and taking unions, we obtain the claim.

From closure under projection, we can deduce closure under intersection:

Corollary 7The intersection of two good sets in is again a good sets in .

*Proof:* It suffices to show that the intersection of two basic sets

and

in is good. But observe that can be obtained from the atomic definable (and hence basic) set by applying two projections, so the claim follows from two applications of Corollary 6.

The only remaining task is to show closure under negation. To get a hint of how to proceed on this, consider again the example of the quadratic residues in :

One can almost describe the complement of this set by selecting a non-quadratic residue of and using the set

though this is not quite the complement of and one has to delete the origin, for instance by using Lemma 2. Applying the algorithm implicit in the proof of that lemma, one ends up with

as an explicit representation of the non-quadratic residues as a basic set.

The selection of an arbitrary non-quadratic residue may seem like a rather *ad hoc* step to take in the above example, which does not initially bode well for generalisation to other definable sets. However, one can make the argument a bit more “canonical” by a bit of Galois theory. Note that while an arbitrary element of need not necessarily have a square root in , it always has a square root in the (unique) quadratic extension of . Of course, will also be a square root. Letting be the Galois conjugation of over , we have

and so is equal to either or . In the former case, is a quadratic residue; otherwise, it is a non-quadratic residue. (Let us ignore the situation when , as Lemma 2 and Corollary 7 give us enough tools to deal with what is going on exceptional sets of lower-dimensional varieties.) Thus, outside of the point , we can express as the set of for which one has for the two square roots , and the complement as the set of for which (extending from to in some arbitrary manner if desired). The descriptions of and its (near-)complement in (3), (4) can be viewed as (shadows of) “norms” of the above assertions , in some sense. This suggests that more generally, given a basic set on a variety , one can use Galois theory to naturally partition (outside of some exceptional set of smaller dimension) into disjoint components, one of which is , and all of which can be described as unions of basic sets, which would lead to the desired closure property with respect to negation. (Not coincidentally, a very similar trick was used in Bombieri’s version of Stepanov’s proof of the Hasse-Weil bound discussed in this previous post, in which an upper bound on for curves was converted into a matching lower bound.)

Proposition 8The complement of a good set in is again a good set.

*Proof:* In view of Corollary 7 and de Morgan’s laws, it suffices to show that the complement of a basic set in is a good set, whenever is absolutely irreducible and defined over . From Proposition 4, we already know that is a good set, so it suffices to show that the set

is good. By an induction on the dimension of , we may freely delete any lower-dimensional component of , thus it will suffice to show that

is good for some generic subset of .

By an induction on the degree of , and Corollary 7, we may assume that is absolutely irreducible on . In particular, and have no common factor (here we are again implicitly using the characteristic zero hypothesis), and so for generic , and have no common zero (otherwise their resultant would vanish generically, leading to a common factor). If we write

for some polynomials on with generically non-zero on , we thus see that for generic , has distinct zeroes in . Indeed, recalling that any finite field has a unique extension of degree , has a unique extension of degree , and all the zeroes of lie in this extension.

It is a standard fact from Galois theory that is a Galois extension of , with the Galois group isomorphic to and generated by the Frobenius endomorphism ; taking ultralimits, we see that is also a Galois extension of , with Galois group again isomorphic to and generated by the ultralimit of the standard Frobenius endomorphisms . For any generic , the distinct zeroes of are acted upon by the Frobenius map. Thus, there exists a permutation such that for all .

Observe that for generic the statement holds precisely when has no fixed points. Thus, it suffices to show that for each permutation , the set of generic for which one can enumerate the zeroes of as with the property that for all , is a good set. But by viewing as a -dimensional linear vector space over and expanding in terms of some arbitrarily chosen basis (cf. the factor in the quadratic residue discussion), and noting that the Frobenius map is a linear transformation of this vector space, we see that this set is of the form covered by Proposition 4, and the claim follows. (One could also avoid the use of an arbitrarily chosen basis here by working with a more abstract version of Proposition 4, if desired.)

Remark 1A closer inspection of the above arguments show that there were really only two properties of the nonstandard finite field that were really used (besides the fact that was a characteristic zero field). The first was the PAC axiom (Lemma 5). The second was the properties of the Galois group , namely that this group is isomorphic to the profinite integers (or equivalently, that has precisely one field extension of each degree). It turns out that these properties in fact completely characterise infinite pseudo-finite fields, which is the main result of the paper of Ax cited previously.

## 12 comments

Comments feed for this article

12 September, 2012 at 5:06 pm

Fred Lunnon“andrelations” -> “and relations”

“carindality” -> “cardinality”

[Corrected, thanks - T.]13 September, 2012 at 9:31 am

tomsimThe first occurence of “metoynm” looks funny, even to this mathematical layman.

[Corrected, thanks. -T.]13 September, 2012 at 9:48 am

rlssR^2 should be R in definition of [1,-1].

[Corrected, thanks - T.]13 September, 2012 at 5:17 pm

Neat Post Related to Formal Systems « Let Us Figure This Out[...] Definable subsets over (nonstandard) finite fields, and almost quantifier elimination Share this:FacebookStumbleUponRedditLike this:LikeBe the first to like this. This entry was posted in Uncategorized. [...]

15 September, 2012 at 11:02 pm

Uri AndrewsQuick note: A quantifier-free definable set is not also known as a 0-definable set. 0-definable simply means definable without parameters.

[Corrected, thanks -T.]16 September, 2012 at 3:18 pm

William Newmananother trivial typo: ‘cosntructible’

[Corrected, thanks - T.]20 September, 2012 at 5:27 am

Emmanuel KowalskiYou mention “Cherlin-van den Dries-Macintyre”, but the paper you link to is the one by Chatzidakis, van den Dries and Macintyre…

[Corrected, thanks - T.]3 October, 2012 at 4:57 am

Anonymouswhat you mean by( the length of the formula is uniformaly bounded in m)…

Which definition of uniformaly bounded did you use here?

3 October, 2012 at 7:54 am

Terence Tao“uniformly bounded in m” means “bounded by some quantity C that does not depend on m”.

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[...] out that one can essentially write all definable sets as an intersection of sets of this form; see this previous blog post for more discussion.) To regularise the set , it is convenient to square the adjacency matrix, [...]

30 December, 2012 at 8:44 pm

hgutahwIn “a good set to be a finite union of good sets in some vector space”, the second occurrence of “good” should be replaced by “basic”.

[corrected, thanks - T.]29 October, 2013 at 8:09 pm

A spectral theory proof of the algebraic regularity lemma | What's new[…] be obtained by combining the description of definable sets over pseudofinite fields (discussed in this previous post) with the Lang-Weil bound (discussed in this previous post). (The former fact is phrased using […]