Model Companions of T_{σ} for stable T

John T. Baldwin ^{∗}

Department of Mathematics, Statistics and Computer Science University of Illinois at Chicago

Saharon Shelah^{†} Department of Mathematics Hebrew University of Jerusalem Rutgers University

May 12, 2001

Let T be a complete first order theory in a countable relational language L. We assume relation symbols have been added to make each formula equivalent to a predicate. Adjoin a new unary function symbol σ to obtain the language L_{σ}; T_{σ} is obtained by adding axioms asserting that σ is an L-automorphism.

The modern study of the model companion of theories with an automorphism has two aspects. One line, stemming from Lascar [6], deals with ‘generic’ automorphisms of arbitrary structures. A second, beginning with Chatzidakis and Hrushovski [1] and questions of Macintyre about the Frobenius automorphism is more concerned with specific algebraic theories. This paper is more in the first tradition: we find general necessary and sufficient conditions for a stable first order theory with automorphism to have a model companion.

Kikyo investigates the existence of model companions of T_{σ} when T is unstable in [3]. He also includes an argument of Kudaibergenov showing that if T is stable with the finite cover property then T_{σ} has no model companion.

∗Partially supported by NSF grant DMS 9803496.

†This is paper 759 in Shelah’s bibliography. The authors thank Mittag-Leffler Institute and the Binational Science Foundation for partial support of this research.

This argument was implicit in [2] and is a rediscovery of a theorem of Winkler [9] in the 70’s. We provide necessary and sufficient conditions for T_{σ} to have a model companion when T is stable. Namely, we introduce a new condition: T_{σ} admits obstructions, and show that T_{σ} has a model companion iff and only if T_{σ} does not admit obstructions. This condition is weakening of the finite cover property: if a stable theory T has the finite cover property then T_{σ} admits obstructions.

Kikyo also proved that if T is an unstable theory without the independence property, T_{σ} does not have a model-companion. Kikyo and Shelah [5] have improved this by weakening the hypothesis to, T has the strict order property.

For p a type over A and σ an automorphism with A ⊂ dom p, σ(p) denotes {ϕ(x, σ(a)) : ϕ(x, a) ∈ p}. References of the form II.4.13. are to [8]

1 Example

In the following example we examine exactly why a particular T_{σ} does not have a model companion. Eventually, we will show that the obstruction illustrated here represents the reason T_{σ} (for stable T) can fail to have a model companion. Let L contain two binary relation symbols E and R and unary predicates P_{i} for i < ω. The theory T asserts that E is an equivalence relation with infinitely many infinite classes, which are refined by R into twoelement classes. Moreover, each P_{i} holds only of elements from one E-class and contains exactly one element from each R class of that E-class.

Now, T_{σ} does not have a model companion. To see this, let ψ(x, y, z) be the formula: E(x, z) ∧ E(y, z) ∧ R(x, y) ∧ x ≠ y. Let Γ be the L_{σ}-type in the variables {z} ∪ ⟨x_{i}y_{i} : i < ω⟩ which asserts for each i, {ψ(x_{i}, y_{i}, z)}, the sequence ⟨x_{i}y_{i} : i < ω⟩ is L-indiscernible and for every ϕ(x, w) ∈ L(T):

(∀w) ⋁{ ⋀_{i∈U} ϕ(x_{i}, w) ↔ ϕ(y_{i}, σ(w)) : U ⊆ lg(w) + 3, |U| > (lg(w) + 3)/2}.

Thus if ⟨b_{i}c_{i} : i < ω⟩a realize Γ in a model M,

σ(avg(⟨b_{i} : i < ω⟩/M)) = avg(⟨c_{i} : i < ω⟩/M).

For any finite Δ ⊂ L(T), let χ_{Δ,k}(x, y, z) be the conjunction of the Δformulas satisfied by ⟨b_{i}c_{i} : i < k⟩a where ⟨b_{i}c_{i} : i < k⟩a are an initial segment of a realization of Γ. Let θ_{Δ,k} be the sentence

(∀x_{0}, … x_{k−1}, y_{0}, … y_{k−1}, z)χ_{Δ,k}(x_{0}, … x_{k−1}, y_{0}, … y_{k−1}, z) →
(∃x_{0}, y_{0}, x_{1}, y_{1})[ψ(x_{0}, y_{0}, z) ∧ ψ(x_{1}, y_{1}, z) ∧ σ(x_{1}) = y_{1}].

We now claim that if T_{σ} has a model companion T_{σ}^{∗}, then for some k and Δ,

T_{σ}^{∗} ⊢ θ_{Δ,k}.

For this, let M ⊧ T_{σ}^{∗} such that ⟨b_{i}c_{i} : i < k⟩a satisfy Γ in M. Suppose M | L ≺ N and N is an |M|^{+}-saturated model of T. In N we can find b, c realizing the average of ⟨b_{i} : i < ω⟩ and ⟨c_{i} : i < ω⟩ over M respectively. Then

σ(avg(⟨b_{i} : i < ω⟩/M)) = avg(⟨c_{i} : i < ω⟩/M)

and so there is an automorphism σ^{∗} of N extending σ and taking b to c. Since (M, σ) is existentially closed (T_{σ}^{∗} is model complete), we can pull b, c down to M. By compactness, some finite subset Γ_{0} of Γ suffices and letting Δ be the formulas mentioned in Γ_{0} and k the number of x_{i}, y_{i} appearing in Γ_{0} we have the claim.

But now we show that if (M, σ) is any model of T_{σ}, then for any finite Δ and any k, (M, σ) ⊧ ¬θ_{Δ,k}. For this, choose b_{i}, c_{i} for i < k which are E-equivalent to each other and to an element a in a class P_{j} where P_{j} does not occur in Δ and with R(b_{i}, c_{i}) and b_{i} ≠ c_{i}. Then b, c, a satisfy χ_{Δ,k} but there are no b_{k}, c_{k} and automorphism σ which makes θ_{Δ,k} true. For, for each j,

T ⊢ (∀x, y, z)(ψ(x, y, z) ∧ P_{j}(z) → [P_{j}(x) ↔ ¬P_{j}(y)]).

To put this situation in a more general framework, recall some notation from [8]. Δ will note a finite set of formulas: {ϕ_{i}(x, y_{i}) : lg(x) = m, i < |Δ|}; p is a Δ-m-type over A if p is a set of formulas ϕ_{i}(x, a) where x = ⟨x_{1}, … x_{m−1}⟩ (these specific variables) and a from A is substituted for y_{i}. Thus, if A is finite there are only finitely many Δ-m-types over A.

Now let Δ_{1} contain Boolean combinations of x = y, R(x, y), E(x, y). Let Δ_{2} expand Δ_{1} by adding a finite number of the P_{j}(z) and let Δ_{3} contain P_{j}(x) where P_{j} does not occur in Δ_{2}.

Now we have the following situation: there exists a set X = {b_{0}, b_{1}, c_{0}, c_{1}, a}, P_{j}(a) holds, all 5 are E-equivalent and R(b_{i}, c_{i}) for i = 0, 1 such that:

1. ⟨b_{i}c_{i} : i ≤ 2⟩ is Δ_{2}-indiscernible over a.

2. ⟨b_{0}c_{0}, b_{1}c_{1}⟩ can be extended to an infinite set of indiscernibles \overline{b}\overline{c} which satisfy the following.

3. ψ(b_{i}, c_{i}, a).

4. σ(avg_{Δ_{2}}(\overline{b}/M) = avg_{Δ_{2}}(\overline{c}/M).

5. tp_{Δ_{1}}(b_{2}c_{2}/X) ⊢ σ(tp_{Δ_{3}}(b_{2}/X)) ≠ tp_{Δ_{3}}(c_{2}/X).

We call a sequence like ⟨b_{i}c_{i} : i ≤ 2⟩a a (σ, Δ_{1}, Δ_{2}, Δ_{3}, n)-obstruction over the emptyset. In order to ‘finitize’ the notions we will give below more technical formulations of the last two conditions: we will have to discuss obstructions over a finite set A. In the example, the identity was the only automorphism of the prime model. We will have to introduce a third sequence b′ to deal with arbitrary σ. But this example demonstrates the key aspects of obstruction which are the second reason for T_{σ} to lack a model companion.

2 Preliminaries

In order to express the notions described in the example, we need several notions from basic stability theory. By working with finite sets of formulas in a stable theory without the finite cover property we are able to refine arguments about infinite sets of indiscernibles to arguments about sufficiently long finite sequences. Let Δ be a finite set of formulas which we will assume to be closed under permutations of variables and negation; ¬¬ϕ is identified with ϕ. Recall that an ordered sequence E = ⟨a_{i} : i ∈ I⟩ is said to be (Δ, p) indiscernible over A if any two properly ordered p-element subsequences of I realize the same Δ-type over A. It is Δ-indiscernible if it is (Δ, p)-indiscernible for all p, or equivalently for all p′ with p′ at most the maximum number of variables in a formula in Δ. For any sequence E = ⟨a_{i} : i ∈ I⟩ and j ∈ I we write E_{j} for ⟨a_{i} : i < j⟩.

We will rely on the following facts/definitions from [8] to introduce two crucial functions for this paper: F (Δ, n) and f(Δ, n).

Fact 2.1 Recall that if T is stable, then for every finite Δ ⊂ L(T) and n < ω there is a finite Δ′ = F (Δ, n) with Δ ⊆ Δ′ ⊂ L(T) and a k^{∗} = f(Δ, n) such that 1. A sequence ⟨e_{i} : i ∈ I⟩ of n-tuples such that for i < j and a finite set

A, tp_{F(Δ,n)}(e_{j}/E_{i}A) = tp_{F(Δ,n)}(e_{i}/E_{i}A) and R(F (Δ, n), 2)(e_{j}/E_{j}A) = R(F (Δ, n), 2)(e_{i}/E_{i}A), (whence, tp_{F(Δ,n)}(e_{j}/E_{i}A) is definable over A) is a sequence of Δ-indiscernibles (II.2.17).

2. For any set of Δ′-indiscernibles over the empty set, E = ⟨e_{i}: i < k⟩ with lg(e_{i}) = n and k ≥ k^{∗} for any θ(u, v) ∈ Δ and any d with lg(d) = lg(v) = m either {e_{i}: ϕ(e_{i}, d)} or {e_{i}: ¬ϕ(e_{i}, d)} has strictly less than k^{∗}/2 elements. (II.4.13., II.2.20 )

3. This implies that, for appropriate choice of k^{∗},

(a) there is an integer m = m(Δ, n) ≥ n such that for any set of Δ′-indiscernibles ⟨e_{i}: i < k⟩ over A with lg(e_{i}) = n and k ≥ k^{∗} and any a with lg(a) ≤ m there is a U ⊆ k with |U| < k^{∗}/2 such that ⟨e_{i}: i ∈ k − U⟩ is Δ-indiscernible over Aa;

(b) moreover if k ≥ k^{∗}, for any set A, avg_{Δ}(⟨e_{i}: i < k⟩/A) is welldefined. Namely, avg_{Δ}(⟨e_{i}: i < k⟩/A) =

\{ϕ(x, a) : |\{e_{i} : i < k, ϕ(e_{i}, a)| ≥ \frac{k^{∗}}{10}, a ∈ A, ϕ(x, y) ∈ Δ\}.

In a), m is the least k ≥ n such all ϕ ∈ Δ have at most k free variables. But avg_{Δ}(⟨e_{i}: i < k⟩/A) need not be consistent. (Let E be all the members of one finite class in the standard fcp example and let A = E.) However,

Fact 2.2 If, in addition to Fact 2.1, T does not have the finite cover property, we can further demand

1. If E = ⟨e_{i}: i < k^{∗}⟩ is a set of Δ′-indiscernibles over the empty set, for any A, avg_{Δ}(E/A) is a consistent complete Δ-type over A.

2. Moreover k^{∗} can be chosen so that any set of Δ′-indiscernibles (of ntuples) with length at least k^{∗} can be extended to one of infinite length (II.4.6).

3. For any pair of F (F (Δ, n))-indiscernible sequences E^{1} = ⟨e_{i}^{1}: i < k⟩ and E^{2} = ⟨e_{i}^{2}: i < k⟩ over a with lg(e_{i}) = n and k ≥ k^{∗} such that

avg_{F(Δ})(E^{1}/aE^{1}E^{2}) = avg_{F(Δ})(E^{2}/aE^{1}E^{2}),

there exist J = ⟨e_{j} : k < j < ω⟩ such that both E^{1}J and E^{2}J are F (Δ)- indiscernible over a. We express the displayed condition on \overline{e}^{1}, \overline{e}^{2} by the formula: λ_{Δ}(\overline{e}^{1}, \overline{e}^{2}, a).

4. If E_{1} and E_{2} contained in a model M are F (Δ, n)-indiscernible over a ∈ M and each have length at least k^{∗}, there is a formula λ_{Δ}(x^{1}, x^{2}, z) such that M ⊧ λ_{Δ}(e^{1}, e^{2}, a) if and only if avg_{Δ}(e^{1}/M) = avg_{Δ}(e_{2}/M).

Proof. For 1, make sure that k^{∗} is large enough that every Δ-type which is k^{∗}-consistent is consistent (II.4.4 3)). Now 3) follows by extending the common F (Δ)-average of E^{1} and E^{2} over aE^{1}E^{2} by 2). Finally, condition 4 holds by adapting the argument for III.1.8 from the set of all L-formulas to Δ; λ_{Δ} is the formula from 3).

Note that both F and f can be chosen increasing in Δ and n.

3 Obstructions

In this section we introduce the main new notion of this paper: obstruction.

We are concerned with a formula ψ(x, y, z) where lg(x) = lg(y) = n and lg(z) = m. We will apply Facts 2.1 and 2.1 with e_{i} = b_{i}b′_{i}c_{i} where each of b_{i}, b′_{i}, and c_{i} has length n. Thus, our exposition will depend on functions F (Δ, 3n), f(Δ, 3n). In several cases, we apply Fact 2.1 with ϕ(u_{1}, u_{2}, u_{3}, v) as θ(u_{2}, v) ↔ θ(u_{3}, v) for various θ.

The following notation is crucial to state the definition.

Notation 3.1 If \overline{d} = ⟨d_{i} : i < r⟩ is a sequence of 3n-tuples, which is Δindiscernible over a finite sequence f, and r ≥ k^{∗} = f(Δ, 3n), then τ_{Δ}(z, \overline{d}f) is the formula with free variable z and parameters \overline{d}f which asserts that there is a subsequence \overline{d}′ of \overline{d} with length f(Δ, 3n) so that \overline{d}′z forms a sequence of Δ-indiscernibles over f.

The following result follows easily from Fact 2.2 3) and the definition of f(Δ, n).

Lemma 3.2 Let p ≥ k = f(Δ, n) and suppose ⟨e_{i} : i < p⟩ is a sequence of 3n-tuples which is F (Δ, 3n)- indiscernible over f. If S_{1}, S_{2} ⊆ p with |S_{1}|, |S_{2}| ≥ k^{∗}/2 then τ_{Δ}(z, \overline{d}|S_{1}f) and τ_{Δ}(z, \overline{d}|S_{2}f) are equivalent formulas.

Now we come to the main notion. Intuitively, ⟨b_{i}b′_{i}c_{i}: i ≤ k⟩a is a (Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction over A if ⟨b_{i}b′_{i}c_{i}: i ≤ k⟩ is an indefinitely extendible sequence of Δ_{2} indiscernibles over a such that the b’s, b′_{i}’s and c’s each have length n and the Δ_{2}-average of the b′_{i} and c is the same (over any set) but any realizations of the Δ_{1}-type of the b′_{i} and the Δ_{1}-type of the c_{i} over a and the sequence have different Δ_{3}-types over A. More formally, we define:

Definition 3.3 For finite Δ_{1} ⊆ Δ_{2} ⊆ L(T) and Δ_{3} ⊆ L(T), finite a ⊆ A ⊂ M ⊧ T with lg(a) ≤ m(Δ, n) (as in Fact 2.1), σ an automorphism of M, and a natural number n, ⟨b_{i}σ(b_{i})c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction over A if the following conditions hold.

1. ⟨b_{i}σ(b_{i})c_{i} : i ≤ k⟩ is F (Δ_{2}, 3n)-indiscernible over a.

2. k ≥ f(Δ_{2}, 3n).

3. avg_{Δ_{2}}(\overline{e}^{1}/M) = avg_{Δ_{2}}(\overline{e}^{2}/M) where (\overline{e}^{1} = ⟨σ(b_{i}) : i < k⟩ and \overline{e}^{2} = ⟨c_{i} : i < k⟩.

4. Writing τ_{Δ_{1}}(⟨b_{i}σ(b_{i})c_{i}) : i < k⟩a) with free variables x, x′, y, we have

M ⊧ (∀x, x′, y)[τ_{Δ_{1}}(x, x′, y, ⟨b_{i}σ(b_{i})c_{i} : i < k⟩a) →

⋁{ϕ(x′, f) ∧ ¬ϕ(y, f) : f ∈ A ∪ ⋃_{i<k}⟨b_{i}σ(b_{i})c_{i}⟩ ∪ a, ϕ ∈ Δ_{3}}]

By Fact 2.2, Condition 3) is expressed by a formula of e^{1}, e^{2} and a. Crucially, the hypothesis of the fourth condition in Definition 3.3 is an L-formula with parameters ⟨b_{i}σ(b_{i})c_{i}) : i < k⟩a; the conclusion is an L-formula with parameters from A as well. The disjunction in the conclusion of condition 4) is nonempty since each b_{i}, σ(b_{i}) is in the domain if Δ_{3} is nontrivial. Δ_{1} and Δ_{2} have 3n type-variables; Δ_{3} has n type-variables.

Fact 3.4 Note that if ⟨b_{i}c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction over A and Δ_{1} ⊆ Δ′_{2} ⊆ Δ_{2}, then ⟨b_{i}c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ′_{2}, Δ_{3}, n) obstruction over A. Further, if ⟨b_{i}c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction over A and A ⊆ A′, where A′ is finite, Δ_{1} ⊆ Δ′_{2} ⊆ Δ_{2}, then ⟨b_{i}c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ′_{2}, Δ_{3}, n) obstruction over A′.

Definition 3.5 1. We say (M, σ) ⊧ T_{σ} has no σ-obstructions when there is a function G(Δ_{1}, n) with F (Δ_{1}, 3n) ⊆ G(Δ_{1}, n) such that if Δ_{1} is a finite subset of L(T) and G(Δ_{1}, n) is contained in the finite Δ_{3} ⊂ L(T), then for every finite subset A of M, there is no (σ, Δ_{1}, G(Δ_{1}, n), Δ_{3}, n) obstruction over A.

2. We say T_{σ} has no σ-obstructions when there is a function G(Δ_{1}, n) (which does not depend on (M, σ)) such that for each (M, σ) ⊧ T_{σ}, if Δ_{1} is a finite subset of L(T), A is finite subset of M, and Δ_{3} is a finite subset of L(T), there is no (σ, Δ_{1}, G(Δ_{1}, n), Δ_{3}, n) obstruction over A.

Definition 3.6 A simple obstruction is an obstruction where the automorphism σ is the identity. The notions of a theory or model having a simple obstruction are the obvious modifications of the previous definition.

Lemma 3.7 T_{σ} has obstructions if and only if T has simple obstructions.

Proof. Suppose T has obstructions; we must find simple obstructions. So, suppose for some Δ_{1}, and n, and for every finite Δ_{2} ⊇ F (Δ_{1}, 3n), there is a finite Δ_{3} and a tuple (M^{Δ_{2}}, σ^{Δ_{2}}, A^{Δ_{2}}, k^{Δ_{2}}) such that: (M^{Δ_{2}}, σ^{Δ_{2}}) ⊧ T_{σ}, A^{Δ_{2}} is a finite subset of M^{Δ_{2}} and b^{Δ_{2}}, σ(b^{Δ_{2}}), c^{Δ_{2}}, a^{Δ_{2}} contained in M^{Δ_{2}} are a (σ^{Δ_{2}}, Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction of length k^{Δ_{2}} over A^{Δ_{2}}. Without loss of generality lg(a) = m = m(Δ_{1}, 3n) and we can write Δ_{3} = Δ_{3}(Δ_{2}). Now, define a family of simple obstruction by replacing each component of the given sequence of obstructions by an appropriate object with left prefix sim.

simA^{Δ_{2}} = A^{Δ_{2}} ∪ {b^{Δ_{2}}, σ(b^{Δ_{2}}), c^{Δ_{2}}}
sim(b^{Δ_{2}}) =^{sim} (b^{′Δ_{2}}) = σ(b^{Δ_{2}})
simc^{Δ_{2}} = c^{Δ_{2}}.

We use the same sequence of formulas for the Δ_{2} and Δ_{3}(Δ_{2}). It is routine to check that we now have an obstruction with respect to the identity.

Lemma 3.8 If T is a stable theory with the finite cover property then T has obstructions.

Proof. By II.4.1.14 of [8], there is a formula E(x, y, z) such that for each d, E(x, y, z) is an equivalence relation and for each n there is a d_{n} such that E(x, y, d_{n}) has finitely many classes but more than n. Let Δ_{1} be {E(x, y, z), ¬E(x, y, z)} and consider any Δ_{2}. Fix lg(x) = lg(y) = r. There are arbitrarily large sequences b_{n} = ⟨b_{j}^{n} : j < n⟩, c_{n} = ⟨c_{j}^{n} : j < n⟩ such that for some d_{n_{1}}, d_{n_{2}}, b_{n} is a set of representatives for distinct classes of E(x, y, d_{1}^{n}) while c_{n} is a set of representatives of distinct classes for E(x, y, d_{2}^{n}) and n_{1} < n_{2}. So by compactness and Ramsey, for any Δ_{2} we can find such b_{k}, c_{k} where k = f(Δ_{2}, 2r) and b_{k}, c_{k} are a sequence of length k of Δ_{2} indiscernibles. Now, if Δ_{3} contains formulas which express that the number of equivalence classes of E(x, y, z) is greater than n_{1} and A contains d_{n_{1}}, d_{n_{2}}, we have an (identity, Δ_{1}, Δ_{2}, Δ_{3}, r) obstruction over A. (Let b = b′ = b_{k}, c = c_{k}.)

4 Model Companions of T_{σ}

In this section we establish necessary and sufficient conditions on stable T for T_{σ} to have a model companion. First, we notice when the model companion, if it exists, is complete.

Note that acl(∅) = dcl(∅) in C_{T}^{eq} means every finite equivalence relation E(x, y) of T is defined by a finite conjunction: ⋀_{i<n} ϕ_{i}(x) ↔ ϕ_{i}(y).

Fact 4.1 1. If T is stable, T_{σ} has the amalgamation property.

2. If, in addition, acl(∅) = dcl(∅) in C_{T}^{eq} then T_{σ} has the joint embedding property.

Proof. The first part of this Lemma was proved by (Theorem 3.3 of [6]) using the definability of types. For the second part, the hypothesis implies that types over the empty set are stationary and the result follows by similar arguments.

Lemma 4.2 Suppose T is stable and T_{σ} has a model companion T_{σ}^{∗}.

1. Then T_{σ}^{∗} is complete if and only if acl(∅) = dcl(∅) in C_{T}^{eq}.

2. If (M, σ) ⊧ T_{σ} then the union of the complete diagram of M (in L) with the diagram of (M, σ) and T_{σ}^{∗} is complete.

Proof. 1) We have just seen that if acl(∅) = dcl(∅) in C_{T}^{eq}, then T_{σ} has the joint embedding property; this implies in general that the model companion is complete. If acl(∅) ≠ dcl(∅) in C_{T}^{eq}, let E(x, y) be a finite equivalence relation witnessing acl(∅) ≠ dcl(∅). Because E is a finite equivalence relation,

T_{1} = T_{σ} ∪ {(∀x)E(x, σ(x))}

is a consistent extension of T_{σ}. But since

T_{σ} ∪ {¬E(x, y)} ∪ {ϕ(x) ↔ ϕ(y): ϕ ∈ L(T)}

is consistent so is

T_{2} = T_{σ} ∪ {(∃x)¬E(x, σ(x))}.

But T_{1} and T_{2} are contradictory, so T_{σ}^{∗} is not complete.

2) Since we have joint embedding (from amalgamation over any model) the result follows as in Fact 4.1.

We now prove the equivalence of three conditions: the first is a condition on a pair of models. The second is given by an infinite set of L_{σ} sentences (take the union over all finite Δ_{2}) and the average requires names for all elements of M. The third is expressed by a single first order sentence in L_{σ}. The equivalence of the first and third suffices (Theorem 4.7) to show the existence of a model companion. In fact 1 implies 2 implies 3 requires only stability; the nfcp is used to prove 3 implies 1.

Lemma 4.3 Suppose T is stable without the fcp. Let (M, σ) ⊧ T_{σ}, a ∈ M and suppose that (M, σ) has no σ-obstructions. Fix ψ(x, y, z) with lg(x) = lg(y) = n and lg(z) = lg(a) = m.

The following three assertions are equivalent:

1. There exists (N, σ), (M, σ) ⊆ (N, σ) ⊧ T_{σ} and

N ⊧ (∃xy)[ψ(x, y, a) ∧ σ(x) = y].

2. Fix Δ_{1} = {ψ(x, y, z)} and without loss of generality lg(z) ≤ m(Δ_{1}, n). For k ≥ 5 · f(Δ_{1}, 3n) any finite Δ_{2} ⊇ F (Δ_{1}, 3n) (Fact 2.1), there are b_{i}, σ(b_{i})c_{i} ∈ ^{3n}M for i < k such that

(a) ⟨b_{i}σ(b_{i})c_{i} : i < k⟩ is F (Δ_{2}, 3n)-indiscernible over a,

(b) for each i < k, ψ(b_{i}, c_{i}, a) holds,

(c) For every d ∈ ^{m}M and ϕ(u, v) ∈ Δ_{2} we have

|{i < k : ϕ(σ(b_{i}), d) ↔ ϕ(c_{i}, d)}| ≥ f(Δ_{2}, 3n)/2.

3. Let Δ_{2} = G(Δ_{1}, n). Then are there are b_{i}, σ(b_{i})c_{i} ∈ ^{3n}M for i < k = 5 · f(Δ_{2}, 3n) such that :

(a) ⟨b_{i}σ(b_{i})c_{i} : i < k⟩ is F (G(Δ_{1}, n), 3n)-indiscernible over a,

(b) for each i < k, ψ(b_{i}, c_{i}, a),

(c) λ_{Δ_{2}}(⟨σ(b_{i}) : i < k⟩, ⟨c_{i} : i < k⟩, a).

Proof. First we show 1) implies 2). Fix b, c ∈ N with N ⊧ ψ(b, c, a) ∧ σ(b) = c. For Δ_{2}, let Δ_{2}^{+} = F (F (Δ_{2}, 3n), 3n). For each Δ_{2}, choose a finite p ⊆ tp_{L(T)}(b, c/M) with the same (Δ_{2}^{+}, 2) rank as tp_{Δ_{2}}(b, c/M) (so tp_{Δ_{2}}(b, c/M) is definable over dom p). Now inductively construct an F (Δ_{2}, 3n)-indiscernible sequence (by Fact 2.1 1)) ⟨b_{i}, c_{i} : i < ω⟩ by choosing b_{i}, c_{i} in M realizing the restriction of tp_{Δ_{2}^{+}}(b, c/M) to dom p along with the points already chosen. Let b′_{i} = σ(b_{i}). By Ramsey’s Theorem for some infinite U ⊆ ω, ⟨b_{i}, b′_{i}, c_{i} : i ∈ U⟩ is F (Δ_{2}, 3n)-indiscernible over a; renumbering let U = ω. Now conditions a) and b) of assertion 2) are clear. For clause c),

avg_{Δ_{2}}(⟨c_{i} : i < ω⟩/M) = tp_{Δ_{2}}(c, M)
= σ(tp_{Δ_{2}}(b, M)) = σ(avg_{Δ_{2}}(⟨b_{i} : i < ω⟩/M))

since σ(b) = c. So, for each ϕ ∈ Δ_{2} and each d ∈ M of appropriate length,

ϕ(x, d) ∈ avg_{Δ_{2}}(⟨c_{i} : i < ω⟩/M)

if and only if

ϕ(x, σ^{−1}(d)) ∈ avg_{Δ_{2}}(⟨b_{i} : i < ω⟩/M).

So for some S_{1}, S_{2} ⊂ ω with |S_{1}|, |S_{2}| < f(Δ_{2}, 3n)/2, we have for all i ∈ ω−(S_{1}∪S_{2}), ϕ(c_{i}, d) if and only if ϕ(b_{i}, σ^{−1}(d)). Since σ is an automorphism of M this implies for i ∈ ω−(S_{1}∪S_{2}), ϕ(c_{i}, d) if and only if ϕ(σ(b_{i}), d) which gives condition c) by using the first k elements of ⟨b_{i}, σ(b_{i})c_{i} : i < ω−S_{1}∪S_{2}⟩.

3) is a special case of 2). To see this, note that 3c) is easily implied by the form analogous to 2c): For every m ≤ m(Δ_{1}, n) and d ∈ ^{m}M and ϕ(u, v) ∈ G(Δ_{1}, n) we have

|{i < k : ϕ(σ(b_{i}), d) ↔ ϕ(c_{i}, d)}| ≥ f(Δ_{2}, 3n)/2.

If T does not have f.c.p. the converse holds and we use that fact implicitly in the following argument. It remains only to show that 3) implies 1) with Δ_{1} = {ψ} and Δ_{2} = G(Δ_{1}, n). Without loss of generality we may assume N is ℵ_{1}-saturated. We claim the type

Γ = {ψ(x, y, a)} ∪ {ϕ(x, d) ↔ ϕ(y, σ(d)) : d ∈ M, ϕ ∈ L(T)} ∪ diag (M)

is consistent. This clearly suffices.

Let k = f(Δ_{2}, 3n). Suppose ⟨b_{i}σ(b_{i})c_{i} : i < k⟩a satisfy 3). Let Γ_{0} be a finite subset of Γ and suppose only formulas from the finite set Δ_{3} and only parameters from the finite set A appear in Γ_{0}. Write b′_{i} for σ(b_{i}).

Now ⟨b_{i}b′_{i}c_{i} : i ≤ f(Δ_{2}, 3n)⟩a easily satisfy the first two conditions of Definition 3.3 for being a (Δ_{1}, Δ_{2}, Δ_{3}, n)-obstruction over A and, in view of Fact 2.2 3), 4), the third is given by condition 3c). Since there is no obstruction the 4th condition must fail. So there exist b^{∗}, (b^{∗})′, c^{∗} so that

M ⊧ τ_{Δ_{1}}(b^{∗}, (b∗)′, c^{∗}, ⟨b_{i}, b′_{i}, c_{i} : i < k⟩a).

and tp_{Δ_{3}}((b^{∗})′/A) = tp_{Δ_{3}}(c^{∗}/A) so Γ_{0} is satisfiable.

As we’ll note in Theorem 4.7, we have established a sufficient condition for T_{σ} to have a model companion. The next argument shows it is also necessary.

Lemma 4.4 Suppose T is stable; if T has an obstruction then T_{σ} does not have a model companion.

More precisely, suppose for some Δ_{1}, and n, and for every finite Δ_{2} ⊇ F (Δ_{1}, 3n), there is a a finite Δ_{3} and a tuple (M^{Δ_{2}}, σ^{Δ_{2}}, A^{Δ_{2}}, k^{Δ_{2}}) such that: (M^{Δ_{2}}, σ^{Δ_{2}}) ⊧ T_{σ}, A^{Δ_{2}} is a finite subset of M^{Δ_{2}}, b^{Δ_{2}}, σ(b^{Δ_{2}}), c^{Δ_{2}}, a^{Δ_{2}} contained in M^{Δ_{2}} are a (σ^{Δ_{2}}, Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction of length k^{Δ_{2}} over A^{Δ_{2}}. Without loss of generality lg(a) = m = m(Δ_{1}, 3n) and we can write Δ_{3} = Δ_{3}(Δ_{2}).

Then the collection K_{σ} of existentially closed models of T_{σ} is not an elementary class.

Proof. We may assume T does not have f.c.p., since if it does we know by Winkler and Kudaibergerov that T_{σ} does not have a model companion. By the usual coding we may assume Δ_{1} = {ψ(x, y, z)} with lg(x) = lg(y) = n, lg(z) = m, k = f(Δ_{1}, 3n) . Without loss of generality each M^{Δ_{2}} is existentially closed. Let D be a nonprincipal ultrafilter on Y = {Δ_{2} : F (Δ_{1}, 3n) ⊆ Δ_{2} ⊂_{ω} L(T)} such that for any Δ ∈ Y the family of supersets in Y of Δ is in D. Expand the language to L^{+} by adding a unary function symbol σ and a 3n-ary relation symbol Q and constants a. Expand each of the M^{Δ_{2}} to an L^{+}-structure N_{Δ_{2}} by interpreting a as a^{Δ_{2}} σ as σ^{Δ_{2}} and Q as the set {b_{i}^{Δ_{2}}, σ(b_{i}^{Δ_{2}})c_{i}^{Δ_{2}} : i < k^{Δ_{2}}} of 3n-tuples. Let (N^{∗}, σ^{∗}, Q^{∗}, a^{∗}) be the ultraproduct of the N_{Δ_{2}} modulo D. Let A denote P^{∗}(N^{∗}), a^{∗} denote the ultraproduct of the a^{Δ_{2}}, and ⟨b_{i}, b′_{i}c_{i} : i ∈ I⟩ enumerate Q^{∗}(N^{∗}). Now we claim

Claim 4.5 1. lg(b_{i}) = lg(σ(b_{i})) = lg(c) = n ; lg(a) = m and σ^{∗}(b_{i}) = b′_{i}.

2. ⟨b_{i}b′_{i}c_{i} : i ∈ I⟩ is a sequence of L(T)-indiscernibles over a^{∗}.

3. For each finite Δ_{2} ⊆ L(T) with Δ_{2} ⊆ F (Δ_{1}, 3n) and each finite subsequence from ⟨b_{i}b′_{i}c_{i} : i ∈ I⟩ indexed by J of length at least k = f(Δ_{2}, 3n) the Δ_{2}-type of ⟨b_{i}b′_{i}c_{i} : i ∈ J⟩a is the Δ_{2}-type of some (σ^{Δ_{2}}, Δ_{1}, Δ_{2}, Δ_{3}, n)-obstruction ⟨b^{Δ_{2}}, σ(b^{Δ_{2}})c^{Δ_{2}}⟩a^{Δ_{2}} in M^{Δ_{2}}over the empty set.

4. (avg_{L}(⟨b′_{i} : i ∈ I⟩/N) = avg_{L}(⟨c_{i} : i ∈ I⟩/N).

This claim follows directly from the properties of ultraproducts. (For item 3, apply Fact 3.4 and the definition of the ultrafilter D.)

Let Γ be the L-type in the variables ⟨x_{i}x′_{i}y_{i} : i ∈ I⟩ ∪ {z} over the empty set of ⟨b_{i}, b′_{i}c_{i} : i ∈ I⟩a^{∗}. For any finite Δ ⊂ L(T), let χ_{Δ,k}(\overline{x}, \overline{x}′\overline{y}, z) be the Δ-type over the empty set of a subsequence of k elements from ⟨b_{i}b′_{i}c_{i} : i ∈ I⟩ and a^{∗} from a realization of Γ with z for a^{∗}.

Recall the definition of τ_{Δ_{1}} from Notation 3.1. Let r = f(Δ_{1}, n) and let θ_{Δ_{1}}(x_{0}, … x_{r−1}, x′_{0}, … x′_{r−1}, y_{0}, … y_{r−1}, z) be the formula: (∃x, x′, y)[χ_{Δ_{1},r}(x_{0}, … x_{r−1}, x′_{0}, … x′_{r−1}, y_{0}, … y_{r−1}, z) ∧τ_{Δ_{1}}(x, x′, y, x_{0}, … x_{r−1}, x′_{0}, … x′_{r−1}, y_{0}, … y_{r−1}, z) ∧ σ(x′) = y].

Without loss of generality we assume 0, 1 … r−1 index disjoint sequences. Now we claim:

Claim 4.6 If K_{σ}, the family of existentially closed models of T_{σ}, is axiomatized by T_{σ}^{∗},

T_{σ}^{∗} ∪ Γ ∪ {σ(x_{i}) = x′_{i} : i ∈ I} ⊢ θ_{Δ_{1}}(x_{0}, … x_{r−1}, x′_{0}, … x′_{r−1}, y_{0}, … y_{r−1}, z).

(Abusing notation we write this with the x_{i}, x′_{i}, y_{i} free.)

For this, let (M′, σ′) ⊧ T_{σ}^{∗} such that ⟨b, b′_{i}, c_{i} : i ∈ I⟩a satisfy Γ in M′ and for each i ∈ I, σ(b_{i}) = b′_{i}. Suppose M′ | L ≺ M′′ and M′′ is an |M′|^{+}-saturated model of T. In M′′ we can find bb′, c realizing the average of ⟨b_{i}b′_{i}c_{i} : i ∈ I⟩ over M′. Then

σ′(tp(b/M′)) = σ′(avg(⟨b_{i} : i ∈ I⟩/M′)) = avg(⟨b′_{i} : i ∈ I⟩/M′)
= avg(⟨c_{i} : i ∈ I⟩/M′) = (tp(c/M′)

(The first and last equalities are by the choice of b, b′, c; the second holds since for each i, σ′(b_{i}) = b′_{i}, the third follows from clause 4 in the description of the ultraproduct.) Now since M′′ is |M′|^{+}-saturated there is an automorphism σ′′ of N extending σ′ and taking b to c.

As (M′, σ′) ⊧ T_{σ}^{∗}, it is existentially closed. So we can pull b, b′c down to M′. Thus, (M′, σ′) ⊧ θ_{Δ_{1}}(b_{0}, … b_{r−1}, b′_{0}, … b′_{r−1}, c_{0}, … c_{r−1}, a). But (M′, σ′) was an arbitrary model of T_{σ}^{∗} ∪ Γ ∪ {σ(x_{i}) = x′_{i} : i ∈ I}; so

T_{σ}^{∗} ∪ Γ ∪ {σ(x_{i}) = x′_{i} : i ∈ I} ⊢
θ_{Δ_{1}}(x_{0}, … x_{r−1}, x′_{0}, … x′_{r−1}, y_{0}, … y_{r−1}, z).

By compactness, some finite subset Γ_{0} of Γ and a finite number of the specifications of σ suffice; let Δ^{∗} be the formulas mentioned in Γ_{0} along with those in F (Δ_{1}, 3n) and k the number of x_{i}, y_{i} appearing in Γ_{0} and let Δ_{2} = F (Δ^{∗}, n). Without loss of generality, k ≥ f(Δ_{1}, 3n). Then, T_{σ}^{∗} ⊢

(∀x_{0} … x_{k−1}, x′_{0}, … x′_{k−1}, y_{0}, … y_{k−1})[(χ_{Δ_{2},k}(x_{0}, … x_{k−1}, x′_{0}, … x′_{k−1}, y_{0}, … y_{k−1}, z)

∧ ⋀_{i<k} σ(x_{i}) = x′_{i}) → θ_{Δ_{1}}(x_{0}, … x_{r−1}, x′_{0}, … x′_{r−1}, y_{0}, … y_{r−1}, z)].

By item 3) in Claim 4.5, fix a Δ_{2} and Δ_{3} = Δ_{3}(Δ_{2}, m) containing Δ_{2} and ⟨b_{i}^{Δ_{2}}b′_{i}^{Δ_{2}}c_{i}^{Δ_{2}} : i < k⟩a^{Δ_{2}} which form a (σ, Δ_{1}, Δ_{2}, Δ_{3}, n)-obstruction over a^{Δ_{2}} and so that:

M^{Δ_{2}} ⊧ χ_{Δ_{2},k}(⟨b_{i}^{Δ_{2}}b′_{i}^{Δ_{2}}c_{i}^{Δ_{2}} : i < k⟩a^{Δ_{2}}).

By the definition of an obstruction, σ(b_{i}^{Δ_{2}}) = b′_{i}^{Δ_{2}}. So by the choice of Γ_{0},

(M^{Δ_{2}}, σ^{Δ_{2}}) ⊧ θ_{Δ_{1}}(⟨b_{i}^{Δ_{2}}b′_{i}^{Δ_{2}}c_{i}^{Δ_{2}} : i < r⟩a^{Δ_{2}}).

Now, let b, b′c ∈ M^{Δ_{2}} with σ^{Δ_{2}}(b′) = c witness this sentence. Then

(M^{Δ_{2}}, σ^{Δ_{2}}) ⊧ τ_{Δ_{1}}(⟨b_{i}^{Δ_{2}}b′_{i}^{Δ_{2}}c_{i}^{Δ_{2}} : i < k⟩a^{Δ_{2}})

By the definition of obstruction,

σ^{Δ_{2}}(tp_{Δ_{3}}(b′/A^{Δ_{2}}∪⋃_{i<k}⟨b_{i}^{Δ_{2}}σ(b_{i}^{Δ_{2}})c_{i}⟩∪a^{Δ_{2}})) ≠ tp_{Δ_{3}}(c/A^{Δ_{2}}∪⋃_{i<k}⟨b_{i}^{Δ_{2}}σ(b_{i}^{Δ_{2}})c_{i}^{Δ_{2}}⟩∪a^{Δ_{2}}).

This contradicts that σ^{Δ_{2}} is an automorphism and we finish.

Finally we have the main result.

Theorem 4.7 If T is a stable theory, T_{σ} has a model companion if and only if T_{σ} admits no σ-obstructions.

Proof. We showed in Lemma 4.4 that if T_{σ} has a model companion then there is no obstruction. If there is no obstruction, Lemma 3.8 implies T does not have the finite cover property. By Lemma 4.3 for every formula ψ(x, y, z) there is an L-formula θ_{ψ}(z) (write out condition 3 of Lemma 4.3) which for any (M, σ) ⊧ T_{σ} holds of any a in M if and only if there exists (N, σ), (M, σ) ⊆ (N, σ) ⊧ T_{σ} and

(N, σ) ⊧ (∃xy)ψ(x, y, a) ∧ σ(x) = y.

Thus, the class of existentially closed models of T_{σ} is axiomatized by the sentences: (∀z)θ_{ψ}(z) → (∃xy)ψ(x, y, a) ∧ σ(x) = y. (We can restrict to formulas of the form ψ(x, σ(x), a) by the standard trick ([4, 1]).

Kikyo and Pillay [4] note that if a strongly minimal theory has the definable mulplicity property then T_{σ} has a model companion. In view of Theorem 4.7, this implies that if T has the definable multiplicity property, then T_{σ} admits no σ-obstructions. Kikyo and Pillay conjecture that for a strongly minimal set, the converse holds: if T_{σ} has a model companion then T has the definable multiplicity property. They prove this result if T is a finite cover of a theory with the finite multiplicity property. It would follow in general from a positive answer to the following question.

Question 4.8 If the strongly minimal theory T with finite rank does not have the definable multiplicity property, must it omit obstructions?

Pillay has given a direct proof that if a strongly minimal T has the definable multiplicity property, then T_{σ} admits no σ-obstructions. Pillay has provided an insightful reworking of the ideas here in a note which is available on his website [7].

Here is a final question:

Question 4.9 Can T_{σ} for an ℵ_{0}-categorical T admit obstructions?

References

[1] Z. Chatzidakis and U. Hrushovski. The model theory of difference fields. Transactions of AMS, 351:2997–3071, 1999.

[2] Z. Chatzidakis and A. Pillay. Generic structures and simple theories. Annals of Pure and Applied Logic, 95:71092, 1998.

[3] Hirotaka Kikyo. Model companions of theories with an automorphism. to appear, 1998.

[4] Hirotaka Kikyo and Anand Pillay. The definable multiplicity property and generic automorphisms. Annals of Pure and Applied Logic, 106:263– 273, 2000.

[5] Hirotaka Kikyo and Saharon Shelah. The strict order property and generic automorphisms. to appear, 2000.

[6] D. Lascar. Les beaux automorphismes. Archive Math. Logic, 31:55–68, 1991.

[7] A. Pillay. Notes on model companions of stable theories with an automorphism. preprint, 2001.

[8] S. Shelah. Classification Theory and the Number of Nonisomorphic Models. North-Holland, 1991. second edition.

[9] P. Winkler. Model completeness and Skolem expansions. In D.H. Saracino and V.B. Weispfennig, editors, Model Theory and Algebra, pages 408–464. Springer-Verlag, 1975.