Finite Shelah 2-rank implies stable. A combinatorial proof.

Question

If you are a model theorist: fix a formula $\varphi(x,y)$.

If you are a combinatorialist: fix an infinite graph $(V,E)$ and write $\varphi(a,b)$ for $(a,b)\in E$.

A $n$-ladder is a pair of sequences $a_1,\dots,a_n$ and $b_1,\dots,b_n$ such that

$$\varphi(a_i,b_j)\quad\Leftrightarrow\quad i\le j$$

A binary tree of height $n$ is a pair of sets $\{a_r : r\in 2^{<n}\}$ and $\{b_s:s\in2^n\}$ such that for all $r\subset s$

$$\varphi(a_r,b_s)\quad\Leftrightarrow\quad r^\frown 1 \subseteq s$$

It is easy to prove that

1. If there is a $2^n$-ladder then there is a binary tree of height $n$.

It is fundamental fact in model theory that

2. If there is a binary tree of infinite height then there is an infinitely long ladder.

I am interested in a finitary/effective version of 2 in the style of 1. It could sound more or less as follows

3. If there is a binary tree of height $O(2^{n})$ then there is $n$-ladder.

Answer 1

I think you're looking for Lemma 6.7.9 in Model Theory by Hodges.

If $\phi$ has ladder index $n$, then $\phi$ has branching index $<2^{n+2}-2$.

Here the ladder index is the maximal $n$ such that there is an $n$-ladder for $\phi$, and the branching index of $\phi$ is the maximal $n$ such that there is a binary tree of height $n$ for $\phi$.