Model Companions of T_{Aut} 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

March 13, 2003

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_{Aut} 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_{Aut} 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_{Aut} has no model companion. 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_{Aut} to have a model companion when T is stable. Namely, we introduce a new condition: T admits obstructions, and show that T_{Aut} has a model companion if and only if T does not admit obstructions. This condition is a weakening of the finite cover property: if a stable theory T has the finite cover property then T admits obstructions.

∗Partially supported by NSF grant DMS 9803496 and DMS-0100594.

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

Kikyo also proved that if T is an unstable theory without the independence property, T_{Aut} 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, σ(p) denotes {ϕ(x, σ(a)) : ϕ(x, a) ∈ p}. References of the form II.4.13. are to [8]. We thank Assaf Hasan for his comments on the manuscript. We also thank the referee for his insightful remarks and in particular forcing us to make explicit and prove Lemma 2.9, which may have independent interest.

Further related work is contained in [?] which investigates when T_{Aut} has a stable model completion.

1 Example

In the following example we examine exactly why a particular T_{Aut} does not have a model companion. Eventually, we will show that the obstruction illustrated here represents the reason T_{Aut} (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 and R are equivalence relations and that E has infinitely many infinite classes, which are refined by R into two-element 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. Thus, x ≠ y ∧ P_{i}(x) ∧ P_{j}(y) implies ¬R(x, y) if i ≠ j.

Now, T_{Aut} 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 ψ(x_{i}, y_{i}, z) holds for each i, the sequence ⟨x_{i}y_{i} : i < ω⟩ is L-indiscernible, the x_{i} are distinct and the y_{i} are distinct, 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 claim that if T_{Aut} has a model companion T_{Aut}^{∗}, then for some k and Δ,

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

For this, let M ⊧ T_{Aut}^{∗} 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_{Aut}^{∗} 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_{Aut}, 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. As, 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 denote 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_{k}(x) where P_{k} 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 ≤ 12⟩ 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.

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

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

3. 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 empty set. 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_{Aut} 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.

We may speak recklessly of indiscernible sequence but in the paper we deal exclusively with Δ-indiscernible sets which are defined just below. For infinite sequences in a stable theory such recklessness is without penalty (since infinite indiscernible sequences are indiscernible sets); since we are speaking of finite sequences, it is essential that we really mean indiscernible sets.

Definition 2.1 Let Δ be a finite set of formulas which we will assume to be closed under permutation or identification of variables and under negation; ¬¬ϕ is identified with ϕ.

1. We say that E = ⟨a_{i} : i ∈ I⟩, where all a_{i} have the same length m, is (Δ, r) indiscernible if it satisfies the following conditions. Suppose i_{0} … i_{r−1} and j_{0} … j_{r−1} are distinct elements of I and for i < t < r, u_{i} is a subset of m with Σ_{i<t}|u_{i}| = r, lg(x_{i}) = u_{i}, and ϕ(x_{0}, … x_{t−1}) ∈ Δ. Then

ϕ(a_{i_{0}} ↾ u_{0}, a_{i_{1}} ↾ u_{1}, … a_{i_{t−1}} ↾ u_{t−1}) ↔ ϕ(a_{j_{0}} ↾ u_{0}, a_{j_{1}} ↾ u_{1}, … a_{j_{t−1}} ↾ u_{t−1}).

2. E is Δ-indiscernible if it is (Δ, r)-indiscernible for all r, or equivalently for all r′ with r′ at most the maximum number of variables in a formula in Δ.

3. For any sequence E = ⟨a_{i} : i ∈ I⟩ and j ∈ I we write E_{j} for ⟨a_{i} : i < j⟩.

Remark 2.2 Pedantically the formulas in Δ contain variables only among x_{0}, … x_{n} for some n, but we will freely write ϕ(x), ϕ(y) to increase intelligibility. We do not distinguish strictly between an arbitrary finite set of formulas Δ and its closure described in Definition 2.1.

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.3 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) with the following properties.

1. Assume we have finite set A and a set E = ⟨e_{i} : i ∈ I⟩ of n-tuples such

that for i < j,

tp_{Δ′}(e_{j}/E_{i}A) = tp_{Δ′}(e_{i}/E_{i}A)

and

R_{(Δ′,2)}(e_{j}/E_{j}A) = R_{(Δ′,2)}(e_{i}/E_{i}A),

(whence, tp_{Δ′}(e_{j}/E_{i}A) is definable over A). Then E is a set of Δindiscernibles over A.

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^{∗}/10 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 3 a), m is the least k ≥ n such all ϕ ∈ Δ have at most k free variables. But, in 3b) avg_{Δ}(⟨e_{i}: i < k⟩/A) need not be consistent. (Let A be all the members of one finite class in the standard fcp example.)

The closure conditions on Δ given in Definition 2.1 guarantee:

Fact 2.4 If ⟨a_{i}b_{i} : i < α⟩ is a set of Δ-indiscernibles over a, with the length of the a_{i} equal to n, then ⟨a_{i}a_{i}b_{i} : i < α⟩ and ⟨b_{i} : i < α⟩ are Δ-indiscernible sets as well.

Recall:

Definition 2.5 The theory T does not have the finite cover property if for every finite Δ (considered with n-variable parameters) there is a k such that for any A and any Δ-type q over A, if q is k-consistent then q is consistent. We require f(Δ, n) greater than this k.

Fact 2.6 If T does not have the finite cover property, in addition to Fact 2.3, we can choose k^{∗} = f(Δ, n) to satisfy the following conditions.

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

2. Any set of Δ′-indiscernibles (of n-tuples) with length at least k^{∗} can be extended to one of infinite length (II.4.6).

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

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

there exists J = ⟨e_{j} : k < j < ω⟩ such that both E^{1}J and E^{2}J are F (Δ, n)-indiscernible over a.

4. We express the displayed condition in 3) on E^{1}, E^{2} by the formula: λ_{Δ}(\overline{e}^{1}, \overline{e}^{2}, a) , where \overline{e}^{i} enumerates E^{i} .

5. 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^{∗}, then M ⊧ λ_{Δ}(\overline{e}^{1}, \overline{e}^{2}, a) if and only if avg_{Δ}(E^{2}/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 (Δ, n)-average of E^{1} and E^{2} over aE^{1}E^{2} by 2). Finally, condition 5) holds by adapting the argument for III.1.8 from the set of all L-formulas to Δ. □_{2.6}

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

The following observations culminate in a new consequence of nfcp that will be used to reduce from ‘obstruction’ to ‘simple obstruction’ in the next section. The first is III.3.4 of [8] or V.1.23 of [?]. Just choose u such that tp(b_{∗}/X) does not fork over u and tp(b_{∗}/u) is stationary. Note that we do not assume the existence of an a_{∗}.

Fact 2.7 Suppose T is stable, and further that ⟨b_{i} : i < |T |^{+}⟩ ∪ {b_{∗}} and X = ⟨a_{i}b_{i} : i < |T |^{+}⟩ are sequences of L-indiscernibles over a. Then there is a U ⊆ X, U indexed by an initial segment of cardinality ≤ |T |, such that if X_{U,j} denotes X − (U ∪ {a_{j}b_{j}}), for every b_{j} ∉ U

tp(b_{∗}/X_{U,j}) = tp(b_{j}/X_{U,j}).

Now we ‘finitize’ this fact.

Lemma 2.8 Fix n and m. For every finite set of formulas Δ there exist k_{0}, k_{1} < ω and a finite set of formulas Δ^{+} such that if k_{2} ≥ k_{1}, a_{i}, b_{i} are sequences of length n, a is set of parameters of size m, while X = ⟨a_{i}b_{i} : i < k_{2}⟩ and ⟨b_{i} : i < k_{2}⟩ ∪ b_{∗} are sets of Δ^{+}-indiscernibles over a, then there is a U ⊆ X, |U| < k_{0}, such that if X_{U,j} denotes X − (U ∪ a_{j}b_{j}), for every a_{j}, b_{j} ∉ U

tp_{Δ}(b_{∗}/X_{U,j}) = tp_{Δ}(b_{j}/X_{U,j}).

Proof. If not, for every t = ⟨k_{0}, k_{1}, Δ_{1}⟩ with Δ_{1} a finite set of formulas containing Δ there is a k_{2}^{t} ≥ k_{1}, a structure M^{t}, and a sequence X^{t} = ⟨a_{i}^{t}b_{i}^{t} : i < k_{2}⟩ and b_{∗}^{t} such that X and ⟨b_{i}^{t} : i < k_{2}⟩ ∪ {b_{∗}} are sequences of Δ^{+}- indiscernibles over a contained in M^{t} but for every U ⊆ X, with |U| < k_{0}^{t}, for some b_{j} ∉ U

tp_{Δ}(b_{∗}/X_{U,j}) ≠ tp_{Δ}(b_{j}/X_{U,j}).

Now expand L by adding constants for a, b_{∗} and a new 2n-ary predicate symbol P. Then (M^{t}, P), where P holds of each tuple ⟨a_{i}^{t}b_{i}^{t}⟩, satisfies the first order sentence expressing this failure. By compactness and saturation we obtain a contradiction to Fact 2.7. □_{2.8}

Lemma 2.9 Suppose T is stable without the finite cover property. For every finite Δ, n there are k_{0}, k_{1} and Δ_{1} such that if X = ⟨a_{i}b_{i} : i < k_{1}⟩, X′ = ⟨b_{i} : i < k_{1}⟩, and X′ ∪ b_{∗} are sequences of Δ_{1}-indiscernibles (of sequences of length n there is V ⊆ k_{1} with |V | < k_{0} and there is an a_{∗} such that ⟨a_{i}b_{i} : i ∈ k_{1} − V ⟩ ∪ {a_{∗}b_{∗}} is a sequence of Δ-indiscernibles.

Proof. Choose Δ^{+}, k_{0}, k_{1} according to Lemma 2.8. Choose a_{k_{1}}, b_{k_{1}} to realize the average of X and let q(x, y) denote the Δ-type of a_{k_{1}}, b_{k_{1}} over X. Since the finite cover property fails there is an r such that the consistency of q is determined by its r-element subsets. Let Δ_{1} contain Δ^{+} and all formulas of the form ⋀_{i<r}(∃x)ϕ_{i}(x, y, u_{1}, v_{1}, … u_{s}, v_{s}) where ϕ_{i}(a_{k_{1}}, b_{k_{1}}, a_{i_{1}}, b_{i_{1}}, … a_{i_{s}}, b_{i_{s}}) holds and ϕ_{i} ∈ Δ. Now if X and X′ satisfy the hypotheses for this choice of Δ_{1}, by Lemma 2.8, q(x, b_{∗}) is consistent as required. □_{2.9}

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.3 and 2.6 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.3 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 of length 3n 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 set of Δ-indiscernibles over f.

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_{i}’s, b′_{i}’s and c_{i}’s each have length n and the Δ_{2}-average of the b′_{i}’s and the c_{i}’s 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 ⟨b_{i}b′_{i}c_{i}: i < k⟩ have different Δ_{3}-types over A. More formally, we define:

Definition 3.2 Fix a finite Δ_{1} ⊆ Δ_{2} ⊆ L(T) and Δ_{3} ⊆ L(T), finite a ⊆ A ⊂ M ⊧ T with lg(a) ≤ m(Δ_{2}, n) (as in Fact 2.3), σ an automorphism of M, and a natural number n. We say ⟨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); lg(b_{i}) = lg(b′_{i}) = lg(c_{i}) = n.

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. Using the formula τ_{Δ_{1}} from Notation 3.1 with x, x′, y representing the free variable z there, 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, ϕ ∈ Δ_{3}}]

By Fact 2.6, Condition 3) is expressed by a formula of e^{1}, e^{2} and a. Crucially, the hypothesis of the fourth condition in Definition 3.2 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. Δ_{1} and Δ_{2} have 3n type-variables; Δ_{3} has n type-variables.

Fact 3.3 Note that (a) if ⟨b_{i}b′_{i}c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction over A and Δ_{1} ⊆ Δ′_{2} ⊆ Δ_{2}, then ⟨b_{i}b′_{i}c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ′_{2}, Δ_{3}, n) obstruction over A. Further, (b) if ⟨b_{i}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}b′_{i}c_{i} : i ≤ k⟩a is a (σ, Δ_{1}, Δ′_{2}, Δ_{3}, n) obstruction over A′. Finally, (c) if W ⊆ k is large enough then ⟨b_{i}b′_{i}c_{i} : i ∈ W ⟩a is a (σ, Δ_{1}, Δ′_{2}, Δ_{3}, n) obstruction over A.

Definition 3.4 1. We say (M, σ) ⊧ T_{Aut} has no σ-obstructions when there is a function G(Δ_{1}, n) with F (Δ_{1}, 3n) ⊆ G(Δ_{1}, n) ⊂_{<ω} L(T) 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_{Aut}, 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.5 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.6 T has obstructions if and only if T has simple obstructions.

Proof. Suppose T has obstructions; we must find simple obstructions; the other direction is obvious. 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_{Aut}, 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}}. Choose Δ_{2} so that it contains the set of formulas Δ_{1}^{+} associated to Δ_{1} as Δ_{1} is associated to Δ in Lemma 2.9. Without loss of generality lg(a) = m = m(Δ_{1}, 3n) and we can choose an appropriate Δ_{3} depending on Δ_{2}. Now, define a family of simple obstructions by replacing each component of the given sequence of obstructions by an appropriate object with left prefix sim.

simA^{Δ_{2}} = A^{Δ_{2}}
sim(b_{i}^{Δ_{2}}) =^{sim} (b_{i}^{′Δ_{2}}) = σ(b_{i}^{Δ_{2}})
simc_{i}^{Δ_{2}} = c_{i}^{Δ_{2}}.
sima^{Δ_{2}} = a^{Δ_{2}}.
simΔ_{1} = Δ_{1}^{+}.

We use the same sets of formulas for the Δ_{2} and Δ_{3}.

We now have an obstruction with respect to the identity. For condition 1) this follows from Assumption 2.4; conditions 2) and 3) are immediate; we check condition 4). Since the following argument is uniform Δ_{2}, we omit the superscript Δ_{2}. Examining the implication in condition 4) for both the original obstruction and the simple obstruction we see it suffices to show, if we write τ^{1}(x′, x′, y) for τ_{Δ_{1}^{+}}(x′, x′, y, ⟨σ(b_{i})σ(b_{i})c_{i} : i < k⟩a) and τ^{2}(x, x′, y) for τ_{Δ_{1}^{+}}(x, x′, y, ⟨b_{i}σ(b_{i})c_{i} : i < k⟩a), that

(∀x′)(∀y)[τ^{1}(x′, x′, y) → (∃x)τ^{2}(x, x′, y)].

We verify the implication. Lemma 2.9(taking the b_{i} there as σ(b_{i}), c_{i} here) implies for any b′, c such that ⟨σ(b_{i}), c_{i} : i < k⟩ ∪ {b′, c} is a sequence of Δ_{1}^{+}-indiscernibles, there is a b so that ⟨b_{i}σ(b_{i}), c_{i} : i < k⟩ ∪ {b, b′, c} is a sequence of Δ_{1}-indiscernibles. Thus [τ^{1}(b′, b′, c) → τ^{2}(b, b′, c)] and we finish.

□_{3.6}

Lemma 3.7 If T is a stable theory with the finite cover property then T has a simple obstruction.

Proof. By II.4.4 of [8], there is a formula E(x, y, z) such that for each d, E(x, y, d) is an equivalence relation and for arbitrarily large n there is a d_{n} such that E(x, y, d_{n}) has exactly n classes. Let Δ_{1} be {E(x, y, z), ¬E(x, y, z)} and consider any Δ_{2}. Fix lg(x) = lg(y) = r. There are arbitrarily long sequences b_{n} = ⟨b_{j}^{n} : j < n⟩ such that for some d_{n}, b_{n} is a set of representatives for distinct classes of E(x, y, d_{n}). So by Ramsey, for any Δ_{2} we can find such b_{k} where k = f(Δ_{2}, 3r) and b_{k} is a sequence of length k of F (Δ_{2}, 3n)-indiscernibles over the empty set and b_{k} is a set of representatives for distinct classes of E(x, y, d_{n}). Now, if Δ_{3} contains formulas which express that the number of equivalence classes of E(x, y, z) is greater than n and A contains representatives of all equivalence classes of E(x, y, d_{n}) we have an (identity, Δ_{1}, Δ_{2}, Δ_{3}, r) obstruction over A. (Let b = b′ = c = b_{k}; the hypothesis of clause 4 of Definition 3.2 is trivially false so the condition is satisfied.) □_{3.7}

4 Model Companions of T_{Aut}

In this section we establish necessary and sufficient conditions on stable T for T_{Aut} 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_{Aut} has the amalgamation property.

2. If, in addition, acl(∅) = dcl(∅) in C_{T}^{eq} then T_{Aut} 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_{Aut} has a model companion T_{σ}^{∗}.

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

2. If (M, σ) ⊧ T_{Aut} 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_{Aut} 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_{Aut} ∪ {(∀x)E(x, σ(x))}

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

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

is consistent so is

T_{2} = T_{Aut} ∪ {(∃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 infinitely many 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.8) 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_{Aut}, a ∈ M and suppose that (M, σ) has no σ-obstructions. Fix ψ(x, y, z) ∈ L_{T} 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_{Aut} 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) and any finite Δ_{2} ⊇ F (Δ_{1}, 3n) (Fact 2.3), 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 there are b_{i}σ(b_{i})c_{i} ∈ ^{3n}M for i < k = 5 · f(Δ_{2}, 3n) such that (for λ_{Δ_{2}} from Fact 2.6 4):

(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.3 ) ⟨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}). 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))

The first and last equalities hold by the choice of the b_{i}, c_{i} and the middle 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. 3c) implies 2c) 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.2 for being a (Δ_{1}, Δ_{2}, Δ_{3}, n)-obstruction over A and, in view of Fact 2.6 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. □4.3

As we’ll note in Theorem 4.8, we have established a sufficient condition for T_{Aut} 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_{Aut} does not have a model companion.

Proof. We may assume T does not have f.c.p., since if it does we know by Winkler [9] and Kudaibergenov [3] that T_{Aut} does not have a model companion. By Lemma 3.6, we may assume T has a simple obstruction. So it suffices to prove:

Suppose for some Δ_{1}, and n, and for every finite Δ_{2} ⊇ F (Δ_{1}, 3n), there is a finite Δ_{3} and a tuple (M^{Δ_{2}}, id_{M^{Δ_{2}}}, A^{Δ_{2}}, k^{Δ_{2}}) such that: (M^{Δ_{2}}, id_{M^{Δ_{2}}}) ⊧ T_{Aut}, A^{Δ_{2}} is a finite subset of M^{Δ_{2}}, b^{Δ_{2}}, σ^{Δ_{2}}(b^{Δ_{2}}) = id_{M^{Δ_{2}}}(b^{Δ_{2}}) = b^{Δ_{2}}, c^{Δ_{2}}, a^{Δ_{2}} contained in M^{Δ_{2}} are an (id_{M^{Δ_{2}}}, Δ_{1}, Δ_{2}, Δ_{3}, n) obstruction of length k^{Δ_{2}} over A^{Δ_{2}}.

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

Without loss of generality lg(a) = m = m(Δ_{1}, 3n) and we can write Δ_{3} = Δ_{3}(Δ_{2}). By the usual coding we may assume Δ_{1} = {ψ(x, y, z)} with lg(x) = lg(y) = n, lg(z) = m, k = f(Δ_{1}, 3n). Again, without loss of generality each (M^{Δ_{2}}, id_{M^{Δ_{2}}}) can be expanded to an existentially closed model (M^{Δ_{2}}, σ_{M^{Δ_{2}}}) such that σ_{M^{Δ_{2}}} fixes A^{Δ_{2}}, a^{Δ_{2}}, b^{Δ_{2}}, and c^{Δ_{2}} pointwise. 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 L to L^{+} by adding a unary function symbol σ, a new unary predicate symbol P, a 3n-ary relation symbol Q and constants a. Expand each of the M^{Δ_{2}} to an L^{+}-structure N_{Δ_{2}} by interpreting P as A^{Δ_{2}}, a as a^{Δ_{2}} σ as σ^{Δ_{2}} = id_{M^{Δ_{2}}} and Q as the set {b_{i}^{Δ_{2}}b_{i}^{Δ_{2}}c_{i}^{Δ_{2}} : i < k^{Δ_{2}}} of 3n-tuples. Let N^{∗} 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.

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 (id, Δ_{1}, Δ_{2}, Δ_{3}, n)-obstruction ⟨b^{Δ_{2}}, b^{Δ_{2}}, c^{Δ_{2}}⟩a^{Δ_{2}} in M^{Δ_{2}} over A^{Δ_{2}}.

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.3 and the definition of the ultrafilter D.) □_{4.5}

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 conjunction of 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^{∗}.

Notation 4.6 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.7 If K_{σ}, the family of existentially closed models of T_{Aut}, is axiomatized by T_{Aut}^{∗}, then

T_{Aut}^{∗} ∪ Γ ∪ {σ(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} for i ∈ I free.)

Note for each i, x_{i} = x′_{i} is in Γ. For this, let (M′, σ′) ⊧ T_{Aut}^{∗} such that ⟨b_{i}, b_{i}, c_{i} : i ∈ I⟩a satisfy Γ in M′. Suppose M′ ≺ M′′ and M′′ is an |M′|^{+}- saturated model of T. In M′′ we can find b, b′, 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, c; the second holds as σ′ is an automorphism, and the third follows from clause 4 in the description of the ultraproduct, Claim 4.5.) Now since M′′ is |M′|^{+}-saturated there is an automorphism σ′′ of M′′ extending σ′ and taking b to c.

As (M′, σ′) ⊧ T_{Aut}^{∗}, it is existentially closed. So we can pull 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_{Aut}^{∗} ∪ Γ ∪ {σ(x_{i}) = x′_{i} : i ∈ I}; so

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

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_{Aut}^{∗} ⊢

(∀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 (id, Δ_{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}}).

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}} witness this sentence; then σ^{Δ_{2}}(b′) = c. Then

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

By the definition of obstruction,

σ^{Δ_{2}}(tp_{Δ_{3}}(b′/A^{Δ_{2}} ∪ a^{Δ_{2}})) ≠ tp_{Δ_{3}}(c/A^{Δ_{2}} ∪ a^{Δ_{2}}).

Since σ^{Δ_{2}} fixes A^{Δ_{2}} ∪ a^{Δ_{2}} pointwise, this contradicts that σ^{Δ_{2}}(b′) = c and we finish. □4.4

Finally we have the main result.

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

Proof. We showed in Lemma 4.4 that if T_{Aut} has a model companion then there is no obstruction. If there is no obstruction, Lemma 3.7 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_{Aut} holds of any a in M if and only if there exists (N, σ), (M, σ) ⊆ (N, σ) ⊧ T_{Aut} and

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

Thus, the class of existentially closed models of T_{Aut} 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]). □_{4.8}

Kikyo and Pillay [4] note that if a strongly minimal theory has the definable multiplicity property then T_{Aut} has a model companion. In view of Theorem 4.8, 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_{Aut} 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.9 If the ω-stable theory T with finite rank does not have the definable multiplicity property, must it admit 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.10 Can T_{Aut} for an ℵ_{0}-categorical stable 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:71–92, 1998.

[3] Hirotaka Kikyo. Model companions of theories with an automorphism. The Journal of Symbolic Logic, 65:1215–1222, 2000.

[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. The Journal of Symbolic Logic, 67:214–217, 2002.

[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. 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. Saracino and V. Weispfennig, editors, Model Theory and Algebra, pages 408–464. Springer-Verlag, 1975.