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 1 In the theory of a field such as , an atomic definable set is the same thing as an affine algebraic set (also known as an affine algebraic variety, with the understanding that varieties are not necessarily assumed to be irreducible), and a quantifier-free definable set is known as a constructible 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:
where is an atomic definable subset of (i.e. the -points of an algebraic variety defined over in ) and is a polynomial.
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:
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:
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 4 Let 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:
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:
Proof: It suffices to show that the intersection of two basic sets
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.
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 8 The 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 1 A 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.