MODEL THEORY AND LINEAR ALGEBRA

DAVID PIERCE

These are notes were written originally in preparation for a talk to be given on Friday, March 26, 2010, in the Department of Mathematics and Computer Science at Çankaya University, Ankara. The talk itself is just a selection. What is said here about vector spaces is based mainly on [10].

Contents

1. History of algebra 1 2. Vector spaces 3 3. Model theory (outline) 6 4. Model theory (detail) 8 5. Model theory of fields 13 6. Model theory of vector spaces 15 References 17

1. History of algebra

¶ 1. In the Elements [4] of Euclid (fl. 300 b.c.e.), Proposition II.5 is, If a straight line be cut into equal and unequal segments, the rectangle contained by the unequal segments of the whole together with the square on the straight line between the points of section is equal to the square on the half.

In other words, if a straight line be divided unequally, the rectangle bounded by the unequal pieces falls short of the square on the half by the square on the segment between the midpoint and the point of unequal section. See Figure 1, where

rect. AD, DB = sq. AC − sq. DC.

\begin{aligned}A & D & C & B \\ & & Figure 1 \end{aligned}

Date: March 26, 2010.

¶ 2. Consequently, Muhammad ibn Mūsā al-Khwārizmī (c. 780–850) [7, pp. 525, 544] asks,

what must be the amount of a square, which, when twentyone dirhams are added to it, becomes equal to the equivalent of ten roots of that square? Solution: … nine. Or… fortynine.

See Figure 2. In our terms, if

x^{2} + 21 = 10x,

then

x = \frac{10}{2} ± \sqrt{(\frac{10}{2})^{2} − 21} = 5 ± \sqrt{4} = 5 ± 2 = 3 or 7,

so x^{2} = 9 or 49.

\begin{aligned}x^{2}  4 10 21 & & x^{2} 10 4  21 \\ & Figure 2 \end{aligned}

¶ 3. Descartes observes in the Geometry (1637) [2, pp. 4, 5]: lines can be multiplied to make lines, not rectangles. So, in Figure 3, if

AB = 1,  BD = a,  BC = b,

then

BE = ab.

Descartes’s purpose is apparently to use geometry as a model for field theory.

\begin{aligned}D & A & B & E & C \\ & Figure 3 \end{aligned}

He implicitly shows that the scalar field of a vector space (of dimension 2 or more) can be found in the space.

2. Vector spaces

¶ 4. A vector space is a triple (𝔙, 𝔎, ∗), where (1) 𝔙 is an abelian group of vectors,

(V, 0, −, +);

(2) 𝔎 is a field of scalars,

(K, 0, 1, −, +, ·);

(3) ∗ is an action of 𝔎 on 𝔙, that is, a function from K × V to V such that

(a) each operation

v ↦ x ∗ v

on V is an endomorphism of 𝔙, and

(b) the function

x ↦ (v ↦ x ∗ v)

is a ring-homorphism from 𝔎 to (End(𝔙), ∘).

So a vector space is a kind of 2-sorted structure, with the signature

{0, −, +; 0, 1, −, +, ·; ∗}.

¶ 5. Descartes’s example suggests how, given a vector space (𝔙, 𝔎, ∗), where

dim_{𝔎}(𝔙) ⩾ 2,

we can interpret 𝔎 and its action on 𝔙 in 𝔙. To do this, we introduce a new symbol ∥ for the binary relation of parallelism on V; this relation is defined by

u ∥ v ⇔ ∃x ∃y (x ∗ u + y ∗ v = 0 & (x ≠ 0 ∨ y ≠ 0)).

Now let

M = {(u, v) ∈ V × V : u ≠ 0 & u ∥ v}.

If (u, v) ∈ M, then we can define the element [u : v] of K by the rule

v = [u : v] ∗ u.

So we have a surjection (u, v) ↦ [u : v] from M onto K. This induces an equivalence-relation ∼ on M:

(u_{0}, u_{1}) ∼ (v_{0}, v_{1}) ⟺ [u_{0}, u_{1}] = [v_{0}, v_{1}].

We now give M/∼ the structure of 𝔎. We shall use the formula

s ∦ u & s ∥ t & u ∥ v & s − u ∥ t − v,

which we denote by

Δ(s, t, u, v).

See Figure 4. To interpret the field 𝔎 in 𝔙, we have to express the formulas

x = y,  x + y = z,  x · y = z,  x ∗ u = v

wholly in terms of vectors. We do this as follows:

\begin{matrix}t & s & 0 & v & u \\ Figure 4. Δ(s, t, u, v) \end{matrix}

t  s  0 u v  z w

Figure 5. [s : t] = [u : v] (one case)

\begin{matrix}u_{1} & 0 & u_{0} & z & v_{1} & v_{0} & u_{1} + z & w_{1} & w_{0} \\ Figure 6. [u_{0} : u_{1}] + [v_{0} : v_{1}] = [w_{0} : w_{1}] \end{matrix}

(1) Equality in K, or

[s : t] = [u : v],  (∗)

is expressed in 𝔙 by

Δ(s, t, u, v) ∨ ∃w ∃z (Δ(s, t, w, z) & Δ(w, z, u, v)),  (†)

where the latter condition is shown in Figure 5; now we can use (∗) to stand for (†).

(2) Addition in 𝔎, or

[u_{0} : u_{1}] + [v_{0} : v_{1}] = [w_{0} : w_{1}],

is expressed in 𝔙, as in Figure 6, by

∃z ([u_{0} : z] = [v_{0} : v_{1}] & [u_{0} : u_{1} + z] = [w_{0} : w_{1}].

(3) Multiplication in 𝔎, or

[u_{0} : u_{1}] · [v_{0} : v_{1}] = [w_{0} : w_{1}], is expressed in 𝔙, as in Figure 7, by

∃z ([u_{1} : z] = [v_{0} : v_{1}] & [u_{0} : z] = [w_{0} : w_{1}].

\begin{matrix}0 & u_{0} & u_{1} & v_{1} & v_{0} & z & w_{1} & w_{0} \\ Figure 7. [u_{0} : u_{1}] · [v_{0} : v_{1}] = [w_{0} : w_{1}] \end{matrix}

(4) Finally, scalar multiplication, or

[u_{0} : u_{1}] ∗ v_{0} = v_{1},

is expressed in 𝔙 by

[u_{0} : u_{1}] = [v_{0} : v_{1}] ∨ (v_{0} = 0 & v_{1} = 0).

¶ 6. So one can define a vector space as a pair (𝔙, ∥_{𝔎}), where (1) 𝔙 is an abelian group (V, 0, −, +), and

(2) the binary relation ∥ respects axioms ensuring that 𝔙 is acted on by

a field, 𝔎. In this sense, a vector space is a 1-sorted structure in the signature

{0, −, +, ∥}.

However, the two notions of a vector space are not entirely equivalent, and not just because spaces in the latter sense are at least 2-dimensional. The substructure relation differs also. For example, we have

(ℍ, ℝ, ∗) ⊆ (ℍ, ℂ, ∗),

but

(ℍ, ∥_{ℝ}) ⊈ (ℍ, ∥_{ℂ}),

since the relations ∥_{ℝ} and ∥_{ℂ} do not agree, even on ℂ (much less on ℍ):

1 ∦_{ℝ} i,  1 ∥_{ℂ} i.

(However, (ℂ, ∥_{ℝ}) ⊆ (ℍ, ∥_{ℂ}).)

¶ 7. Let VS be the theory of vector spaces in the original sense, in the signature

{0, −, +; 0, 1, −, +·; ∗}.

That is, VS is the set of sentences of first-order logic in the given signature that are true in all vector spaces. (A logic is first order when all variables stand for individuals, not sets as such.) Every model (𝔙, 𝔎, ∗) of VS embeds in a 1-dimensional model

(𝔏, 𝔏, ∗);

just let 𝔏 be a field-extension of 𝔎 such that

[𝔏 : 𝔎] ⩾ dim_{𝔎} 𝔙,

and embed a basis of (𝔙, 𝔎, ∗) in a basis of (𝔏, 𝔎, ∗).

¶ 8. Let VS_{2} be the theory of vector spaces of dimension at least 2 in the signature

{0, −, +, ∥}.

Every model embeds in a 2-dimensional model. Indeed, suppose L/K is a field-extension, and a, b ∈ L, and (a, b, 1) is linearly independent over K. Then (K^{3}, ∥_{K}) embeds in (L^{2}, ∥_{L}) under

(x, y, z) ↦ (x − az, y − bz),

that is,

(x y z) ↦ (x y z) (\begin{matrix}1 & 0 \\ 0 & 1 \\ −a & −b \end{matrix}) .

For, the following are equivalent:

(x, y, z) ∥_{K} (u, v, w),
0 = det (\begin{matrix}x & y & z \\ u & v & w \\ a & b & 1 \end{matrix})

= det ((\begin{matrix}x & y \\ u & v \end{matrix}) − (\begin{matrix}z \\ w \end{matrix}) (a b))

= det ((\begin{matrix}x & y & z \\ u & v & w \end{matrix}) (\begin{matrix}1 & 0 \\ 0 & 1 \\ −a & −b \end{matrix})) ,

(x − az, y − zb) ∥_{L} (u − aw, v − bw).

We used here the identity

det ( \begin{matrix}U & v^{t} \\ a & 1 \end{matrix} ) = det(U − v^{t} · a),

which follows from

( \begin{matrix}U & v^{t} \\ a & 1 \end{matrix} ) · ( \begin{matrix}I & 0^{t} \\ −a & 1 \end{matrix} ) = ( \begin{matrix}U − v^{t} · a & v^{t} \\ 0 & 1 \end{matrix} ) .

3. Model theory (outline)

¶ 9. We have entered model theory, which I define as

the study of structures quâ models of theories.

Examples of structures include

(𝔙, 𝔎, ∗), (𝔙, ∥_{𝔎}), (ℚ, <), (ℚ, +, ·), (ℝ, +, ·, <), (ℂ, +, ·).

Model theory has also been called

the geography of tame mathematics.

Tameness has no one definition. However, one measure of tameness is the effective axiomatizability of the (first-order) theory,

Th(𝔄),

of a structure 𝔄.

¶ 10. In the following,

ℕ = {1, 2, 3, … },

and S stands for x ↦ x + 1. Outer universal quantifiers of sentences are suppressed. The structure (ℕ, 1, S, +) is “tame”, because of:

Theorem (Presburger, 1929). Th(ℕ, 1, S, +) is axiomatized by:

(1) 1 ≠ Sx;

(2) Sx = Sy ⇒ x = y;

(3) x + 1 = Sx;

(4) x + (y + 1) = (x + y) + 1;

(5) the first-order induction axioms: for each formula φ(x),

φ(1) & ∀x (φ(x) ⇒ φ(Sx)) ⇒ ∀φ (x).

¶ 11. An arbitrary theory T is complete if

T ⊢ σ or T ⊢ ¬σ

for all sentences σ of the signature of T. The theory of a structure is automatically complete. Then Presburger’s theorem is that a particular theory given by axioms is complete.

¶ 12. By contrast, (ℕ, 1, S, +, ·) is “wild”, by Gödel’s Incompleteness Theorem:

Theorem (Gödel, 1931 [5]). Th(ℕ, 1, S, +, ·) cannot be effectively axiomatized.

¶ 13. Even though Th(ℕ, 1, S, +) can be (effectively) completely axiomatized in first-order logic, the axioms do not determine (ℕ, 1, S, +) (up to isomorphism), as we shall see. However, (ℕ, 1, S) is characterized (up to isomorphism) by its satisfaction of the axioms identified by Dedekind (1888)

[1] and Peano (1889) [9], namely Presburger’s (1) and (2)—

1 ≠ Sx,  Sx = Sy ⇒ x = y,

—along with the second-order induction axiom: the sentence

1 ∈ X & ∀t (t ∈ X ⇒ St ∈ X) ⇒ ∀t t ∈ X.

¶ 14. That (ℕ, 1, S) satisfies (second-order) induction means ℕ is the smallest set that contains 1 and is closed under S. Another way to say this is that ℕ has a recursive definition:

(1) 1 ∈ ℕ,

(2) if x ∈ ℕ, then Sx ∈ ℕ.

This, together with the other two axioms (1) and (2), is logically equivalent to the validity of recursive definitions of operations on ℕ: operations such as addition, given by Presburger’s (3) and (4)—

x + 1 = Sx,  x + (y + 1) = (x + y) + 1

—, or multiplication, given by

x · 1 = x,  x · (y + 1) = x · y + x,

or exponentiation, given by

x^{1} = x,  x^{y+1} = x^{y} · x.  (‡)

In particular, despite Gödel’s Incompleteness Theorem, (ℕ, 1, S, +, ·) can be completely characterized, in a sense, in second-order logic.

¶ 15. From Peano on, some people have not recognized that the possibility of defining a set recursively does not, by itself, allow functions on the set to be defined recursively. Addition and multiplication are justified by induction alone, as is shown implicitly in Landau’s Foundations of Analysis (1929) [8]; but exponentiation is not:

Theorem (Dyer-Bennet, 1940 [3]; P., 2009). If n ∈ ℕ, then (ℤ/(n), 1, S) satisfies (second-order) induction; but it admits exponentiation defined as in (‡) if and only if n ∈ {1, 2, 6, 42, 1806}.

4. Model theory (detail)

¶ 16. That induction does not always imply recursion can be seen in the development of logic itself. I now review this development in detail. To be precise then, a structure is one or more disjoint sets called sorts, together with some (or no) distinguished

(1) operations: functions from finite products of sorts to one sort;

(2) constants: operations taking no arguments;

(3) relations: subsets of finite products of the sorts. If G is a group, and f is the function X ↦ ⟨X⟩ that converts a subset of G into the subgroup that it generates, then the pair

(G, f)

is not a structure, although the quadruple

(G, 𝒫(G), ∈, f)

is a (two-sorted) structure.

¶ 17. A structure has a signature, namely a set of symbols for the distinguished operations (including constants) and relations. So the signature of (𝔙, 𝔎, ∗) is

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

The symbols ‘know’ which sorts their arguments are from. The symbols are called non-logical, to distinguish them from logical symbols, namely,

(1) Boolean connectives: ¬, &, ∨, ⇒, ⇔, …;

(2) quantifiers: ∃ and ∀;

(3) punctuation: ( and );

(4) the sign of equality, =;

(5) variables. In first-order logic, each variable is required to range only over the elements of a particular sort, and not (for example) over the subsets of a sort. In talking about (𝔙, 𝔎, ∗), we let boldface variables like u range over V; and plainface variables like x, over K.

¶ 18. From logical and non-logical symbols, one builds up formulas that refer to structures of a particular signature. The construction will be discussed later. All formulas here will be first-order, unless otherwise specified. A formula may have free variables; if it does not, then the formula is a sentence. A sentence is either true or false in a structure (with a suitable signature); if the sentence σ is true in the structure 𝔄, we write

𝔄 ⊨ σ;

we may say also that 𝔄 satisfies σ. For example,

ℚ ⊨ ∀x ∃y (x = 0 ∨ x · y = 1),
ℤ ⊭ ∀x ∃y (x = 0 ∨ x · y = 1).

A set of sentences of some signature is a theory. If T is a theory, and all of its elements are true in 𝔄, then 𝔄 is a model of T. If σ is a sentence that is true in every model of T, then σ is a logical consequence of T, and we may write

T ⊨ σ.

¶ 19. A (first-order) theory T is complete if, for every sentence σ of its signature, either T ⊨ σ or T ⊨ ¬σ. The set of sentences that are true in 𝔄 is the theory of 𝔄, denoted by

Th(𝔄);

it is automatically complete. If Σ ⊆ T, and every sentence of T is a logical consequence of Σ, then Σ is a set of axioms for T.

¶ 20. Given a signature ℒ and a set C of parameters, we recursively define the set

Fm_{ℒ} (C)

of first-order formulas of ℒ in C. For each formula, there is a finite tree, as in Figure 8, proving that the formula is a formula. Moreover, such trees are unique; so we can also recursively define functions on Fm_{ℒ} (C). For example, given an ℒ -structure 𝔄 that includes C, and given a function v that assigns values from 𝔄 to the variables used in formulas, we can determine recursively whether

𝔄 ⊨ φ[v],

that is, whether φ true in 𝔄 under v.

¶ 21. We distinguish some sentences as logical axioms. Then the set of theorems is the closure of the set of axioms under detachment (or modus ponens,

(σ, (σ ⇒ τ)) ↦ τ.

Again, for each theorem, there is a finite tree, as in Figure 9, proving that the theorem is a theorem. But now the tree is not unique; so we cannot define

∃x ∃y (x ∗ u + y ∗ v = 0 & (x ≠ 0 ∨ y ≠ 0)) ; ∃y (x ∗ u + y ∗ v = 0 & (x ≠ 0 ∨ y ≠ 0)) ; (x ∗ u + y ∗ v = 0 & (x ≠ 0 ∨ y ≠ 0)) ; x ∗ u + y ∗ v = 0 ; (x ≠ 0 ∨ y ≠ 0) ; \begin{aligned}x ≠ 0 \\ & y ≠ 0 \end{aligned} ; Figure 8

¬∃x φ ; ¬φ(a) ; (¬φ(a) ⇒ ¬∃x φ) ; \begin{aligned}(¬φ(a) ⇒ ¬φ(b)) \\ & ((¬φ(a) ⇒ ¬φ(b)) ⇒ (¬φ(a) ⇒ ¬∃x φ)) \end{aligned}

Figure 9. Proof of ¬∃x φ, where φ is ¬(x = x ⇒ x = x)

functions recursively on the set of theorems. These points are elaborated in the following paragraphs.

¶ 22. Let PV be a set of propositional variables, perhaps

{P_{n}: n ∈ ℕ}.

The set of propositional formulas, say PF, is the smallest set that includes PV and is closed under the operations

F ↦ ¬F,  (F, G) ↦ (F & G).

This just means PF satisfies induction (with respect to PV and these operations).

¶ 23. More is true: Functions can be defined recursively on PF, because there is only one way to construct a given formula. For example, suppose h: PV → 𝔽_{2} (where 𝔽_{2} is a two-element field). Then h extends uniquely to a function H on PF such that

H(¬F) = 1 + H(F),  H(F & G) = H(F) · H(G).

A propositional formula F is a tautology if H(F) = 1 for all choices of h.

¶ 24. In practice, one uses abbreviations in formulas, as

(F ∨ G) for ¬(¬F & ¬G),
(F ⇒ G) for ¬F ∨ G,
(F ⇔ G) for ((F ⇒ G) & (G ⇒ F)).

¶ 25. Let us now develop first-order logic in a signature ℒ. For simplicity, we assume ℒ is the signature of a one-sorted structure; for definiteness, we assume

ℒ = {0, −, +, ∥}.

Fix a set X of individual variables. Let C be a set of parameters— individuals from some ℒ -structure 𝔙. The set of terms over C is the smallest set that includes X and is closed under

c,  0,  t ↦ −t,  (t, u) ↦ (t + u),

where c ranges over C. Call this set

Tm_{ℒ} (C);

by definition, it satisfies induction with respect to X and the given operations.

¶ 26. Also, functions can be defined recursively on Tm_{ℒ} (C), because there is only one way to construct a given term. For example, if v: X → V, then there is a unique function ṽ from Tm_{ℒ} (C) into V that extends v and satisfies

ṽ(c) = c, ṽ(0) = 0, ṽ(−t) = −ṽ(t), ṽ(t + u) = ṽ(t) + ṽ(u).

Here, for example, t + u is a string of symbols; but ṽ(t) + ṽ(u) is the image of (ṽ(t), ṽ(u)) under the operation of + on 𝔙.

¶ 27. We now define simultaneously the set Fm_{ℒ} (C) of formulas over C and the function assigning to each formula φ its set F V (φ) of free variables.

(1) If t, u ∈ Tm_{ℒ} (C), then the strings

t = u,  t ∥ u

are in Fm_{ℒ} (C), and both F V (t = u) and F V (t ∥ u) consist of the variables actually appearing in t or u.

(2) Fm_{ℒ} (C) is closed under φ ↦ ¬φ, and

F V (¬φ) = F V (φ).

(3) If φ is in Fm_{ℒ} (C), and x ∈ F V (φ), then ∃x φ is in Fm_{ℒ} (C), and

F V (∃x φ) = F V (φ) ∖ {x}.

(4) If φ and ψ are in Fm_{ℒ} (C), and no variable occurring non-freely in one of them occurs (freely or non-freely) in the other, then (φ & ψ) is in Fm_{ℒ} (C), and

F V (φ & ψ) = F V (φ) ∪ F V (ψ).

Then Fm_{ℒ} (C) satisfies a kind of induction. Moreover functions can be defined recursively on Fm_{ℒ} (C). Indeed, if v: X → V as above, and φ is a formula, let φ[v] be the result of replacing each instance of each free variable x in φ with v(x). Then φ[v] is true in 𝔙, and we write

𝔙 ⊨ φ[v],

according to the following recursive definition.

(1) 𝔙 ⊨ (t = u)[v] if and only if

ṽ(t) = ṽ(u).

(2) 𝔙 ⊨ (t ∥ u)[v] if and only if

ṽ(t) ∥ ṽ(u)

(3) 𝔙 ⊨ ¬φ[v] if and only if

𝔙 ⊭ φ[v].

(4) 𝔙 ⊨ ∃x φ[v] if and only if

𝔙 ⊨ φ[v′]

for some v′ that agrees with v on F V (∃x φ). A formula σ is a sentence if F V (σ) = ∅. In this case, σ[v] is just σ. If σ is true in all ℒ -structures that include C, then σ is logically valid, and we may write simply

⊨ σ.

¶ 28. If we use sentences as propositional variables, then a propositional formula is also a sentence: if the propositional formula is a tautology, then we may refer also to the sentence as a tautology. If F V (φ) = {x}, and c ∈ C, then φ(c) is the result of replacing each instance of x in φ with c. Now we define a sentence to be a logical axiom if it is:

(1) a tautology;

(2) a sentence of one of the forms

t = t,
(t = u ⇒ u = t),
((t = u & u = s) ⇒ t = s),
(c = d ⇒ (φ(c) ⇒ φ(d)));

(3) a sentence

(σ ⇒ σ′),

where σ and σ′ are sentences, and we get σ′ from σ by replacing each occurrence of x with y;

(4) a sentence

(φ(c) ⇒ ∃x φ(x));

(5) a sentence

((σ ⇒ ¬φ(c)) ⇒ (σ ⇒ ¬∃x φ(x))),

where c does not occur in σ. The set of theorems is the smallest set that contains the logical axioms and that contains τ if it contains σ and (σ ⇒ τ).

¶ 29. If σ is a theorem, we may write

⊢ σ.

Every theorem is valid: if ⊢ σ, then ⊨ σ. The converse is Gödel’s Completeness Theorem:

Theorem (Gödel, 1930). If ⊨ σ, then ⊢ σ.

A sentence σ is provable from a collection S of sentences, and we may write

S ⊢ σ,

if some sentence

τ_{0} & ⋯ & τ_{n−1} ⇒ σ

is a theorem, where τ_{0}, …, τ_{n−1} are in S.

Theorem (Malcev, 1936). If S ⊨ σ, then S ⊢ σ.

Corollary (Compactness Theorem). If every finite subset of S has a model, then S has a model.

Proof. If S has no model, then

S ⊨ 0 ≠ 0,  S ⊢ 0 ≠ 0,  S_{0} ⊢ 0 ≠ 0

for some finite subset S_{0} of S; but then S_{0} has no model. □

Compactness fails in second-order logic: The Dedekind–Peano Axioms, together with

{c ≠ 1, c ≠ S1, c ≠ SS1, c ≠ SSS1, … },

have no model, although every finite subset does.

5. Model theory of fields

¶ 30. Henceforth the logic is first-order. If 𝔄 is a structure (of one sort, for simplicity,) in a signature ℒ, and φ ∈ Fm_{ℒ} (A) with free variables from the list (x_{1}, …, x_{n}), and (c_{1}, …, c_{n}) ∈ A^{n}, then the result of replacing each free variable x_{k} in φ with c_{k} is denoted by

φ(c_{1}, …, c_{n}).

Then φ defines in 𝔄 the n-ary relation

{(c_{1}, …, c_{n}) ∈ A^{n}: 𝔄 ⊨ φ(c_{1}, …, c_{n})},

which can be denoted by

φ^{𝔄}.

A definable set is a singulary definable relation. If F V (ψ) = {x_{1}, …, x_{n}, y}, then

(∃y ψ)^{𝔄} = π(ψ^{𝔄}),

\begin{aligned}A^{n} & A & ψ^{𝔄} & (∃y ψ)^{𝔄} & π \\ & Figure 10 \end{aligned}

where π is the projection given by

π(c_{1}, …, c_{n}, d) = (c_{1}, …, c_{n}).

See Figure 10. A theory T admits quantifier-elimination (QE) if, for every model 𝔄 of T, the collection of relations definable by quantifier-free formulas is closed under projection. Having a theory with QE is a further measure of tameness.

¶ 31. Let ACF be the theory of algebraically closed fields: field theory, together with, for each n in ℕ,

∀t_{1} ⋯ ∀t_{n} ∃x x^{n} + t_{1}x^{n−1} + ⋯ + t_{n−1}x + t_{n} = 0.  (§)

Let ACF_{0} be the theory of algebraically closed fields of characteristic 0, namely ACF together with, for each prime p,

\underbrace{1 + ⋯ + 1}_{p} ≠ 0.

Let RCF be the theory of real-closed ordered fields: the theory of ordered fields, together with (§) for each odd n in ℕ, and also

∀y ∃x (y > 0 ⇒ y = x^{2}).

Theorem (Tarski^{1}). ACF and RCF admit QE. In particular, the definable sets:

(1) in an algebraically closed field, are the finite and co-finite sets;

(2) in a real-closed field, are the finite unions of intervals and singletons.

¶ 32. A structure 𝔄 has a diagram, denoted by

diag(𝔄);

this is the set of quantifier-free sentences with parameters from A that are true in 𝔄.

Theorem. For a theory T, the following are equivalent:

(1) T admits QE; (2) whenever 𝔄 ⊆ 𝔐 for some model 𝔐 of T, and 𝔄 is finitely generated,

1According to Hodges [6, p. 85], Tarski announced these results in 1949, publishing the proof the result on RCF in [11].

the theory

T ∪ diag(𝔄)

is complete.

¶ 33. By considering prime fields, we can now conclude:

Theorem.

(1) Th(ℂ, +, ·) is axiomatized by ACF_{0}.

(2) Th(ℝ, +, ·, <) is axiomatized by RCF.

¶ 34. If T ∪ diag(𝔐) is complete whenever 𝔐 ⊨ T, then T is called model complete.^{2} So ACF and RCF and all other theories with QE are model complete.

¶ 35. A theory T^{∗} is a model companion of a theory T (in the same signature if

(1) a model of one embeds in a model of the other, that is,

T_{∀} = T^{∗}_{∀};

(2) T^{∗} is model complete. So ACF and RCF are model companions of the theories of fields and ordered fields, respectively.

¶ 36. model companions are useful for the following reason. Suppose T^{∗} is a model companion of T, and

𝔐 ⊨ T^{∗},  𝔑 ⊨ T,  𝔐 ⊆ 𝔑.

Say φ is quantifier-free, with parameters from M, and

𝔑 ⊨ ∃x φ.

Then

𝔐 ⊨ ∃x φ.

Indeed, we have 𝔑 ⊆ 𝔐′ for some model 𝔐′ of T^{∗}. Then 𝔐′ ⊨ ∃x φ, so

T^{∗} ∪ diag(𝔐) ⊨ ∃x φ.

6. Model theory of vector spaces

¶ 37. Let VS_{K} be the theory of vector spaces over the field 𝔎, in the signature

{0, −, +} ∪ {a∗: a ∈ K}.

This theory admits QE.

¶ 38. Let VS be the theory of vector spaces over an arbitrary field, in the signature

{0, −, +, 0, −, +, ∗}.

This has a model companion, namely the theory of one-dimensional vector spaces over an algebraically closed field. In particular, every space embeds in a one-dimensional space.

2The definition is due to Abraham Robinson.

¶ 39. Let VS^{2} be the theory of vector-spaces of dimension at least 2:

VS^{2} = VS ∪{∃u ∃v ∀x ∀y (x ∗ u + y ∗ v = 0 ⇒ x = 0 & y = 0)}.

This has the same model companion as VS, but is not included in a model complete theory, because the union of a chain of models of VS^{2} need not be a model. For example, let

K_{n} = ℚ(π^{1/2^{n}}),  L = ⋃_{n∈ℕ}K_{n} = ℚ(π, π^{1/2}, π^{1/4}, …).

Then (K_{n+1}, K_{n}) ⊨ VS_{2}, and

(K_{n+1}, K_{n}) ⊆ (K_{n+2}, K_{n+1}),

but

⋃_{n∈ℕ}(K_{n+1}, K_{n}) = (L, L),

a model of VS, but not VS^{2}.

¶ 40. As before, let VS_{2} be the theory of vector spaces of dimension at least 2 in the signature

{0, −, +, ∥}.

This has a model companion, namely the theory of 2-dimensional vector spaces over an algebraically closed field.

¶ 41. More generally, if n ∈ ℕ, let VS_{n} be the theory of vector spaces of dimension at least n in the signature

{0, −, +, ∥^{n}},

where ∥^{n} stands for the n-ary relation of linear dependence. (If we include the signature of the scalar field, then the space can have any dimension.) This has a model companion, namely the theory of n-dimensional vector spaces over an algebraically closed field. For, if again K ⊆ L, and (a_{1}, …, a_{n}, 1), that is, (a, 1), is an (n + 1)-tuple from L that is linearly independent over K, then (K^{n+1}, ∥_{K}^{n}) embeds in (L^{n}, ∥_{L}^{n}) under

x ↦ x · ( \frac{I_{n}}{−a} ) .

¶ 42. There is an analogy with fields. Let

M = K(a_{0}, …, a_{n}),

where (a_{0}, …, a_{n}) is algebraically independent over K. Then there is a field L such that K ⊆ L, and

tr-deg(ML/L) = n,

but if (b_{1}, …, b_{n}) from M is algebraically independent over K, then it remains so over L. Indeed, we can take

L = K(x, y),

where x is transcendental over M, but

y = ∑_{k=0}^{n} a_{k}x^{k}.

References

[1] Richard Dedekind, Essays on the theory of numbers. I: Continuity and irrational numbers. II: The nature and meaning of numbers, authorized translation by Wooster Woodruff Beman, Dover Publications Inc., New York, 1963. MR MR0159773 (28 #2989)

[2] Descartes, The geometry of René Descartes, Dover Publications, Inc., New York, 1954, Translated from the French and Latin by David Eugene Smith and Marcia L. Latham, with a facsimile of the first edition of 1637.

[3] John Dyer-Bennet, A theorem on partitions of the set of positive integers, Amer. Math. Monthly 47 (1940), 152–154. MR MR0001234 (1,201b)

[4] Euclid, Euclid’s Elements, Green Lion Press, Santa Fe, NM, 2002, All thirteen books complete in one volume, the Thomas L. Heath translation, edited by Dana Densmore. MR MR1932864 (2003j:01044)

[5] Kurt Gödel, On formally undecidable propositions of principia mathematica and related systems I (1931), From Frege to Gödel (Jean van Heijenoort, ed.), Harvard University Press, 1976, pp. 596–616.

[6] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 94e:03002

[7] Victor J. Katz (ed.), The mathematics of Egypt, Mesopotamia, China, India, and Islam: A sourcebook, Princeton University Press, Princeton and Oxford, 2007.

[8] Edmund Landau, Foundations of analysis. The arithmetic of whole, rational, irrational and complex numbers, third ed., Chelsea Publishing Company, New York, N.Y., 1966, translated by F. Steinhardt; first edition 1951; first German publication, 1929. MR 12,397m

[9] Giuseppe Peano, The principles of arithmetic, presented by a new method (1889), From Frege to Gödel (Jean van Heijenoort, ed.), Harvard University Press, 1976, pp. 83–97.

[10] David Pierce, Model-theory of vector-spaces over unspecified fields, Arch. Math. Logic 48 (2009), no. 5, 421–436. MR MR2505433

[11] Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley and Los Angeles, Calif., 1951, 2nd ed. MR MR0044472 (13,423a)

Mathematics Dept, METU, Ankara 06531, Turkey

E-mail address: dpierce@metu.edu.tr
URL: http://metu.edu.tr/~dpierce/