Model-Theory of Fields: Background

David Pierce

2004.10.25

These notes are intended as a quick summary of first-order logic as used in model-theory and the model-theoretic study of fields. I originally wrote them for the algebra study group at METU in 2002, when we were looking at [3, ch. 6]. For less terse accounts, see [2] or [4] or even [1].

My notational conventions are these. The set of natural numbers is ω, and each natural number n is the set {0, …, n − 1} of its predecessors. In particular, 0 is ∅. If I ⊆ ω, and M is a set, then M^{I} is the set of functions from I to M. A typical element of M^{I} can be written (a_{i} : i ∈ I) or just a or a⃗.

Model-theory begins with the distinctions indicated in the table on p. 2. Technical terms in bold are not defined further; those that are slanted, will be.

Formally, a structure with signature L can be defined as a pair (M, ℑ), where M is a set, and ℑ is a function assigning an interpretation to each constant-, function- and relation-symbol in L. (I may refer to relation-symbols as predicates, and to constant-symbols as constants.) The set M is called the universe of the structure. One rarely refers to ℑ explicitly, but one may write the structure as 𝔐 (in a more elaborate font) to indicate the presence of ℑ.

The signature L_{r} of (unital) rings and fields is

{+, −, ·, 0, 1},

where + and · are binary, and − is a unary, function-symbol, and 0 and 1 are constant-symbols. The signature L_{or} of ordered rings and fields contains also the binary relation-symbol ⩽. To indicate explicitly that the integers are to be thought of as composing an ordered ring, one might write this structure as

(ℤ, +^{ℤ}, −^{ℤ}, ·^{ℤ}, 0^{ℤ}, 1^{ℤ}, ⩽^{ℤ}).

However, the superscripts are rarely needed; one might write (ℤ, +, −, ·, 0, 1, ⩽), or just refer to ‘the ordered ring ℤ’.

Terms can be defined thus (here f is as in the table):

(∗) Constant-symbols and variables are terms.

(†) If t_{0}, …, t_{n−1} are terms, then so is ft_{0} … t_{n−1}.

If t is a term, and I is a subset of ω containing the indices of all variables appearing in t, then t^{𝔐} can be understood in the obvious way as a function from M^{I} to M.

Informally, letters like x, y and z stand for variables. The definition of ‘term’ uses the so-called Polish notation, which needs no brackets. Conventionally, binary symbols are written between their arguments, so that · + x y z is written (x + y) · z. The manner of writing terms is not mathematically important; what is important is that a term of L is an unambiguous recipe for constructing a function in each L-structure.

For every commutative ring 𝔄, there is a unique homomorphism of ℤ into 𝔄; the image of ℤ in A is (the universe of) the prime ring of 𝔄. Every element of the prime ring is the interpretation of a term, namely −(1 + ⋯ + 1) or 0 or 1 + ⋯ + 1. Then every polynomial over the prime ring is the interpretation of a term of L_{r}, and every term has such an interpretation in 𝔄 (if A is infinite).

Table 1: Model-theoretic symbols and meanings

IMAGE REALITY
SYMBOL INTERPRETATION
SYNTAX SEMANTICS
signature L 𝔐, an L-structure

OPERATIONS ON M: basic operations:

variable v_{i} a ↦ a_{i} : M^{I} → M, if i ∈ I
constant-symbol c c^{𝔐}, an element of M
n-ary function-symbol f f^{𝔐} : M^{n} → M
term t t^{𝔐}, a composition of basic operations
LOGICAL SYMBOLS: FUNCTIONS ON 𝒫(M^{I})
connectives: operations:
∧ ∩
¬ A ↦ A^{c}
∨ ∪
→ (A, B) ↦ A^{c} ∪ B
↔ (A, B) ↦ (A^{c} ∪ B) ∩ (A ∪ B^{c})
quantifiers: projections:
∃v_{i} A ↦ {(a_{j} : j ∈ I ∖ {i}) : a ∈ A}
∀v_{i} A ↦ {(a_{j} : j ∈ I ∖ {i}) : a ∈ A^{c}}^{c}

RELATIONS ON M: basic relations:

= equality
n-ary relation-symbol R R^{𝔐}, a subset of M^{n}
formulas: definable relations:
atomic formula α α^{𝔐}, a solution-set
open formula β β^{𝔐}, a constructible set
formula ϕ ϕ^{𝔐}
sentence true or false
⊢ ⊧
⊧ ⊆

If we want to allow arbitrary coefficients from A, we introduce them into the signature. In general, if B ⊆ M, then L(B) is L with a new constant-symbol for each element of B.

Atomic formulas take the form (t_{0} = t_{1}) or Rt_{0} … t_{n−1} (where R is as in the table; the latter formula is in Polish notation.) The corresponding interpretations in 𝔐 are thus:

• (t_{0} = t_{1})^{𝔐} is the inverse image of {(a, a) : a ∈ M} under (t_{0}^{𝔐}, t_{1}^{𝔐}), and

• (Rt_{0} … t_{n−1})^{𝔐} = (t_{0}^{𝔐}, …, t_{n−1}^{𝔐})^{−1}R^{𝔐}.

In L_{r}, the atomic formulas correspond to polynomial equations over a prime ring; the interpretations of the formulas are the solution-sets of the equations. In L_{or}, some atomic formulas correspond to inequalities.

In the propositional calculus, the connectives ∧ and ¬ are adequate to symbolize every truth-table. In particular, one has the equivalences:

P ∨ Q ∼ ¬P ∧ ¬Q; P → Q ∼ ¬P ∨ Q; P ↔ Q ∼ P → Q ∧ Q → P.

I shall use the arrows ⟹ and ⟺ not as formal symbols, but as abbreviations for ordinary expressions like ‘implies’ and ‘if and only if’ respectively.

Hence we can define open (or basic, or quantifier-free) formulas thus.

(∗) Atomic formulas are open.

(†) If α is open, then so is ¬α.

(‡) If α and β are open, then so is (α ∧ β).

Informally, redundant brackets can be omitted. (Or one can use Polish notation.)

Arbitrary formulas are defined as open formulas are, with an extra provision:

(§) If ϕ is a formula, then so is (∃x ϕ) for any variable x.

For every formula ϕ, there is a set fv(ϕ) of indices of its free variables, given thus:

(∗) If α is atomic, then fv(α) is the set of indices of variables appearing in ϕ.

(†) fv(¬ϕ) = fv(ϕ).

(‡) fv(ϕ ∧ ψ) = fv(ϕ) ∪ fv(ψ).

(§) fv(∃v_{i} ϕ) = fv(ϕ) ∖ {i}.

If fv(ϕ) = n, then ϕ can be written as ϕ(v_{0}, …, v_{n−1}), and ϕ^{𝔐} should be a subset of M^{n}. Indeed, we define:

• (¬ϕ)^{𝔐} = (ϕ^{𝔐})^{c};

• (ϕ ∧ ψ)^{𝔐} = ϕ^{𝔐} ∩ ψ^{𝔐};

• (∃v_{i} ϕ)^{𝔐} is the image of ϕ^{𝔐} under a ↦ (a_{j} : j ∈ I ∖{i}) : M^{I} → M^{I∖{i}}, where fv(ϕ) ⊆ I.

In 𝔐, the sets definable over ∅ are the interpretations of formulas of L. These sets are also called 0-definable. If B ⊆ M, then the B-definable sets are the interpretations of formulas of L(B). Usually definable means M-definable.

In algebraic geometry, if 𝔎 is a field, then the constructible sets of 𝔎 are the sets definable by open formulas of L_{r}(K). Chevalley’s Theorem [5, § 4.4, p. 33] is that, if K is algebraically closed, then all definable sets of 𝔎 are constructible.

A sentence is a formula with no free variables. If σ is a sentence, then σ^{𝔐} is a subset of M^{∅}. But M^{∅} = {∅}, whose subsets are ∅ and {∅}, that is, 0 and 1, which can be considered as false and true respectively.

If σ^{𝔐} = 1, then we write

𝔐 ⊧ σ

and say that 𝔐 is a model of σ. In particular, if fv(ϕ) = {0}, then

𝔐 ⊧ ∃v_{0} ϕ ⟺ ϕ^{𝔐} ≠ ∅.

If Γ is a set of sentences, then the expression

𝔐 ⊧ Γ

has the obvious meaning. If 𝔐 ⊧ Γ ⟹ 𝔐 ⊧ σ for all L-structures 𝔐, then we write

Γ ⊧ σ

and say σ is a logical consequence of Γ. One can define a notion of formal proof, and write Γ ⊢ σ (‘σ is deducible from Γ’) when there is a formal proof of σ from Γ. Gödel’s Completeness Theorem is that the symbols ⊢ and ⊧ are interchangeable.

A theory is a set of sentences that contains all of its logical consequences. If T is a theory, and Γ ⊧ T, then Γ is a set of axioms for T.

In L_{r}, the axioms for the (first-order) theory of fields are standard. They can be written in universal form, except for the axiom

∀x ∃y (x = 0 ∨ xy = 1).

The theory ACF of algebraically closed fields has the additional axioms

∀v_{0} ∀v_{1} … ∀v_{n−1} ∃y v_{0} + v_{1}y + … v_{n−1}x^{n−1} + y^{n} = 0.

The model-theoretic version of Chevalley’s Theorem is that ACF admits elimination of quantifiers, that is, for all positive n, for every n-ary formula ϕ of L_{r}, there is an open formula α such that

ACF ⊧ ∀v_{0} … ∀v_{n−1} (ϕ ↔ α).

One method of proof relies on the fact that a model of ACF is determined up to isomorphism by its characteristic and its transcendence-degree.

Ultra-products

Let (𝔐^{(i)} : i ∈ I) be an indexed set of L-structures. We define a productstructure

∏_{i∈I} 𝔐^{(i)},

or 𝔐 for short, as follows. The universe, M, is the product ∏_{i∈I} M^{(i)}. A typical element of this is (a^{(i)} : i ∈ I), or simply a. Then each 𝔐^{(i)} is an L(M)-structure when we define

a^{𝔐^{(i)}} = a^{(i)}.

For the symbols of L, let this definition be a notational convention, so that s^{(i)} means s^{𝔐^{(i)}} when s ∈ L.

If σ is a sentence of L(M), then its Boolean value, ∥σ∥, is defined to be the set

{i ∈ I : 𝔐^{(i)} ⊧ σ}.

The map σ ↦ ∥σ∥ is a sort of homomorphism: ∥σ ∧ τ∥ = ∥σ∥ ∩ ∥τ∥ and ∥¬σ∥ = ∥σ∥^{c}.

Having M, we define 𝔐 by:

• c^{𝔐} = (c^{𝔐^{(i)}} : i ∈ I),

• f^{𝔐}(a) = (f^{𝔐^{(i)}}(a^{(i)}) : i ∈ I),

• a ∈ R^{𝔐} ⟺ ∥Ra∥ = I.

Let 𝔉 be a filter on I (that is, the dual of an ideal of 𝒫(I)). Define an equivalencerelation ∼ on M by:

a ∼ b ⟺ ∥a = b∥ ∈ 𝔉.

(In case 𝔉 = {I}, this relation is equality.) The reduced product 𝔐/𝔉 has universe M/∼, and:

• c^{𝔐/𝔉} = c^{𝔐}/∼,

• f^{𝔐/𝔉}(a/∼) = f^{𝔐}(a)/∼,

• (a/∼) ∈ R^{𝔐/𝔉} ⟺ ∥Ra∥ ∈ 𝔉.

The validity of this definition must be checked: If a, b ∈ M^{n}, then

∥a_{0} = b_{0} ∧ … ∧ a_{n−1} = b_{n−1}∥ ⊆ ∥f(a) = f(b)∥,

so a ∼ b ⟹ f(a) ∼ f(b). Also,

∥a_{0} = b_{0} ∧ … ∧ a_{n−1} = b_{n−1}∥ ∩ ∥Ra∥ ⊆ ∥Rb∥,

so a ∼ b ∧ ∥Ra∥ ∈ 𝔉 ⟹ ∥Rb∥ ∈ 𝔉.

Lemma. Say σ_{e} (e < 2) are sentences of L(M) such that

𝔐/𝔉 ⊧ σ_{e} ⟺ ∥σ_{e}∥ ∈ 𝔉

in each case. Then 𝔐/𝔉 ⊧ σ_{0} ∧ σ_{1} ⟺ ∥σ_{0} ∧ σ_{1}∥ ∈ 𝔉.

Proof. ∥σ_{0}∥ ∩ ∥σ_{1}∥ = ∥σ_{0} ∧ σ_{1}∥ ⊆ ∥σ_{e}∥.

Lemma. Say ϕ is a formula of L(M) with one free variable, and

𝔐/𝔉 ⊧ ϕ(a) ⟺ ∥ϕ(a)∥ ∈ 𝔉

for all a in M. Then 𝔐/𝔉 ⊧ ∃x ϕ ⟺ ∥∃x ϕ∥ ∈ 𝔉.

Proof. ∥ϕ(a)∥ ⊆ ∥∃x ϕ∥ for all a in M. Also, there a in M such that 𝔐^{(i)} ⊧ ϕ(a) if 𝔐^{(i)} ⊧ ∃x ϕ. Then ∥ϕ(a)∥ = ∥∃x ϕ∥.

Theorem (Łoś). If 𝔘 is an ultrafilter on I, then

𝔐/𝔘 ⊧ σ ⟺ ∥σ∥ ∈ 𝔘  (1)

for all sentences σ of L(M).

Proof. Since all sentences are constructed from atomic formulas using only ∧, ∃ and ¬, it is enough to note that if (1) holds when σ = θ, then it holds when σ = ¬θ.

Corollary (Compactness). If every finite subset of a theory T has a model, then T has a model.

Proof. Let I comprise the finite subsets of T. Each Γ in I determines a filter (Γ), namely the set

{Γ′ ∈ I : Γ ⊆ Γ′}.

Any finite collection {(Γ_{0}), …, (Γ_{m−1})} of subsets of I has intersection containing Γ_{0} ∪ ⋯ ∪ Γ_{m−1}; so the intersection is non-empty. Hence some ultrafilter 𝔘 on I contains each (Γ). For each Γ in I, let 𝔐^{(Γ)} be a model of Γ. If σ ∈ T, then ({σ}) ⊆ ∥σ∥, so ∥σ∥ ∈ 𝔘. By the theorem of Łoś, ∏_{Γ∈I} 𝔐^{(Γ)}/𝔘 ⊧ T.

Let T be the set of sentences of L such that ∥σ∥ ∈ 𝔉. If 𝔘 is an ultrafilter on I that includes 𝔉, then

𝔐/𝔘 ⊧ T.

Conversely, suppose 𝔑 ⊧ T. The set {∥σ∥ : 𝔑 ⊧ σ} is closed under finite intersection. Also, if 𝔑 ⊧ σ, then ∥σ∥^{c} ∉ 𝔉. Hence {∥σ∥ : 𝔑 ⊧ σ} ∪ 𝔉 is included in an ultrafilter 𝔘, such that

𝔑 ⊧ σ ⟺ ∥σ∥ ∈ 𝔘 ⟺ 𝔐/𝔘 ⊧ σ

for all sentences σ of L. We write

𝔑 ≡ 𝔐/𝔘,

and say that 𝔑 and 𝔐/𝔘 are elementarily equivalent.

Example. Let T be the set of sentences of L_{r}, each of which is true in all but finitely many finite fields. Then

∏_{q∈I} 𝔽_{q}/𝔘 ⊧ T,

where I is the set of prime powers, for all non-principal ultrafilters 𝔘 on I. Conversely, every model of T is elementarily equivalent to such an ultraproduct.

References

[1] Elisabeth Bouscaren, editor. Model theory and algebraic geometry, volume 1696 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1998. An introduction to E. Hrushovski’s proof of the geometric Mordell-Lang conjecture.

[2] C. C. Chang and H. J. Keisler. Model theory, volume 73 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, third edition, 1990.

[3] Michael D. Fried and Moshe Jarden. Field arithmetic, volume 11 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1986.

[4] Wilfrid Hodges. Model theory, volume 42 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993.

[5] James E. Humphreys. Linear algebraic groups. Springer-Verlag, New York, 1975. Graduate Texts in Mathematics, No. 21.