An application of Compactness and Ramsey theorem

363 Views Asked by At

Definition: A formula $\varphi(x,y)$ has $VC_{ind}-density ≤ r$ for $r ∈ R$ if there is $K \in \omega$ such that for every finite and indiscernible sequence $\overline{b} = \langle b_i : i < N \rangle ∈ M^{|y|·N}$, $|S_{\varphi}(range(\overline{b}))| < K · N^r$. We denote this by $VC_{ind} ≤ r$.
(Where $S_{\varphi}(A)$ is the set of all $\varphi$-types over A for for $A \subseteq M^{|y|}$, such that $M$ is the underlying set of the monster model $\mathcal{M}$ of the complete theory $T$.)

Now suppose $VC_{ind} \geq d$, for some positive $d \in \omega$. Let $0 < \epsilon < 1/2$. How we could show By compactness, Ramsey’s theorem, and saturation of the monster model, there is some indiscernible sequence $\langle a_i \rangle_{i \in \mathbb{R}}$ such that $|S_{\varphi}(A)| ≥ |A|^{d−\epsilon}$ for arbitrarily large finite $A ⊆ \langle a_i \rangle_{i \in \mathbb{R}}$.

Would be grateful for your hints or solutions.

1

There are 1 best solutions below

6
On

I may edit (or delete) this (sketch of an) answer in the next days.

Note that for each $n$ there is a first order formula $\vartheta_n(x_1,\dots,x_n)$ such that

$$M\models\vartheta_n(a_1,\dots,a_n)\ \Leftrightarrow\ |S_{\varphi}(a_1,\dots,a_n)| ≥ n^{d−\varepsilon}$$

The formula $\vartheta_n(a_1,\dots,a_n)$ may be horribly long. For instance, for $d=2$, when $\varepsilon$ is sufficiently small, $\vartheta_2(a_1,a_2)$ should say that $|S_{\varphi}(a_1,a_2)|=4$, that is, that

$$\varphi(x,a_1)^{\eta_1}\wedge\varphi(x,a_2)^{\eta_2}$$

is consistent for every $\eta_1,\eta_2\in\{0,1\}$. As usual, $\varphi^0=\neg\varphi$ and $\varphi^1=\varphi$.

Let $p(x_i :i<\omega)$ be the type that contains all these formulas. Every finite subset of $p(x_i :i<\omega)$ is satisfied by indiscernible sequences of arbitrary finite length. Therefore $p(x_i :i<\omega)$ is satisfied by an infinite indiscernible sequence of order-type $\omega$. It is standard to stretch this sequence to a sequence of order type $\mathbb R$ with the same EM-type.

P.S. Your definition is taken from this paper. Correct? It is a rather technical article which assumes a wealth of prerequisites.