Chernikov and Simon’s proof of Shelah’s theorem^{∗}

M. Ziegler

October 17, 2010

Let T be a complete theory with monster model ℂ and M ≺ ℂ a model of T. A relation X ⊂ M is externally definable if for some formula ϕ(x, y) and parameter c ∈ ℂ we have X = ϕ(M, c). Shelah has shown in [3] for dependent (i.e. NIP) T that the structure M together with all externally definable relation has quantifier elimination. Pillay gave a better proof in [2]. Recently a new proof was given by Chernikov and Simon in [1]. The purpose of this note is to present a variant of their proof which avoids adding new predicates to the language.

We will need the following notation: a | ⌣^{∗}_{M} c means that tp(a/Mc) is a coheir of tp(a/M). The following is easy to see:

Lemma 1. (1) B | ⌣^{∗}_{M} c, a | ⌣^{∗}_{M} Bc ⇒ aB | ⌣^{∗}_{M} c

(2) If A | ⌣^{∗}_{M} c, then every type over AM is realised by some b with bA | ⌣^{∗}_{M} c.

The next proposition is a version of Proposition 1.1 of [1].

Proposition 2. Let M be a model. ϕ(x, y) a formula without the independence property and c ∈ ℂ. Then there is a set A and an L(A)–formula θ(x) such that

a) A | ⌣^{∗}_{M} c

b) θ(M) = ϕ(M, c)

c) For all b with bA | ⌣^{∗}_{M} c, we have ⊧ θ(b) → ϕ(b, c).

Proof. Consider the set Q of all global types q which are coheirs of their restriction to M and contain ϕ(x, c). Clearly Q is a closed subset of S(ℂ). Let q_{α}, (α < λ) be an enumeration of Q. We construct recursively an ascending sequence of sets A_{α} and of L(A_{α}) formulas θ_{α}(x) as follows: Set A′ = ⋃_{β<α} A_{β}. By assumption we have A′ | ⌣^{∗}_{M} c. Then try to choose an infinite sequence a_{0}, b_{0}, a_{1}, … such that

a’) {a_{0}, b_{0}, a_{1}, …}A′ | ⌣^{∗}_{M} c

b’) a_{i} ⊧ q_{α} ↾ a_{0}b_{0} … b_{i−1}MA′c

c’) b_{i} ⊧ q_{α} ↾ a_{0}b_{0} … a_{i}MA′ ∪ {¬ϕ(x, c)} Since q_{α} is a coheir of q_{α} ↾ M, the sequence a_{0}, b_{0}, … is indiscernible over M. ϕ(x, y) is NIP and ⊧ ϕ(a_{i}, c)∧¬ϕ(b_{i}, c), so the construction must fail. For b_{i} we can always choose an arbitrary realization of q_{α} ↾ a_{0}b_{0} … b_{i−1}MA′c and have then {a_{0}, b_{0}, … b_{i}}A′ | ⌣^{∗}_{M} c by Lemma 1 (1).

∗I thank Enrique Casanovas for pointing out an inaccuracy in an earlier version.

So the construction must fail at some stage where we cannot find b_{i} which satisfies a’) and c’). Set A_{α} = {a_{0}, b_{0}, …, a_{i}} ∪ A′ and choose a formula θ_{α} ∈ q_{α} ↾ MA_{α} such that for all b with bA_{α} | ⌣^{∗}_{M} c we have ⊧ θ(b) → ϕ(b, c).

We take for A the union of all the A_{α}. The formulas θ_{α} cover the space Q. So there are finitely many α_{1}, …, α_{n−1} such that θ = ⋁_{i<n} θ_{α_{i}} is contained in all q ∈ Q. It is clear that the properties a) and c) are true. Since mA | ⌣^{∗}_{M} c for all m ∈ M, this implies also θ(M) ⊂ ϕ(M, c). If m belongs to ϕ(M, c), we have q = tp(m/ℂ) ∈ Q. So θ ∈ q and we have m ∈ θ(M).

Let R = θ(M) be an externally defined relation on M. θ(x) is an honest definition of R if for all L(M)–formulas ψ(x)

θ(M) ⊂ ψ(M) ⇒ θ(ℂ) ⊂ ψ(ℂ).

Corollary 3 ([1]). In a dependent theory every externally definable relation on M has an honest definition.

Proof. If R = ϕ(M, c), choose A and θ as in the proposition. Then R = θ(M). We claim that θ(x) is an honest definition of R: Assume θ(M) ⊂ ψ(M). Then all m ∈ M satisfy ϕ(m, c) → ψ(m), which implies that ⊧ ϕ(b, c) → ψ(b) for all b with b | ⌣^{∗}_{M} c. So by the proposition we have ⊧ θ(b) → ψ(b) for all b with bA | ⌣^{∗}_{M} c. With Lemma 1 (2) this implies θ(ℂ) ⊂ ψ(ℂ).

Shelah’s theorem follows from this like in [1]: Let R ⊂ M^{2} be a relation with an honest definition θ(x, y). Then ∃yθ(x, y) is an external definition of π(R) = {m ∈ M | (m, n) ∈ R for some n ∈ M}. To see this consider m_{0} ∈ M and the formula ψ(x, y) = ¬x ≐ m_{0}. Then m_{0} ∈ π(R) iff θ(M) ⊄ ψ(M) iff θ(ℂ) ⊄ ψ(ℂ) iff ⊧ ∃yθ(m_{0}, y).

References

[1] Artem Chernikov and Pierre Simon. Externally definable sets and dependent pairs. arXiv:math.LO71007.4468, 2010.

[2] Anand Pillay. On externally definable sets and a theorem of shelah. In Felgner Festchrift, Studies in Logic. College Publiications, 2007.

[3] Saharon Shelah. Strongly dependent theories. Israel Journal of Mathematics, accepted. math.LO/0504197.