Model Companions of Theories with an Automorphism

Kikyo, Hirotaka

June 29, 1998

Abstract For a theory T in L, T_{σ} is the theory of the models of T with an automorphism σ. If T is an unstable model complete theory without the independence property, then T_{σ} has no model companion. If T is an unstable model complete theory and T_{σ} has the amalgamation property, then T_{σ} has no model companion. If T is model complete and has the fcp, then T_{σ} has no model completion.

1 Introduction

In [ChP], Chatzidakis and Pillay studied the theory T_{P}, the theory of models of T with a distinguished new unary predicate P, and T_{σ}, the theory of models of T with a distinguished new automorphism σ. They showed that if T is stable, T = T^{eq}, and admits QE, then the model companions of T_{P} and T_{σ} are simple. The typical case is that the model companion of ACF_{σ} exists and called ACF A, where ACF is the theory of algebraically closed field. They also showed that the model companion of T_{P} exists if and only if T admits the elimination of ∃^{∞}, but they did not show any conditions on the existence of the model companion of T_{σ}.

Khudaibergenov proved that if T is stable and has the fcp then T_{σ} has no model companion, by reducing to the case that T does not admit the elimination of ∃^{∞}. In this case the argument is similar to that for T_{P}.

The work has been done while the author was visiting MSRI. The author would like to thank MSRI for its hospitality.

In this paper, we show that T_{σ} has no model companion if T is unstable without the independence property, or T is unstable and T_{σ} has the amalgamation property. If T is stable then T_{σ} has the amalgamation property, or more generally it has PAPA [L1, L2, ChP] in T^{eq}. So, if T is model complete and has the fcp, then T_{σ} has no model completion. In particular, if T = T^{eq}, admits the elimination of quantifiers, and has PAPA, then T_{σ} has no model companion if T has the fcp.

Here is a history of the results. Tsuboi tried to extend the result of Chatzidakis and Pillay for T_{σ} to the case T is simple, and investigated the theory of the random graph with an automorphism. He tried to give an axiomatization of the model companion of the theory, and found some difficulty when σ has a fixed point of certain kind. Looking at this difficulty, the author found that the theory of the random graph with an automorphism does not have the model companion. When the author told Pillay about this, he suggested that the fcp might be the reason. The author checked this property for the theory of the dense linear order without endpoints, the o-minimal theories, and the theory of the atomless Boolean algebra. It turned out that there are no model companions of T_{σ} for these theories. With some more work, we could generalize them to the theorems in this paper.

We could not get rid of the assumption that T_{σ} has the amalgamation property in general. For our argument, the formulas with the independence property are harmful. The random graph has the independence property and the unstability comes only from this, but in this case the argument for the existence of an appropriate fixed point works because of its randomness. Even if we assume that T is simple or supersimple, it seems that the machineries developed for the simple theories don’t give good information.

There are some theories T such that T_{σ} has no model companion but has independence property and does not have the amalgamation property. ACFA is such an example. It seems that our argument does not work in this example.

The author would like to thank Akito Tsuboi for the valuable discussions about the random graph, and Zoé Chatzidakis and Ehud Hrushovski for the information about ACFA and pseudo-finite fields. The author also would like to thank Daniel Lascar and Anand Pillay for the valuable discussions and comments.

2 Preliminaries

First we recall some basic definitions and facts. If M ⊂ N are models of a model complete theory then M is an elementary substructure of N. So the truth of any definable relations with parameters from M are preserved upwards and downwards. In fact, the following are equivalent:

(1) T is model complete;

(2) Every formula is equivalent to an existential formula modulo T;

(3) Every formula is equivalent to a universal formula modulo T.

Note also that a model complete theory can be axiomatized by universalexistential sentences (a universal-existential theory). If a theory T admits the elimination of quantifiers then T is model complete.

Definition 2.1 Let T and T′ be two theories (not necessarily complete) in the same language. T′ is a model companion of T if T′ is model complete, every model of T can be extended to a model of T′ and every model of T′ can be extended to a model of T. T′ is a model completion of T if T′ is a model companion of T, and if M is a model of T and M_{1}, M_{2} are models of T′ extending M then M_{1} and M_{2} are elementarily equivalent over M. If T has a model completion then T must have the amalgamation property and if T has the amalgamation property then the model companion of T is a model completion of T.

Recall that if T is a universal-existential theory and T′ a model companion of T, then M is a model of T′ if and only if M is an existentially closed model of T.

We need some more notation and definition for our arguments. ⟨⋯⟩ denotes a sequence, and Iˆ I′ denotes the concatenation of sequences I and I′.

Definition 2.2 Let I = ⟨ā_{i} : i < ω⟩ be a sequence of tuples, L a language and B a set of parameters. The average L-type of I over B is the partial type Av_{L}(I/B) defined by

Av_{L}(I/B) = {φ(x̄, b̄) :⊧ φ(ā_{i}, b̄) for all but finitely many i < ω}.

Definition 2.3 Let M be an L-structure, σ an automorphism of M and p(x̄) an L-type over M. σp(x̄) is the type

{φ(x̄, σ(m̄)) : φ(x̄, m̄) ∈ p(x̄), φ(x̄, ȳ) ∈ L}.

3 Unstable models with an automorphism

For the rest of the paper, unless stated otherwise, we assume that T is a complete and model complete theory in the language L. We use σ to denote the unary function symbol representing an automorphism of a model of T. T_{σ} is the union of T and the set of axioms stating that σ is an L-automorphism. Note that T_{σ} is a universal-existential theory in L(σ) = L ∪ {σ}.

Theorem 3.1 If T is an unstable model complete theory without the independence property, then T_{σ} has no model companion.

Proof Since T is unstable, there is an antisymmetric L-definable relation x̄ < ȳ such that for some sequence {ā_{i} : i < ω}, ā_{i} < ā_{j} if and only if i < j.

Suppose that T_{σ} has the model companion T_{A}. Consider the following theory T_{1} in the language L(σ, ā, b̄) where ā and b̄ are sequences of new constants:

(1) The axioms in T_{A};

(2) ⟨σ^{i}(ā) : i < ω⟩ˆ ⟨b̄⟩ is L-indiscernible;

(3) ā < σ(ā).

We claim first that T_{1} is consistent. First, we work in a big model of T. Let ⟨ā_{i} : i < ω⟩ˆ ⟨b̄⟩ be an L-indiscernible sequence such that ā_{0} < ā_{1}. We can choose a model M of T and an automorphism σ of M such that M contains this sequence and σ(ā_{i}) = ā_{i+1} for i < ω. M satisfies (2) and (3) with ā = ā_{0}. Since (M, σ) is a model of T_{σ}, it can be extended to a model (M′, σ′) of T_{A}. Since M′ is an L-elementary extension of M, M′ satisfies (2) and (3) also.

Now we claim that T_{1} ⊢ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄].

Let (M, σ) be any model of T_{1}. Then I = ⟨σ^{i}(ā) : i < ω⟩ is an Lindiscernible sequence in M. Let p(x̄) = Av_{L}(I/M). Since T does not have the independence property, p(x̄) is a complete L-type over M. By the definition of the average type, the formula ā < x̄ < b̄ belongs to p(x̄). Also, it is easy to check that σ(p) = p. So, there is an elementary extension M′ of M and an automorphism σ′ of M′ such that σ′ extends σ and fixes some realization of p(x̄) in M′. In particular,

(M′, σ′) ⊧ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄].

Since (M, σ) is existentially closed among the models of T_{σ} and the relation < can be written in an existential form modulo T,

(M, σ) ⊧ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄].

Thus we have the claim.

By compactness, T′_{1} ⊢ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄] for some finite subset T′_{1} of T_{1}. In particular, the axiom (2) can be replaced by the indiscernibility of ⟨σ^{i}(ā) : i < N⟩ˆ ⟨b̄⟩ for some natural number N. Now choose a model (M, σ, ā, b̄_{0}) of T_{1}. If we change the interpretation of b̄ to σ^{k}(ā) for some k > N, still it is a model of T′_{1}. We have

(M, σ, ā, σ^{k}(ā)) ⊧ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < σ^{k}(ā)],

but this cannot happen because σ is an L-automorphism and must preserve the relation <.

The proof of the theorem above is a generalization of the direct proof of the fact that the following examples have no model companion.

Example 3.2 The model companions of T_{σ} do not exist for the following theories: The theory T of dense linear order, or more generally, model complete o-minimal theories; The theory of p-adic number field in Macintyre’s language.

There are many theories which have the independence property but the corresponding T_{σ} has no model companion.

Theorem 3.3 If T is an unstable model complete theory and T_{σ} has the amalgamation property, then T_{σ} has no model companion.

Proof Let T_{S} be a Skolemization of T in the language L_{S}.

First, we work in a big model of T_{S}. Since T is unstable, there is an antisymmetric L-definable relation x̄ < ȳ such that for some sequence {ā_{i} : i < ω}, a_{i} < a_{j} if and only if i < j. Choose an L_{S}-indiscernible sequence ⟨ā_{i} : i ∈ Z⟩ˆ ⟨b̄_{i} : i ∈ Z⟩ such that ā_{0} < ā_{1}. Let M_{0} be the Skolem hull of this sequence. Then the map σ_{0} given by σ_{0}(ā_{i}) = ā_{i+1} and σ_{0}(b̄_{i}) = b̄_{i+1} extends to an L_{S}-automorphism of M_{0}.

The reduct of (M_{0}, σ_{0}) to L(σ) is a model of T_{σ}.

Now suppose that T_{σ} has the model companion T_{A}. Then (M_{0}, σ_{0}) has an extension (M_{1}, σ_{1}) which is a model of T_{A}.

Now consider the following theory T_{1} in the language L_{S}(σ, P, ā, b̄) where P is a new unary predicate symbol, and ā, b̄ are sequences of new constant symbols:

(1) The axioms in T_{A};

(2) Every functions in L_{S} are total on P and P is closed under every functions in L_{S};

(3) P is a model of T_{S};

(4) σ is an L_{S}-automorphism on P;

(5) ⟨σ^{i}(ā) : i ∈ Z⟩ˆ ⟨σ^{i}(b̄) : i ∈ Z⟩ is L_{S}-indiscernible in P;

(6) ā < σ(ā).

Note that the Skolem functions in L_{S} \ L are considered here as partial functions. If we interpret P by M_{0} in M_{1}, we get a model of T_{1}. Thus T_{1} is consistent.

Now we claim that T_{1} ⊢ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄].

Let (M_{1}, σ_{1}, ā, b̄) be any model of T_{1}. Let M_{0} be the Skolem hull of the sequence I = ⟨σ^{i}(ā) : i ∈ Z⟩ˆ ⟨σ^{i}(b̄) : i ∈ Z⟩ in P (M_{1}). Note that M_{0} is an elementary L_{S}-substructure of P (M_{1}). In particular, M_{0} is a model of T.

Since σ_{1} is an L_{S}-automorphism on P (M_{1}), M_{0} is closed under σ_{1} and σ_{0} = σ_{1}|M_{0} is an L_{S}-automorphism of M_{0}. Hence, (M_{0}, σ_{0}) is a model of T_{σ}.

Now consider the average L-type p(x̄) of ⟨σ_{0}^{i}(ā) : i < ω⟩ over M_{0}. Let φ(x̄, m̄) be an L-formula with parameters m̄ in M_{0}. Since M_{0} is the Skolem hull of I, φ(x̄, m̄) can be written as a formula in L_{S} with finite number of parameters from I, say σ_{0}^{i}(ā) and σ_{0}^{i}(b̄) for |i| < k. By the L_{S}-indiscernibility of I, the truth value of φ(σ_{0}^{n}(ā), m̄) are the same for n > k. So, one of φ(x̄, m̄) or ¬φ(x̄, m̄) belongs to p(x̄). Hence, p(x̄) is complete over M_{0}. Note that the formula ā < x̄ < b̄ belongs to p(x̄). Also, it is easy to check that σ_{0}(p) = p.

Now we can find an L-elementary extension M_{2} of M_{0} and an L-automor-phism σ_{2} of M_{2} such that σ_{2} extends σ_{0} and fixes some realization of p(x̄) in M_{2}. In particular, (M_{2}, σ_{2}) is a model of T_{σ} and

(M_{2}, σ_{2}) ⊧ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄].

By the amalgamation property of T_{σ}, there is an extension (M_{3}, σ_{3}) of (M_{1}, σ_{1}) such that (M_{3}, σ_{3}) is a model of T_{σ} and (M_{2}, σ_{2}) embeds in (M_{3}, σ_{3}) over (M_{0}, σ_{0}). Then we have

(M_{3}, σ_{3}) ⊧ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄].

Since T is model complete, < can be written in an existential form modulo T. As (M_{1}, σ_{1}) is a model of T_{A}, it is existentially closed among the models of T_{σ}. Hence,

(M_{1}, σ_{1}) ⊧ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄].

Thus we have the claim.

By compactness, only a finite part of T_{1} is necessary to deduce the formula ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < b̄]. In particular, the axiom (5) can be replaced by the axiom

⟨σ^{i}(ā) : |i| < N⟩ˆ ⟨σ^{i}(b̄) : |i| < N⟩ is L_{S}-indiscernible in P;

for some natural number N and still deducing the above formula. We can satisfy these axioms by taking a model (M, σ, ā, b̄_{0}) of T_{1} and changing the interpretation of b̄ to σ^{k}(ā) for some k > 2N. Then we have

(M, σ, ā, σ^{k}(ā)) ⊧ ∃x̄ [σ(x̄) = x̄ ∧ ā < x̄ < σ^{k}(ā)],

but this cannot happen because σ is an L-automorphism and must preserve the relation <.

With the following fact proved by Kudaibergenov, we can conclude that if T has the fcp and model complete then T_{σ} has no model completion.

Definition 3.4 For a complete theory T, we say that T does not admit the elimination of ∃^{∞} if there are a formula φ(x̄, ȳ) and a set of parameters {ā_{n} : n < ω} such that for each n < ω, the number of the realizations of φ(x̄, ā_{n}) is finite but greater than n.

Fact 3.5 (Kudaibergenov) (1) If T is model complete and does not admit the elimination of ∃^{∞}, then T_{σ} has no model companion.

(2) If T is stable, model complete and has the fcp, then T_{σ} has no model companion.

Proof (1) Suppose T does not admit the elimination of ∃^{∞} and T_{σ} has the model companion T_{A}. Let φ(x̄, ȳ) and a set of parameters {ā_{n} : n < ω} be such that for each n < ω, the number of the realizations of φ(x̄, ā_{n}) is finite but greater than n. Let M_{0} be a model of T containing a_{n}’s. (M_{0}, id) where id is the identity map on M is a model of T_{σ}, so there is a model (M, σ) of T_{A} extending (M_{0}, id). Since M_{0} ≺ M and the set of realizations of each φ(x̄, ā_{n}) in M_{0} is finite, it is the same in M. So, σ fixes every realization of each φ(x̄, ā_{n}). Let U be a non-principal ultrafilter on ω. Make an ultrapower (M̃, σ̃) = (M, σ)^{ω}/U, and let b̄ = ⟨ā_{i} : i < ω⟩/U. Since each σ is the identity on each φ(x̄, ā_{i}), σ̃ is also the identity on φ(x̄, b̄). On the other hand, the number of realizations of φ(x̄, b̄) in M̃ is infinite. But it is impossible to have a model of T_{A} such that the automorphism fixes pointwise an infinite definable set.

(2) Suppose T is stable, model complete, and has the fcp. Then T^{eq} is also model complete and does not admit the elimination of ∃^{∞} by the fcp theorem [SH]. Suppose in addition that T_{σ} has the model companion T_{A}. Now it is routine to check that T_{A} ∪(T^{eq})_{σ} is the model companion of (T^{eq})_{σ}. This contradicts (1).

Corollary 3.6 Suppose T is model complete and not necessarily complete. If T has some model with the fcp, then T has no model completion. In particular, if T = T^{eq}, admits the quantifier elimination, has the PAPA [L1, L2, ChP] and the fcp, then T_{σ} has no model companion.

Example 3.7 The theories of the random graph and the atomless Boolean algebra have the PAPA. More generally, unstable countably categorical theories obtained by the Fraïssé’s method from a class of finite structures which admits the free amalgamation have the PAPA [L2]. The model companions of T_{σ} do not exist for these theories.

4 Some remarks

Hrushovski proved that ACF A_{σ} does not have neither the model companion nor the amalgamation property. Chatzidakis proved that P sf_{σ}, where P sf is the theory of pseudo-finite fields, does not have the model companion by a similar argument to Hrushovski’s. Their arguments are very specific to the field theory. It seems that our method does not work in these theories.

Here is another example of a theory T such that T_{σ} does not have the amalgamation property due to M. Ziegler [L1].

Example 4.1 The language has two predicate symbols R(x, y, z) and U(x). Let (M, <) be a dense linear order without endpoints and interpret R and U on M so that R(a, b, c) if and only if a < b < c and U(M) is dense and codense in M. Then Th(M; R, U) admits the quantifier elimination, but does not have neither the amalgamation property nor the independence property.

Hence, the theorems 3.1 and 3.3 are independent.

It is possible to expand the Ziegler’s example to have the independence property without the T_{σ} having the amalgamation property. To show this, we give a lemma concerning the types fixed by an automorphism. The proof is similar to that of the existence of a nonforking extension of a type in [SH].

Definition 4.2 Let M be a model and σ an automorphism of M. A formula φ(x̄, m̄), where φ(x̄, ȳ) is parameter-free and m̄ ∈ M, is said to be σ-consistent if {φ(x̄, σ^{n}(m̄)) : n < ω} is consistent.

Lemma 4.3 Let M be a model, σ an automorphism of M, and p(x̄) a partial type over M. The following are equivalent.

(1) There is a complete type q(x̄) over M such that p(x̄) ⊂ q(x̄) and σq(x̄) = q(x̄);

(2) For any formulas φ_{1}(x̄, m̄_{1}), …, φ_{k}(x̄, m̄_{k}) over M,

p(x̄) ⊢ φ_{1}(x̄, m̄_{1}) ∨ ⋯ ∨ φ_{k}(x̄, m̄_{k})

implies that φ_{i}(x̄, m̄_{i}) is σ-consistent for some i between 1 and k.

Proof (1) ⇒ (2). Let q(x̄) be a complete type over M such that p(x̄) ⊂ q(x̄) and σq(x̄) = q(x̄). Suppose

p(x̄) ⊢ φ_{1}(x̄, m̄_{1}) ∨ ⋯ ∨ φ_{k}(x̄, m̄_{k}).

Then one of φ_{i}(x̄, m̄_{i})’s is in q(x̄). It is σ-consistent.

(2) ⇒ (1). Let

Σ(x̄) = {¬φ(x̄, m̄) : φ(x̄, m̄) is not σ-consistent, φ(x̄, ȳ) ∈ L, m̄ ∈ M}.

By compactness and (2), p(x̄)∪Σ(x̄) is consistent. Let q(x̄) be any completion of p(x̄) ∪ Σ(x̄) over M.

Suppose σq(x̄) ≠ q(x̄). Then φ(x̄, m̄) ∈ q(x̄) and ¬φ(x̄, σ(m̄)) ∈ q(x̄), thus φ(x̄, m̄) ∧ ¬φ(x̄, σ(m̄)) ∈ q(x̄) for some φ(x̄, m̄). On the other hand, φ(x̄, m̄) ∧ ¬φ(x̄, σ(m̄)) is an L(M)-formula but is not σ-consistent. So, its negation belongs to Σ(x̄) ⊂ q(x̄). This is a contradiction. Hence σq(x̄) = q(x̄).

It seemed that this lemma would be useful for our general argument to find a fixed point, but we could not use it.

Example 4.4 There are many expansions of the Ziegler’s example whose T_{σ} do not have the amalgamation property.

Let M = Q \ {0} and consider (M; R(x, y, z), U(x)) where R(a, b, c) if and only if b is in between a and c, and U(M) = {m/2^{n} : m, n ∈ Z}.

Let α be the automorphism of M given by α(x) = −x for x ∈ Q. Put any relations on Q^{+} = {x ∈ Q : x > 0}. Expand the each relation P (x_{1}, …, x_{k}) to M in the minimum way so that

• P (x_{1}, …, x_{k}) if and only if P (α(x_{1}), …, α(x_{k})), and

• P (x_{1}, …, x_{i}, …, x_{k}) if and only if P (x_{1}, …, x_{i−1}, α(x_{i}), x_{i+1}, …, x_{k}) for each i.

α is an automorphism for the expanded structure. Also, each new relation P restricted to Q^{+} does not change by this modification. So, if you put a relation with the independence property at the beginning, the property is preserved.

Now consider the two partial types

p_{1}(x) = {R(a, x, b) : a < 0 < b} ∪ {U(x)} and
p_{2}(x) = {R(a, x, b) : a < 0 < b} ∪ {¬U(x)}.

By the lemma above, it is easy to check that both p_{1}(x) and p_{2}(x) have some complete extensions to M which are fixed by α. We can extend α in two ways so that it has some fixed point realizing each one of p_{1}(x) and p_{2}(x), but it is impossible to have two distinct fixed point at the same time extending α.

If we do not put any new relations on some open interval containing 0 then there will be no model companions for T_{σ}, but we don’t know if this is true in general.

References

[ChP] Z. Chatzidakis and A. Pillay, Generic structures and simple theories, preprint.

[Ho] W. Hodges, Model theory, Cambridge Univ. Press, Cambridge, 1993.

[L1] D. Lascar, Autour de la propriété du petit indice, Proc. London Math. Soc. 62 (1991) 25-53.

[L2] D. Lascar, Les beaux automorphismes, Arch. Math. Logic 31 (1991) 55-68.

[M] A. Macintyre, Twenty years of p-adic model theory, In Logic Colloquium ’84, ed. J.B. Paris et al, 121-153, North Holland, Amsterdam, 1986.

[P] A. Pillay, An introduction to stability theory, Clarendon, Oxford, 1983.

[SH] S. Shelah, Classification theory and the number of non-isomorphic models, North Holland, Amsterdam, 1978.

Department of Mathematical Sciences Tokai University 1117 Kitakaname, Hiratsuka 259-12 Japan

e-mail:kikyo@ss.u-tokai.ac.jp