CONNECTIONS BETWEEN FINITE AND INFINITE MODEL THEORY

Part I Finite variable theories

1 Finite variable logic; basic definitions and notation Let V = {v_{1}, v_{2}, v_{3}, …} be a set of variables. x, y, z, x̄, ȳ, z̄, sometimes with indices will denote variables or (finite) sequences of variables. L will always denote the set of all first-order formulas over some vocabulary (or signature). We assume that L is countable. If a formula in L is denoted by φ(x̄) then we mean that every free variable in that formula belongs to the sequene x̄. For any n < ω, L^{n} denotes the set of all formulas φ(x̄) ∈ L such that at most n distinct variables occur in φ(x̄) (whether bound or free). An L^{n}-theory is a set of sentences from L^{n}. An L^{n}-theory T is called a complete L^{n}-theory if for any sentence φ ∈ L^{n}, T ⊢ φ or T ⊢ ¬φ; of course, a complete L^{n}-theory need not be complete with respect to L. If M is an L-structure then let

T h_{L^{n}}(M) = {φ ∈ L^{n} : φ is a sentence and M ⊧ φ}. So T h_{L^{n}}(M) is always a complete L^{n}-theory.

2 Examples

L^{n}-theories may have only infinite models, only finite models or both infinite and finite models.

(a) M = (ℕ, S); S = successor function/relation. T h_{L^{3}}(M) has no finite model.

(b) M = (ℚ, <). T h_{L^{3}}(M) has no finite model.

(c) Let M be a finite graph such that v_{1}, …, v_{m} lists all vertices of M and there is an edge between v_{i} and v_{j}, where i < j, if and only if i < m and j = i+1. Then any model of T h_{L^{3}}(M) is isomorphic to M.

(d) Let M be an infinite tree such that for some m < ω, no path in M has length m. T h_{L^{n}}(M) has arbitrarily large finite models, for any n.

(e) Let K be a finite field. Let T be a set of sentences wich formalize the axioms of a K-vector space. With scalar multiplication and vector addition represented by function symbols we may assume that T is an L^{3}-theory. With scalar multiplication and vector addition represented by relation symbols we may assume that T is an L^{7}-theory. T has arbitrarily large finite models and (hence) infinite models.

We are interested in finding conditions under which an L^{n}-theory with infinite models will also have (arbitrarily large) finite models.

3 Various types Let Φ ⊆ L, let M be an L-structure and let A ⊆ M. Define

T h_{Φ}(M, A) = {φ(ā) : φ(x̄) ∈ Φ, M ⊧ φ(ā)},

and let T h_{Φ}(M) = T h_{Φ}(M, ∅) which is the set of sentences in Φ that are true in M. For a sequence of variables x̄ we define

Φx̄(A) = {φ(x̄, ā) : φ(x̄, ȳ) ∈ Φ, ā ∈ A},

and Φx̄ = Φx̄(∅). A Φ-type over A (with respect to T h_{Φ}(M, A)) in the free variables x̄ is a set p(x̄) ⊆ Φx̄(A) such that p(x̄)∪T h_{Φ}(M, A) is consistent. A Φ-type p(x̄) over A is called a complete Φ-type over A if whenever φ(x̄, ā) ∈ Φx̄(A) then φ(x̄, ā) ∈ p(x̄) or ¬φ(x̄, ā) ∈ p(x̄). S_{m}^{Φ}(A, M) is the set of all complete Φ-types over A (with respect to T h_{Φ}(M, A)) in the free variables v_{1}, …, v_{m}. We write S_{m}^{n}(A, M) instead of S_{m}^{L^{n}}(A, M). For a complete L^{n}-theory T we define S_{m}^{n}(T) = S_{m}^{n}(∅, M), where M is any model of T (so T h_{L^{n}}(M, ∅) = T).

4 Some facts about L^{n}-types

Fact 4.1 For any complete L-theory T, S_{n}^{n}(T) is finite if and only if there are only finitely many L^{n}-formulas in the free variables v_{1}, …, v_{n} up to equivalence modulo T.

Fact 4.2 (Dawar, Lindell, Weinstein; Poizat) Suppose that the vocabulary of L is finite and contains no function symbols. If T is a complete L^{n}-theory and S_{n}^{n}(T) is finite then there is φ ∈ L^{n} that axiomatizes T (i.e. φ ⊢ T and T ⊢ φ). Moreover, we can choose φ so that its quantifier rank is at most |S_{n}^{n}(T)| + n.

Fact 4.3 (i) If a complete L^{n}-theory T has a finite model M then |S_{n}^{n}(T)| ≤ |M|^{n}. (ii) If T is a complete L^{n}-theory and S_{n}^{n}(T) is infinite then T has no finite models.

Thus, when looking for finite models of a complete L^{n}-theory T we can rule out the case when S_{n}^{n}(T) is infinite.

5 Closure maps

Definition 5.1 Let M be an L-structure.

(i) We call a function cl : P(M) → P(M) a closure map/function if whenever A ⊆ B ⊆ M then A ⊆ cl(A), cl(cl(A)) = cl(A) and cl(A) ⊆ cl(B). (ii) If cl(A) = A then we say that A is closed.

A few examples:

(a) If cl(A) = A for any A ⊆ M then cl is a closure map; we say that such a closure map is trivial.

(b) If, for every A ⊆ M, cl(A) is the substructure of M which A generates then cl is a closure map.

(c) If, for every A ⊆ M, cl(A) is the algebraic closure of A then cl is a closure map.

(d) If M is a vector space and cl(A) is the linear span of A then cl is a closure map.

6 Amalgamation classes

Let Φ ⊆ L.

If M and N are L structures and a_{i} ∈ M, b_{i} ∈ N, for i < λ, then we write

(M, (a_{i} : i < λ)) ≡_{Φ} (N, (b_{i} : i < λ))

if for every m < ω and φ(x_{1}, … x_{m}) ∈ Φ and {i_{1}, …, i_{m}} ⊆ λ,

M ⊧ φ(a_{i_{1}}, …, a_{i_{m}}) if and only if N ⊧ φ(b_{i_{1}}, …, b_{i_{m}}).

A function f : A → N, where A ⊆ M, is called a Φ-elementary embedding if for every φ(x̄) ∈ Φ and ā ∈ A with |ā| = |x̄|, we have

M ⊧ φ(ā) if and only if N ⊧ φ(f(ā)).

If M ⊆ N are L-structures such that for every φ(x̄) ∈ Φ and every ā ∈ M with |ā| = |x̄|, M ⊧ φ(ā) if and only if N ⊧ φ(ā), then we say that M is a Φ-elementary substructure of N and that N is a Φ-elementary extension of M, which we write as M ≼_{Φ} N.

Assumption 6.1 For the rest of this section we assume the following:

(1) T ⊆ Φ is a set of sentences.

(2) Φ is closed under subformulas.

(3) For any M ⊧ T a closure map cl is fixed such that if M, N ⊧ T, a_{i} ∈ M, b_{i} ∈ N, for i < λ and

(M, (a_{i} : i < λ)) ≡_{Φ} (N, (b_{i} : i < λ))

then {a_{i} : i < λ} is closed if and only if {b_{i} : i < λ} is closed.

(4) cl is uniformly locally finite on every M ⊧ T; that is, for every M ⊧ T and m < ω there is m′ < ω such that if A ⊆ M and |A| ≤ m then |cl(A)| ≤ m′.

Definition 6.2 A non-empty class A of L-structures is called a Φ-amalgamation class for T if:

(1) Every structure in A is a model of T.

(2) A is closed under isomorphisms.

(3) A is closed under Φ-elementary substructures, i.e. if N ∈ A and M ≼_{Φ} N then M ∈ A.

(4) Whenever M_{1}, M_{2} ∈ A and ā ∈ M_{1}, b̄ ∈ M_{2} are closed sequences of the same length and

(M_{1}, ā) ≡_{Φ} (M_{2}, b̄),

then there are N ∈ A and a Φ-elementary embedding f : M_{2} → N such that M_{1} ≼_{Φ} N and f(b̄) = ā.

Remark 6.3 If there is a Φ-amalgamation class for T then there is, by the downward Löwenheim-Skolem theorem, an amalgamation class for T such that all structures in it are countable.

A couple of examples:

(a) Let n ≥ 4, let M be a tree such that for some m < ω no path in M has length m and let T = T h_{L^{n}}(M). Moreover, for any M ⊧ T and any A ⊆ M let cl(A) = A. Then the class of all models of T is an L^{n}-amalgamation class for T.

(b) Let n ≥ 3, let K be a finite field and let T ⊆ L^{3} formalize the axioms of K-vector spaces in a language where scalar multiplication and vector addition is represented by function symbols. For any M ⊧ T and any A ⊆ M let cl(A) be the substructure which is generated by A. Then the class of all models of T is an L^{n}-amalgamation class for T. But if we would have defined cl as in (a) then T would not have any L^{n}-amalgamation class; this is a consequence of results that will follow.

Definition 6.4 Suppose that A is a Φ-amalgamation class for T.

(i) We say that p ⊆ Φ is a closed (Φ, A)-type if there are M ∈ A and a closed finite sequence ā ∈ M such that

p = {φ(x̄) ∈ Φ : M ⊧ φ(ā)}.

(ii) We say that an L-structure M is (Φ, ω, A)-saturated for closed sets if whenever b̄ ∈ N ∈ A, ā ∈ M ∩ N, ā and b̄ā are closed finite sequences and

(M, ā) ≡_{Φ} (N, ā),

then there exists c̄ ∈ M such that (M, c̄ā) ≡_{Φ} (N, b̄ā); from an earlier assumption it follows that c̄ā is closed.

Lemma 6.5 If A is a Φ-amalgamation class for T such that the set of all closed (Φ, A)-types is countable, then there exists a countable L-structure M, such that

(i) M ⊧ T

(ii) M is (Φ, ω, A)-saturated, and

(iii) for every finite ā ∈ M there exists N ∈ A such that ā ∈ N and (M, ā) ≡_{Φ} (N, ā).

The proof is like a Fraissé construction except that we deal with Φ-elementary substructures instead of substructures and amalgamation is according to point (4) in the definition of a Φ-amalgamation class; we make use of the fact that if there is an amalgamation class for T then there is one in which all structures are countable.

Definition 6.6 If M is a model like in Lemma ?? then we call M a limit of A.

Lemma 6.7 Suppose that every unnested atomic formula of L is equivalent to a formula in Φ. Let A be a Φ-amalgamation class for T and suppose that M and N are limits of A. Then for any closed finite sequences ā ∈ M and b̄ ∈ N with |ā| = |b̄|,

if (M, ā) ≡_{Φ} (N, b̄) then (M, ā) ≡_{L} (N, b̄).

Proofsketch. Using properties (ii) and (iii) of Lemma ?? one carries out a back and forth argument which shows that there is an isomorphism from M to N which sends ā to b̄. □

Definition 6.8 An L-structure M is Φ-determined if for any closed finite sequences ā, b̄ ∈ M,

if (M, ā) ≡_{Φ} (M, b̄) then (M, ā) ≡_{L} (M, b̄).

By Lemma ??, any limit of a Φ-amalgamation class is Φ-determined.

We have seen that the existence of a Φ-amalgamation class for T implies that T has a model which is Φ-determined. We also have a partial converse, but we need the following definition:

An L-structure M is ω-homogeneous if for any finite sequences ā, b̄ ∈ M such that (M, ā) ≡_{L} (M, b̄) and for any c ∈ M there is d ∈ M such that (M, āc) ≡_{L} (M, b̄d).

Lemma 6.9 If M a model of T which is Φ-determined and either finite, or infinite and ω-homogeneous, then there is a Φamalgamation class for T.

Proofsketch. Take as the Φ-amalgamation class all N which are isomorphic to some countable N′ ≼_{Φ} M. □ Recall that Φx̄ = {φ(x̄) : φ(x̄) ∈ Φ}. We say that an infinite L-structure M is ω-categorical if T h_{L}(M) is ω-categorical; an ω-categorical structure is ω-homogeneous. By combining the previous lemmas we get the following.

Proposition 6.10 Supose that every atomic formula in L is equivalent to a formula in Φ and that for any x̄, Φx̄ is finite up to equivalence modulo T. Then the following are equivalent:

(i) There exists a Φ-amalgamation class for T.

(ii) There exists M ⊧ T which is Φ-determined, and if M is infinite, then M is ω-categorical (because cl is locally finite on M).

7 Stability

In this section we assume the following:

(1) For any L-structure that we talk about a closure map cl is fixed.

(2) If T is an L^{n}-theory, M, N ⊧ T, a_{i} ∈ M, b_{i} ∈ N, for i < λ

and

(M, (a_{i} : i < λ)) ≡_{L^{n}} (N, (b_{i} : i < λ))

then {a_{i} : i < λ} is closed if and only if {b_{i} : i < λ} is closed.

(2) cl is uniformly locally finite on every M ⊧ T; that is, for every M ⊧ T and m < ω there is m′ < ω such that if A ⊆ M and |A| ≤ m then |cl(A)| ≤ m′.

Definition 7.1

(i) Suppose that A is an L^{n}-amalgamation class (for T). We say that A is stable in L^{n} if for every φ(x̄, ȳ) ∈ L^{n} there exists k < ω such that there does not exist M ∈ A and ā_{i}, b̄_{i} ∈ M, for i < k, satisfying M ⊧ φ(ā_{i}, b̄_{j}) ⇔ i ≤ j.

(ii) We adopt the convention that every finite structure is stable.

(iii) An infinite L-structure M is stable if for every φ(x̄, ȳ) ∈ L, there exists k < ω such that there does not ā_{i}, b̄_{i} ∈ M, for i < k, satisfying M ⊧ φ(ā_{i}, b̄_{j}) ⇔ i ≤ j.

(iv) A formula φ(x̄, ȳ) is unstable with respect to a theory T if there exist M ⊧ T and ā_{i}, b̄_{i} ∈ M, i < ω, such that M ⊧ φ(ā_{i}, b̄_{j}) ⇔ i ≤ j; otherwise φ(x̄, ȳ) is stable with respect to T.

Proposition 7.2 Suppose that n is greater than the arity of any function symbol in the vocabulary of L and that n is at least as great as the arity of any relation symbol in the vocabulary of L. If T is a complete L^{n}-theory such that S_{n}^{n}(T) is finite then the following are equivalent:

(i) there is a stable L^{n}-amalgamation class for T.

(ii) T has a stable model which is L^{n}-determined (and hence ωcategorical).

In addition to results in the previous section, the proof uses that

if formulas φ_{i}(x̄, ȳ, i = 1, …, m are stable with respect to some complete L-theory then any boolean combination of the φ_{i}’s is stable with respect to the same theory, and

the fact (Ryll-Nardzewski theorem) that if M is ω-categorical then, for any x̄, there are only finitely many formulas, modulo T h_{L}(M), in the free variables x̄.

Definition 7.3 An L-structure M is ω-stable if whenever M′ ≡_{L} M, A ⊆ M′ and |A| ≤ ω then |S_{1}^{L}(A, M)| ≤ ω.

A basic fact from stability theory is that if M is ω-stable then M is stable.

Another fact, which is essential here, is the following:

Fact 7.4 Cherlin, Harrington, Lachlan) If M is ω-categorical and ω-stable and M ⊧ φ then there exists a finite substructure N ⊆ M such that N ⊧ φ.

Lemma 7.5 Suppose that M is an infinite L-structure such that cl(A) = A for any A ⊆ M and S_{n}^{n}(∅, M) is finite. If M is stable and L^{n}-determined then M is ω-stable.

Proofsketch. Under the premises of the lemma it follows that any L-formula is equivalent, modulo T h_{L}(M), to a boolean combination of L^{n}-formulas and there are only finitely many L^{n}-formulas up to equivalence modulo T h_{L^{n}}(M). Thus any complete L-type p(x̄) over a set A is determined by p(x̄)∩L^{n}(A). Now the lemma follows from the fact that if 0 < m < ℵ_{0} then (ℵ_{0})^{m} = ℵ_{0} and from Shelah’s “unstable formula theorem”, which tells us that if φ(v_{1}, ȳ) is stable and A ⊆ M is countable then S_{1}^{φ(v_{1},ȳ)}(A) is countable. □

Recall that if T is a complete L^{n}-theory such that S_{n}^{n}(T) is finite then T is axiomatized by an L^{n}-sentence. Therefore we get:

Corollary 7.6 Suppose that T is a complete L^{n}-theory such that S_{n}^{n}(T) is finite and suppose that M is ω-categorical and ω-stable and M ⊧ T. Then, for any finite subset A ⊆ M there is a finite L^{n}-elementary substructure N ≼_{L^{n}} M; and consequently N ⊧ T.

Corollary 7.7 Let T be a complete L^{n}-theory such that S_{n}^{n}(T) is finite and suppose that for any M ⊧ T and any A ⊆ M, cl(A) = A. If there is a stable L^{n}-amalgamation class A for T such that A contains at least one infinite structure then T has arbitrarily large finite models.

We now turn to the case when ‘cl’ is not trivial (think of vector spaces, for example).

Definition 7.8 Let T be an L^{n}-theory. T has the strong L^{n}- amalgamation property over countable models if, whenever

M_{0} ⊧ T, M_{0} ≼_{L^{n}} M_{i}, i = 1, 2, where M_{i} is countable for i = 1, 2, ā_{1} ∈ M_{1}, ā_{2} ∈ M_{2} are finite sequences and

(M_{1}, cl(ā_{1})M_{0}) ≡_{L^{n}} (M_{2}, cl(ā_{2})M_{0})

then

there are M and L^{n}-elementary embeddings f_{i} : M_{i} → M, i = 1, 2, such that f_{1}(ā_{1}) = f_{2}(ā_{2}) and f_{i} is the identity on

M_{0} for i = 1, 2.

If T = T h_{L^{n}}(M), for sufficiently large n, where M is a vector space over a finite field, then T has the strong L^{n}-amalgamation property over countable models.

Proposition 7.9 Suppose that T is a complete L^{n}-theory such that S_{n}^{n}(T) is finite and T has the strong L^{n}-amalgamation property over countable models.

(i) If M ⊧ T and M is stable and L^{n}-determined then M is ω-stable.

(ii) If there is a stable L^{n}-amalgamation class A for T such that A contains at least one infinite structure the T has arbitrarily large finite models; these can be taken as L^{n}-elementary substructures of the limit of A.

Proofsketch. (ii) follows from (i) and earlier results. Concerning (i): The assumptions that S_{n}^{n}(T) is finite, M is stable and L^{n}-determined (so M is ω-categorical) imply, via Shelah’s “unstable formula theorem”, that for any countable A ⊆ M′ ≡_{L} M, S_{1}^{L^{n}}(A, M′) is countable. The useful consequence of the L^{n}- amalgamation property over countable models is that if N ≼ N′ ⊧ T, where N is countable, and ā, b̄ ∈ N′ are finite sequences then

(N′, cl(ā)N) ≡_{L^{n}} (N′, cl(b̄)N)

implies

(N′, cl(āN)) ≡_{L^{n}} (N′, cl(b̄N)).

This property together with the assumption that M is L^{n}-determined (which by the ω-categoricity of M implies that any N ≡_{L} M is L^{n}-determined) shows that M is ω-stable, by a counting types argument. □

8 Recursive bounds

In this section we use a decidability result from the theory of smoothly approxiamable structures to derive a couple of results about recursive upper bounds on the size of the least model of particular kinds of sentences or L^{n}-theories. The relevant result is the following one, due to Cherlin and Hrushovski:

Theorem 8.1 We can effectively decide whether for a given sentence and k < ω, that sentence has a finite model M such that |S_{4}^{L}(T h(M))| = k.

We define a recursive function 𝔣 : ω^{2} → ω as follows:

Let 𝔣(n, k) = k if n < 2 or k = 0.

Now suppose that n ≥ 2 and k ≥ 1.

• Let φ_{1}, …, φ_{m} be an enumeration of all sentences (up to equivalence) of quantifier rank at most k+n in a language with k constant symbols and k i-ary relation symbols for every 1 ≤ i ≤ n, and we assume that = is one of the binary relation symbols.

• For 1 ≤ i ≤ m use Theorem ?? to decide if φ_{i} has a finite model M_{i} such that |S_{4}(T h(M_{i}))| ≤ k;

• if such a model of φ_{i} exists then search until we find such M_{i} and let ℓ_{i} = |M_{i}|; otherwise let ℓ_{i} = 0.

• Then let 𝔣(n, k) = max{ℓ_{1}, …, ℓ_{m}}.

Definition 8.2 An L-structure M is smoothly approximable if M is ω-categorical and if any L-sentence which is true in M is true in a finite substructure N ⊆ M such that

• for any θ(x̄) ∈ L there is χ(x̄) ∈ L such that

{ā ∈ N : M ⊧ θ(ā)} = {ā ∈ N : N ⊧ χ(ā)},

and

• for any ā, b̄ ∈ N of the same finite length

(N, ā) ≡_{L} (N, b̄) ⟺ (M, ā) ≡_{L} (M, b̄).

Of interest here is that any ω-categorical and ω-stable structure is smoothly approximable; this essentially follows from the work of Cherlin, Harrington and Lachlan on structures that are ωcategorical and ω-stable.

Corollary 8.3 Let n ≥ 4 and let φ be a sentence such that no function symbols occur in φ, the arity of every relation symbol in φ is at most n and at most n distinct variables occur in φ. If M ⊧ φ, where M is smoothly approximable and |S_{4}^{n}(T h(M))| = |S_{4}(T h(M)|, then φ has a finite model of cardinality at most 𝔣(n, |S_{n}^{n}(T h(M))|).

Proof of ??. Suppose that φ, n and M satisfies the premises of the corollary. Without loss of generality we may assume that M is an L-structure and that φ is an L-sentence, where L is the language that occurs in the definition of 𝔣. Since M is smoothly approximable it follows that M has a finite substructure N such that N ⊧ φ and |S_{4}(T h(N))| ≤ |S_{4}(T h(M))|. By Fact ??, T h_{L^{n}}(M) is axiomatized by an L^{n}-sentence with quantifier rank at most |S_{n}^{n}(T h(M))| + n. Since, by assumption, |S_{4}(T h(M))| = |S_{4}^{n}(T h(M))| ≤ |S_{n}^{n}(T h(M))| it follows from the definition of 𝔣 that T h_{L^{n}}(M) and hence φ has a finite model of cardinality at most 𝔣(n, |S_{n}^{n}(T h(M))|). □

Corollary 8.4 Let n ≥ 4 and let L be a language with finite vocabulary which contains no function symbols and in which all relation symbols have arity at most n. If T is a complete L^{n}- theory such that

• S_{n}^{n}(T) is finite,

• for any M ⊧ T and A ⊆ M, cl(A) = A, and

• there is a stable L^{n}-amalgamation class for T,

then T has a model of cardinality at most 𝔣(n, |S_{n}^{n}(T)|).

Proof. Suppose that T satisfies the above conditions. First note that (by Fact ??) T is axiomatized by an L^{n}-sentence with quantifier rank ≤ |S_{n}^{n}(T)| + n. By previous results T has an ω-categorical ω-stable model M which is L^{n}-determined; in particular M is smoothly approximable. Since the closure is trivial we get |S_{4}^{n}(T h(M))| = |S_{4}(T h(M)|. Now Corollary ?? implies that T has a model of cardinality at most 𝔣(n, |S_{n}^{n}(T)|). □

Corollary ?? can also be proved by using weaker decidability results than Theorem ?? from the theory of countable stable structures with elimination of quantifiers which the theory of smoothly approximable structures generalizes.

Remark 8.5 If 1 < n < 4 then Corollary ?? and Corollary ?? still hold if we replace S_{n}^{n}(T h(M)) by S_{4}^{n}(T h(M)) and S_{n}^{n}(T) by S_{4}^{n}(T), respectively.

Comments: Grohe (Large finite structures with few L^{k}-types, Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 1450, Springer) has shown that for n ≥ 3 there does not exist a recursive function f_{n} : ω → ω such that for every complete L^{n}-theory T with finite models,

min{|M| : M ⊧ T } ≤ f_{n}(|S_{n}^{n}(T)|).

Except for Corollary ?? above (from which Corollary ?? follows) an existence result is obtained by Dawar (Types and indiscernibles in finite models; in Logic Colloquium ’95, Lecture Notes in Logic, vol 11, Springer). We may ask: How general can a class, T , of complete L^{n}-theories with finite models be if we require that there exists a recursive function f such that min{|M| : M ⊧ T } ≤ f(|S_{n}^{n}(T)|) for all T ∈ T ? Another problem is to determine such a function f more precisely, perhaps starting with some smaller class of theories on which we have more control.

Part II

ω-categorical expansions of pregeometries

9 ω-categoricity and pregeometries

L will always denote the set of all first order formulas over some vocabulary (signature).

We say that an L-structure M is ω-categorical if T h_{L}(M) is ωcategorical. The properties of ω-categoricity that are of use here are points (2) and (3) in the following well-known characterisation:

Fact 9.1 Engeler, Ryll-Nardzewski, Svenonius) The following are equivalent for an L-structure M:

(1) M is ω-categorical.

(2) S_{n}^{L}(∅, M) is finite for every 0 < n < ω.

(3) For every 0 < n < ω there are, up to equivalence in T h_{L}(M), only finitely many formulas with all free variables among x_{1}, …, x_{n}.

Definition 9.2 Let M be an L-structure.

(i) For any φ(x̄, ȳ) ∈ L and ā ∈ M of the same length as ȳ, let

φ(M, ā) = {b̄ ∈ M : M ⊧ φ(b̄, ā)}.

(ii) For any A ⊆ M the algebraic closure of A (in M), denoted acl_{M}(A) is defined as acl_{M}(A) =

{b ∈ M : for some φ(x, ȳ) ∈ L and ā ∈ A, |φ(M, ā)| < ω and b ∈ φ(M, ā)}.

(iii) We say that a set A ⊆ M is algebraically closed if acl_{M}(A) = A.

Definition 9.3 Let G be a set and let cl : P(G) → P(G) be a function, where P(G) is the powerset of G. We call cl a closure operator and say that (G, cl) is a pregeometry if the following conditions are satisfied:

(1) If A ⊆ G then A ⊆ cl(A) and cl(cl(A)) = cl(A).

(2) If A ⊆ B ⊆ G then cl(A) ⊆ cl(B).

(3) If A ⊆ G, a, b ∈ G and a ∈ cl(A ∪ {b}) then a ∈ cl(A) or b ∈ cl(A ∪ {a}).

(4) If A ⊆ G and a ∈ cl(A) then there is a finite B ⊆ A such that a ∈ cl(B).

The properties (1), (2) and (4) hold if we replace G by any structure M and cl by acl_{M}. Here we will study ω-categorical structures M such that also (3) holds for (M, acl_{M})

If (M, acl_{M}) is a pregeometry then we can speak about the dimension of any A ⊆ M, denoted dim_{M}(A) (or just dim(A)), which is defined by

dim_{M}(A) = min{|B| : B ⊆ A and A ⊆ acl_{M}(B)}.

In particular, if A ⊆ acl_{M}(∅) then dim_{M}(A) = 0. The above characterization of ω-categorical structures imply the following:

Fact 9.4 If M is an ω-categorical structure and A ⊆ M is finite then acl_{M}(A) is finite.

10 Finiteness and independence notions

Definition 10.1 A structure M has the finite submodel property if whenever φ is a sentence and M ⊧ φ, then there exists a finite substructure N ⊆ M such that N ⊧ φ.

Observation: If T is a complete L-theory with infinite models and M ⊧ T and M has the finite submodel property then T is not finitely axiomatizable.

Definition 10.2 Let 0 < k < ω and suppose that M is an Lstructure such that (M, acl_{M}) is a pregeometry. We say that M is polynomially k-saturated if there is a polynomial P (x) such that for every n_{0} < ω there is a natural number n ≥ n_{0} and a finite substructure N ⊆ M such that:

(1) n ≤ |N| ≤ P (n).

(2) N is algebraically closed.

(3) Whenever ā ∈ N, dim_{M}(ā) < k and q(x) ∈ S_{1}^{L}(ā, M) is nonalgebraic there are distinct b_{1}, …, b_{n} ∈ N such that M ⊧ q(b_{i}) for each 1 ≤ i ≤ n.

Examples of structures which are polynomially k-saturated, for every 0 < k < ω, include the random graph and infinite vector spaces, projective spaces and affine spaces over finite fields.

Lemma 10.3 If M is polynomially k-saturated for every 0 < k < ω, then M has the finite submodel property.

Assumptions: From now on L and L are first order languages such that L’s vocabulary is included in L’s vocabulary, so L ⊆ L. Moreover, M will be an ω-categorical L structure such that

(1) (M, acl_{M}) is a pregeometry.

(2) M has elimination of quantifiers.

(3) M↾L has elimination of quantifiers.

If points (2) and (3) are not fulfilled then we can just new relation symbols to L and L and the resulting expansion of M will then satisfy all the above assumptions (for the extended languages).

Observe that if acl_{M} coincides with acl_{M↾L} and ā ∈ M and b̄ ∈ M satisfy the same L-formulas then ā is algebraically closed if and only if b̄ is algebraically closed.

Definition 10.4 Suppose that acl_{M} coincides with acl_{M↾L}. We say that M satisfies the k-independence hypothesis over L if the following holds: Whenever A and B are algebraically closed substructures of M and

(1) dim_{M}(B) ≤ k,

(2) dim_{M}(A) < k,

(3) f : A↾L → B↾L is an L-embedding, and

(4) if A′ ⊂ A (proper inclusion) is an algebraically closed substructure then the restriction f : A′ → B is an L-embedding (it preserves all atomic L-formulas),

then there are an algebraically closed substructure C ⊆ M and an L-ismorphism g : B↾L → C↾L such that

(5) gf : A → C is an L-embedding, and

(6) for any algebraically closed substructure B′ ⊆ B such that f(A) ⊈ B′, g : B′ → C is an L-embedding.

(a) Let the vocabulary of L be {=} and let the vocabulary of L be {=, E} where E is a binary relation symbol. Let M be the random graph in the language L where E is interpreted as the edge relation. Then M and M↾L have elimination of quantifiers and acl_{M}(A) = A and dim_{M}(A) = |A| for any A ⊆ M. Since any finite graph embedds into M it follows that M satisfies the k-independence hypothesis over L for any k < ω; with the notation of the definition, the case when dim_{M}(A) = 2 is the most interesting.

(b) Let L be as in (a) and let L = {=, R_{1}, …, R_{m}} where R_{i} are relation symbols of any arity. Let M be the random structure in the language L. For the same reasons as in (a) M satisfies the k-independence hypothesis over L for any k < ω; however the verification becomes a bit more interesting for A of dimension > 2 if L contains relation symbols of arity greater than 2.

(c) A vector space with the bipartite random graph “on top”: Let K be the class of all finite structures N = (V, P, E, +, f_{0}, f_{1}, 0) such that:

1. V, the universe of N, is a vector space over the field F = {0, 1}.

2. P is a unary relation.

3. E is a binary relation symbol interpreted as an irreflexive and symmetric relation.

4. + is a binary function symbol interpreted as vector addition and the constant symbol 0 is interpreted as the zero vector.

5. f_{i}(v) = i · v, for i = 0, 1 and any v ∈ V (so f_{i} represents scalar multiplication).

6. N ⊧ ∀xy( E(x, y) → [ E(y, x) ∧ [ (P (x) ∧ ¬P (y)) ∨ (¬P (x) ∧ P (y)) ] ] ).

7. N ⊧ P (0). It is easy to verify that K is nonempty and has the hereditary property, the joint embedding property and the amalgamation property and is uniformly locally finite (see Hodges book Model Theory). Hence the Fraissé limit of K, which we call M, exists and is ω-categorical with elimination of quantifiers. Since the reduct of M to the language with vocabulary {=, P, E} is the random bipartite graph, M is not smoothly approximable.

Let L ⊆ L be the sublanguage which contains all symbols of L except P and E. Then M↾L is a vector space over a finite field, so M↾L has elimination of quantifiers. It is not hard to see, using quantifier elimination of M and the fact that any structure in K can be embedded into M (since M is the Fraissé limit of K), that acl_{M} is linear span. Hence acl_{M} and acl_{M↾L} coincide. Again using the fact that M is the Fraissé limit of K it follows that M satisfies the k-independence hypothesis over L, for every k < ω.

12 Finite models

We still assume the following:

Assumptions: L and L are first order languages such that L’s vocabulary is included in L’s vocabulary, so L ⊆ L. Moreover, M will be an ω-categorical L structure such that

(1) (M, acl_{M}) is a pregeometry.

(2) M has elimination of quantifiers.

(3) M↾L has elimination of quantifiers.

Theorem 12.1 Suppose that acl_{M↾L} coincides with acl_{M}, M↾L is polynomially k-saturated and M satisfies the k-independence hypothesis over L. If φ ∈ L is an unnested sentence, in which at most k distinct variables occur, and M ⊧ φ, then φ has arbitrarily large finite models.

Note that Theorem ?? only speaks about arbitrarily large finite models, but does not claim that these are embeddable in M.

Theorem 12.2 Suppose that acl_{M↾L} coincides with acl_{M} and, for every 0 < k < ω, M↾L is polynomially k-saturated and M satisfies the k-independence hypothesis over L. Then M is polynomially k-saturated, for every 0 < k < ω, and M has the finite submodel property.

We say that M has trivial (also called degenerate) algebraic closure if for any A ⊆ M, acl_{M}(A) = ⋃_{a∈A} acl_{M}(a).

As an application of the first theorem we have:

Corollary 12.3 Suppose that M is simple with SU-rank 1 and has trivial algebraic closure. If φ ∈ L^{3} is unnested and M ⊧ φ then φ has arbitrarily large finite models.

Examples of simple M with SU-rank 1 and has trivial algebraic closure include the random graph, random structure and the random “pyramid-free” 3-hypergraph (also constructed as a Fraissé limit); it is not known (I think) whether the last example has the finite submodel property.