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 {{\mathcal L}} (which, in this post, will always be a single-sorted, first-order language). A structure is a set {X}, 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 {X} as a metonym for the entire structure, much as we usually refer to a group {(G,1,\cdot,()^{-1})} simply as {G}, a vector space {(V, 0, +, \cdot)} simply as {V}, 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 {a+b+c} instead of {(a+b)+c} or {a+(b+c)}, 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 {{\bf R}} or {{\bf C}}, 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 {X}, one can introduce the notion of a definable subset of {X}, or more generally of a Cartesian power {X^n} of {X}, defined as a set {E \subset X^n} of the form

\displaystyle E = \{ (x_1,\ldots,x_n): P(x_1,\ldots,x_n) \hbox{ true} \} \ \ \ \ \ (1)

for some formula {P} in the language {{\mathcal L}} with {n} free variables and any number of constants from {X} (that is, {P(x_1,\ldots,x_n)} is a well-formed formula built up from a finite number of constants {c_1,\ldots,c_m} in {X}, the relations and operations on {X}, logical connectives such as {\neg}, {\wedge}, {\implies}, and the quantifiers {\forall, \exists}). Thus, for instance, in the theory of the arithmetic of the natural numbers {{\bf N} = ({\bf N}, 0, 1, +, \times)}, the set of primes {{\mathcal P}} is a definable set, since we have

\displaystyle {\mathcal P} = \{ x \in {\bf N}: (\exists y: x=y+2) \wedge \neg (\exists z,w: x = (z+2)(w+2)) \}.

In the theory of the field of reals {{\bf R} = ({\bf R}, 0, 1, +, -, \times, ()^{-1})}, the unit circle {S^1} is an example of a definable set,

\displaystyle S^1 = \{ (x,y) \in {\bf R}^2: x^2+y^2 = 1 \},

but so is the the complement of the circle,

\displaystyle {\bf R}^2 \backslash S^1 = \{ (x,y) \in {\bf R}^2: \neg(x^2+y^2 = 1) \}

and the interval {[-1,1]}:

\displaystyle [-1,1] = \{ x \in {\bf R}: \exists y: x^2+y^2 = 1\}.

Due to the unlimited use of constants, any finite subset of a power {X^n} of any structure {X} is, by our conventions, definable in that structure. (One can of course also consider definability without parameters (also known as {0}-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 {P()} 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 {P()} is quantifier-free (i.e. it can contain logical connectives, but does not contain the quantifiers {\forall, \exists}).

Example 1 In the theory of a field such as {{\bf R}}, 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 {{\bf R}}, the interval {[-1,1]} is a definable set, but not a quantifier-free definable set (and certainly not an atomic definable set); and similarly for the primes over {{\bf N}}.

A quantifier-free definable set in {X^n} is nothing more than a finite boolean combination of atomic definable sets; in other words, the class of quantifier-free definable sets over {X} 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 {X} is the smallest class that contains the quantifier-free definable sets, and is also closed under the operation of projection {\pi_n: E \mapsto \pi_n(E)} from {X^{n+1}} to {X^n} for every natural number {n}, where {\pi_n: X^{n+1} \rightarrow X^n} is the map {\pi_n(x_1,\ldots,x_n,x_{n+1}) := (x_1,\ldots,x_n)}.

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 {k} (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 {\{ (x,y) \in k^2: xy=1 \}} is the non-atomic, but still quantifier-free definable, set {\{ x \in k: \neg (k=0) \}}.) In the converse direction, it is not difficult to use the nullstellensatz to deduce quantifier elimination. For theory of the real field {{\bf R}}, 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 {[-1,1]} (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 {F}. If interpreted naively, quantifier elimination is trivial for a finite field {F}, since every subset of {F^n} 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 {F} is large, but the length of the formulae used to construct one’s definable sets stays bounded uniformly in the size of {F} (where we view any constant in {F} as contributing a unit amount to the length of a formula, no matter how large {F} is). A simple counting argument then shows that only a small number of subsets of {F^n} become definable in the asymptotic limit {|F| \rightarrow \infty}, since the number of definable sets clearly grows at most polynomially in {|F|} for any fixed bound on the formula length, while the number of all subsets of {|F|^n} grows exponentially in {n}.

Another way to proceed is to work not with a single finite field {F}, or even with a sequence {F_m} of finite fields, but with the ultraproduct {F = \prod_{m \rightarrow p} F_m} 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 {E} of {F^n} is nothing more than the ultraproduct {E = \prod_{m \rightarrow p} E_m} of definable subsets {E_m} of {F_m^n} for all {m} sufficiently close to {p}, with the length of the formulae used to define {E_m} uniformly bounded in {m}. In the language of nonstandard analysis, one can view {F} as a nonstandard finite field.

The ultraproduct {F} 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 {F = \prod_{m \rightarrow p} F_m} of finite fields with {|F_m|} going to infinity, quantifier elimination fails. For instance, in a finite field {F_m}, the set {E_m := \{ x \in F_m: \exists y \in F_m: x=y^2 \}} of quadratic residues is a definable set, with a bounded formula length, and so in the ultraproduct {F =\prod_{m \rightarrow p} F_m}, the set {E := \prod_{m\rightarrow p} E_m} 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 {F}, and so the only constructible sets (i.e. the only quantifier-free definable sets) are either finite or cofinite in {F}. Since the quadratic residues have asymptotic density {1/2} 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 {F} be a nonstandard finite field of characteristic zero, and let {E \subset F^n} be a definable set over {F}. Then {E} is the union of finitely many sets of the form

\displaystyle E = \{ x \in V(F): \exists t \in F: P(x,t) = 0 \} \ \ \ \ \ (2)

where {V(F)} is an atomic definable subset of {F^n} (i.e. the {F}-points of an algebraic variety {V} defined over {F} in {F^n}) and {P: F^{n+1} \rightarrow F} 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 {F \backslash \{0\} = \{ x \in F: \neg(x=0) \}} uses a negation, but can also be described using a single existential quantifier as {\{ x \in F: \exists t: xt = 1 \}}.) 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 {n=1}, the only varieties {V} are the affine line and finite sets, and we can simplify the above statement, namely that any definable subset of {F} takes the form {\{ x\in F: \exists t \in F: P(x,t) = 0 \}} for some polynomial {P} (i.e. definable sets in {F} are nothing more than the projections of the {F}-points of a plane curve).

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

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 {(\alpha + O(|F|^{-1/2})) |F|^d} for some positive standard rational {\alpha} and integer {d}. Equivalently, any non-empty definable subset of {F^n} for some standard finite field {F} using a formula of length at most {M} has a standard cardinality of {(\alpha + O_{M,n}(|F|^{-1/2})) |F|^d} for some positive rational of height {O_{M,n}(1)} and some natural number {d} between {0} and {n}. (For instance, in the example of the quadratic residues given above, {d} is equal to {1} and {\alpha} equal to {1/2}.) 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 {F = \prod_{m \rightarrow p} F_m} of characteristic zero. Let us temporarily define a basic set to be a set (2) for some atomic definable set {V} and some polynomial {P}, and a good set to be a finite union of basic sets in some vector space {F^n}. 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 {\overline{F}} be the algebraic closure of {F}. This is an algebraically closed field that has a nonstandard Frobenius endomorphism {Frob: \overline{F} \rightarrow \overline{F}}, defined as the ultralimit of the Frobenius maps {x \mapsto x^{|F_m|}} on each of the finite fields {F_m}. This is a nonstandard automorphism of {\overline{F}} whose fixed points are precisely {F}. An atomic definable set over {F} is the same thing as the {F}-points {V(F)} of an variety {V} over {\overline{F}} 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 {\overline{F}} into absolutely irreducible components. Some of these components may remain Frobenius-invariant and will thus continue to be defined over {F}. If a component is not Frobenius invariant, we may intersect it with all of its Frobenius conjugates without losing any of its {F}-points; by the Noetherian property, this will reduce that component to an absolutely irreducible variety defined over {F}. Thus, every variety defined over {F} can be replaced with a union of finitely many absolutely irreducible varieties defined over {F}, without losing or gaining any {F}-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

\displaystyle \{ x \in V(F): \exists t \in F: P(x,t) = 0 \}

with {V} absolutely irreducible. We consider the constant term {P_0(x) := P(x,0)} of {P}. If this term vanishes identically on {V}, then this basic set is all of {V(F)}. Otherwise, observe that we may factorise

\displaystyle P(x,P_0(x)t) = P_0(x) Q(x,t)

for some polynomial {Q(x,t)} with {Q(x,0) \equiv 1}, and then

\displaystyle \{ x \in V(F): \exists t \in F: P(x,t) = 0 \} = \{ x \in V(F): P_0(x) = 0 \} \cup \{ x \in V(F): \exists t \in F: Q(x,t) = 0 \}.

From this, we see that any good set can be expressed as the union of the {F}-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

\displaystyle \{ x \in V(F): \exists t \in F: P(x,t) = 0 \}

with {V} absolutely irreducible and {P(x,0) \equiv 1}.

This leads us to the following useful lemma:

Lemma 2 (Hypersurface removal) Let {E} be a good set in {F^n}, and let {Q: \overline{F}^n \rightarrow \overline{F}} be a polynomial. Then {\{ x \in E: Q(x) \neq 0 \}} is also good.

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

\displaystyle \{ x \in V(F): Q(x) \neq 0 \} = \{ x \in V(F): \exists t: Q(x) t - 1 = 0 \}.

In the latter case, we observe that

\displaystyle \{ x \in V(F): (\exists t \in F: P(x,t)=0) \wedge Q(x) \neq 0 \} = \{ x \in V(F): \exists t: P(x,Q(x) t)=0 \}

whenever {P} has unit constant term. \Box

This allows us to generalise {V} to be constructible rather than algebraic:

Corollary 3 Any set of the form {\{ x \in V(F): \exists t \in F: P(x,t)=0\}}, where {V(F)} is a quantifier-free definable set (i.e. the {F}-points of a constructible set), and {P} is a polynomial from {\overline{F}^{n+1}} to {\overline{F}}, is good.

Proof: Again, we may assume {P} takes coefficients in {F}. 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 {V \backslash W} can be written as the finite union of sets of the form {\{ x \in V: Q(x) \neq 0\}} for various polynomials {Q}, and the claim then follows from the preceding lemma. \Box

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

Proposition 4 Let {V, W} be constructible sets defined over {F} with irreducible Zariski closures, and let {\phi: V \rightarrow W} be a regular map, also defined over {F}, with the property that all fibres {\phi^{-1}(\{w\})}, {w \in W} are zero-dimensional. Then {\phi(V(F)) = \{ \phi(v): v \in V(F) \}} is good. (In particular, the set of {F}-points of any constructible set is a good set.)

Proof: By restricting {V} if necessary, we may assume that {\phi} is dominant. The field {F(V)} of {F}-valued rational functions on {V} can then be viewed as a field extension of {F(W)} (using the pullback map by {\phi}); 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 {F} has characteristic zero, to ensure that the field extension is separable), {F(V)} is generated by {F(W)} and a rational function {f} on {V}, which by clearing denominators one can assume to be integral with respect to the polynomial ring {F[W]}, thus

\displaystyle R( f(x), \phi(x) ) = 0

for some polynomial {R} with coefficients in {F} with {R} monic as a polynomial over {F[W]}. Each of the coordinate functions {x_1,\ldots,x_n} on the affine variety {V} can then be viewed (again after clearing denominators) as a polynomial (over {F[W]}) in {f}, divided by some non-trivial polynomial {Q \in F[W]}, thus

\displaystyle x_i = P_i( f(x), \phi(x) ) / Q(\phi(x)).

for all {i=1,\ldots,n} and all {x = (x_1,\ldots,x_n)} in {V}, and some polynomials {P_i} with coefficients in {F}. From this, we see that for any {w \in W(F)} with {Q(w) \neq 0}, {\phi^{-1}( \{w\})} has an {F}-point if and only if {R(\cdot,w)} has a root in {F}. Thus we have

\displaystyle \phi(V(F)) = \{ w \in W(F): Q(w) \neq 0; \exists t: R(t,w) = 0 \} \cup (\phi(V(F)) \cap \{ Q = 0 \}).

Using Corollary 3 and an induction hypothesis on the dimension of {W} to deal with the residual term {\phi(V(F)) \cap \{ Q = 0 \}}, we obtain the claim. \Box

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

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

Proof: We write {V} as an ultralimit of varieties {V_m} defined over {F_m}. As {V} is absolutely irreducible, we have {V_m} absolutely irreducible with dimension {\hbox{dim}(V)} for {m} close to {p} (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

\displaystyle |V_m(F_m)| = (1 + O(|F_m|^{-1/2})) |F_m|^{\hbox{dim}(V)}.

Since {|F_m|} goes to infinity as {m \rightarrow p}, we conclude that {V_m(F_m)} is non-empty for {m} sufficiently close to {p}, and so {V(F)} is non-empty also by Los’s theorem. The same argument works for {W(F)}, using the Schwarz-Zippel bound from the previous post to handle the set removed from {V} to form {W}. \Box

We can now establish closure with respect to projection:

Corollary 6 If {E \subset F^{n+1}} is good, then {\pi_n(E) \subset F^n} is also good.

Proof: It suffices to establish that

\displaystyle \{ x \in F^n: \exists s,t \in F: (x,s,t) \in V(F) \}

is a good set whenever {V(F)} is a constructible subset of {F^{n+2}}. Let {\pi} be the projection map from {V} to {\overline{F}^n}, so our task is to show that {\pi(V(F))} is good. By decomposing {V}, we may assume that {V} has irreducible closure, and that all the fibres of {\pi} in {\pi(V)} have the same dimension, which is either {0}, {1}, or {2}. If the fibres have dimension {2}, then by the PAC axiom {\pi(V(F)) = \pi(V)(F)}, and the claim follows from Corollary 3. If the fibres have dimension {0}, 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 {V}, since the contribution of any subvariety of {V} of strictly smaller dimension can be handled by an induction hypothesis. Generically, the fibre over a point {x \in V} is then given by a curve {\{ (s,t): P(x,s,t) = 0 \}} for some polynomial {P} defined over {F}. If {x} is an {F}-point of {V}, then by the PAC axiom, this curve contains an {F}-point in the plane {F^2} if and only if {P(x,\cdot,\cdot)}, viewed as a polynomial of two variables, contains an absolutely irreducible factor defined over {F}. If one fixes the degree {d} of this factor, this is a definable constraint on {d+1} coefficients, and by Proposition 4, the set of {x \in V(F)} for which this constraint is obeyed is a good set. Letting {d} vary from {1} to {\hbox{deg}(P)} and taking unions, we obtain the claim. \Box

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

Corollary 7 The intersection of two good sets in {F^n} is again a good sets in {F^n}.

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

\displaystyle E = \{ x \in V(F): \exists t: P(x,t) = 0 \}

and

\displaystyle E' = \{ x \in V'(F): \exists t': P'(x,t') = 0 \}

in {F^n} is good. But observe that {E \cap E'} can be obtained from the atomic definable (and hence basic) set {\{ (x,t,t') \in F^{n+2}: x \in V \cap V'; P(x,t)=P'(x,t')=0 \}} by applying two projections, so the claim follows from two applications of Corollary 6. \Box

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 {F}:

\displaystyle E := \{ x \in F: \exists t \in F: x = t^2 \}. \ \ \ \ \ (3)

One can almost describe the complement of this set by selecting a non-quadratic residue {\epsilon} of {F} and using the set

\displaystyle \{ x \in F: \exists t \in F: x = \epsilon t^2 \}, \ \ \ \ \ (4)

though this is not quite the complement of {E} 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

\displaystyle F \backslash E = \{ x \in F: \exists t \in F: 1 = \epsilon x t^2 \}

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

The selection of an arbitrary non-quadratic residue {\epsilon} 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 {x} of {F} need not necessarily have a square root {t} in {F}, it always has a square root {t} in the (unique) quadratic extension {F_{(2)}} of {F}. Of course, {-t} will also be a square root. Letting {\sigma} be the Galois conjugation of {F_{(2)}} over {F}, we have

\displaystyle \sigma(t)^2 = \sigma(t^2) = \sigma(x) = x = t^2

and so {\sigma(t)} is equal to either {t} or {-t}. In the former case, {x} is a quadratic residue; otherwise, it is a non-quadratic residue. (Let us ignore the situation when {x=0}, 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 {\{0\}}, we can express {E} as the set of {x} for which one has {\sigma(t)=t} for the two square roots {\{t \in \overline{F}: x=t^2\}}, and the complement as the set of {x} for which {\sigma(t)=-t} (extending {\sigma} from {F_{(2)}} to {\overline{F}} in some arbitrary manner if desired). The descriptions of {E} and its (near-)complement in (3), (4) can be viewed as (shadows of) “norms” of the above assertions {\sigma(t)=t}, {\sigma(t)=-t} in some sense. This suggests that more generally, given a basic set {E} on a variety {V}, one can use Galois theory to naturally partition {V(F)} (outside of some exceptional set of smaller dimension) into disjoint components, one of which is {E}, 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 {V(F)} for curves {V} was converted into a matching lower bound.)

Proposition 8 The complement of a good set in {F^n} 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 {\{ x \in V(F): \exists t \in F: P(x,t) = 0 \}} in {F^n} is a good set, whenever {V} is absolutely irreducible and defined over {F}. From Proposition 4, we already know that {F^n \backslash V(F)} is a good set, so it suffices to show that the set

\displaystyle \{ x \in V(F): \not \exists t \in F: P(x,t) = 0 \}

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

\displaystyle \{ x \in V'(F): \not \exists t \in F: P(x,t) = 0 \}

is good for some generic subset {V'} of {V}.

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

\displaystyle P(x,t) = P_d(x) t^d + \ldots + P_0(x)

for some polynomials {P_0,\ldots,P_d} on {V} with {P_d} generically non-zero on {V}, we thus see that for generic {x \in V(F)}, {P(x,\cdot)} has {d} distinct zeroes in {\overline{F}}. Indeed, recalling that any finite field {F_m} has a unique extension {F_{m,(d)}} of degree {d}, {F} has a unique extension {F_{(d)}} of degree {d}, and all the {d} zeroes of {P(x,\cdot)} lie in this extension.

It is a standard fact from Galois theory that {F_{m,(d)}} is a Galois extension of {F_m}, with the Galois group isomorphic to {{\bf Z}/d{\bf Z}} and generated by the Frobenius endomorphism {Frob_{F_m}: x \mapsto x^{|F_m|}}; taking ultralimits, we see that {F_{(d)}} is also a Galois extension of {F}, with Galois group again isomorphic to {{\bf Z}/d{\bf Z}} and generated by the ultralimit {Frob_F} of the standard Frobenius endomorphisms {Frob_{F_m}}. For any generic {x \in V(F)}, the {d} distinct zeroes {t_1,\ldots,t_d} of {P(x,\cdot)} are acted upon by the Frobenius map. Thus, there exists a permutation {\sigma:\{1,\ldots,d\} \rightarrow \{1,\ldots,d\}} such that {Frob_F(t_i) = t_{\sigma(i)}} for all {i=1,\ldots,d}.

Observe that for generic {x \in V(F)} the statement {\exists t \in F: P(x,t) = 0} holds precisely when {\sigma} has no fixed points. Thus, it suffices to show that for each permutation {\sigma}, the set of generic {x \in V(F)} for which one can enumerate the zeroes of {P(x,\cdot)} as {t_1,\ldots,t_d} with the property that {Frob_F(t_i) = t_{\sigma(i)}} for all {i=1,\ldots,d}, is a good set. But by viewing {F_{(d)}} as a {d}-dimensional linear vector space over {F} and expanding in terms of some arbitrarily chosen basis (cf. the factor {\epsilon} 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.) \Box

Remark 1 A closer inspection of the above arguments show that there were really only two properties of the nonstandard finite field {F} that were really used (besides the fact that {F} was a characteristic zero field). The first was the PAC axiom (Lemma 5). The second was the properties of the Galois group {Gal(\overline{F}/F)}, namely that this group is isomorphic to the profinite integers {\hat {\bf Z}} (or equivalently, that {F} 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.