Hoja calculo

On externally definable sets and a theorem of Shelah
Anand Pillay∗ University of Leeds April 27, 2006
In [4] Saharon Shelah proves the striking and important result that if T is a complete theory without the independence property, M is a model of T , and M ∗ is the expansion of M by adjoining predicates for “externally definable” subsets of M, M × M, ..., then T h(M ∗ ) has quantifier elimination.Shelah’s proof is not so long, but arguably rather obscure. The aim of this expository paper is to give a direct and conceptual proof of Shelah’s theorem. In fact we give two proofs, the first going through quantifier-free heirs of quantifier-free types and the second through quantifier-free coheirs of quantifier-free types. We would hope that our proofs might suggest various strengthenings of thetheorem (namely stronger conclusions). As this paper is expository we feel free to give more details than we normally would. Special cases of Shelah’s result were proved earlier in [1] (the o-minimal case) and [2] (the weakly o-minimal case). Frank Wagner and Victor Verbovskiy ([5]) also found a somewhat simplified account of Shelah’s proof. Thanks to Martin Ziegler for discussions, to Udi Hrushovskiand Kobi Peterzil for comments on earlier versions, and to the referee for a few notational suggestions. ¯ Our notation is standard. We work in a large saturated model M of a complete theory T in a language L. The symbols x, y range over finite tuples ¯ of variables, and a, b, .. over finite tuples of elements of M . We will make systematic use of some basic notions of model theory, such as coheirs,heirs, definability of types, etc, but with respect to com∗

Supported by a Marie Curie Chair

1

plete quantifier-free types. We will give a brief summary. qf tp(−) denotes quantifier-free type of ..... For M a model of T (namely elementary sub¯ structure of M ) Sqf (M ) denotes the set of complete quantifier-free types over M . Likewise for Sqf (A), Sqf (T )... We will say that p(x) ∈ Sqf (M) is quantifier-free definable if for each quantifier-free L-formula φ(x, y) there is a quantifier-free formula ψ(y) over M (namely with parameters from M ) such that for each b ∈ M , φ(x, b) ∈ p(x) iff |= ψ(b). We call the map taking φ(x, y) to ψ(y) a (quantifier-free) defining scheme d say, for p(x). If A ⊇ M , we can apply the scheme d to A to get d(A) ∈ Sqf (A), an extension of p. (Namely for a ∈ A,φ(x, a) ∈ d(A) iff |= d(φ)(a).) Suppose that p(x) ∈ Sqf (M ), M ⊆ A and q(x) ∈ Sqf (A) is an extension of p(x). In this context we say that q(x) is a quantifier-free heir of p if for every quantifier-free formula φ(x, y) over M such that φ(x, b) ∈ q(x) for some b ∈ A there is b ∈ M such that φ(x, b ) ∈ p(x). Likewise we say that q(x) is a quantifier-free coheir of p(x) if q is finitely satisfiable in M, namely every formula in q(x) is satisfied by a tuple from M . Lemma 0.1. Suppose that M is a fixed model of T . (i) If p(x) ∈ Sqf (M ) is quantifier-free definable, with defining schema d, then for any A ⊇ M , d(A) is the unique quantifier-free heir of p(x) over A. (ii) If every complete quantifier-free type over M (in any finite number of variables) is quantifier-free definable, then any p(x) ∈ Sqf (M )has a unique quantifier-free coheir over any A ⊇ M . Proof. (i) is standard. (ii) Suppose a1 and a2 realize distinct quantifier-free coheirs of p(x) ∈ Sqf (M ) over M b. Then qf tp(b/M ai ) is a quantifier-free heir of qf tp(b/M ) for i = 1, 2. But for some quantifier-free formula φ(x, y) over M , we have |= φ(a1 , b) ∧ ¬φ(a2 , b), which contradicts (i) as both a1 and a2 have the same quantifierfreetypes over M . Note that in (ii) there is no reason whatsoever why the unique quantifier-free coheir of p should coincide with its unique quantifier-free heir. The notion of a quantifier-free indiscernible sequence (ai : i < ω) over a set A of parameters is clear. The following is standard. Lemma 0.2. (i) Let p(x) ∈ Sqf (M ) be quantifier-free definable, with defining schema d. Let a0 realize p(x) and...