Notes on the model theory of finite and pseudo-finite fields Zoé Chatzidakis, CNRS - Université Paris 7.

These notes contain the material covered during a mini-course I taught at the Universidad Autónoma de Madrid, 15 - 25 November 2005. The course was funded by the Marie Curie RTN MODNET and by the Universidad Autónoma, and I thank them for their financial support and hospitality. I also thank the audience for their enthusiasm and comments, and Margarita Otero who made this course possible.

1. Preliminary results in model theory In this section we recall some basic model theoretic notions and results which we will

assume throughout the course. We let L be a first-order language, T an L-theory, A, B, C, … L-structures.

(1.1) Morphisms. Let A and B be L-structures, F : A → B a map.

(1) F is a homomorphism (of L-structures) if for all n, n-ary relation R, n-ary function f and n-tuple a in A.

A ⊧ R(a) ⇒ B ⊧ R(F (a)) and f(F (a)) = F (f(a)).

(2) F is an embedding iff F is an injective homomorphism and for every n, n-ary relation R and n-tuple a in A, we have

A ⊧ R(a) ⟺ B ⊧ R(F (a)).

(3) F is an isomorphism iff F is an embedding and is surjective.

(4) F is an elementary embedding iff F (A) ≺ B. Equivalently, if for every formula φ(x)

and tuple a in A,

A ⊧ φ(a) ⟺ B ⊧ φ(F (a)).

(5) A partial isomorphism g : A → B is an embedding g of some substructure A_{0} of A into B.

(1.2) A test for being an elementary substructure. Let A ⊆ B be L-structures. Then A ≺ B if and only if for every formula φ(x, y) and tuple a in A,

B ⊧ ∃y φ(a, y)

if and only if there is some tuple b in A such that

B ⊧ φ(a, b).

(1.3) Some consequences. The following results are easy:

(1) If A ≺ B and B ≺ C then A ≺ C.

(2) If A ≺ C, B ≺ C and A ⊆ B, then A ≺ B.

(3) Let (A_{i})_{i∈ℕ} be an increasing chain with A_{i} ≺ A_{i+1} for every i, and let A_{ω} = ⋃_{i∈ℕ} A_{i}. Then A_{i} ≺ A_{ω} for every i.

(1.4) Some preservation results. We start with a compactness result. Proposition. Let T_{1} and T_{2} be theories, with T_{1} ∪ T_{2} consistent, and let Δ be a set of sentences closed under finite disjunctions. The following conditions are equivalent¿

(1) There is Γ ⊆ Δ such that T_{1} ∪ Γ axiomatizes T_{1} ∪ T_{2}.

(2) For all models A and B of T_{1}, if A ⊧ T_{2} and B satisfies all sentences of Δ satisfied by A, then B ⊧ T_{2}.

Proof. (1) implies (2) is clear. Assume that (2) holds, and let Γ = {ψ ∈ Δ | T_{1} ∪ T_{2} ⊢ ψ}. We need to show that T_{1} ∪ Γ ⊢ T_{2}, i.e., that every model of T_{1} ∪ Γ is a model of T_{2}. Let B ⊧ T_{1} ∪ Γ, and let

Σ = {¬ψ | ψ ∈ Δ, B ⊧ ¬ψ}.

We will show that T_{1} ∪ T_{2} ∪ Σ is consistent. Otherwise, using compactness, there are ¬ψ_{1}, …, ¬ψ_{m} ∈ Σ, φ ∈ T_{2} such that T_{1} ∪ {¬ψ_{1}, …, ¬ψ_{m}, φ} is inconsistent, i.e.,

T_{1} ∪ {φ} ⊢ ψ_{1} ∨ ⋯ ∨ ψ_{m}.

Since Δ is closed under disjunction, the sentence ψ_{1} ∨⋯∨ψ_{m} is in Γ, and therefore cannot be in Σ. This gives us the desired contradiction, and shows that T_{1} ∪ T_{2} ∪ Σ is consistent.

Let A be a model of T_{1} ∪ T_{2} ∪ Σ. If ψ ∈ Δ holds in A, then ¬ψ ∉ Σ, and therefore B ⊧ ψ. By condition (2), we obtain that B ⊧ T_{2}. Corollary. Let T be a theory, φ(x) a formula such that T ∪{∃xφ(x)} is consistent. Let Δ be a set of formulas in the variables x, closed under disjunctions. The following conditions are equivalent:

(1) There are formulas ψ_{1}(x), …, ψ_{m}(x) ∈ Δ such that

T ⊢ ∀x [φ(x) ↔ (ψ(x) ∧ ⋯ ψ_{m}(x))].

(2) Whenever A and B are models of T, and a, b are tuples in A, B respectively, if A ⊧ φ(a) and every formula ψ(x) ∈ Δ which is satisfied by a in A is also satisfied by b in B, then B ⊧ φ(b).

Proof. Assume x is of length n, and enlarge the language by adding an n-tuple c of (new) constants. We apply the theorem to the sentence φ(c) and obtain formulas ψ_{1}(x), …, ψ_{m}(x) ∈ Δ such that T ∪ {ψ_{1}(c), … ψ_{m}(c)} axiomatizes T ∪ {φ(c)}, in other words

T ⊢ φ(c) ↔ (ψ_{1}(c) ∧ ⋯ ∧ ψ_{m}(c)).

Since the symbols in c do not appear in T, we then obtain

T ⊢ ∀x [φ(x) ↔ (ψ(x) ∧ ⋯ ψ_{m}(x))].

(1.5) The above results can be used to show the following preservation theorem. For more details, see e.g. Chang and Keisler. We let T be a theory, φ(x) a formula.

(1) The following conditions are equivalent:

(a) For all models A and B of T, homomorphism F : A → B and tuple a in A, if A ⊧ φ(a) then B ⊧ φ(F (a)).

(b) There is a positive formula ψ(x) (that is, ψ is built from atomic formulas using ∧, ∨, ∃, ∀, but not using ¬) such that T ⊢ ∀x φ(x) ↔ ψ(x).

(2) The following conditions are equivalent:

(a) For all models A ⊆ B of T and tuple a in A, if A ⊧ φ(a) then B ⊧ φ(b).

(b) There is an existential formula ψ(x) such that T ⊢ ∀x φ(x) ↔ ψ(x).

(3) The following conditions are equivalent:

(a) For all models A ⊆ B of T and tuple a in A, if B ⊧ φ(a) then A ⊧ φ(a).

(b) There is a universal formula ψ(x) such that T ⊢ ∀x φ(x) ↔ ψ(x).

(4) The following conditions are equivalent:

(a) For every increasing chain (A_{i})_{i∈ℕ} of models of T and tuple a in A_{0}, if A_{i} ⊧ φ(a) for every i, then ⋃_{i∈ℕ} A_{i} ⊧ φ(a).

(b) There is a ∀∃-formula ψ(x) such that T ⊢ ∀x φ(x) ↔ ψ(x).

(1.6) Model complete theories, elimination of quantifiers.

Recall that a theory T is model complete iff whenever A and B are models of T and A ⊆ B, then A ≺ B.

The theory T eliminates quantifiers iff for every formula φ(x) there is a quantifier-free formula ψ(x) such that T ⊢ ∀x φ(x) ↔ ψ(x). Remarks. Recall that if A is a subset of an L-structure M, the language L(A) is obtained by adding to L new constant symbols, one for each element of A. We denote by Δ(A) (or Δ_{M}(A)) the quantifier-free diagram of A, i.e., the set of quantifier-free sentences of L(A) which hold in M. Using compactness, one easily obtains

(1) T is model complete if and only if for every model A of T, the theory T ∪ Δ(A) is complete (in L(A)).

(2) T eliminates quantifiers if and only if for every subset A of a model M of T, the theory T ∪ Δ_{M}(A) is complete (in L(A)).

(3) If T is model complete, then it has an axiomatization by ∀∃-sentences. Proof. (1) B is a model of T ∪ Δ(A) if and only if B contains an isomorphic copy of A. If T ∪ Δ(A) is complete and B ⊇ A, then (B, a)_{a∈A} ≡ (A, a)_{a∈A}, i.e., A ≺ B.

(2) The left-to-right implication is easy, and the right-to-left implication follows from Proposition (1.4).

(3) The union of an increasing chain of models of T is a model of T by (1.3). Apply (1.5).

(1.7) Proposition. Let T be a theory.

(1) To show that T is model complete, it is enough to show that whenever A ⊆ B are models of T and φ(x, y) is a quantifier-free formula, a is a tuple of elements of A, then

B ⊧ ∃y φ(a, y) ⟺ A ⊧ ∃y φ(a, y).

(One then says that A is existentially closed in B, also denoted by A ≺_{1} B.)

(2) T is model complete if and only if every formula φ(x) is equivalent modulo T to an existential formula ψ(x) (i.e., T ⊢ ∀x(φ(x) ↔ ψ(x))), if and only if every formula is equivalent modulo T to a universal formula.

(3) To show that T eliminates quantifiers, it is enough to show that if C is a substructure of the models A and B of T, then there is a model D of T which contains A and B as elementary substructures.

(4) (Assume that L is countable) To show that T eliminates quantifiers, it is enough to find a model M of T with the following properties:

(a) Every countable model of T embeds in M.

(b) If F : A_{0} → B_{0} is a partial isomorphism, with A_{0}, B_{0} finite subsets of M, and c ∈ M, then there is some partial isomorphism extending F and having c in its domain. Part (a) follows from a more general result:

(1.8) Back and forth Theorem. Let A and B be L-structures. Assume that there is a family I of partial isomorphism from A to B such that

(a) (Forth) Pour tout a ∈ A and F ∈ I, there is F′ ∈ I which extends F and with a ∈ dom(F′).

(b) (Back) Pour tout b ∈ B and F ∈ I, there is F′ ∈ I which extends F and with b ∈ Im(F′). Then A ≡ B.

Definition. A family of partial isomorphisms between two L-structures has the property of the back-and-forth if it satisfies the above conditions (a) and (b).

(1.9) Proof of (1.7) (1) Let A ⊆ B be models of T. Since A ≺_{1} B, T h(A, a)_{a∈A} ∪ Δ(B) is consistent. Indeed, our hypothesis says that all universal formulas of L(A) which hold in A also hold in B. Let A_{1} ⊧ T h(A, a)_{a∈A} ∪Δ(B), we may assume that A_{1} is an elementary extension of A which contains B. Then B ≺_{1} A_{1}, and using the same reasoning, there is an elementary extension B_{1} of B which contains A_{1}. Repeating the same argument, we build by induction a chain

A_{0} = A ⊆ B_{0} = B ⊆ A_{1} ⊆ B_{1} ⊆ ⋯ ⊆ A_{n} ⊆ B_{n} ⊆ A_{n+1} ⊆ ⋯

where A_{n} ≺ A_{n+1} and B_{n} ≺ B_{n+1}. Then C = ⋃_{n∈ℕ} A_{n} = ⋃_{n∈ℕ} B_{n} is an elementary extension of A and of B, whence A ≺ B (see (1.3)).

(2) If every formula is equivalent modulo T to an existential formula, it is also equivalent modulo T to a universal formula (since the negation of an existential formula is a universal formula). This shows the equivalence of the last two conditions. The equivalence of the first two follows from the definition of model completeness and the preservation result (1.5)(2).

(3) If T does not eliminate quantifiers, there is a substructure C of models A and B of T such that (A, c)_{c∈C} ≢ (B, c)_{c∈C}. Then clearly one cannot find D in which both A and B elementarily embed.

(4) We will show the theorem of the back and forth. One shows by induction on the number of quantifiers of a formula φ(x) in prenex form that if F ∈ I and a is a tuple in dom(F), then

A ⊧ φ(a) ⟺ B ⊧ φ(F (a)).

For quantifier-free formulas, this is exactly the definition of partial isomorphism. Write the formula φ(x) as ∃y ψ(x, y), y a single variable, and assume that the result holds for ψ(x, y). Let F ∈ I, a ∈ dom(F), and assume that A ⊧ φ(a). Then there is c ∈ A such that A ⊧ ψ(a, c). By hypothesis (forth), there is F′ ∈ I extending F and with c ∈ dom(F′). By induction hypothesis, B ⊧ ψ(F′(a), F′(c)), i.e., B ⊧ φ(F (a)). One shows the other direction in the same way, using now the “back” direction.

(1.10) Examples (1) The theory of the field ℂ (or more generally, the theory of algebraically closed fields)

eliminates quantifiers in the language of rings {+, −, ·, 0, 1}.

(2) Let us now consider the field ℝ in the language of rings. One can show that its theory is model complete. However, it does not eliminate quantifiers. Indeed let C = ℚ(α), where α^{2} = 2. One can embed C into ℝ in two different ways: by sending α to \sqrt{2} (the positive square root of 2) or to −\sqrt{2}. But clearly (ℝ, \sqrt{2}) ≢ (ℝ, −\sqrt{2}) since \sqrt{2} has a square root in ℝ, while −\sqrt{2} does not.

(1.11) Ultraproducts

Definitions. Let I be a set, A_{i}, i ∈ I, a family of L-structures, and F a subset of P(I) (the set of subsets of I).

(1) F is a filter (on I) iff: (i) ∅ ∉ F; (ii) if X, Y ∈ F then X ∩ Y ∈ F; (iii) if X ∈ F and Y ⊇ X then Y ∈ F.

(2) F is an ultrafilter iff it is a maximal filter, i.e., is contained properly in no filter. One shows easily that a filter F is an ultrafilter if and only if, for every X ⊆ I, either X or I \ X is in F.

(3) A filter F is principal iff there is some i ∈ I such that {i} ∈ F. If there is no such i, it is called non-principal.

(4) We define an L-structure on the Cartesian product ∏_{i∈I} A_{i} as follows. We view an element a of ∏_{i∈I} A_{i} as a function from I to the disjoint union of the A_{i}’s, whose value at i is in A_{i}. If f is an n-ary function symbol, R is an n-ary function symbol, and (a_{1}, …, a_{n}) ∈ ∏_{i∈I} A_{i}, then f(a_{1}, …, a_{n})(i) = f(a_{1}(i), …, a_{n}(i)), and ∏_{i∈I} A_{i} ⊧ R(a_{1}, …, a_{n}) iff A_{i} ⊧ R(a_{1}(i), …, a_{n}(i)) for every i ∈ I. Finally, the interpretation of a constant c is the function which to i associates the interpretation of c in A_{i}.

(5) Let F be a filter on I. We define an equivalence relation ≡_{F} on ∏_{i∈I} A_{i} by setting

a ≡_{F} b ⟺ {i ∈ I | a(i) = b(i)} ∈ F.

The equivalence class of a ∈ ∏_{i∈I} A_{i} will be denoted by [a]_{F}, and the set of equivalence classes by ∏_{i∈I} A_{i}/F. ∏_{i∈I} A_{i}/F has a natural L-structure: the constant c is interpreted by [c]_{F}; f([a_{1}]_{F}, …, [a_{n}]_{F}) = [f(a_{1}, …, a_{n})]_{F}, and R([a_{1}]_{F}, …, [a_{n}]_{F}) holds iff {i ∈ I | A_{i} ⊧ R(a_{1}(i), …, a_{n}(i))} ∈ F. The structure ∏_{i∈I} A_{i}/F is called the reduced product of the structures A_{i} with respect to F. If F is an ultrafilter, then ∏_{i∈I} A_{i}/F is called the ultraproduct of the A_{i} with respect to F. If all A_{i} are equal to the same structure A, then we talk of reduced power and of ultrapower of A.

(6) Observe that the natural map ∏_{i∈I} A_{i} → ∏_{i∈I} A_{i}/F is a homomorphism of Lstructures.

(1.12) Examples. If I is finite, then all ultrafilters on I are principal. Note that if F is principal, say {j} ∈ I, then the ultraproduct ∏_{i∈I} A_{i}/F is naturally isomorphic to A_{j}.

The best known non-principal filter (on an infinite set I) is called the Fréchet filter and is the set of all subsets X of I such that I \ X is finite. It is contained in all non-principal ultrafilters on I (Exercise).

Observe that if A ⊂ I is infinite, then it intersects every cofinite subset of I; hence A and the Fréchet filter generate a (proper) filter, and A belongs to a non-principal ultrafilter.

(1.13) Łos’ Theorem. Let I be infinite, F a filter on I, (A_{i})_{i∈I} a family of L-structures, and A = ∏_{i∈I} A_{i}/F.

(1) Let φ(x) be a positive L-formula, a a tuple in ∏_{i∈I} A_{i}. Then

A ⊧ φ([a]_{F}) ⟺ {i ∈ I | A_{i} ⊧ φ(a(i))} ∈ F.

(2) Assume now that F is an ultrafilter, and let φ(x) be any formula, a a tuple in ∏_{i∈I} A_{i}.

Then

A ⊧ φ([a]_{F}) ⟺ {i ∈ I | A_{i} ⊧ φ(a(i))} ∈ F.

This result is not difficult to prove, using induction on the complexity of the formulas. Note the restriction in (1) of φ(x) being positive: the result definitely doesn’t hold for formulas involving a negation, as can be shown by the following easy example. Let a, b ∈ ∏_{i} A_{i}. Then [a]_{F} = [b]_{F} ⟺ {i ∈ I | a(i) = b(i)} ∈ F. But if F is not an ultrafilter, choose A ⊂ I such that A and I \ A are not in F; then (assuming |A_{i}| ≥ 2 for all i, choose b such that {i ∈ I | a(i) = b(i)} = A. Clearly [a]_{F} ≠ [b]_{F} but {i ∈ I | a(i) ≠ b(i)} ∉ F.

(1.14) One immediate consequence of Łos’ theorem is that if F is an ultrafilter on I, then the L-structure A embeds elementarily into its ultrapower A^{I}/F, via the map which to an element a associates [â]_{F}, where â is the function taking the value a on I.

(1.15) Theorem (Keisler-Shelah). Two L-structures A and B are elementarily equivalent if and only if they have isomorphic ultrapowers.

(1.16) Let I be infinite, F a non-principal ultrafilter on I, and A an L-structure. Assume that the language L is countable. Then A^{I}/F is ω_{1}-saturated, i.e., if B ⊂ A^{I}/F is countable, and Σ(x) is a set of L(B)-formulas which is finitely satisfiable in A^{I}/F, then there is a tuple b ∈ A^{I}/F which satisfies all formulas of Σ(x). Proof. The set of L(B)-formulas is countable, and therefore we may choose an enumeration ψ_{n}(x) of Σ(x). For each n, choose b(n) ∈ A satisfying ⋀_{i=1}^{n} ψ_{i}(x), and let b = [(b(n))_{n}]_{F}.

(1.17) Exercise. Under the same hypotheses on I, F, L, show that the conclusion of (1.16) also holds if one assumes that the tuple x of variables has length ω.

(1.18) Exercise (harder). Let I be infinite, F an ultrafilter on I, and (A_{i})_{i∈I} a family of L-structures of cardinality ≤ ℵ_{0}. Show that ∏_{i∈I} A_{i}/F is either finite or of cardinality ≥ 2^{ℵ_{0}}.

(1.19) Exercise. Let F be a filter on a set I, and let J ∈ F, A_{i}, i ∈ I, a family of L-structures. Let

G = {X ∩ J | X ∈ F}.

(1) Show that G is a filter on J, and that if F is an ultrafilter, so is G.

(2) Show that

∏_{i∈I} A_{i}/F ≃ ∏_{i∈J} A_{i}/G.

(1.20) Exercise. Let I and J be sets, and F, G be filters on I and J respectively.

(1) Let D be the set of subsets X of I × J satisfying:

{i ∈ I | {j | (i, j) ∈ X} ∈ G} ∈ F.

Verify that this set is a filter, and that F and G are ultrafilters, then so is D.

(2) Verify that if (A_{i,j})_{i∈I,j∈J} is a family of L-structures, then the natural isomorphism

∏_{(i,j)∈I×J} A_{i,j} → ∏_{i∈I}(∏_{j∈J} A_{i,j})

induces an isomorphism

∏_{(i,j)∈I×J} A_{i,j}/D → ∏_{i∈I}(∏_{j∈J} A_{i,j}/G)/F.

(1.21) More on saturated models. Let κ be an infinite cardinal (greater that |L|), M an L-structure. Then M is κ-saturated iff for every n and subset A of M of cardinality < κ, if Σ(x) (where x is an n-tuple of variables) is a set of L(A)-formula which is finitely satisfiable in M, then there is an n-tuple a in M which satisfies all formulas in Σ. M is saturated if it is |M|-saturated. One can then show that an L-structure M is κ-saturated if and only if the two following conditions hold:

(i) (κ-universality) Every model of T h(M) of cardinality < κ embeds elementarily into M.

(ii) (κ-homogeneity) If λ < κ and (a_{i})_{i<λ}, (b_{i})_{i<λ} are two sequences of elements of M such that (M, a_{i})_{i<λ} ≡ (M, b_{i})_{i<λ}, and if a ∈ M then there is b ∈ M such that (M, a_{i}, a)_{i<λ} ≡ (M, b_{i}, b)_{i<λ}.

(1.22) Theorem. Let M be an infinite L-structure, and κ an infinite cardinal. Then M has an elementary extension which is κ-saturated. Proof. Exercise. The proof is done in two steps.

(1) First show that M has an elementary extension M_{1} such that for every n and subset A of M of cardinality < κ, if Σ(x) (where x is an n-tuple of variables) is a set of L(A)-formula which is finitely satisfiable in M, then there is an n-tuple a in M_{1} which satisfies all formulas in Σ.

(2) Now, using step 1, build an increasing chain M_{α}, α < κ^{+} of elementary extensions of M such that

(i) M_{0} = M; (ii) if α is a limit ordinal then M_{α} = ⋃_{β<α} M_{β}. (iii) If α = β + 1, then M_{β} ≺ M_{α} and for every n and subset A of M_{β} of cardinality < κ,

if Σ(x) (where x is an n-tuple of variables) is a set of L(A)-formula which is finitely satisfiable in M_{β}, then there is an n-tuple a in M_{α} which satisfies all formulas in Σ. You then verify that M_{κ^{+}} = ⋃_{α<κ^{+}} M_{α} is κ-saturated and an elementary extension

of M. Can you bound its cardinality? (Here we are using the fact that κ^{+} is regular, and in particular that a subset of κ^{+} of cardinality < κ cannot be cofinal in κ^{+}.)

(1.23) Criterion for completeness of a theory. Let T be a theory in a language L, and κ an infinite cardinal ≥ |L|. Then T is complete if and only if whenever M_{1} and M_{2} are two κ-saturated models of T, there exists a (non-empty) family I of partial isomorphisms M_{1} → M_{2} which has the property of the back-and-forth.

(1.24) Criterion for elimination. Let T, L, κ be as above, and Δ a set of L-formulas closed under disjunction. The following conditions are equivalent:

(1) Every L-formula is equivalent modulo T to a Boolean combination of formulas from Δ.

(2) For any two κ-saturated models M_{1} and M_{2} of T, consider the set I(M_{1}, M_{2}) of partial isomorphisms from M_{1} to M_{2}, with domain of cardinality < κ and which preserve formulas from Δ (i.e., if the tuple a is in the domain of f ∈ I and φ(x) ∈ Δ, then M_{1} ⊧ φ(a) ⟺ M_{2} ⊧ φ(f(a))). Then either this set is empty, or it has the property of the back-and-forth.

Observe that this criterion works for theories which are not complete (e.g., the theory of algebraically closed fields). The condition that I be non-empty is equivalent to: M_{1} and M_{2} satisfy the same sentences in Δ.

(1.25) Definability of structures. Let M be an L-structure, and N be an L′-structure. We say that the L′-structure N is definable in M iff there is some definable subset S of M^{k} for some k, and a bijection F : N → S such that:

– For each n-ary relation R ∈ L′, R^{∗} = F (R) is definable.

– For each n-ary function f ∈ L′, the image by F of the graph of f definable, and we will denote by f^{∗} the function it defines on S^{n}.

Then the L′-structures N and S are isomorphic.

Comments. By definable, I mean possibly with parameters from M. To be precise, one would say N is A-definable in M, whenever S, all R^{∗}, f^{∗}, c^{∗} = F (c) where c ranges over all constant symbols of L′, are definable with parameters from A.

Exercise. Show that if N is definable in M (with parameters from A ⊂ M) and F is the isomorphism N → S, then to every formula φ(x) ∈ L′ we can associate an L(A)-formula φ^{∗}(x̄) such that, for every tuple a in N^{m}, we have

N ⊧ φ(a) ⟺ M ⊧ φ^{∗}(F (a)).

Exercise. Show that the field ℂ is definable in the field ℝ.

(1.26) Interpretation of structures. Let M be an L-structure, N an L′-structure. Then N is interpretable in M iff there is a definable subset S of M^{k} for some k, a definable subset E of M^{2k} which defines an equivalence relation on S, and a bijection F between N and the set S/E of E-equivalences classes of S, such that:

– For each n-ary relation R ∈ L′, the set of tuples (a_{1}, …, a_{n}) ∈ S^{n} such that (F^{−1}(a_{1}/E), …, F^{−1}(a_{n}/E)) ∈ R, is definable in M.

– For each n-ary function f ∈ L′, the set of tuples (a_{1}, …, a_{n}, b) ∈ S^{n+1} such that f(F^{−1}(a_{1}/E), …, F^{−1}(a_{n}/E)) = F^{−1}(b/E), is definable in M.

Exercise. Show that if N is interpretable in M (with parameters from A ⊂ M), and F is the isomorphism N → S/E, then to every formula φ(x) ∈ L′ we can associate an L(A)- formula φ^{∗}(x̄) such that, for every tuple a = (a_{1}, …, a_{n}) in N^{n}, and tuple b = (b_{1}, …, b_{n}) where each b_{i} ∈ F (a_{i}), we have

N ⊧ φ(a) ⟺ M ⊧ φ^{∗}(b).

Exercise. Let G be a group (the language is the language of groups {·,^{−1} , 1}), and assume that H is a definable normal subgroup of G. Show that the quotient group G/H is interpretable in the group G.

These two exercises should convince you of the fact that “definability” and “interpretation” are just fancy names for very natural concepts that you have already used.

(1.27) Theory of a class, models of a theory.

We fix a first-order language L. Given a class K of L-structures, one can consider its theory, Th(K), consisting of the sentences which hold in all elements of K. Dually, given an L-theory T, we may consider the class Mod(T) of all models of T.

Clearly one has K ⊆ Mod(Th(K)), and the class Mod(Th(K)) is called the elementary class generated by K. The inclusion is in general strict. If K = Mod(Th(K)) then K is called an elementary class. Proposition. Let K be a class of L-structures. Then K is an elementary class if and only if it is closed under ultraproducts and elementary substructures. Proof. The necessity of the condition is clear, since the class of models of a theory is closed under these operations. For the sufficiency, it suffices to show that every model of Th(K) embeds elementarily into an ultraproduct of members of K. By (1.15) and the fact that an ultrapower of an ultraproduct of members of K is an ultraproduct of members of K (see exercise (1.20)), it suffices to show that every model of Th(K) is elementarily equivalent to an ultraproduct of members of K.

So, let M ⊧ Th(K), and let I be the set of all L-sentences true in A. Observe that I is closed under finite conjunctions. If θ ∈ I, then ¬θ ∉ Th(K), i.e., there is some M_{θ} ∈ K such that M_{θ} ⊧ θ, and we choose one such. For each ψ ∈ I, consider X_{ψ} = {θ ∈ I | M_{θ} ⊧ ψ}. Then each X_{ψ} is non-empty, and furthermore, since I is closed under finite conjunctions, the set {X_{ψ} | ψ ∈ I} has the finite intersection property. Let U be an ultrafilter on I which contains all X_{ψ}, ψ ∈ I. By Łos’ theorem, M ≡ ∏_{θ∈I} M_{θ}/U.

(1.28) Example. If K = {M}, then Mod(Th(K)) is simply the set of L-structures elementarily equivalent to M. By Keisler-Shelah (1.15), every member of Mod(Th(K)) embeds elementarily into an ultrapower of M.

(1.29) Example 2. Consider the class K of all finite fields, and T_{f} its theory. Then, every model of T_{f} which is finite is in K, and every model of T_{f} which is infinite is elementarily equivalent to an ultraproduct of finite fields. Thus, to show that the pseudo-finite fields are exactly the infinite models of T_{f}, it suffices to show that if F is a pseudo-finite field, then it is elementarily equivalent to an ultraproduct of finite fields.

2. Finite fields - properties

(2.1) Basic properties

If p is a prime number, then pℤ is a maximal ideal of ℤ and ℤ/pℤ is a field with p elements. This field is denoted by 𝔽_{p}, and it is the prime field of characteristic p, i.e., it is contained in every field of characteristic p.

Let F be a finite field. Since 1 ∈ F, it necessarily contains one of the fields 𝔽_{p}, and is therefore a vector space over 𝔽_{p}, whence of cardinality p^{n} for some n ∈ ℕ.

Let F be a field of characteristic p having q = p^{n} elements, let K be an algebraically closed field containing F. Let us consider the multiplicative group F^{×} = F \{0} of F. It has q − 1 elements and hence every non-zero element of F satisfies the equation X^{q−1} − 1 = 0. Thus all elements of F satisfy X^{q} − X = 0. The derivative of this equation equals −1, all its roots are therefore simple roots, and we obtain

X^{q} − X = ∏_{a∈F}(X − a).

Conversely, let us consider the set S ⊂ K of all solutions of X^{q} − X = 0. As above, its roots are all distinct. S is closed under multiplication, and S \ {0} by multiplicative inverse. Because we are in characteristic p and q is a power of p, we have (a+b)^{p} = a^{p} +b^{p} and (a + b)^{q} = a^{q} + b^{q}. This implies that S is closed under addition, and is therefore a subfield of K.

So, we have shown: Theorem. Let F be a finite field. Then for some prime p and q = p^{n}, F has q elements. Its elements are exactly the roots of the equation X^{q} − X = 0.

(2.2) The multiplicative group of a finite field. Let F = 𝔽_{q} be a finite field. We will show that F^{×} is cyclic. It can be written as a direct sum of cyclic subgroups, and if it is not cyclic, then its exponent m is a proper divisor of q − 1. But all roots of X^{q−1} = 1 are simple roots, whence all roots of X^{m} = 1 are simple as well (since m ≢ 0 modulo p). This implies that q − 1 = m.

(2.3) Perfect fields. Recall that a field F of characteristic p > 0 is perfect if every element of F has a p-th root. By convention, every field of characteristic 0 is perfect.

If F = 𝔽_{p^{n}} is finite, then the order of F^{×} is prime to p, which implies that every element is (multiplicatively) divisible by p, i.e., F is perfect.

An example of imperfect field is 𝔽_{p}(t), where t is transcendental over 𝔽_{p}.

The perfect hull of a field F is the smallest perfect field containing F. If F is of characteristic p > 0 and is not perfect, it is obtained by adjoining to F all p^{n}-th roots of elements of F. It is then denoted by F^{1/p^{∞}}.

(2.4) The algebraic closure of 𝔽_{p}.

Let m, n be positive integers, p a prime. Then

𝔽_{p^{m}} ⊆ 𝔽_{p^{n}} ⟺ m divides n,

and in that case we have [𝔽_{p^{n}} : 𝔽_{p^{m}}] = n/m.

Indeed, if 𝔽_{p^{m}} ⊆ 𝔽_{p^{n}} then 𝔽_{p^{n}} is a 𝔽_{p^{m}}-vector space, hence m divides n and [𝔽_{p^{n}} : 𝔽_{p^{m}}] = n/m. Conversely, if m divides n, then p^{m} − 1 divides p^{n} − 1, whence all roots of X^{p^{m}−1} = 1 are contained in 𝔽_{p^{n}}, i.e., 𝔽_{p^{m}} ⊆ 𝔽_{p^{n}}.

It follows easily that for any m, n ≥ 1, 𝔽_{p^{m}} ∩ 𝔽_{p^{n}} = 𝔽_{p^{d}} and 𝔽_{p^{m}}𝔽_{p^{n}} (the composite field of 𝔽_{p^{m}} and 𝔽_{p^{n}}) = 𝔽_{p^{e}} where d is the greatest common divisor of m and n, and e is the least common multiple of m and n.

Let α be algebraic over 𝔽_{p}. Then 𝔽_{p}(α) is a finite-dimensional 𝔽_{p}-vector space, and is therefore also finite. This implies that the algebraic closure 𝔽_{p}^{alg} of 𝔽_{p} is ⋃_{n∈ℕ} 𝔽_{p^{n}}.

(2.5) The Frobenius map. Fix a prime p, and let F be a field of characteristic p. Using the binomial rule, one has, for every a, b ∈ F, (a + b)^{p} = a^{p} + b^{p}. Since x^{p} = 0 implies x = 0, this means that the map x ↦ x^{p} is an injective endomorphism of the field F. This map is called the Frobenius map. It is the identity on 𝔽_{p} (since every element of 𝔽_{p} satisfies X^{p} − X = 0), and defines an automorphism of each 𝔽_{p^{n}}. Hence it defines an element φ of Gal(𝔽_{p}^{alg}/𝔽_{p}). Observe that if d ∈ ℕ, the elements of 𝔽_{p}^{alg} which are fixed by φ^{d} are precisely the elements of 𝔽_{p^{d}}. Furthermore, one checks that the restriction φ|_{𝔽_{p^{d}}} of φ to

𝔽_{p^{d}} has order exactly d: φ^{ℓ} being the identity on 𝔽_{p^{d}} means exactly that all elements of 𝔽_{p^{d}} satisfy X^{p^{ℓ}} = X, and therefore that d divides ℓ.

This will allow us to describe Gal(𝔽_{p}^{alg}/𝔽_{p}) in a nice fashion, see below. But first we need to do a little infinite Galois theory and introduce pro-finite groups.

3. Topological groups, profinite groups and infinite Galois theory

(3.1) Topological groups. A topological group is a group G endowed with a topology, such that group multiplication : G × G → G and the inverse map G → G are continuous (G × G is endowed with the product topology). It then follows that multiplication (on the left or on the right) by an element g of the group defines a homeomorphism of G. Observe also that in order to define the topology, it suffices to give a basis of open sets containing 1: if g ∈ G, then translating the basis by g will give us a basis of open sets containing g. Some properties. Let G be a topological group.

(1) Let H be a subgroup of G. Then the closure H̄ of H in G is also a subgroup of G. If H is normal in G so is H̄.

(2) Let H be an open subgroup of G. Then H is clopen, i.e., open and closed. If H is a closed subgroup of G of finite index, then H is clopen.

(3) Assume that G is compact, and let H be an open subgroup of G. Then [G : H] < ∞. [Note: in English, compact does not imply Hausdorff].

(4) Let U ⊂ G and assume that U and V are dense open subsets of G. Then U · V = G.

(5) Let U, V ⊂ G. Then Ū · V̄ ⊂ \overline{U · V}.

(6) Let H be a subgroup of G and assume that H is dense in G, and that G is T_{1} (i.e., every singleton is closed). Then Z(G) ∩ H = Z(H). [Recall that the center of a group G, denoted by Z(G), is the set of elements commuting with all elements of G].

(7) Assume that G is T_{1}, and let g ∈ G. Then the centraliser of g in G, C_{G}(g), is a closed subgroup of G. If H is abelian, then so is H̄. Similarly for nilpotent and solvable.

Proof. (1) If X is a closed set containing H, then X^{−1} (= {g^{−1} | g ∈ X}) contains H^{−1} = H. Hence H̄ is closed under the inverse map. Similarly, if g ∈ H, then gH̄ = \overline{gH} ⊆ H̄, so that H · H̄ ⊆ H̄. Similarly, if h ∈ H̄, then Hh ⊂ \overline{Hh} = H̄h, and Hh ⊂ H̄, so that H̄ · H̄ = H̄, i.e., H̄ is a subgroup of G.

If H is normal in G, then for every g ∈ G we have gH = Hg; hence also gH̄ = H̄g.

(2) G is the disjoint union of the cosets gH, where g runs through a set of representatives of G/H. If H is open, so is every coset, and the union of the cosets gH for g ∉ H is open, and is the complement of H in G. Hence H is also closed. Similar proof for the second assertion, using the fact that there are only finitely many cosets.

(3) G is the union of the open sets gH, and therefore, by compactness, there are only finitely many of them, i.e., [G : H] < ∞.

(4) Let g ∈ G. Then V^{−1} and gV^{−1} are also dense open subsets of G. Hence U ∩ gV ≠ ∅, i.e., there are u ∈ U and v ∈ V such that u = gv^{−1}, and g = uv.

(5) As in the proof of (1), we first get that U · V̄ ⊆ \overline{U · V}, then that Ū · V̄ ⊆ \overline{U · V}.

(6) Clearly Z(G) ∩ H ⊆ Z(H). Assume h ∈ H, h ∉ Z(H), and let g ∈ G be such that [g, h] = g^{−1}h^{−1}gh ≠ 1. Choose some open set U containing [g, h] and not containing 1 (here we use the T_{1}-property of G). By continuity of the commutator map (x, y) ↦ [x, y], there are some open subset U_{1} and U_{2} of G, with h ∈ U_{1} and g ∈ U_{2}, and such that the image of U_{1} × U_{2} under the commutator map is contained in U. In particular, [h, U_{2}] ⊂ U; by density of H, U_{2} ∩ H ≠ ∅, and this implies that h ∉ Z(H).

(7) C_{G}(g) = {h ∈ G | [g, h] = 1}. The set X of pairs (h_{1}, h_{2}) such that [h_{1}, h_{2}] = 1 is closed (because {1} is closed), hence so is X ∩ {g} × G, and the latter is homeomorphic to C_{G}(g).

Hence, if H is abelian, then for every h ∈ H, C_{G}(h) is a closed subgroup of G which contains H, and therefore H̄.

(3.2) Profinite groups and infinite Galois groups. There are several equivalent definitions of profinite groups. A profinite group is a topological group, which is compact, Hausdorff, and totally disconnected (i.e., has a basis of open sets which consists of clopen sets). Equivalently, it is an inverse limit of a projective system of finite groups with the corresponding topology. This might not be very informative, we will see how it works for Galois groups.

Let F be a field. We know that F^{alg} is the union of all finite normal algebraic extensions of F. We are interested in Aut(F^{alg}/F), the group of automorphisms of F^{alg} which fix the elements of F, and I will (abusively) denote it by Gal(F^{alg}/F). Note that if F is of characteristic p > 0, σ ∈ Aut(F^{alg}), and a^{p} = b ∈ F^{alg} then necessarily σ(a)^{p} = σ(b), so that knowing σ on b forces the value of σ on a. Thus every automorphism of the separable closure F^{sep} of F (the set of elements of F^{alg} which satisfy a separable equation over F) which is the identity on F will extend uniquely to an element of Aut(F^{alg}/F).

Let N be the family of all finite Galois extensions of F, and if L ⊆ M ∈ N, let π_{LM} : Gal(M/F) → Gal(L/F) be the restriction map. Then these maps are epimorphisms, and if L ⊆ M ⊆ N ∈ N, we have π_{MN}π_{LM} = π_{LN}. We endow each (finite) group Gal(L/F) with the discrete topology, and consider the group ∏_{L∈N} Gal(L/F) (pointwise multiplication), endowed with the product topology (recall that a basic set of the product topology on ∏_{i∈I} X_{i} is a set ∏_{i∈I} U_{i} where each U_{i} is open in X_{i} and all but finitely many of the U_{i}’s equal X_{i}). This space therefore has a basis consisting of clopen sets.

Furthermore, since a finite discrete topological space is compact and Hausdorff, the group ∏_{L∈N} Gal(L/F) is also compact Hausdorff.

We then consider the subgroup

H = {(σ_{L})_{L} ∈ ∏_{L∈N} Gal(L/F) | if L ⊆ M ∈ N then σ_{M}|_{L} = σ_{L}}.

One verifies that H is a closed subgroup of ∏_{L∈N} Gal(L/F), and that the map Gal(F^{alg}/F) → ∏_{L} Gal(L/F) defined by σ ↦ (σ|_{L})_{L} embeds Gal(F^{alg}/F) into H. Furthermore, one verifies that each element of H defines an automorphism of F^{alg} which fixes F, and therefore this map is in fact an isomorphism.

The embedding of Gal(F^{alg}/F) into ∏_{L} Gal(L/F) gives it the structure of a topological group, and it is compact, Hausdorff and totally disconnected. A basis for the topology is given by the translates of the subgroups Gal(F^{alg}/L), L ∈ N (exercise). It follows that every open set containing the identity contains an open set of the form Gal(F^{alg}/L) for some L ∈ N.

The way of describing Gal(F^{alg}/F) as an inverse limit of a projective system of finite groups is as follows: the inverse system is the set {Gal(L/F), π_{LM} | L ⊆ M ∈ N }, and we write Gal(F^{alg}/F) = lim_{←}Gal(L/F).

(3.3) Description of Gal(𝔽_{p}^{alg}/𝔽_{p}). The family of all finite Galois extensions of 𝔽_{p} can be indexed by the integers n ≥ 2, and we have seen that Gal(𝔽_{p^{n}}/𝔽_{p}) ≃ ℤ/nℤ. The maps π_{mn} for m dividing n are then simply the epimorphisms ℤ/nℤ → ℤ/mℤ given by reducing modulo m. Thus

Gal(𝔽_{p}^{alg}/𝔽_{p}) = {(a_{n})_{n≥2} ∈ ∏_{n≥2} ℤ/nℤ | if m|n then a_{m} ≡ a_{n}mod(m)}.

This group is also denoted by ℤ̂, or lim_{←} ℤ/nℤ. One can show that it is isomorphic to ∏_{ℓ aprime} ℤ_{ℓ}, where ℤ_{ℓ} denotes the set of ℓ-adic integers, i.e., ℤ_{ℓ} = lim_{←} ℤ/ℓ^{n}ℤ.

Exercise. Verify that the subgroup ⟨φ⟩ of ℤ̂ generated by (1)_{n} is dense, i.e., that it intersects every open subsets of ℤ̂. (Observe that (1)_{n} corresponds to the Frobenius in the isomorphism Gal(𝔽_{p}^{alg}/𝔽_{p}) ≃ ℤ̂).

(3.4) The Galois correspondence. The Galois correspondence works almost as well as in the finite case, but we need to consider closed subgroups instead of arbitrary ones. I.e., separable algebraic extensions of F correspond to closed subgroups of Gal(F^{alg}/F).

Thus if H_{0} is a subgroup of Gal(F^{alg}/F), E the subfield of F^{sep} of elements fixed by all elements of H_{0}, then Gal(F^{alg}/E) will be the closure of H_{0} in Gal(F^{alg}/F) for the topology.

Note also that if E is a (maybe infinite) Galois extension of F, then one can define Gal(E/F) in a similar way, by restricting one’s attention to the family N_{E} of finite Galois extensions of F contained in E. Then the subgroup Gal(F^{alg}/E) will be a normal (closed) subgroup of Gal(F^{alg}/F), and the quotient Gal(F^{alg}/F)/Gal(F^{alg}/E) is naturally isomorphic to Gal(E/F), the restriction map Gal(F^{alg}/F) → Gal(E/F) being continuous for the topology.

Thus we have a correspondence between quotients of Gal(F^{alg}/F) by continuous homomorphisms and Galois extensions of F.

An aside: to check that a group epimorphism G → H between profinite groups is continuous, it suffices to check that the kernel of this map is a closed subgroup of G.

(3.5) Example. Consider again the Frobenius map φ ∈ Gal(𝔽_{p}^{alg}/𝔽_{p}), and let H_{0} be the subgroup it generates. Then the elements of 𝔽_{p}^{alg} which are fixed by φ are all in 𝔽_{p}. However, H_{0} being countable, it certainly doesn’t equal ℤ̂ (which has cardinality 2^{ℵ_{0}}, exercise).

(3.6) More on ℤ̂.

We will discuss a few properties of ℤ̂, and in particular show that if F is a perfect field, then Gal(F^{alg}/F) ≃ ℤ̂ if and only if F has exactly one (separable) extension of degree n for every n > 1. (Since our field F is perfect, we do not need to worry about separability).

First observe that this condition is certainly necessary: for every n, ℤ̂ has a unique open subgroup H_{n} of index n (namely, in the notation of (3.3), the set of sequences (a_{i})_{i≥2} such that a_{i} is divisible by n in ℤ/iℤ. Equivalently, if ¯1 denotes the sequence which equals 1 everywhere, then this subgroup is the closure of the subgroup generated by n¯1 in ℤ̂, and we will denote it by nℤ̂. Hence, by Galois theory, this implies that F has exactly one separable extension of degree n: the subfield of F^{sep} consisting of elements fixed by H_{n}.

Let us now assume that F has a unique separable extension of degree n for each n > 1, and let us see what this implies. Let L be a finite Galois extension of F and G its Galois group over F. First note that our hypothesis implies that all subgroups of G are normal (since the conjugate of a subgroup of G has the same order as that subgroup). We will show that G is cyclic. This is done by induction on its order, call it n. If n is prime, there is nothing to prove, since G ≃ ℤ/nℤ. Otherwise, let p be a prime dividing n, and a ∈ G an element of order p. Then the subgroup ⟨a⟩ is a normal subgroup of G, and by induction hypothesis, the quotient G/⟨a⟩ is cyclic. Hence there is b ∈ G such that G = ⟨a, b⟩. If a ∈ ⟨b⟩, then G = ⟨b⟩ and we are done. Otherwise, we have ⟨a⟩ ∩ ⟨b⟩ = (1) (because a has order p), and the commutator [a, b] = a^{−1}b^{−1}ab belongs to the intersection of the normal subgroups ⟨a⟩ and ⟨b⟩, i.e., a and b commute. Thus G = ⟨a, b⟩ = ⟨a⟩ × ⟨b⟩. Because G has a unique subgroup of order p, we get that p does not divide the order of b, and therefore G is cyclic.

We have therefore shown the following: assume that the perfect field F has exactly one extension of degree n for each n > 1. Then all (continuous) quotients of the profinite Gal(F^{alg}/F) are cyclic, and for every n > 1 it has a quotient ≃ ℤ/nℤ.

(3.7) Proposition. Let G be a profinite group.

(1) If all continuous finite quotients of G are cyclic, then there is a (continuous) epimorphism ℤ̂ → G.

(2) If moreover for every n > 1, G has a continuous quotient isomorphic to ℤ/nℤ, then any continuous epimorphism from ℤ̂ onto G is an isomorphism.

Proof. (1) Note first of all that G is abelian. Using the compactness of G, we can therefore find an element a ∈ G such that for every open subgroup H of G, aH generates G/H. Indeed, for each open subgroup H of G, let S_{H} be the set of elements whose image in G/H is a generator of G/H. This set is closed (since it is a union of cosets of H), non-empty, and if H ⊆ H′ then S_{H′} ⊂ S_{H}. Hence, if H_{1} and H_{2} are open normal subgroups of G, then S_{H_{1}H_{2}} ⊆ S_{H_{1}} ∩ S_{H_{2}}, and eveery finite intersection of S_{H} is non-empty. By compactness of G, there is some element a in the intersection of all S_{H}.

Consider the set I of numbers n such that G has an open subgroup H_{n} of index n. Then G embeds (continuously) into ∏_{n∈I} G/H_{n} [by definition of a profinite group, the intersection of all open subgroups of a profinite group is 1; moreover, by compactness, every open subgroup is of finite index and is therefore also closed]. By compactness, we get that G is in fact isomorphic to

{(b_{n}) ∈ ∏_{n∈I} G/H_{n} | if n|m then b_{n} ≡ b_{m} mod n}.

Thus the continuous epimorphism ∏_{n>1} ℤ/nℤ → ∏_{n∈I} G/H_{n} restricts to an epimorphism f : ℤ̂ → G.

(2) Our hypothesis implies that the set I defined above coincides with the set of integers > 1, whence the map f is injective, and G ≃ ℤ̂.

So, we need to show that any (continuous) epimorphism g : ℤ̂ → ℤ̂ is injective. Let N = Ker(g). Then N is a closed subgroup of ℤ̂. Since g is an epimorphism, for every n > 1 we have that g^{−1}(nℤ̂) is the unique subgroup of ℤ̂ of index n, i.e., equals nℤ̂. As N ⊂ g^{−1}(nℤ̂) for every n > 1, we get that N ⊂ ⋂_{n>1} nℤ̂ = (1), i.e., g is injective. Remarks. (1) The result of (2) extends easily to a profinite group G such that for every n > 1, G has only finitely many open subgroups of index ≤ n.

(2) ℤ̂ is also called the free profinite group on one generator. It can be defined using universal properties. Similarly, one can define free profinite groups on 2, 3, …, ℵ_{0}, … generators.

(3.8) Definition. If G is a profinite group, then X ⊂ G generates topologically G, or is a set of topological generators, iff the subgroup of G generated by X is dense in G. This means: if N is an open subgroup of G, then the image of X in G/N generates G/N. We saw already that ¯1 is a topological generator of ℤ̂. Exercise.

(1) Find a necessary and sufficient condition on the sequence (a_{n})_{n≥2} ∈ ℤ̂ ⊂ ∏_{n≥2} ℤ/nℤ to be a topological generator of ℤ̂. Show that if (a_{n})_{n≥2} is a topological generator of ℤ̂, then there is an automorphism of ℤ̂ which sends ¯1 to (a_{n})_{n≥2}.

(2) Show that if f : ℤ̂ → G is a continuous epimorphism, where G is a profinite group, and σ is a topological generator of G, then f^{−1}(σ) contains a topological generator of ℤ̂. [Hint: show that if g : A → B is an epimorphism between two finite cyclic groups, then every generator of B lifts to a generator of A. This result is true in more generality and is called Gaschütz lemma: let g : A → B be an epimorphism of finite groups, and assume that A is generated by d elements. If X ⊂ B is of size d and generates B, then there is some set Y generating A, of size d, and such that g(Y) = X.]

4. Zariski topology, etc.

In this section I recall some basic terminology coming from old-fashioned algebraic geometry, a good reference is Chapter III in Lang’s book Introduction to algebraic geometry. We fix two algebraically closed field K ⊆ Ω. Let n ∈ ℕ, X = (X_{1}, …, X_{n}).

(4.1) The Zariski topology. The Zariski topology on K^{n} is given by the following basic closed sets

V (f_{1}(X), …, f_{m}(X)) = {a ∈ K^{n} | f_{1}(a) = ⋯ = f_{m}(a) = 0},

where f_{1}(X), …, f_{m}(X) ∈ K[X]. Similarly, if B ⊂ K[X], we define V (B) = {a ∈ K^{n} | f(a) = 0 for all f(X) ∈ B}. Zariski closed sets are also called algebraic sets.

Dually, given a subset S of K^{n}, we define I(S) = {f(X) ∈ K[X] | f(a) = 0 for all a ∈ S}. Note that I(S) is a radical ideal (i.e., if it contains f^{n} then it contains f). Hilbert’s Nullstellensatz tells us that if I is a proper radical ideal of K[X], then V (I) ≠ ∅, and that if f_{1}(X), …, f_{m}(X) ∈ K[X], then I(V (f_{1}(X), …, f_{m}(X))) is the radical of the ideal generated by f_{1}(X), …, f_{m}(X).

Dually, if S ⊂ K^{n}, then V (I(S)) is the smallest Zariski-closed subset of K^{n} containing S, it is called the Zariski closure of S, and denoted by S̄.

Thus there is a correspondence between Zariski closed subsets of K^{n} and radical ideals of K[X]. Since K[X] is Noetherian, we get that every strictly descending chain of closed subsets of K^{n} is finite.

One can show that the Zariski topology on K^{n} is the topology induced by the Zariski topology on Ω^{n}.

(4.2) Irreducible components, (affine) varieties. Recall that a closed set is irreducible if it is not the union of two proper closed subsets. One verifies (fairly easily) that the Zariski closed set S is irreducible if and only if the ideal I(S) is prime.

The Noetherianity of the topology then implies that every closed subset S of K^{n} can be expressed as a finite union of irreducible closed sets, and these closed sets correspond to the minimal prime ideals containing I(S). They will be called the irreducible components of the closed set S.

By convention, an (affine) variety is an irreducible closed subset of K^{n}.

(4.3) Coordinate ring, field of definition of an algebraic set. Let S ⊂ K^{n} be an algebraic set, I = I(S). We then form the ring K[S] = K[X]/I, this is the coordinate ring of S (over K). If S is a variety, then K[S] will be a domain, and the dimension of S is the transcendence degree of the field of fractions K(S) of K[S] over K. If S is an arbitrary algebraic set, then dim(S) will be the sup of the dimensions of the irreducible components of S.

If F is a subfield of K such that I is generated by I ∩ F [X], then we say that S is defined over F, and the ring F [S] = F [X]/I ∩ F [X] is the coordinate ring of S over F. There is a smallest subfield of K over which S is defined, and it is called the field of definition of S. Warning. The algebraic set S may be definable over F without being defined over F, but this phenomenon only occurs in positive characteristic. Here is an example: if K is of characteristic p, and t ∈ K is transcendental over 𝔽_{p}, then the closed set {t} is definable over F = 𝔽_{p}(t^{p}) (by the equation X^{p} = t^{p}), but it is not defined over F, since the ideal of K[X] generated by X^{p} − t^{p} does not contain the element (X − t).

(4.4) Rational points. Let S ⊆ K^{n} be an algebraic set, and F a subfield (or subring) of K. Then S(F) = S ∩ F^{n} is the set of S-rational points of S. We define S(Ω) to be the set of points in Ω^{n} which satisfy f(X) = 0 for all f ∈ I(S). (We usually write S instead of S(Ω)). If S is a variety, a point a in S(Ω) is generic over K iff tr.deg(K(a)/K) = dim(S).

(4.5) Tensor products of F -algebras. Let F be a field. Recall that an F -algebra is simply a ring containing F, and it is therefore an F -vector space. Let A and B be two F -algebras. The F -algebra A ⊗_{F} B is defined as follows:

Let E_{A} and E_{B} be bases of the F -vector spaces A and B respectively; we assume that they both contain 1. Then as a vector space, A ⊗_{F} B is the F -vector space with basis E = {a ⊗ b | a ∈ E_{A}, b ∈ E_{B}}.

We now need to define multiplication on A ⊗_{F} B. By definition, every element of A ⊗_{F} B will be a finite F -linear combination of elements of the basis. Let c, c′ ∈ E_{A} and d, d′ ∈ E_{B}. Write cc′ = ∑_{a∈E_{A}} α_{a}a, dd′ = ∑_{b∈E_{B}} β_{b}b, where the α_{a} and β_{b} are in F. Then define

(c ⊗ d) · (c′ ⊗ d′) = ∑_{a∈E_{A},b∈E_{B}} α_{a}β_{b}a ⊗ b.

Note that this sum makes sense since almost all α_{a} and β_{b} are 0.

One extends multiplication to A ⊗_{F} B in the unique fashion so that multiplication is associative, distributive with the addition. Observe that A embeds into A ⊗_{F} B by identifying a ∈ E_{A} with a⊗1, and similarly for B (identify b ∈ E_{B} with 1⊗b). One denotes these copies of A and B by A ⊗ 1 and 1 ⊗ B, and their elements by a ⊗ 1, 1 ⊗ b respectively. One then defines a ⊗ b to be the element (a ⊗ 1) · (1 ⊗ b). One important property is that if a ∈ A, b ∈ B and c ∈ F, then c(a ⊗ b) = ca ⊗ b = a ⊗ cb. Exercise. Convince yourself of the fact that the isomorphism type of A ⊗_{F} B does not depend on the choice of the bases E_{A} and E_{B}.

(4.6) Regular extensions. Let F ⊆ E be fields. Then E is a regular extension of F iff E and F^{alg} are linearly disjoint over F, i.e.: if elements of the F -vector space E are linearly independent, then they are also linearly independent in the F^{alg}-vector space EF^{alg}. One can show that this condition is symmetric. Equivalently, this happens iff the F -algebra E ⊗_{F} F^{alg} is a domain. We will use this equivalent formulation.

If F is of characteristic 0 or is perfect, then E is a regular extension of F if and only if E ∩ F^{alg} = F. [This criterion does not work for imperfect fields.]

Let V be an algebraic set defined over F, and assume it is F -irreducible, i.e., cannot be written as the union of two proper closed subsets defined over F, or equivalently, the ideal I(V) ∩ F [X] is prime. Consider the ring F [V] = F [X]/I(V) ∩ F [X], and its field of fractions F (V). Then one has:

V is a variety ⟺ F (V) is a regular extension of F

(4.7) Exercise. Show that if F is a subfield of E and L, and L is a Galois extension of F, then E and L are linearly disjoint over F if and only E ∩ L = F.

5. Bounds on ideals in polynomial rings, and applications We will want to express in a field F the following property: if V is a variety defined

over F, then V has a point with its coordinates in F. I.e., for all m, n, X = (X_{1}, …, X_{n}), we want to find axioms which are satisfied by F if and only if

For all f_{1}(X), …, f_{m}(X) ∈ F [X] which generate a prime ideal in F^{alg}[X], there is an n-tuple a such that f_{1}(a) = ⋯ = f_{m}(a) = 0.

The difficulty is of course to express that f_{1}(X), …, f_{m}(X) generate a prime ideal in F^{alg}[X].

(5.1) Total degree. Let i = (i_{1}, …, i_{n}) ∈ ℕ^{n}. We define X^{i} = X_{1}^{i_{1}}X_{2}^{i_{2}} ⋯ X_{n}^{i_{n}}, and its (total) degree to be i_{1} + ⋯ + i_{n}. A polynomial in F [X] is an F -linear combination of monomials of this form, and we define its total degree to be the sup of the degrees of the monomial occurring in it. For each integer d, the set of polynomials of total degree ≤ d forms a finite-dimensional vector space over F, and is denoted by F [X]_{≤d}. Say its dimension is N(d). Then the vector space F [X]_{≤d} is definable in F (using N(d)-tuples), as is the graph of the multiplication F [X]_{≤d} × F [X]_{≤d} → F [X]_{≤2d}. [For that one fixes an enumeration m_{i} of all monomials in X such that if the degree of m_{i} is strictly less than the degree of m_{j} then i < j; thus the polynomial f(X) = ∑_{i=1}^{N(d)} a_{i}m_{i} ∈ F [X]_{≤}d is encoded by the N(d)-tuple (a_{1}, …, a_{N(d)}).]

(5.2) Bounds. The following result is classical, it was proved first by Hermann [He], later by Seidenberg [S] (and there is a proof using ultraproducts in [DS]). I state it in its entirety, although I will only need items (1) and (4). Theorem. Let n, d be positive integers, X = (X_{1}, …, X_{n}).

(1) There is a constant A = A(n, d) such that for every field F, polynomials f_{1}, …, f_{m}, g ∈ F [X]_{≤d}, if g belongs to the ideal of F [X] generated by f_{1}, …, f_{m}, then there are h_{1}, …, h_{m} ∈ F [X]_{≤A} such that g = ∑_{i=1}^{m} f_{i}h_{i}.

(2) There is a constant B = B(n, d) such that for every field F, for every ideal I of F [X] generated by elements of F [X]_{≤d} and for every g ∈ F [X]_{≤d}, if g^{k} ∈ I for some integer k, then g^{B} ∈ I.

(3) There is a constant C = C(n, d) such that for every field F, ideals I and J generated by elements of F [X]_{≤d}, the ideals I ∩J and J : I = {f ∈ F [X] | fI ⊆ J} are generated by elements of F [X]_{≤C}.

(4) There is a constant D = D(n, d) such that for every field F and ideal I of F [X] generated by elements of F [X]_{≤d}, if I is not prime, then there are g, h ∈ F [X]_{≤D} such that gh ∈ I but g, h ∉ I.

(5) There is a constant E = E(n, d) such that for every field F and ideal I of F [X] generated by elements of F [X]_{≤d}, there are at most E minimal prime ideals containing I, and they are generated by elements of F [X]_{≤E}.

Note that the number m will be bounded by the number N(d) of monomials of degree ≤ d.

(5.3) Corollary. Let n ≥ 1. There is a formula φ(y), y an mN(d)-tuple of variables, such that in every field F, for every mN(d)-tuple a in F, if f_{1}, …, f_{m} is the m-tuple of elements of F [X]_{≤d} encoded by a, then

F ⊧ φ(a) ⟺ the ideal of F [X] generated by f_{1}, …, f_{m} is prime.

Proof. Let D = D(n, d), A = A(n, D). Then f_{1}, …, f_{m} generate a prime ideal I in F [X] if and only if for all g, h ∈ F [X]_{≤D}, either gh ∉ I or one of g, h is in I, if and only if for all g, h ∈ F [X]_{≤D}, either for all h_{1}, …, h_{m} ∈ F [X]_{≤A}, gh ≠

∑_{i=1}^{m} h_{i}f_{i}, or there are h_{1}, …, h_{m} ∈ F [X]_{≤A} such that [g = ∑_{i=1}^{m} h_{i}f_{i} or h = ∑_{i=1}^{m} h_{i}f_{i}].

This last statement is clearly an elementary property of the mN(d)-tuple a of coefficients of f_{1}, …, f_{m}.

(5.4) Corollary. Let n ≥ 1. There is a quantifier-free formula ψ(y), y an mN(d)-tuple of variables such that in every field F, for every mN(d)-tuple a in F, if f_{1}, …, f_{m} is the m-tuple of elements of F [X]_{≤d} encoded by a, then

F ⊧ ψ(a) ⟺ the ideal of F^{alg}[X] generated by f_{1}, …, f_{m} is prime.

Proof. Take the formula φ(y) given by (5.3). By quantifier-elimination of the theory of algebraically closed fields, there is a quantifier-free formula ψ(y) such that in every algebraically closed field K, for every mN(d)-tuple a in K we have

K ⊧ φ(a) ⟺ K ⊧ ψ(a).

But if the tuple a is in the subfield F of K, we have

K ⊧ ψ(a) ⟺ F ⊧ ψ(a).

Thus F ⊧ ψ(a) if and only if the m-tuple (f_{1}, …, f_{m}) of F [X]_{≤d} encoded by a generates a prime ideal in F^{alg}[X].

(5.5) Pseudo-algebraically closed fields. A field F is pseudo-algebraically closed (abbreviated by PAC) if every variety V defined over F has an F -rational point. Using the above, we therefore get: Corollary. There is a theory (in the language of rings) whose models are exactly the PAC fields.

(5.6) Side comments on PAC fields. Examples are: real closed fields, separably closed fields, and we will see also that ultraproducts of finite fields are PAC.

An algebraic extension of a PAC field is also PAC.

In order to show that a field F is PAC, it suffices to show: every (irreducible) curve C defined over F has infinitely many points with their coordinates in F.

6. Pseudo-finite fields and their elementary theory

In this section, we will introduce pseudo-finite fields, study their theory, and show that they are the infinite models of the theory of finite fields.

(6.1) Definition. A field F is pseudo-finite iff it satisfies the following three conditions. P1 F is perfect (i.e., either char(F) = 0 or if char(F) = p > 0 then every element is a

p-th power). P2 For every n > 1, Gal(F^{alg}/F) ≃ ℤ̂. P3 Every variety V defined over F has an F -rational point.

(6.2) Lemma. There is a set of sentences (in the language of rings) whose models are exactly the pseudo-finite fields, and we denote this set (or rather, the deductive closure of this set) by Psf.

Proof. In other words, we need to show that these properties can be expressed by sentences.

Property P1 is easy: you add a collection of sentences saying that if p = 0 then ∀x∃y y^{p} = x (p is the term 1 + 1 + ⋯ + 1, p-times).

Property P3 is an infinite collection of sentences θ_{n,d}, one for each pair (n, d). The sentence θ_{n,d} will say: for every variety V defined by polynomials in F [X_{1}, …, X_{n}]_{≤d}, there exists x ∈ V.

Property P2 is a little more complicated. We will show below that it is enough to find a collection of sentences, one for each n > 1, expressing that F has exactly one algebraic extension of degree n. Let us assume this result, and fix some n > 1.

Consider the formula Irr(y) where y = (y_{1}, …, y_{n}) which says: ∀z_{1}, …, z_{n}, for all 1 ≤ d < n the polynomials X^{n} + y_{1}X^{n−1} + ⋯ + y_{n} and (X^{d} + z_{1}X^{d−1} + ⋯ + z_{d})(X^{n−d} + z_{d+1}X^{d−1} + ⋯ + z_{n}) are not equal.

It is clear that it is a first-order formula, and it exactly says that the polynomial X^{n} + y_{1}X^{n−1} + ⋯ + y_{n} is irreducible (over F).

Thus the sentence ∃y Irr(y) will guarantee that F has at least one algebraic extension of degree n.

In order to show that having exactly one extension of degree n is an elementary property of the field F, we will express the following fact in a first-order way: if Irr(y) and Irr(y′) hold, then the algebraic extension obtained from F by adjoining a root of the polynomial X^{n} + ∑_{i=1}^{n} y_{i}X^{n−i} contains a root of the polynomial X^{n} + ∑_{i=1}^{n} y′_{i}X^{n−i}.

To do that, we will show that if Irr(a) holds in F, and α is a root of the polynomial X^{n} + ∑_{i=1}^{n} a_{i}X^{n−i}, then the structure (F (α), +, ×, 0, 1, P_{F}) is definable in F, where +, ×, 0, 1 are the usual addition, multiplication and constants on the field F (α), and P_{F} is a predicate for the subfield F. The idea is to view F (α) as an F -vector space with basis {1, α, …, α^{n−1}}, and to define in this vector space operations that make it isomorphic to the field F (α).

We let S = F^{n}, +^{∗} the usual addition on the vector space S, and 0^{∗} = (0, 0, …, 0), 1^{∗} = (1, 0, …, 0), P_{F}^{∗} the set of elements {(b, 0, …, 0) | b ∈ F }. Clearly these sets, elements and relations are definable in F, with no parameters.

Multiplication by α induces a linear transformation of the vector space F (α), and its matrix is

M_{α} = ( \begin{matrix}0 & 0 & ⋯ & 0 & −a_{n} \\ 1 & 0 & ⋯ & 0 & −a_{n−1} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 1 & −a_{1} \end{matrix} )

since α^{n} = − ∑_{i=1}^{n} a_{i}α^{n−i}. Note that multiplication by α^{i} is also a linear transformation, and its matrix is simply M_{α}^{i}. So, we define ×^{∗} as follows

(x_{1}, …, x_{n}) ×^{∗} (y_{1}, …, y_{n}) = (x_{1}I_{n} + x_{2}M_{α} + ⋯ x_{n}M_{α}^{n−1}) ( y_{1} ; y_{2} ; ⋮ ; y_{n} ) .

Here I_{n} denotes the identity (n × n)-matrix. Observe that the definition of ×^{∗} uses the tuple (a_{1}, …, a_{n}), but is totally uniform.

Hence, there is a formula θ^{∗}(y) of the language of fields, such that if Irr(b) holds for some n-tuple b in F and β is a root of X^{n} + ∑_{i=1}^{n−1} b_{i}X^{n−i}, then

F ⊧ θ^{∗}(b) if and only if F (β) satisfies that if c is an n-tuple of elements of F which satisfies Irr(x) in F, then ∃z z^{n} + ∑_{i=1}^{n} c_{i}z^{n−i}.

(6.3) Lemma. Let F be a perfect field, and assume that Gal(F^{alg}/F) ≃ ℤ̂. Let E be an elementary extension of F. Show that Gal(E^{alg}/E) = ℤ̂, that F^{alg} ∩ E = F and that E^{alg} = EF^{alg}.

Proof. Exercise.

(6.4) Theorem. Let Q be the set of all prime powers, and let U be a non-principal ultrafilter on Q. Then the field F^{∗} = ∏_{q∈Q} 𝔽_{q} is a pseudo-finite field.

Proof. Since each 𝔽_{q} is prefect, F^{∗} is perfect. Also, each 𝔽_{q} satisfies all axioms of P2, and therefore so does F^{∗}. However, no finite field 𝔽_{q} will satisfy all axioms in P3. Indeed, fix q, and consider the algebraic set V defined by

Y ∏_{0≤i<j≤q}(X_{i} − X_{j}) = 1.

One verifies easily that this set is a variety (it coordinate ring is 𝔽_{q}[X_{0}, …, X_{q}, ∏_{0≤i<j≤q}(X_{i}− X_{j})^{−1}], which is a domain, and whose field of fractions is purely transcendental over 𝔽_{q}), but it cannot have an 𝔽_{q}-rational point, since 𝔽_{q} only has q distinct elements. However, this is essentially the only problem. A result of Lang-Weil (see below (6.5)) will tell us that any axiom θ_{n,d} occurring in P3 will hold in all sufficiently large 𝔽_{q}’s. Hence given n, d, the set of q ∈ Q such that 𝔽_{q} satisfies θ_{n,d} is cofinite, and therefore must be in U. By Łos’ theorem, F^{∗} satisfies all θ_{n,d}.

(6.5) The theorem of Lang-Weil. For every positive integers n, d, there is positive constant C (= C(n, d)) such that for every finite field 𝔽_{q} and variety V defined by polynomials in 𝔽_{q}[X_{1}, …, X_{n}]_{≤d},

||V (𝔽_{q})| − q^{dim(V)}| ≤ Cq^{dim(V)−1/2}.

[Recall that V (𝔽_{q}) is the set of points of V ∩ 𝔽_{q}^{n}, and dim(V) is the dimension of V, i.e., tr.deg(𝔽_{q}(V)/𝔽_{q}).]

In particular, if q > C^{2}, then any variety V as above will have a rational point in 𝔽_{q}. Indeed, we get

0 < −Cq^{dim(V)−1/2} + q^{dim(V)} ≤ |V (𝔽_{q})|.

The constant C can in fact be effectively computed.

(6.6) Recall that we want to show that the pseudo-finite fields are exactly the models of the theory T_{f} consisting of all sentences true in all finite fields. For that, we will study the completions of Psf, and show that any pseudo-finite field is elementarily equivalent to an ultraproduct of finite fields. In fact a stronger statement is true: a pseudo-finite field of characteristic 0 is elementarily equivalent to an ultraproduct of fields 𝔽_{p}, p ranging over all primes. But for that, we need first to find the elementary invariants of pseudo-finite fields. The results given below will also allow us to show that the completions of Psf are model complete if one enlarges the language in a certain way.

(6.7) Lemma. Let F be a perfect PAC field.

(1) Let a be a tuple in some field containing F, and assume that the field F (a) is a regular extension of F. Then there is an F -morphism F [a] → F.

(2) Assume that F is ℵ_{1}-saturated, that A is a countable subset of some field containing F and that F (A) is a regular extension of F. Then there is an F -morphism F [A] → F.

Proof. (1) Consider the ideal I(a/F) = {f(X) ∈ F [X] | f(a) = 0}, where X is a tuple of the same length as a. Then F [a] ≃ F [X]/I(a/F), and our regularity assumption tells us that the algebraic set V defined by I(a/F) is a variety. Hence there is b ∈ V (F). The map which sends a to b extends to an F -morphism F [a] → F: by definition of V, b satisfies all polynomial equations over F which are satisfied by a.

(2) Finding this map is the same thing as finding some subset B of F which satisfies all equations satisfied by the (infinite) tuple A. Use (1) and ℵ_{1}-saturation.

(6.8) The embedding lemma. Let K, E, F be perfect fields, with K ⊂ E, F, F and E are regular extensions of K, E is countable and F is an ℵ_{1}-saturated pseudo-finite field. Assume that we have a continuous isomorphism Φ : Gal(F^{alg}/F) → Gal(E^{alg}/E) such that for every a ∈ K^{alg} and σ ∈ Gal(F^{alg}/F), Φ(σ)(a) = σ(a).

Then there is a K^{alg}-embedding φ : E^{alg} → F^{alg} such that F is a regular extension of φ(E), and for every a ∈ E^{alg} and σ ∈ Gal(F^{alg}/F),

φ(Φ(σ)(a)) = σ(φ(a)).

Comments. (1) Since all fields are perfect, the regularity of F over K is equivalent to K^{alg} ∩ F = F.

(2) What is important in this result, is the fact that there is a K-embedding φ of E into F such that F is a regular extension of φ(E).

(3) Because E and F are regular extensions of K, the restriction maps Gal(E^{alg}/E) → Gal(K^{alg}/K) and Gal(F^{alg}/F) → Gal(K^{alg}/K) are onto. Thus the first condition on Φ simply tells us that the following diagram commutes:

Gal(F^{alg}/F)  ⟶^{Φ}  Gal(E^{alg}/E)
↘  ↙
Gal(K^{alg}/K)

The second condition on Φ simply tells us that it coincides with the map induced by φ from Gal(F^{alg}/F) to Gal(E^{alg}/E), σ ↦ φ^{−1}σφ. Proof of the embedding lemma. We work inside a large algebraically closed field Ω, and we may actually “move” E and assume that it is linearly disjoint from F over K, so that E^{alg} and F^{alg} are linearly disjoint over K^{alg}. Indeed, replacing E^{alg} by a K^{alg}-isomorphic copy ψ(E), it suffices to solve the problem for ψ(E), replacing Φ by the map Ψ^{−1}Φ, where Ψ : Gal(ψ(E^{alg}/ψ(E)) → Gal(E^{alg}/E) is the map σ ↦ ψ^{−1}σψ. Getting the embedding φ of ψ(E^{alg}) into F^{alg} will then give us the desired embedding of E^{alg} into F: simply take φψ.

Because E^{alg} and F^{alg} are linearly disjoint over K^{alg}, and because E and F are regular extensions of K, we get that E and F are linearly disjoint over K. We also get that

Gal(E^{alg}F^{alg}/EF) ≃ Gal(E^{alg}/E) ×_{Gal(K^{alg}/K)} Gal(F^{alg}/F),

where the right-hand-side group denotes the set of elements (σ_{1}, σ_{2}) of Gal(E^{alg}/E) × Gal(F^{alg}/F) such that σ_{1}|_{K^{alg}} = σ_{2}|_{K^{alg}}. Indeed, one shows (easily) that the Galois extensions E^{alg}F and EF^{alg} are linearly disjoint over EF K^{alg}, and the result follows by Galois theory.

An alternate way of looking at it is to notice that the field E^{alg}F^{alg} is simply the field of fractions of E^{alg} ⊗_{K^{alg}} F^{alg}. If σ_{1} ∈ Gal(E^{alg}/E) and σ_{2} ∈ Gal(F^{alg}/F) have the same restriction to K^{alg}, one then defines (σ_{1}, σ_{2})(a ⊗ b) = σ_{1}(a) ⊗ σ_{2}(b) for a ∈ E^{alg} and b ∈ F^{alg}, and then checks that this extends to an automorphism of E^{alg} ⊗_{K^{alg}} F^{alg}.

Under this identification, because of our condition on Φ, the graph of Φ^{−1} can be naturally viewed as a closed subgroup H of Gal(E^{alg}F^{alg}/EF). Moreover, if σ_{0} ∈ Gal(F^{alg}/F) is a topological generator of Gal(F^{alg}/F), then the element τ_{0} = (Φ(σ_{0}), σ_{0}) is a topological generator of H (and of course Φ(σ_{0}) is a topological generator of Gal(E^{alg}/E)). Observe that the map τ_{0} ↦ σ_{0} defines an isomorphism between H and Gal(F^{alg}/F).

Extend τ_{0} to an automorphism τ of (EF)^{alg}, and let M be the subfield of (EF)^{alg} of elements fixed by τ. Then, because τ|_{E^{alg}} = Φ(σ_{0}) and τ|_{F^{alg}} = σ_{0}, we have

M ∩ E^{alg} = E, M ∩ F^{alg} = F,

i.e., M is a regular extension of E and of F. Observe also that the restriction maps H = Gal((EF)^{alg}/M) → Gal(E^{alg}/E) and H → Gal(F^{alg}/F) being isomorphisms (because they are epimorphisms, and all groups are isomorphic to ℤ̂), we obtain that

(EF)^{alg} = ME^{alg} = MF^{alg}.

Because M contains F, the field MF^{alg} is in fact the ring generated by M and F^{alg}. Because E is countable, there is some countable subfield M_{0} of M containing E and such that F^{alg}[M_{0}] contains E^{alg}. Then, F (M_{0}) is contained in M and is therefore a regular extension of F. By Lemma (6.7), there is an F -morphism F [M_{0}] → F, and because F^{alg} and F M_{0} are linearly disjoint over F, this morphism extends to an F^{alg}-morphism φ : F^{alg}[M_{0}] → F^{alg}. This is our desired φ.

Observe first that since M_{0} contains E, we have φ(E) ⊂ F. We need to show that Φ coincides with the map induced by φ on the Galois groups. So, let a ∈ E^{alg}, and write it a = ∑_{i} m_{i}b_{i} for some m_{i} ∈ M_{0} and b_{i} ∈ F^{alg}. Then

Φ(σ_{0})(a) = τ(a) = ∑_{i} τ(m_{i})τ(b_{i}) = ∑_{i} m_{i}σ_{0}(b_{i})

because τ is the identity on M and τ|_{F^{alg}} = σ_{0}. Thus

φ(Φ(σ_{0})(a)) = ∑_{i} φ(m_{i})σ_{0}(b_{i})

because φ is the identity on F^{alg}. On the other hand we have

σ_{0}(φ(a)) = σ_{0}(∑_{i} φ(m_{i})b_{i}) = ∑_{i} φ(m_{i})σ_{0}(b_{i})

because the φ(m_{i}) are in F. This gives us the desired equality. Because σ_{0} is a topological generator of Gal(F^{alg}/F), if σ ∈ Gal(F^{alg}/F) and a ∈ E^{alg}, then σ(φ(a)) = σ_{0}^{j}(φ(a)) for some integer j, and thus we get the desired result.

To show that F is a regular extension of φ(E), it suffices to show that φ(E)^{alg} ∩ F = φ(E). Let a ∈ E^{alg}. Then

φ(a) ∈ F ⟺ σ_{0}(φ(a)) = φ(a)
⟺ φ(Φ(σ_{0})(a)) = φ(a)
⟺ Φ(σ_{0})(a) = a
⟺ a ∈ E.

(6.9) Comments. This is a rather weak version of the embedding lemma. The full version of this lemma can be obtained by changing some of the hypotheses and the conclusion. Here are the changes to be made:

– F does not need to be pseudo-finite, only PAC (but it is still ℵ_{1}-saturated and perfect).

– Φ is a (continuous) epimorphism from Gal(F^{alg}/F) → Gal(L/E), where L is a Galois extension of E.

The conclusion on the regularity of the extension F of φ(E) is then replaced by: φ(L) ∩ F = φ(E).

The strategy of the proof is essentially the same. Again, one has the graph H of Φ sitting as a closed subgroup of Gal(F^{alg}/F)×_{Gal(K^{alg}/K)}Gal(E^{alg}/E), and one uses the fact that H ≃ Gal(F^{alg}/F) is projective to “lift” H to a closed subgroup of Gal((EF)^{alg}/EF). See the book Field arithmetic by Fried and Jarden [FJ].

There is also a version of this lemma for imperfect PAC fields.

(6.10) Corollary. Let K_{1}, K_{2}, E, F be perfect fields, with E a regular extension of K_{1}, F a regular extension of K_{2}, E countable and F pseudo-finite ℵ_{1}-saturated. Assume that we have an isomorphism Φ : Gal(F^{alg}/F) → Gal(E^{alg}/E) and an isomorphism φ_{0} : K_{1}^{alg} → K_{2}^{alg} satisfying for all a ∈ K_{1}^{alg} and σ ∈ Gal(F^{alg}/F),

φ_{0}(Φ(σ)(a)) = σ(φ_{0}(a)).

Then φ_{0} extends to an embedding φ : E → F such that F is a regular extension of φ(E), and for all a ∈ E^{alg} and σ ∈ Gal(F^{alg}/F),

φ(Φ(σ)(a)) = σ(φ(a)).

Proof. If K_{1}^{alg} = K_{2}^{alg} and φ_{0} is the identity, then this is simply (6.8). We will show how to reduce to the situation of that lemma. Extend φ_{0} to an isomorphism ψ defined on E^{alg}. Now apply the previous lemma to the situation (ψ(E^{alg}), F^{alg}, Ψ^{−1}Φ) where Ψ : Gal(ψ(E)^{alg}/ψ(E)) → Gal(E^{alg}/E) is the map σ ↦ ψ^{−1}σψ. One needs of course to verify that they satisfy the hypotheses of Lemma (6.8), but this is easily done, since ψ extends φ_{0}. One then finds a K_{2}^{alg}-embedding ρ of ψ(E)^{alg} into F^{alg} satisfying the conclusions of (6.8). Take φ = ρψ, and verify that it works.

(6.11) Proposition. Let E and F be pseudo-finite fields, K a common subfield which is perfect and such that E and F are regular extensions of K. Then

E ≡_{K} F.

Proof. By ≡_{K} we mean that E and F are elementarily equivalent in the language L(K) of rings to which one has added constants for the elements of K. First of all we may assume that K is countable (since K can be expressed as a union of perfect subfields which are countable and relatively algebraically closed in E and F). Then, we may assume that E and F are ℵ_{1}-saturated: indeed, let E^{∗} and F^{∗} be elementary extensions of E and F respectively, and which are ℵ_{1}-saturated (see (1.22) for the existence). Then

E ≡_{K} F ⟺ E^{∗} ≡_{K} F^{∗}.

Step 1. Let E_{0} ≺ E be countable and containing K. Then E is a regular extension of E_{0}, and E_{0} is a regular extension of K. We want to apply the embedding Lemma (6.8), but for that we need to find the isomorphism Φ. Let σ_{1} be a topological generator of Gal(F^{alg}/F), and consider its restriction σ_{0} to K^{alg}. Then σ_{0} extends to a topological generator σ_{2} of Gal(E^{alg}/E) (see (3.8)) and sending σ_{1} to σ_{2} will define a group isomorphism Φ between Gal(F^{alg}/F) and Gal(E^{alg}/E) (which are both isomorphic to ℤ̂). By definition, σ_{1} and σ_{2} have the same action on K^{alg}.

By Lemma (6.3), the restriction map Gal(E^{alg}/E) → Gal(E_{0}^{alg}/E_{0}) is an isomorphism, and we let Φ_{0} be the composition of Φ with this isomorphism.

By (6.10), there is a K^{alg}-embedding φ_{0} : E_{0}^{alg} → F^{alg}, such that F is a regular extension of φ_{0}(E_{0}), and the map Gal(F^{alg}/F) → Gal(E_{0}^{alg}/E_{0}) dual to φ_{0} coincides with Φ_{0}. Step 2. Let F_{0} ≺ F be countable and contain φ_{0}(E_{0}). We want to find an embedding of F_{0} into E which extends φ_{0}^{−1} and has certain properties. Obviously we will use (6.10). Because F_{0} ≺ F, the restriction map Gal(F^{alg}/F) → Gal(F_{0}^{alg}/F_{0}) is an isomorphism, and this allows us (by composing it with Φ^{−1}) to get an isomorphism Ψ_{0} : Gal(E^{alg}/E) → Gal(F_{0}^{alg}/F_{0}) such that the tuple (E, F_{0}, φ_{0}^{−1}, Ψ_{0}) satisfies the hypotheses of (6.10).

Hence there is some ψ_{0} : F_{0}^{alg} → E^{alg}, which extends φ_{0}^{−1}, and is such that E is a regular extension of ψ_{0}(F_{0}), and the map Gal(E^{alg}/E) → Gal(F_{0}^{alg}/F) dual to ψ_{0} coincides with Ψ_{0}. Step 3. We now use the same technique as in step 2 to build inductively sequences of partial isomorphisms φ_{i} and ψ_{i} such that:

(i) The domain of φ_{i} is an elementary substructure E_{i} of E and F is a regular extension of the image of φ_{i}; the domain of ψ_{i} is an elementary substructure of F, and E is a regular extension of the image of ψ_{i}.

(ii) Each ψ_{i} extends φ_{i}^{−1}, and each φ_{i+1} extends ψ_{i}^{−1}.

Consider now E_{ω} = ⋃_{i∈ℕ} E_{i} and F_{ω} = ⋃_{i∈ℕ} F_{i}. Then E_{ω} ≺ E and F_{ω} ≺ E. Moreover, E_{ω} ≃_{K} F_{ω}: take ⋃_{i} φ_{i} (= ⋃_{i} ψ_{i}^{−1}). Since E_{ω} and F_{ω} are K-isomorphic, we have E_{ω} ≡_{K} F_{ω}. From E_{ω} ≺ E and F_{ω} ≺ F, we deduce E ≡_{K} F.

(6.12) Corollary. Let E ⊂ F be pseudo-finite fields. Then E ≺ F ⟺ E^{alg} ∩ F = E. Proof. Immediate by (6.11).

(6.13) Theorem. Let E and F be pseudo-finite fields, and K a common subfield. Then

E ≡_{K} F ⟺ E ∩ K^{alg} ≃_{K} F ∩ K^{alg}.

Proof. First note that since E and F are perfect, E∩K^{sep} ≃_{K} F ∩K^{sep} ⟺ E∩K^{alg} ≃_{K} F ∩ K^{alg}.

Assume that E ≡_{K} F, and let N be the set of all finite Galois extensions of K. For each L ∈ N, we consider the set S_{L} = {σ ∈ Gal(K^{alg}/K) | σ(E ∩ L) = F ∩ L}. This set is a union of cosets of the open subgroup Gal(K^{alg}/L), and is therefore open and closed. If L ⊆ M ∈ N, then S_{M} ⊆ S_{L}; hence if L, M ∈ N, then S_{L} ∩ S_{M} ⊇ S_{LM}. It therefore suffices to show that each S_{L} is non-empty: if we do that, we will have shown that any finite intersection of S_{L}’s is non-empty. By compactness of Gal(K^{alg}/K), it will follow that ⋂_{L∈N} S_{L} is non-empty, i.e., that E ∩ K^{alg} ≃_{K} F ∩ K^{alg}. Fix L ∈ N, and α ∈ L such that E ∩ L = K(α) (this is where we use the separability of L over K). Let f(X) ∈ K[X] be the minimal polynomial of α over K. Then E ⊧ ∃x f(x) = 0, and therefore F ⊧ ∃x f(x) = 0. Thus there is a K-embedding of E ∩ L into F ∩ L, by some σ ∈ Gal(L/K), and hence [F ∩ L : K] ≥ [E ∩ L : K]. Reasoning similarly with F ∩ L, we obtain that [E ∩ L : K] ≥ [F ∩ L : K] and therefore [E ∩ L : K] = [F ∩ L : K], i.e., σ(E ∩ L) = F ∩ L, and S_{L} ≠ ∅.

This shows one direction. For the other, fix some K-isomorphism φ_{0} : E ∩ K^{alg} → F ∩ K^{alg}, and extend it to a K-isomorphism φ defined on E. Then E ≡_{K} φ(E) because φ is a K-isomorphism, and φ(E) ≡_{F ∩K^{alg}} F by Proposition (6.11). Remark. The left-to-right direction holds for arbitrary fields. Let E and F be fields, K a common subfield. Then E ≡_{K} F implies E ∩ K^{alg} ≃_{K} F ∩ K^{alg}. If E and F are perfect, then the above proof works with no change, and also if K is perfect. If K is not perfect, then in particular K is infinite and one sets N to be the set of all finite normal extensions of K, and defines S_{L} as before. If L_{1}, …, L_{n} are the conjugates of L∩F over K (under the action of Aut(L/K)), one then shows (as in the separable case) that for every a ∈ E ∩ L, there is some i such that a ∈ L_{i}. Then the result follows from Lemma. Let K be an infinite field, and V, V_{1}, …, V_{n} subspaces of the K-vector space W. If V ⊆ V_{1} ∪ ⋯ ∪ V_{n}, then V ⊆ V_{i} for some i.

The proof of this lemma is by induction on n. If n = 1 there is nothing to prove. If V_{1} ∩ V ⊆ V_{2} ∪ ⋯ ∪ V_{n}, then actually V ⊆ V_{2} ∪ ⋯ ∪ V_{n} and we are done by induction hypothesis. So, assume that V_{1} ∩ V ⊄ V_{2} ∪ ⋯ ∪ V_{n}, take a ∈ V ∩ V_{1}, a ∉ V_{2} ∪ ⋯ ∪ V_{n} and b ∈ V. For every k ∈ K, we have a + bk ∈ V, and therefore there is some i such that a + bk ∈ V_{i}. Because K is infinite, there are k ≠ ℓ ∈ K and i such that a + bk and a + bℓ belong to the same V_{i}. Then (a + bk) − (a + bℓ) = b(k − ℓ) ∈ V_{i}, which implies that b ∈ V_{i}, a ∈ V_{i} and therefore i = 1, V ⊆ V_{1}.

(6.14) Theorem. The completions of Psf are obtained by specifying the characteristic, and adding a collection of sentences of the form ∃t f(t) = 0 and ∀t f(t) ≠ 0, where f(T) ranges over all polynomials in the single variable T and with coefficients in ℤ. Proof. This is a direct consequence of (6.13), or rather of its proof: the isomorphism type of the relative algebraic closure of the prime field inside a field can be described by a conjunction of sentences of that form.

(6.15) Theorem. Let φ(x) be a formula. Then there is a formula ψ(x) which is a Boolean combination of formulas of the form ∃t f(x, t) = 0, where f(X, T) is a polynomial over ℤ, T a single variable (and X a tuple of variables of the same length as x). Proof. This follows from Corollary (1.4) and (the proof of) Theorem (6.13). Indeed, let Δ be the set of Boolean combinations of formulas of the form ∃t f(x, t) = 0, where f(X, T) is a polynomial over ℤ, T a single variable. This set is clearly closed under disjunctions. By Corollary (1.4), we need to show that if E is a pseudo-finite field, a a tuple in E satisfying φ(x), and if F is another pseudo-finite field, and b a tuple in F which satisfies (in F) all formulas in Δ which are satisfied by a in E, then F ⊧ φ(b).

So, let E, a and F, b be as above. Note that the formula expressing that p = 0 is in Δ (nothing prevents the polynomial f(X, T) to be constant). Hence our hypothesis implies that the prime subfields k of E and F are isomorphic. Similarly, the tuples a and b satisfy exactly the same equations over ℤ (hence over ℤ/pℤ if the characteristic is p), and this implies that there is an isomorphism ψ between the subrings k[a] of E and k[b] of F which sends a to b. This isomorphism extends to an isomorphism ψ between the subfields k(a) and k(b). Our assumption on a and b satisfying the same formulas from Δ says that if f(a, T) ∈ k[a][T], then

E ⊧ ∃t f(a, t) = 0 ⟺ F ⊧ ∃t f(b, t) = 0.

It follows that the isomorphism ψ extends to an isomorphism between k(a)^{alg} ∩ E and k(b)^{alg} ∩F. The fact that F ⊧ φ(b) now follows from the more general version of Theorem (6.13): Theorem (6.13)’. Let E and F be pseudo-finite fields, K_{1} a subfield of E and K_{2} a subfield of F. Assume that we have an isomorphism ψ between K_{1} and K_{2}. Then

(E, a)_{a∈K_{1}} ≡ (F, ψ(a))_{a∈K_{1}} ⟺ there is ψ′ ⊃ ψ such that ψ(E ∩ K_{1}^{alg}) = F ∩ K_{2}^{alg}.

[Here (E, a)_{a∈K_{1}} ≡ (F, ψ(a))_{a∈K_{1}} means that in the language L(K_{1}), the constant corresponding to a ∈ K_{1} is interpreted in F by the element ψ(a).] Proof. Extend ψ to some isomorphism θ defined on E. Then (E, a)_{a∈K_{1}} ≡ (θ(E), ψ(a))_{a∈K_{1}}. By (6.13), we have

(θ(E), ψ(a))_{a∈K_{1}} ≡ (F, ψ(a))_{a∈K_{1}} ⟺ θ(E) ∩ K_{2}^{alg} ≃_{K_{2}} F ∩ K_{2}^{alg}

and the result follows: K_{2}-isomorphisms between θ(E) ∩ K_{2}^{alg} and F ∩ K_{2}^{alg} are in oneto-one correspondence with isomorphisms between E ∩ K_{1}^{alg} and F ∩ K_{2}^{alg} which extend ψ.

(6.16) Model completeness. We form the language L_{c} by adjoining to the language L of rings new constant symbols c_{i,n}, where 2 ≤ n ∈ ℕ and 1 ≤ i ≤ n. The theory Psf_{c} is obtained by adding to the theory Psf for each n an axiom stating that the polynomial X^{n} + ∑_{i=1}^{n} c_{i,n}X^{n−i} is irreducible.

Note that every pseudo-finite field expands to a model of Psf_{c}: if F is pseudo-finite, for each n choose the c_{i,n} to be the coefficients of some (monic) irreducible polynomial of degree n. Theorem. The theory Psf_{c} is model complete. Proof. Let E ⊆ F be models of Psf_{c}. If L is an algebraic extension of E of degree n, then L is generated over E by a solution of the equation X^{n} + ∑_{i=1}^{n} c_{i,n}X^{n−i}. Since F ⊧ Psf_{c}, this polynomial stays irreducible over F, i.e., F ∩ L = E. Then Corollary (6.12) gives us E ≡_{E} F, i.e., E ≺ F.

(6.17) Theorem. Let F be a pseudo-finite field, and S ⊂ F^{n} be definable. Then there is an algebraic set W ⊆ F^{n+m} such that, if π : F^{n+m} → F^{n} is the natural projection, then π(W) = S, and for each y ∈ S, the fiber π^{−1}(y) ∩ W is finite. Proof. We may assume that S is ∅-definable. Expand F to a model of Psf_{c}. By model completeness of Psf_{c}, we know that every formula φ(x) is equivalent modulo Psf_{c} to an existential formula (of L_{c}). Since an inequation x ≠ 0 is equivalent (modulo the theory of fields) to the formula ∃y xy = 1, we may assume that ψ(x) is positive, and therefore there is an algebraic set W ⊂ F^{n+m} such that π(W) = S. To check that W can be chosen so that the fibers are finite, we need to look a little closer at the way one obtains W.

By (6.15), we know that S is definable by a Boolean combination of formulas ∃t f(x, t) = 0, where f(X, T) ∈ ℤ[X, T], T a single variable. I.e., it is equivalent to a conjunction of disjunctions of formulas φ_{i}(x), where φ_{i}(x) is either ∃t f_{i}(x, t) = 0, or ∀t f_{i}(x, t) ≠ 0.

Step 1. Replace each formula φ_{i}(x) of the form ∃t f_{i}(x, t) = 0 by an L-formula ψ_{i}(x) expressing that either the polynomial f_{i}(x, T) is identically 0, (i.e., viewed as a polynomial in T its coefficients are all 0), or that some coefficient of f_{i}(x, T) has a multiplicative inverse and ∃t f_{i}(x, t) = 0. Thus ψ_{i}(x) is the conjunction of a (positive) quantifier-free formula in x, and of an existential formula ∃yρ_{i}(y, x) which is such that, in any field F, for any tuple a in F, the formula ρ_{i}(y, a) has only finitely many solutions. Step 2. Assume now that φ_{i}(x) is of the form ∀t f(x, t) ≠ 0.

We will show that it is equivalent modulo Psf_{c} to the disjunction of a formula which says that the polynomial f(x, T) is constant and takes a non-zero value (i.e., the conjunction of some equations with an existential formula saying that the constant coefficient is invertible), and of an existential formula ∃y ρ_{i}(x, y) = 0 where y is a tuple of variables, ρ_{i}(x, y) is a conjunction of equations, and for every field F and tuple a in F, the formula ρ_{i}(x, a) has only finitely many solutions in F.

For that, it suffices to say the following: let m be the degree of f(x, T) in T, and assume that f(x, T) is not identically constant. Then F does not contain a root of this polynomial if and only adding a root of this polynomial defines a proper extension of F. I.e., if and only if, in the Galois extension L of F of degree m! (which contains therefore all roots of f(x, T)), the polynomial f(x, T) can be written ∏_{i=1}^{m}(T − a_{i}) where the a_{i}’s are not in F. Using the interpretation of L in F (using the constants c_{i,m!}), we see that this is expressible by an existential formula (see (6.2)). The variables which appear in the formula ρ_{i} with an existential quantifier will be:

– variables for the coefficients b_{i,j} of the a_{i}’s with respect to the basis {1, α, …, α^{m!−1}, where α is a root of X^{m!}+∑ c_{i,m!}X^{m!−i}. Up to a permutation of the a_{i}’s, these are uniquely determined.

– variables c_{j} with 1 ≤ j ≤ m, which appear in the equation ∏_{i=2}^{m!} b_{i,j}c_{j} − 1 which implies that the element a_{j} is not in F.

This finishes the proof of the second step. Step 3. So we have shown that φ(x) is equivalent modulo Psf_{c} to a conjunction of disjunctions of positive existential formulas ∃yψ_{i}(x, y) where for each field F and tuple a, the set of elements satisfying ψ_{i}(a, y) is finite. The conclusion follows observing that the conjunction of two formulas ∃y ⋀ f_{1}(x, y) = ⋯ = f_{m}(x, y) = 0 and ∃y ⋀ g_{1}(x, y) = ⋯ = g_{n}(x, y) = 0 is (logically) equivalent to ∃y, z f_{1}(x, y) = ⋯ = f_{m}(x, y) = g_{1}(x, z) = ⋯ = g_{n}(x, z) = 0, and that their disjunction is equivalent (modulo the theory of fields) to ∃y, z ⋀_{i,j} f_{i}(x, y)g_{j}(x, z) = 0.

An alternate and more model-theoretic proof, is simply to use Corollary (1.4) and Theorem (6.13). But one still needs to use the trick given in Step 2. Try it as an exercise, considering the set Δ of existential formulas of the form ∃y ψ(x, y), where ψ(x, y) is a conjunction of equations, and satisfying that for every field F and tuple a the set ψ(a, y) is finite.

(6.18) Theorem. The pseudo-finite fields are exactly the infinite models of T_{f}. The pseudo-finite fields of characteristic 0 are exactly the infinite models of the set of sentences true in all prime fields. Proof. In order to prove the first assertion, by Proposition (1.27) we need to show that if F is a pseudo-finite field, then there is some non-principal ultrafilter U on the set Q of all powers of prime numbers, and such that

F ≡ ∏_{q∈Q} 𝔽_{q}/U, i.e., by (6.14), F ∩ k^{alg} ≃_{k} ( ∏_{q∈Q} 𝔽_{q}/U) ∩ k^{alg},

where k denotes the prime subfield of F. The proof is actually easier when char(F) > 0, but we will first do the case where char(F) = 0. In that case, note that the second assertion implies the first. Let F be a pseudo-finite field of characteristic 0 and write ℚ^{alg} as the union of an increasing chain L_{n}, n ∈ ℕ, of finite Galois extensions of ℚ. For each n, let E_{n} = L_{n} ∩F, and let I(n) be the (finite) set of subfields of L_{n} which properly contain E_{n}. We will find a sentence θ_{n} which describes L_{n} ∩ F. Choose a generator α of E_{n} over ℚ, and let f_{n}(T) be its minimal polynomial over ℚ. Similarly, for each M ∈ I(n), choose a generator β_{M} of M over ℚ, let g_{M}(T) be the minimal polynomial of β_{M} over ℚ, and define g_{n}(T) = ∏_{M∈I(n)} g_{M}(T). Consider now the sentence θ_{n} : ∃t f_{n}(t) = 0 ∧ ∀t g_{n}(t) ≠ 0. This is a sentence satisfied by F, and if E is any field of characteristic 0, then E ⊧ θ_{n} ⟺ E ∩ L_{n} ≃ E_{n}.

The formula θ_{0} ∧ ⋯ ∧ θ_{n} is still of the right form (since ⋀_{i} ∀t g_{i}(t) ≠ 0 is equivalent to ∀t ∏_{i} g_{i}(t) ≠ 0). It suffices to show that for every n, the set A_{n} = {p prime | 𝔽_{p} ⊧ θ_{0} ∧ ⋯ ∧ θ_{n}} is non-empty and infinite. Indeed, if U is an ultrafilter on the set P of all prime numbers and which contains all A_{n}’s, then for each n, we will have, by Łos’ theorem

F^{∗} = ∏_{p∈P} 𝔽_{p}/U ⊧ θ_{n},

so that we will obtain

F^{∗} ∩ ℚ^{alg} ≃ F ∩ ℚ^{alg}, i.e., F^{∗} ≡ F.

The infiniteness of the sets A_{n}’s follows from Tchebotarev’s theorem. The consequence of Tchebotarev’s theorem which we will use is : Let f_{1}(T), …, f_{m}(T), g(T) ∈ ℤ[T], T a single variable. Let L be the Galois extension of ℚ obtained by adjoining all roots of the polynomials f_{i}(T), i = 1, …, m. Assume that there is a subfield E of L such that Gal(L/E) is cyclic and

E ⊧ ⋀_{i=1}^{m} ∃t f_{i}(t) = 0 ∧ ∀t g(t) ≠ 0.

Then the set of prime numbers p such that 𝔽_{p} ⊧ ⋀_{i=1}^{m} ∃t f_{i}(t) = 0 ∧ ∀t g(t) ≠ 0 is infinite.

Let us now assume that F is of characteristic p > 0. If F ∩𝔽_{p}^{alg} is infinite, then let I be an infinite sequence of integers such that if n < m ∈ I then n|m and F ∩ 𝔽_{p}^{alg} = ⋃_{n∈I} 𝔽_{p^{n}}. Take for U any non-principal ultrafilter containing {p^{n} | n ∈ I}. One then verifies easily that a polynomial f(T) ∈ 𝔽_{p}[T] has a root in F if and only if it has a root in all but finitely many of the 𝔽_{p^{n}}, n ∈ I, if and only if it has a root in ∏_{n∈Q} 𝔽_{p^{n}}/U.

If F ∩ 𝔽_{p}^{alg} is finite, say of size p^{n}, then consider the set I = {p^{ℓn} | ℓ a prime }, and take for U any non-principal ultrafilter containing I. Again, one verifies that if F^{∗} = ∏_{m∈ℕ} 𝔽_{p^{m}}/U, then F^{∗} ∩ 𝔽_{p}^{alg} ≃ 𝔽_{p^{n}}.

(6.19) Corollary/Remark. Observe that we have shown the following: let k be a prime field, E and algebraic extension of k which has at most one algebraic extension of each degree. Then there is some pseudo-finite field F such that F ∩ k^{alg} ≃ E.

(6.20) Decidability issues. Observe first that by Theorem (6.18) we have

Psf ⊂ Psf_{0} ⊂ T_{prime} and Psf ⊂ T_{f} ⊂ T_{prime}.

We will first show that the theory Psf is decidable, that is, that there is an algorithm which decides, given a sentence θ, whether it is true in all pseudo-finite fields or not. From this we will be able to derive the decidability of the other theories.

We have an enumeration of a set Γ consisting of axioms for the theory Psf (this assumes that the bounds given in (5.2) on degrees of polynomials can be computed effectively, but they can). Hence, we can produce an enumeration of the set of all proofs made using axioms of Γ, and therefore of the theory Psf (by the completeness theorem, if a sentence is true in all pseudo-finite fields, then it is provable from Γ). Similarly, we have an enumeration of a set Γ_{0} of axioms for the theory Psf_{0} of all pseudo-finite fields of characteristic 0, and of the theory Psf_{0}. Note that Γ_{0} = Γ ∪ {p ≠ 0 | p a prime}.

This tells us that if θ is in Psf, then going through the enumeration of Psf we will find it. However, we need another procedure to decide if θ ∉ Psf. This is what we will do below. Let us fix a sentence θ.

Let ψ_{n}, n ∈ ℕ, be an enumeration of all sentences which are Boolean combinations of sentences of the form ∃t f(t) = 0, where f(T) ∈ ℤ[T]. By (6.15), we know that Psf ⊢ θ ↔ ψ_{n} for some n, i.e., θ ↔ ψ_{n} ∈ Δ, and therefore we can effectively find this ψ_{n}. Note that the proof of θ ↔ ψ_{n} uses only a finite number of axioms expressing the PAC property, and we can therefore find a constant C_{1} (given by Lang-Weil (6.5)) such that in all finite field 𝔽_{q} with q > C_{1} we have

𝔽_{q} ⊧ θ ↔ ψ_{n}.

It now remains to decide whether ψ_{n} is true in all pseudo-finite fields. I.e., we need to show that if k is a prime field, and E ⊂ k^{alg} has at most one algebraic extension of each degree, then E ⊧ ψ_{n}. Step 1 Decide whether ψ_{n} ∈ Psf_{0} or not.

Observe that ψ_{n} is (equivalent to) a disjunction of sentences of the form ⋀_{i} ∃t f_{i}(t) = 0 ∧ ∀t g(t) ≠ 0. If g(T) is not identically constant, then ℚ^{alg} |̸= ∀t g(t) ≠ 0, and therefore, we can assume that ψ_{n} is a disjunction of sentences of the form ⋀_{i} ∃t f_{i}(t) = 0. Let L be the splitting field of all polynomials appearing in ψ_{n}. Then one can compute effectively Gal(L/ℚ), as well as those subfields E of L such that Gal(L/E) is cyclic. Hence we an decide whether or not ψ_{n} is true in all subfields E of L such that Gal(L/E) is cyclic. If it is not, then ψ_{n} ∉ Psf_{0} and therefore ψ_{n} ∉ Psf, i.e., θ ∉ Psf_{0}, θ ∉ Psf. Step 2 Decide whether ψ_{n} ∈ Psf.

Assume that ψ_{n} ∈ Psf_{0}. The proof of ψ_{n} from Γ_{0} only uses finitely many axioms expressing that the characteristic is ≠ p, and therefore there is a constant C_{2} such that ψ_{n} holds in all pseudo-finite fields of characteristic p > C_{2}. It therefore remains to check whether ψ_{n} holds in all those of characteristic p ≤ C_{2}. Fix one such p. Then, as in step 1 we can assume that ψ_{n} is positive, and (because Gal(𝔽_{p}^{alg}/𝔽_{p}) is pro-cyclic), it suffices to check that 𝔽_{p} ⊧ ψ_{n}. This is certainly decidable. Step 3. Decidability of T_{f} and of T_{prime}.

We know that the equivalence θ ↔ ψ_{n} is true in all fields of size > C_{1}. If ψ_{n} ∉ Psf, then θ ∉ T_{f} and we are done. Assume that ψ_{n} ∈ Psf. Then θ is true in all fields of size > C_{1}, and we can decide whether or not it is true in all fields of size ≤ C_{1}. This gives the decidability of T_{f}.

Similarly for T_{prime}, we reduce to the case where ψ_{n} ∈ Psf_{0}. Then θ is true in all fields 𝔽_{p} with p > C_{1}, C_{2}, and it suffices to check what happens in the others. This shows the decidability of T_{prime}.

7. Measure, definability, and other applications

(7.1) Counting points. We saw in Theorem (6.18) that every pseudo-finite field is elementarily equivalent to an ultraproduct of finite fields. This implies in fact that every pseudo-finite field elementarily embeds into an ultraproduct of finite fields (an ultrapower of ultraproducts is an ultraproduct). Now, every finite field can be equipped with a measure (the counting measure), and one would think that the ultraproduct of these measures might define something interesting on F. It turns out that this is the case, and we will see below how it works. The main tool is the following Theorem. Let φ(x, y) be a formula, x an n-tuple of variables (y an m-tuple of variables). Then there is a finite set D ⊂ {0, 1, …, n} × ℚ^{>0} ∪ {(0, 0)} of pairs (d, μ), and a constant C > 0, formulas φ_{d,μ}(y) for (d, μ) ∈ D such that:

(1) If 𝔽_{q} is a finite field and a an m-tuple in 𝔽_{q}, then there is some (d, μ) ∈ D such that

||φ(𝔽_{q}, a)| − μq^{d}| < Cq^{d−1/2}.  (∗)

[Here φ(𝔽_{q}, a) denotes the set {b ∈ 𝔽_{q}^{n} | 𝔽_{q} ⊧ φ(b, a)}.]

(2) The formula φ_{d,μ}(y) defines in each 𝔽_{q} the set of tuples a such that (∗) holds. I am not going to give a proof of this result, although I will later sketch a strategy for

the proof. With some work one can show that the constant C can be found effectively, see [FHJ2], and also [[FS], [FHJ1]. First a few remarks.

(7.2) Remarks.

(1) Observe that the pair (0, 0) has been put in D to take care of the case when φ(𝔽_{q}, a) is empty.

(2) If φ(x, a) defines a variety V, then this is simply the Theorem of Lang-Weil, with d = dim(V) and μ = 1.

(3) Thus, if φ(x, a) defines an algebraic set W, all of whose irreducible components are defined over 𝔽_{q}, then d will be the maximal dimension of the irreducible components of W, and μ the number of these components of maximal dimension. Note that therefore, if φ(x, y) is quantifier-free, then the associated set of pairs will be contained in {0, …, n} × ℕ^{>0} ∪ {(0, 0)}.

(4) If q is sufficiently large, the formulas φ_{d,μ}(y) will define a partition of the parameter set 𝔽_{q}^{m}.

(5) If n = 1, then there are positive numbers A ∈ ℕ and r ∈ ℚ such that for every 𝔽_{q} and

tuple a in 𝔽_{q},

either |φ(𝔽_{q}, a)| < A or |φ(𝔽_{q}, a)| ≥ rq.

Indeed, let D be the set of pairs (d, μ) associated to φ(x, y); define A_{0} = sup{μ | (0, μ) ∈ D}, r_{0} = inf{μ | (1, μ) ∈ D}. Let r = r_{0}/2 and A = sup{A_{0} + C, 4C^{2}/r_{0}^{2}}. Using (∗), this gives the assertion.

(6) Observe that if q is sufficiently large, (0, μ) ∈ D and 𝔽_{q} ⊧ φ_{0,μ}(a), then, because q^{−1/2} becomes very small, and in particular < 1/2, the number μ must give the exact size of the set φ(𝔽_{q}, a) defined by φ(x, a).

(7.3) Some simple applications of this result.

(1) There is no formula of the language of rings which defines in each field 𝔽_{q}^{2} the subfield 𝔽_{q}.

(2) We know that the multiplicative group of 𝔽_{q} is cyclic, of order q − 1. There is no formula which defines in all fields 𝔽_{q} the set of generators of the multiplicative group 𝔽_{q}^{×}.

(3) Let G, H be groups definable in the pseudo-finite field F, and assume that f : G → H is definable, Ker(f) is finite, and dim(G) = dim(H) = d. Then

μ(G)[H : f(G)] = μ(H)|Ker(f)|.

Proof. (1) If φ(x) is a formula, there are A > 0 and r ∈ ℚ^{>0} such that for every finite field 𝔽_{q}, the size of the set defined by φ is either ≤ A or greater than rq. hence, we cannot have a formula which defines in all 𝔽_{q^{2}} a set of size \sqrt{q^{2}}.

(2) The function ϕ (called the Euler function) giving the number of generating elements of a cyclic group can be computed. Note that if m, n are relatively prime integers then ϕ(nm) = ϕ(n)ϕ(m) (since ℤ/mnℤ ≃ ℤ/nℤ × ℤ/mℤ). Also one has that ϕ(p^{n}) = (p − 1)p^{n−1}, since any lifting of a generator of ℤ/pℤ to ℤ/p^{n}/ℤ is a generator of ℤ/p^{n}ℤ.

First observe that if p^{n} > 2, then ϕ(p^{n}) ≥ \sqrt{n}. Hence, for every A ∈ ℕ, the set of integers n such that ϕ(n) < A is finite.

We will now show that for every ε > 0, there is some prime power q such that ϕ(q − 1) < ε(q − 1). Observe that

ϕ(n)/n = ∏_{ℓ a prime divisor of n}(1 − \frac{1}{ℓ}).

Fix some prime p, and let ℓ_{1}, …, ℓ_{m} be distinct prime numbers, M = ∏_{i=1}^{m}(ℓ_{i} − 1). Then for every i, we have p^{M} ≡ 1 mod(ℓ_{i}) and therefore ϕ(p^{M} − 1) ≤ (p^{M} − 1) ∏_{i=1}^{m}(1 − 1/ℓ_{i}). Hence we can find arbitrarily small values of \frac{ϕ(p^{M} −1)}{p^{M} −1}, which shows our assertion.

The existence of a formula defining the set of generators in all 𝔽_{q} would then, as in (1), contradict (7.2)(5).

(3) Let F^{∗} = ∏_{i∈I} 𝔽_{q_{i}}/U be an elementary extension of F, let a be a tuple of elements of F needed to define f, G and H (and their group law, and (a(i))_{i} a sequence such that [a(i)_{i}]_{U} = a.

Let φ_{1}(x, a) be the formula defining G, ψ_{1}(x, y, z, a) the one defining its group law, φ_{2}(x, a) the formula defining H, ψ_{2}(x, y, z, a) the one defining its group law, and θ(x, y, a) the formula defining the graph of f. The following property is then a first order property of the parameter a:

ψ_{i}(x, y, z, a) is the graph of a group operation on the set defined by φ_{i}(x, a) (i = 1, 2), and θ(x, y, a) is the graph of a group morphism between the set defined by φ_{1}(x, a) and the set defined by φ_{2}(x, a), whose kernel is of size m.

Hence, by Łos’ theorem, for a set J ∈ U, we have, for all j ∈ J, that the following statement holds in 𝔽_{q_{j}}: ψ_{1}(x, y, z, a(j)) is the graph of a group operation on the set G_{j} defined by φ_{1}(x, a(j)), ψ_{2}(x, y, z, a(j)) is the graph of a group operation on the set H_{j} defined by φ_{2}(x, a(j)), and θ(x, y, a(j)) is the graph of a group morphism f_{j} : G_{j} → H_{j}, whose kernel is of size m.

But G_{j} and H_{j} are finite!! Hence we have |G_{j}|[H_{j} : f_{j}(G_{j})] = |H_{j}||Ker(f_{j})|. For q_{j} sufficiently large, dividing by q_{j}^{d}, we get μ(G_{j})[H_{j} : f_{j}(G_{j})] = μ(H_{j})|Ker(f)|.

There is a first-order formula which expresses that fact, is satisfied in all 𝔽_{q_{j}} for j ∈ J, and therefore is satisfied by a in F^{∗}, whence also in F. This gives the result.

(7.4) Very rough sketch of the proof of Theorem (7.1). The result is proved by induction on the complexity of formulas.

Let us first assume that φ(x, y) is positive quantifier-free, that is, it is a disjunction of conjunction of equations (over ℤ).

Let 𝔽_{q} be a finite field, and a a tuple in 𝔽_{q}. Consider the set S defined by φ(x, a). Then S = W (𝔽_{q}), where W is the algebraic set given by the equations of φ(x, a). However, we do not know that the Theorem of Lang-Weil can tell us the estimate of how many points there are: we will be able to apply this theorem only if all irreducible components of W are defined over 𝔽_{q}. In order to be able to use Lang-Weil, we must therefore find an algebraic set W′ such that W′(𝔽_{q}) = W (𝔽_{q}) and all irreducible components of W′ are defined over 𝔽_{q}. This is done in the following fashion:

Write W = W_{1} ∪ ⋯ ∪ W_{m} where each W_{i} is irreducible over 𝔽_{q}. If W_{i} is a variety, then we know by Lang-Weil (6.5) that |W (𝔽_{q})| ∼ q^{dim(W_{i})} and we do nothing. If W_{i} is not a variety, then W_{i} has several irreducible components, and any point in W_{i}(𝔽_{q}) will belong to the intersection W′_{i} of these components, and we replace W_{i} by W′_{i}. We repeat the procedure and find eventually an algebraic set W′, all of whose irreducible components are defined over 𝔽_{q} and such that W′(𝔽_{q}) = W (𝔽_{q}). This procedure is effective, and using the results on bounds in polynomial rings, and we can write W′ = W′_{1} ∪⋯∪W′_{ℓ}, where the W′_{i} are varieties defined over 𝔽_{q}. If d is the maximum of the dimensions of the W′_{i}, and μ is the number of components of W′ of dimension d, the result of Lang-Weil will then give us that |W (𝔽_{q})| ∼ μq^{d}. One also knows that having dimension d is an elementary property of the coefficients of a set of polynomials defining a variety. Thus, there is a formula φ_{a}(y) satisfied by a in 𝔽_{q} and which expresses how we obtained W′ from W, and that W′ has exactly μ components of maximal dimension d. For each pair (𝔽_{q}, a) we can find such a formula. By compactness, there are a finite number of those, say φ_{1}(y), …, φ_{k}(y) such that in any finite field 𝔽, we have 𝔽 ⊧ ∀y (∃xφ(x, y)) ↔ (⋁_{j} φ_{j}(y)). To each formula φ_{j}(y) is associated a pair (d, μ), and we group them to obtain the desired φ_{d,μ}.

The case of a quantifier-free formula φ(x, y) follows, observing that modulo the theory of fields, an inequation z ≠ 0 is equivalent to ∃y yz = 1. Thus, every quantifier-free definable set is in bijection, via a projection, with an algebraic set. We then use the first case.

Let us now assume that φ(x, y) is arbitrary. Then, Theorem (6.17) tells us, using compactness, that there are positive quantifier-free L_{c}-formulas ψ_{1}(x, y, z), …, ψ_{m}(x, y, z) such that

Psf ⊢ ∀x, y (φ(x, y) ↔ ∃z ⋁_{j} ψ_{j}(x, y, z)),

and furthermore such that for some integer N, in any field F one has

F ⊧ ∀x, y (∃z ψ_{j}(x, y, z) → ∃^{≤N}z ψ_{j}(x, y, z)).

The same equivalence holds in sufficiently large finite fields, say of size ≥ C′ for some C′ (only depending on φ(x, y)). Given some sufficiently large finite field 𝔽 and tuple a in 𝔽, we know by the previous steps how to estimate the size of the sets defined by the formulas ψ_{i}(x, a, z). The problem is that the set defined by ⋁_{j} ψ_{j}(x, a, z) is not in bijection with the set defined by φ(x, a): given some x in that set, there may be several z such that ψ_{j}(x, a, z) holds. One uses a trick to transform the algebraic sets defined by the ψ_{j}, in such a way that we are able to count how many z are sitting above an x. Then we use some counting arguments and induction to conclude. The constant C of the Theorem will be sufficiently large so that, in field of size smaller than C′ (and in which we do not necessarily have the equivalence), the inequality still holds. E.g., one can choose C ≥ C′^{n}, where n = |x|.

(7.5) Definition of the measure on pseudo-finite fields. Let φ(x, y) be a formula (x and n-tuple of variables), and D, φ_{d,μ}(y) the set and formulas given by Theorem (7.1). It follows from Remark (7.2)(6) that if F is a pseudo-finite field and a a tuple in F, then there will be a unique pair (d, μ) ∈ D such that F ⊧ φ_{d,μ}(a). We then define dim(φ(x, a)) = d and μ(φ(x, a)) = μ. If S is the set defined by φ(x, a), then we also write dim(S) and μ(S) respectively. Proposition. Let F be a pseudo-finite field, S, T two definable sets.

(1) If V is a variety defined over F, then dim(V (F)) = dim(V) and μ(V (F)) = 1.

(2) Assume that T ∩ S = ∅. Then

μ(S ∪ T) = \{ \begin{matrix}μ(S) + μ(T) & if dim(S) = dim(T), \\ μ(S) & if dim(S) > dim(T), \\ μ(T) & if dim(S) < dim(T). \end{matrix}

(3) Assume that f : S → T is a definable function, which is onto. If for all y ∈ T, dim(f^{−1}(y)) = d, then dim(S) = dim(T)+d. If moreover for every y ∈ T, μ(f^{−1}(y)) = m, then μ(S) = mμ(T).

(4) Let us define a function m_{S} on definable subsets of S as follows. Assume that T ⊂ S is definable, and let (d, μ) = (dim(S), μ(S)), (e, ν) = (dim(T), μ(T)). Then

m_{S}(T) = \{ \begin{matrix}0 & if e < d, \\ ν/μ & if d = e. \end{matrix}

Then m_{S} is a finitely additive measure on the set of definable subsets of S.

(5) Let S̄ be the Zariski closure of S (in F^{alg}. I.e., the smallest Zariski closed set containing S. It is defined over F). Then dim(S) = dim(S̄). [That is, we are saying that the algebraic dimension of the algebraic set S̄ coincides with the model-theoretic dimension of the set S]

Proof. (1) is clear.

Recall that F embeds elementarily in some ultraproduct ∏_{q∈Q} /U of finite fields. Assume that S is defined by φ(x, a), write a = [a_{q}]_{U}, and S_{q} for the subset of 𝔽_{q}^{n} defined by φ(x, a_{q}). Note that for some set A ∈ U, we will then have 𝔽_{q} ⊧ φ_{d,μ}(a_{q}) for all q ∈ A, and therefore |S_{q}| ∼ μq^{d}. A moment’s thought shows that this gives items (2) - (4).

(5) By (6.17), there is an algebraic set W (F) ⊂ F^{n+ℓ} such that S = π(W (F)) and the restriction of the projection π to W is finite-to-one. Without loss of generality, W (F) is Zariski dense in W, and by (3) we obtain that dim(W) = dim(S). Working now in F^{alg}, we have that π is also finite-to-one on a Zariski-dense open subset of W, and therefore dim(W) = dim(V) (algebraic dimensions). Since V ⊇ S̄, we get that dim(V) = dim(S̄).

(7.6) Existence of certain bounds. Let φ(x, y) be a formula.

(1) There is a number M such that in any finite or pseudo-finite field F, the length of a chain of definable subsets of F^{n} defined by formulas φ(x, a) for some tuples a in F, is bounded by M.

(2) There is a number M such that in any finite field or pseudo-finite field F, if S is a definable set and (a_{i})_{i∈I} is a set of tuples such that each φ(x, a_{i}) defines a subset of S of the same dimension d as S, and for i ≠ j, dim(φ(x, a_{i}) ∧ φ(x, a_{j})) < d, then |I| ≤ M.

Proof. These two facts follow from general properties of measures. It suffices to show them for all pseudo-finite fields, since then they will be true in all sufficiently large finite fields, whence, taking into account the finitely many small finite fields, we will get the bound M.

(1) Assume that this is not the case, i.e., that there are such chains of arbitrarily large length. Then, going to a sufficiently saturated pseudo-finite field F, we can find a sequence (a_{i})_{i∈ℕ} of tuples in F such that if i < j then the set S_{j} defined by φ(x, a_{j}) is strictly contained in the set S_{i} defined by φ(x, a_{i}). Let D be the finite set of pairs associated to φ. Because D is finite, we may, going to a subsequence, assume that for every i ∈ ℕ, dim(S_{i}) = d and μ(S_{i}) = μ. The proof is by induction on d.

If d = 0, then we know that μ is the size of the set S_{i}, and therefore |I| = 1. Assume d > 0 and that the result holds for all definable sets of smaller dimension. For i > 0 let T_{i} = S_{0} \ S_{i}. Then the sets T_{i}, i ∈ ℕ, form a strictly increasing chain of subsets of S_{0}, and we have dim(T_{i}) < d (since (dim(S_{i}), μ(S_{i})) = (dim(S_{0}), μ(S_{0}))). This contradicts the induction hypothesis and proves the result.

(2) Let D be the set of pairs associated to the formula φ(x, y), and let ν be the inf of all μ such that (d, μ) ∈ D. If φ(x, a_{i}), i ∈ I, define subsets S_{i} of S such that dim(S_{i}) = d and dim(S_{i} ∩ S_{j}) < d, then we get m_{S}(S_{i}) ≥ ν/μ(S) and m_{S}(S_{i} ∩ S_{j}) = 0. This gives |I| ≤ μ(S)/ν.

8. Applications to finite fields Applications are usually obtained in the following fashion. We have a family of sets

defined over finite fields (for instance, GL_{n}(𝔽_{q}), where n is fixed, q varies), and we know it has a certain property P. From this we deduce that the corresponding set defined in pseudo-finite fields (say, GL_{n}(F)) has also property P. From this one deduces a certain property Q of the set, and then conclude that Q is also true in all sufficiently large finite fields. We saw already an application of this strategy in the previous section, where we found bounds on the size of certain families of definable sets. Here are more applications. Most of this material comes from the paper [HP2] by Hrushovski-Pillay. The proofs are fairly elementary, and pleasant to read. They introduce some techniques which are classical in simplicity theory.

(8.1) Projective varieties. We defined affine varieties in section 4. Projective varieties are a more general concept. Let K be an algebraically closed field. We define the ndimensional projective space over K, ℙ^{n}(K) as follows: consider K^{n+1} \ {0}, and quotient by the equivalence relation

(x_{0}, …, x_{n})E(y_{0}, …, y_{n}) ⟺ ∃λ x_{0} = λy_{0}, …, x_{n} = λy_{n}.

The resulting object is ℙ^{n}(K), and the E-equivalence class of (x_{0}, …, x_{n}) is (often) denoted by (x_{0} : …: x_{n}). (Observe that ℙ^{n}(K) is interpretable in K). Zariski-closed subsets of ℙ^{n}(K) are the images (in K^{n+1}/E) of zero-sets of finite sets of homogeneous polynomials. There is a covering of ℙ^{n}(K) by affine subsets: namely, for each 0 ≤ i ≤ n, consider the set U_{i} of elements (x_{0} : …: x_{n}) with x_{i} ≠ 0. There is a bijection f_{i} : U_{i} → K^{n} obtained by sending (x_{0} : …: x_{n}) to (x_{0}/x_{i}, …, x_{i−1}/x_{i}, x_{i+1}/x_{i}, …, x_{n}/x_{i}) (i.e., one divides all coordinates of a representing element by the i-th one, then deletes the i-th coordinate). This bijection is continuous for the Zariski topology, and a subset W of ℙ^{n}(K) is Zariskiclosed if and only if for every i, f_{i}(W ∩ U_{i}) is Zariski-closed (in K^{n}).

A morphism f : V → W between two varieties is a function from V (K) to W (K), whose coordinate functions are given locally by polynomials (i.e., for every a ∈ V (K), f(a) ∈ W (K), and there is some open subset U of V (K) containing a, and on which f is given by a tuple of elements of K[V ∩ U].

(8.2) Algebraic groups. Recall that an algebraic group is an algebraic set G (affine or projective), with a group law such that multiplication G × G → G and the inverse map G → G are morphisms. This implies that these two maps are continuous (for the Zariski topology), and that G is a topological group. Hence, all results of section 3 apply.

The connected component of G is the (unique) irreducible component of the algebraic set G which contains the identity element 1, and it is denoted by G^{0}. If G is defined over K, then so is G^{0} (because 1 ∈ G(K)). The irreducible components of G are disjoint, and are the cosets of G^{0} in G.

If G = G^{0}, then one says that G is connected. Examples. The best-known examples are probably GL_{n}(K) (the group of n×n invertible matrices), the additive group of K (usually denoted by 𝔾_{a}(K)) and the multiplicative group K^{×} (usually denoted by 𝔾_{m}(K)). A priori, GL_{n}(K) is an open subset of K^{n}, since it is defined by det(x_{i,j}) ≠ 0, but it is in definable bijection with the subvariety of K^{n+1} defined by det(x_{i,j}y − 1 = 0. Similarly for K^{×}. Non-affine examples are elliptic curves, for instance the projective variety defined by y^{2}z = x(x − z)(x − 2z) (which can also be viewed as the affine variety defined by y^{2} = x(x − 1)(x − 2) to which one adds the point at infinity (0 : 1 : 0)).

(8.3) Some properties of algebraic groups. Let G be an algebraic group. Then all properties listed in (3.1) apply, since the Zariski topology on G is T_{1}. Moreover we have:

(1) The center of G, Z(G), is an algebraic subgroup of G.

(2) A finite normal subgroup of a connected algebraic group is central. Proof. (1) If g ∈ G, the centraliser C_{G}(g) of g in G is a Zariski-closed subgroup of G (see (3.1)(7)). Now, Z(G) is the intersection of all C_{G}(g) and is therefore Zariski-closed.

(2) If H is a finite normal subgroup of G, and h ∈ H, then h has only finitely many conjugates under the action of G (since they are all in the finite group H), and this implies that C_{G}(h) has finite index in G. Because G is connected, this implies that C_{G}(h) = G, i.e., that h ∈ Z(G).

(8.4) Definable subgroups of algebraic groups. Let F be a pseudo-finite field, G an algebraic group defined over F, and H a definable subgroup of G(F).

(1) Let H̄ be the Zariski closure of H. Then [H̄(F) : H] is finite.

(2) Assume that H̄ = G. Then there is an algebraic group G′ and a surjective morphism f : G′ → G, everything defined over F, such that f(G′(F)) is a subgroup of finite index of H (and therefore of G(F)), and Ker(f) is finite (central).

Proof. (1) By Proposition (7.5)(5), we know that dim(H̄) = dim(H) = dim(H̄(F)), and therefore m_{H̄(F)}(H) > 0. Since the cosets of H in H̄(F) are disjoint, there are at most finitely many, i.e., [H(F) : H] is finite.

(2) The proof of this result can be found in [HP2] and is fairly technical, I will not give it. In view of Theorem (6.17) it is not very suprising. Remarks. (1) A morphism f : G → H of algebraic groups which is onto and has finite kernel is called an isogeny, and the groups G and H are said to be isogenous. Observe that since G is connected, the kernel of f is necessarily central: Ker(f) is a finite normal subgroup of G(K).

(2) Note the following immediate application of the fact that pseudo-finite fields behave like finite fields: if f : G → H is an isogeny of (connected) algebraic groups defined over the pseudo-finite field F, then |Ker(f)(F)| = [H(F) : f(G(F))], see also (7.3).

(8.5) The following result is very useful. It is a generalisation of a theorem of Chevalley for algebraic groups, and also a generalisation of a model-theoretic result called Zilber’s irreducibility theorem and which holds in superstable groups of finite U-rank. Theorem. Let F be a pseudo-finite field, G an algebraic group defined over F. Let X(i), i ∈ I be a family of definable subsets of G(F) (no uniformity is assumed).

(1) Then there is a definable subgroup H of G(F) and indices i_{1}, …, i_{M} ∈ I such that

H ⊂ X(i_{1})^{±1} · X(i_{2})^{±1} ⋯ Xi_{M}^{±1},

and for every i ∈ I, X(i)H/H is finite.

(2) If for every i ∈ I, the Zariski closure \overline{X(i)} of X(i) is a variety and contains 1 (the identity element of G), then in fact H equals the subgroup of G(F) generated by all X(i), i ∈ I, and its Zariski closure H̄ equals the algebraic subgroup of G generated by all \overline{X(i)}, i ∈ I, and is contained in \overline{X(i_{1})}^{±1} · \overline{X(i_{2})^{±1}} ⋯ \overline{Xi_{M}^{±1}}.

Very rough sketch of proof. I will not give the proof, it is rather long. One starts by showing (2). The statement that the subgroup generated by the \overline{X(i)} is an algebraic subgroup of G is classical, due to Chevalley. Without loss of generality the family X(i) is closed under inverses. Grosso modo one considers all sets W_{α} of the form \overline{X_{α(1)}} ⋯ \overline{X_{α(m)}}, takes one of maximal dimension, and then shows that W_{α} · W_{α} is the group H_{0} generated by all \overline{X(i)}.

To get the result for the family X(i), one then considers the set U = X_{α(1)} ⋯ X_{α(m)}, and show it has same dimension as H_{0}. Lemma (8.6) below tells us that the subgroup H generated by U is definable, and since it has the same dimension as H_{0}, it must be of finite index in H_{0}(F), and H_{0} = H̄.

Proof of (1) from (2). The irreducible components of each \overline{X(i)} are defined over F; partitioning each X(i) into finitely many pieces if necessary (and enlarging the family), we may therefore assume that each \overline{X(i)} is irreducible. If X(i) does not contain 1, then replace it by T (i) = g_{i}^{−1}X(i) for some g_{i} ∈ X(i). By (1), the group H generated by the T (i) is definable, and we have X(i)H = g_{i}^{−1}H.

(8.6) Lemma. Let U be a definable subset of G(F), and assume that dim(U) = dim(G). Then the subgroup H generated by U is definable, and there is an integer M such that every element of H is the product of at most M elements of U or of U^{−1}.

(8.7) Corollary. Let G be an algebraic group defined over the pseudo-finite field F, and let H be a definable subgroup of G. Suppose that H is definably simple, i.e., that it has no proper non-trivial definable normal subgroup, and that is non-abelian. Then H is simple. Proof. Without loss of generality, H̄ = G. Then G = G^{0}, since G^{0}(F) ∩ H is definable and normal in H. Also, Z(G) ∩ H = (1). Furthermore, H has no definable subgroup of finite index: if H_{1} is such a subgroup, then ⋂_{g∈H} H_{1}^{g} is definable, of finite index in H, and normal.

Let N be a normal subgroup of H. If N is finite, and 1 ≠ g ∈ N then C_{H}(g) is a definable subgroup of H of finite index, and therefore equals H. But then C_{G}(g) = H̄, which contradicts Z(G) ∩ H = 1. Hence N cannot be finite, and the conjugation class of any 1 ≠ g ∈ N is infinite. Pick 1 ≠ g ∈ H, let X = g^{H} = {h^{−1}gh | h ∈ H} and let Y = g^{−1}X. Then Ȳ = g^{−1}X̄ = g^{−1}g^{G} is irreducible, and contains 1. Hence, by (8.5), the subgroup U of H generated by Y is definable. It is clearly normal, contained in N and non-trivial: this give us the desired contradiction.

(8.8) Theorem. Let n > 1. There is an integer k such that every subgroup of GL_{n}(𝔽_{p}) which is generated by elements of order p is of the form ⟨g_{1}⟩·. . . ·⟩g_{k}⟨ for some g_{1}, …, g_{k} ∈ G of order p.

Sketch of proof. If g ∈ GL_{n}(𝔽_{p}) is of order p > n, then

⟨g⟩ = {exp(t log(g)) | t ∈ 𝔽_{p}},

where log(g) = (g − I_{n}) − (g − I_{n})^{2} + ⋯ + (−1)^{n−1}(g − I_{n})^{n−1}/(n − 1) and exp(v) = v + v^{2}/2! + ⋯ + v^{n−1}/(n − 1)!.

If there is no such k, we can find a increasing sequence p(i), i ∈ ℕ, of prime numbers, and for each i ∈ ℕ, a subset A_{i} of elements of GL_{n}(𝔽_{p(i)}) of order p(i), such that the subgroup G_{i} of GL_{n}(𝔽_{p(i)}) generated by A_{i} cannot be written as ⟨a_{1}⟩ · . . . · ⟨a_{i}⟩ for any elements a_{1}, …, a_{i} ∈ G_{i} of order p(i).

Consider the structure M_{i} = (𝔽_{p(i)}, +, ·, A_{i}) and let M = (F, +, ·, A) a non-principal ultraproduct of the M_{i}’s. Then F is a pseudo-finite field, and A is a set of unipotent elements of GL_{n}(F). For each a ∈ A, consider the (definable) subgroup X(a) = {exp(t log(a)) | t ∈ F }. Its Zariski closure is the subgroup (of GL_{n}(F^{alg})) defined by Y (a) = {exp(t log(a)) | t ∈ F^{alg}}, which is a variety. Hence, by Theorem (8.5), the subgroup H of GL_{n}(F) generated by the X(a), a ∈ A, is definable, and of the form X(a_{1}) · . . . · X(a_{k}) for some k and a_{1}, …, a_{k} ∈ A.

There is a formula ψ(x_{1}, …, x_{k}) which is satisfied by a_{1}, …, a_{k} in M, and which expresses that X(a_{1}) · . . . · X(a_{k}) is a subgroup G of GL_{n}(F) which contains A. if for each 1 ≤ ℓ ≤ k, (a_{ℓ}(i)) is a sequence representing the element a_{i}, by Łos’ theorem, there is an infinite set J of integers i such that the tuples (a_{1}(i), …, a_{k}(i)) satisfy ψ. But this contradicts our assumption on the structures M_{i} and gives the desired contradiction. Remark. Observe also the following: let us call G^{∗} the algebraic subgroup of GL_{n}(F^{alg} generated by the Y (a), a ∈ A. By (8.5) again, we have that [G^{∗}(F) : G] < ∞. By compactness, this implies that there is some integer d such that, whenever G is a subgroup of GL_{n}(𝔽_{p}) generated by elements of order p, if G^{∗} denotes the algebraic subgroup generated by all Y (a), a ∈ G of order p, then [GL_{n}(𝔽_{p}) : G] ≤ d. Furthermore, it follows (easily) that if p > d, then G contains all elements of order p of G ∗ (𝔽_{p}). This result was proved by Nori [N].

(8.9) Other results include: Theorem. Let G be an almost simple algebraic group defined over the pseudo-finite field F (G is almost simple if Z(G) is finite and G/Z(G) is a simple (non-abelian) simple algebraic group). Then G(F) has a smallest definable subgroup H of finite index, and H/Z(H) is simple (as an abstract group). Theorem. Let G be an almost simple algebraic subgroup of GL_{n} defined over ℤ. Then there are a finite number of formulas ψ_{1}(x, y), …, ψ_{m}(x, y) such that whenever p is a prime and M is a maximal subgroup of G(𝔽_{p}) then for some i and tuple a_{i} in 𝔽_{p}, M is defined by the formula ψ_{i}(x, a_{i}).

(8.10) Proposition (folklore). Let R be a domain which is finitely generated as a ring. If R is a field, then R is finite. If R is infinite, then for every 0 ≠ a ∈ R, there are infinitely many maximal ideals of R which do not contain a. Proof. The proof is by induction on the number of generators of R, and it suffices to show the second assertion, since it implies the first one (a field has no maximal ideal other than (0)). So, assume that R is infinite. If n = 1, then R = ℤ, and the assertion is clear. Assume that the result holds for the subring S of R and that R = S[t]. There are two cases to consider: Case 1. t is transcendental over S.

Then R is a polynomial ring over S. Assume first that S is finite (so that it is a field). Then S[t] contains infinitely many irreducible polynomials, and each irreducible polynomial generates a maximal ideal. A non-zero element of R has only finitely many irreducible factors, and this gives the result.

If S is infinite and 0 ≠ a(t) ∈ R, then S contains infinitely many elements c such that a(c) ≠ 0. If a(c) ≠ 0, then by induction hypothesis, there are infinitely many maximal ideals P of S such that a(c) ∉ P. Then (P, t − c) is a maximal ideal of R which does not contain a(t). Case 2. t is algebraic over S.

If S is finite, then so is R and we are done. Assume that R is infinite, let f(X) ∈ S[X] be a polynomial vanishing at t and of minimal degree. If b is its leading coefficient, then t is integral over S[1/b], and therefore, if P is a maximal ideal of S not containing b, then P extends to a maximal ideal of R (not containing b): indeed, the ideal P extends uniquely to a maximal ideal P′ of S[1/b]; the image of the monic polynomial f(X)/b in the ring S[1/b][X] is therefore non-constant, and has a non-constant irreducible factor.

Let 0 ≠ a ∈ R, and let g(X) ∈ S[X] be a polynomial vanishing at a and of minimal degree. Since a ≠ 0, the constant term c of the polynomial g(X) is non-zero. Let P be a maximal ideal of R which does not contain bc (by induction hypothesis, there are infinitely many of those). By the discussion above, P generates a proper ideal of S. If P′ is a maximal ideal of R which contains P, then P′ ∩ S = P. This finishes the proof.

(8.11) Let R be a domain, generated by a_{1}, …, a_{n} as a ring. Let X = Max(R) the set of maximal ideals of R. We define a topology on X as follows: a basis of open sets are the open sets O_{a} = {P ∈ X | a ∉ P }. Proposition. Let R be as above, and assume that R is infinite.

(1) If P ∈ X, then R/P is finite.

(2) Let m ∈ ℕ. The set {P ∈ X | |R/P | ≤ m} is finite.

(3) If a, b ∈ R are non-zero, then O_{a} ∩ calo_{b} = O_{ab}. Hence a finite intersection of basic open sets is a basic open set. The space X is compact, and every singleton is closed.

(4) Let 0 ≠ a ∈ R. Then O_{a} is infinite. Proof. (1) The quotient R/P is a field, which is generated by the images a_{1}/P, …, a_{n}/P of a_{1}, …, a_{n} in R/P. By (8.10), R/P must be finite.

(4) is also clear by (8.10).

(2) If P, P′ ∈ X, we have P = P′ if and only if a_{1}/P, …, a_{n}/P and a_{1}/P′, …, a_{n}/P′ satisfy the same equations with coefficients in ℤ. Hence, P = P′ if and only if there is an isomorphism between the field R/P and R/P′ which sends a_{i}/P to a_{i}/P′ for 1 ≤ i ≤ n. But there are only finitely many isomorphism types of fields with n elements named, and having size ≤ m.

(3) If P is a maximal ideal of R, then P is prime. Hence, if a, b ∈ R, then ab ∉ P ⟺ a ∉ P and b ∉ P. This shows the first assertion.

Let P ∈ X. If Q ∈ X, Q ≠ P, there is b_{Q} ∈ Q \ P. Then {P } = ⋂_{Q∈X,Q≠P} O_{b_{Q}}.

Let U_{i}, i ∈ I, be a family of open sets such that X = ⋃_{i} U_{i}. By (1), every U_{i} is a union of basic open sets, and we may therefore assume that every U_{i} is a basic open set, i.e., of the form O_{a_{i}} for some 0 ≠ a_{i} ∈ R. Then X = ⋃_{i} O_{a_{i}} is equivalent to ∅ = ⋂_{i}(X \O_{a_{i}}), i.e., no element of X contains all a_{i}’s, i.e., the ideal generated by all a_{i}’s contains 1. Hence there are b_{1}, …, b_{m} ∈ R, i(1), …, i(m) ∈ I such that 1 = ∑_{j=1}^{m} b_{i}a_{i(j)}. Then X = ⋃_{j=1}^{m} O_{a_{i(j)}}. Note X is in general not Hausdorff.

(8.12) Exercise. Let R be an infinite domain, generated by a_{1}, …, a_{n} as a ring. Let (b_{m})_{m∈ℕ} be an enumeration of the elements of R. For each m choose a maximal ideal P (m) of R such that b_{0} ⋯ b_{m} ∉ P (m). Show that if U is any non-principal ultrafilter on ℕ, then R embeds naturally into (∏_{m∈ℕ} R/P (m))/U.

(8.13) (8.12) can be used to show results on “reduction mod p” for almost all p. For instance, the following result appears in [MVW], and is proved in [HP2] using modeltheoretic techniques: Theorem. Let G be an algebraic subgroup of GL_{n} which is defined over ℚ, and is almost simple and simply connected (almost simple means that Z(G) is finite, and G/Z(G) is simple non-abelian; simply connected means that there is no proper isogeny from any algebraic group onto G). Let Γ be a finitely generated subgroup of G(ℚ) which is Zariski dense in G. The homomorphism π_{p} : ℤ → 𝔽_{p}, “reduction mod p”, then gives us for almost all p an algebraic subgroup G_{p} of GL_{n} (which is also almost simple and simply connected), and sends Γ to a subgroup Γ_{p} of G_{p}(𝔽_{p}).

Then for almost all p, π_{p}(Γ) = G_{p}(𝔽_{p}).

(8.14) The Frobenius. For each q = p^{n} ∈ Q, consider the field 𝔽_{p}^{alg} together with the automorphism σ_{q} : x ↦ x^{q}.

Let U be a non-principal ultrafilter on Q, and consider the difference field

(K, σ^{∗}) = ∏_{q∈Q}(𝔽_{p}^{alg}, σ_{q})/U.

Hrushovski [H] and Macintyre [M] showed that this difference field is generic, i.e., that every finite system of difference equations over K (i.e., polynomial equations in X, σ^{∗}(X), …,, where X is a tuple of variables) which has a solution in some difference field extending (K, σ^{∗}) already has a solution in K^{∗}. To do that, Hurshovski shows a Lang-Weil-type estimate of the number of solutions of certain systems in the difference fields (𝔽_{p}^{alg}, si_{q}). By linearizing the system of equations, and applying a trick, one reduces genericity question to the following question: given varieties U and V defined over K^{∗} and of the same dimension, with V ⊂ U × U^{σ^{∗}} (U^{σ^{∗}} denotes the variety obtained by applying σ^{∗} to the defining equations of U), and such that the projection maps V → U and V → U^{σ^{∗}} are dominant, show that there is some a ∈ K^{∗} such that (a, σ^{∗}(a)) ∈ V. The result of Hrushovski, which implies the genericity of the difference fields (K^{∗}, σ^{∗}), is the following: Theorem. Fix d and n. There is a constant C > 0 such that, for any q ∈ Q, whenever U and V are varieties of dimension d defined over 𝔽_{p}^{alg} by polynomials in 𝔽_{p}^{alg}[X_{1}, …, X_{n}]_{≤}d and 𝔽_{p}^{alg}[X_{1} …, X_{n}, Y_{1}, …, Y_{n}]_{≤}d respectively, and are such that V ⊂ U × U^{σ_{q}} and the projection maps V → U and V → U^{σ_{q}} are dominant, then

||{a ∈ 𝔽_{p}^{alg}^{n} | (a, σ_{q}(a)) ∈ V }| − cq^{d}| < Cq^{d−1/2},

where c = [𝔽_{p}^{alg}(V) : 𝔽_{p}^{alg}(U)]/[𝔽_{p}^{alg}(V) : 𝔽_{p}^{alg}(U)]_{insep}.

Generic difference fields have very nice model-theoretic properties, similar to the ones exhibited by pseudo-finite fields. Observe that F ix(si), the subfield of elements fixed by σ, is then pseudo-finite. Generic difference fields can be thought of as “universal models” for difference fields. As for pseudo-finite fields, the elementary theory of a generic difference field is entirely determined by the behaviour of the automorphism on the algebraic closure of the prime field. Again, one almost obtains quantifier-elimination; every definable set is the finite-to-one projection of a set defoned by difference equations. The theory of generic difference field is decidable, and any of its completions is supersimple and eliminates imaginaries. Furthermore, Ryten and Tomasic have shown that Hrushovski’s result allows one to define a finitely additive measure on definable subsets of generic difference fields, similar to the one defined for pseudo-finite fields.

Bibliography

[A] J. Ax, The elementary theory of finite fields, Annals of Math. 88 (1968), 239 – 271.

[CK] C.C. Chang, H.J. Keisler, Model theory, North-Holland, Amsterdam 1977.

[CDM] Z. Chatzidakis, L. van den Dries, A. Macintyre, Definable sets over finite fields, J.

reine u. ang. Math. 427 (1992), 107 – 135.

[DS] L. van den Dries, K. Schmidt, Bounds in the theory of polynomials rings over fields.

A non-standard approach. Invent. Math. 76 (1984), 77 – 91.

[FHJ1] M. Fried, D. Haran, M. Jarden, Galois stratification over Frobenius fields, Adv. in Math. 51 (1984), 1 – 35.

[FHJ2] M. Fried, D. Haran, M. Jarden, Effective counting of the points of definable sets over

finite fields, Israel J. Math. 85 (1994), 103 – 133.

[FJ] M. Fried, M. Jarden, Field Arithmetic, Ergebnisse 11, Springer Berlin-Heidelberg 1986.

[FS] M. Fried, G. Sacerdote, Solving diophantine problems over all residue class fields of a number field and all finite fields, Annals of Math. 104 (1976), 203 – 233.

[He] G. Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736 – 788.

[H] E. Hrushovski, The first-order theory of the Frobenius, preprint, available at ArXiv:

    http://front.math.ucdavis.edu/math.LO/0406514.

[HP1] E. Hrushovski, A. Pillay, Groups definable in local fields and pseudo-finite fields, Israel J. of Math. 85 (1994), 203 – 262.

[HP2] E. Hrushovski, A. Pillay, Definable subgroups of algebraic groups over finite fields, J.

reine angew. Math. 462 (1995), 69 – 91.

[L1] S. Lang, Introduction to algebraic geometry, Addison-Wesley Pub. Co., Menlo Park 1973.

[L2] S. Lang, Algebra, Addison-Wesley Pub. Co., Menlo Park 1984.

[M] A. Macintyre, Nonstandard Frobenius, in preparation.

[MVW] C.R. Matthews, L.N. Vaserstein and B. Weisfeiler, Congruence properties of Zariski

dense subgroups, Proc. London ¡ath. Soc. XLVIII (1984), 385 – 576.

[N] M.V. Nori, On subgroups of GL_{n}(𝔽_{p}), Inventiones Math. 88 (1987), 257 – 275.

[S] A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273 – 313.