# The "tree property" and dividing types

Recall that a family of formulas $$\{\varphi_i(v)\}_{i\in I}$$ is said to be "$$k$$-inconsistent" if every conjunction of $$k$$ distinct members of the family is inconsistent. We say that an $$\mathcal{L}$$-formula $$\varphi(v,w)$$ has the "tree property" for $$k$$ if there is a collection of parameters $$\{b_s:\emptyset\neq s\in\omega^{<\omega}\}$$, where $$\omega^{<\omega}=\bigcup_{n\in\omega}\omega^n$$, such that (a) $$\{\varphi(v,b_{si})\}_{i\in\omega}$$ is $$k$$-inconsistent for every $$s\in\omega^{<\omega}$$, and (b) $$\{\varphi(v,b_s):\emptyset\neq s\subseteq\sigma\}$$ is consistent for every $$\sigma\in\omega^\omega$$. In other words, the children of every node of the tree are $$k$$-inconsistent, and every path through the tree cuts out a consistent family of formulas. A theory $$T$$ is simple if there is no formula with the tree property, modulo $$T$$.

I'm having a bit of trouble with proposition 7.2.5. in Tent and Ziegler, which proves that $$T$$ is simple if and only if there is a cardinal $$\kappa$$ such that, for all models $$M$$ and all $$p\in S_n(M)$$, there is some $$X\subseteq M$$, of size $$\leqslant\kappa$$, such that $$p$$ does not divide over $$X$$. I'm having trouble in particular with their proof of the backwards direction; I've copied it verbatim below. We work in a monster model $$\mathfrak{C}$$.

If $$\varphi(v,w)$$ has the tree property, there are $$\varphi$$-$$k$$ dividing sequences $$(\varphi(v,b_\alpha))_{\alpha<\kappa^+}$$. It is easy to construct an ascending sequence of models $$(M_\alpha)_{\alpha<\kappa^+}$$ such that each $$\varphi(v,b_\alpha)$$ divides over $$M_\alpha$$ and such that $$b_\beta\in M_\alpha$$ for all $$\beta<\alpha$$. Extend the collection $$\{\varphi(v,b_\alpha)\}_{\alpha<\kappa^+}$$ to a type $$p(v)\in S(M)$$, where $$M=\bigcup_{\alpha<\kappa^+}M_\alpha$$. Then $$p$$ divides over each $$M_\alpha$$.

(A "$$\varphi$$-$$k$$" dividing sequence over $$X$$, of length $$\lambda$$, is a consistent family $$(\varphi(v,b_\alpha))_{\alpha<\lambda}$$ such that each $$\varphi(v,b_\alpha)$$ divides over $$X\cup\{b_\beta\}_{\beta<\alpha}$$ with respect to $$k$$. Tent and Ziegler have proved that every formula with the tree property for $$k$$ has a $$\varphi$$-$$k$$ dividing sequence over any parameter set, of any length.)

Unfortunately the construction of the models is unclear to me. We seem to have two choices; the naive approach is to choose a single dividing sequence $$(\varphi(v,b_\alpha))_{\alpha<\kappa^+}$$ at the onset, say over $$\emptyset$$, and then try to construct the desired models with this dividing sequence fixed. I run into problems with this approach, however. Constructing $$M_0$$ is fine; we can use, eg, exercise 7.1.1. of Tent and Ziegler to find a model $$M_0$$ such that $$\varphi(v,b_0)$$ divides over $$M_0$$. (This is just an application of the "standard lemma" on indiscernible sequences.) However, I struggle with the higher stages:

For simplicity, I focus on constructing $$M_1$$, which is representative of the problem I'm having in the general case too. We know that $$\varphi(v,b_1)$$ divides over $$b_0$$, and that $$\varphi(v,b_0)$$ divides over $$M_0$$. If we could show that $$\varphi(v,b_1)$$ divides over $$\{b_0\}\cup M_0$$, we would then be done; we could find $$\mathcal{I}$$ an $$M_0\cup\{b_0\}$$-indiscernible sequence such that $$b_1\in\mathcal{I}$$ and $$(\varphi(v,b))_{b\in\mathcal{I}}$$ is $$k$$-inconsistent, and then use (the argument of) exercise 7.1.1. to find a model $$M_1\succeq M_0$$ such that $$b_1\in M_1$$ and such that $$\mathcal{I}$$ remains indiscernible over $$M_1$$. Then $$\varphi(v,b_1)$$ would divide over $$M_1$$, witnessed by $$\mathcal{I}$$, as desired. However, I'm not convinced that $$\varphi(v,b_1)$$ will divide over $$\{b_0\}\cup M_0$$ in general... to show such a thing, we'd want to use a sort of transitivity property of the following shape:

If $$\varphi(v,b)$$ divides over $$\{a\}$$, and $$\varphi(v,a)$$ divides over $$X$$, then $$\varphi(v,b)$$ divides over $$X\cup\{a\}$$. (Subject to some appropriate conditions on $$X$$, $$a$$, and $$b$$, eg that $$\varphi(v,a)\wedge\varphi(v,b)$$ is consistent.)

However, this is of different form than all the transitivity properties of dividing that we've proved so far; for instance, in exercise 7.1.7. we showed that

If $$\operatorname{tp}(a/X\cup\{b\})$$ does not divide over $$X$$, and $$\varphi(v,b)$$ divides over $$X$$, then $$\varphi(v,b)$$ divides over $$X\cup\{a\}$$.

Most transitivity properties have been of this form, obtaining a conclusion of dividing with one hypothesis of dividing and one hypothesis of non-dividing. As far as I can tell, this is of fundamentally different shape than obtaining a conclusion of dividing from two hypotheses of dividing, so I'm not even convinced the desired result is true. (My attempts to prove it, even in the specific case above, have not led anywhere, although I haven't been able to come up with a counterexample either.)

So, this approach doesn't appear fruitful to me. The second approach is to construct not only the models but also the parameters $$(b_\alpha)_{\alpha<\kappa^+}$$ inductively. However, we seem to run into a different problem here; in this approach, for the rest of Tent and Ziegler's argument to work, we need to ensure that $$\varphi(v,b_\alpha)$$ is consistent with $$\{\varphi(v,b_\beta)\}_{\beta<\alpha}$$ at each stage, and I don't see how to do this. For simplicity, again suppose that we have constructed $$M_0$$ and $$b_0$$ as above and are trying to construct $$M_1$$ and $$b_1$$. We can find a $$\varphi$$-$$k$$ dividing sequence over $$M_0\cup\{b_0\}$$; call it $$(a_\alpha)_{\alpha<\kappa^+}$$. Unfortunately, this alone is of no help, since there is no guarantee that $$\{\varphi(v,b_0),\varphi(v,a_\gamma)\}$$ is consistent, for any $$\gamma$$.

So I'm at a bit of a loss. Tent and Ziegler do say this construction should be easy, so I'm wondering if I'm overthinking something or missing something obvious; any insight (or hints!) would be appreciated. Once we've actually constructed the models, then I don't have any trouble with finishing the argument. Indeed, if $$X\subseteq M$$ is such that $$|X|\leqslant \kappa$$, then for each $$x\in X$$ let $$\alpha(x)$$ be minimal such that $$x\in M_{\alpha(x)}$$. Then $$\gamma:=\bigcup_{x\in X}\alpha(x)$$ is a union of $$\leqslant\kappa$$ sets, each of cardinality $$\leqslant\kappa$$, so $$\gamma<\kappa^+$$. Then we have $$X\subseteq M_\gamma$$, and so, since $$p\ni\varphi(v,b_\gamma)$$ divides over $$M_\gamma$$, it divides over $$X$$ as well.

To be clear, the statement you want to prove is:

If $$T$$ has the tree property, then for every cardinal $$\kappa$$, there is model $$M$$ and a type $$p\in S(M)$$ such that for all $$X\subseteq M$$ with $$|X|\leq \kappa$$, $$p$$ divides over $$X$$.

Note that if we drop the condition that $$M$$ is a model, the proof is easy, given that we know that the tree property gives rise to dividing sequences. If $$\varphi(x,y)$$ has the tree property, then there is a $$\varphi$$-$$k$$-dividing sequence $$(\varphi(x,b_\alpha))_{\alpha<\kappa^+}$$. Let $$B = \{b_\alpha\mid \alpha<\kappa^+\}$$. By the definition of dividing sequence, $$\{\varphi(x,b_\alpha)\mid \alpha<\kappa^+\}$$ is consistent, so we can take $$p\in S(B)$$ to be any completion of this partial type. Now for any $$X\subseteq B$$ with $$|X|\leq \kappa$$, since $$\kappa^+$$ is regular there is some $$\beta<\kappa^+$$ such that $$X\subseteq B_\beta = \{b_\alpha\mid \alpha<\beta\}$$. By the definition of dividing sequence, $$\varphi(x,b_\beta)\in p$$ divides over $$B_\beta$$, and hence over $$X$$, so $$p$$ divides over $$X$$.

Now we want to "upgrade" $$B$$ to a model. There's a standard trick for turning behavior over arbitrary sets into behavior over models: Skolemization. It's entirely possible that there's a straightforward way to carry out the proof in T&Z without Skolemizing, but I agree with you that it's not obvious.

Let $$\mathfrak{C}^+$$ be an expansion of the monster model $$\mathfrak{C}$$ by Skolem functions, let $$L^+$$ be the expanded language, and let $$T^+$$ be $$\mathrm{Th}_{L^+}(\mathfrak{C}^+)$$. Then $$T^+$$ has the tree property, witnessed by the same $$L$$-formula $$\varphi(x;y)$$ and the same tree.

[Aside: This is one of the benefits of the tree property characterization of (non)-simplicity - it is "purely local" in the sense that it only depends on the behavior of a single formula $$\varphi(x,y)$$, so it is preserved under expansions and reducts which contain $$\varphi$$. Notice that, in contrast, it is not obvious that the existence of a $$\varphi$$-$$k$$-dividing chain is preserved under expansion, because an instance $$\varphi(x,b)$$ which divides over $$A$$ may no longer divide over $$A$$ after expanding the language. The same goes for characterizing (non)-stability by the order property, and many other properties in model theory.]

Now we carry out the proof above in $$T^+$$. We have an $$L$$-formula $$\varphi(x,y)$$ with the tree property, so there is a $$\varphi$$-$$k$$-dividing sequence $$(\varphi(x,b_\alpha))_{\alpha<\kappa^+}$$. Let $$M = \langle \{b_\alpha\mid \alpha<\kappa^+\}\rangle$$, the substructure of the monster generated by all the parameters in the sequence. Since $$T^+$$ has Skolem functions, $$M\models T^+$$. Similarly, for all $$\beta<\kappa^+$$, if we define $$M_\beta = \langle \{b_\alpha\mid \alpha<\beta\}\rangle$$, then $$M_\beta\models T^+$$. Note that $$M = \bigcup_{\beta<\kappa^+} M_\beta$$.

By the definition of dividing sequence, $$\{\varphi(x,b_\alpha)\mid \alpha<\kappa^+\}$$ is consistent, so we can take $$p\in S(M)$$ to be any completion of this partial type. Now for any $$X\subseteq M$$ with $$|X|\leq \kappa$$, since $$\kappa^+$$ is regular there is some $$\beta<\kappa^+$$ such that $$X\subseteq M_\beta$$. By the definition of dividing sequence, $$\varphi(x,b_\beta)\in p$$ divides over $$\{b_\alpha\mid \alpha<\beta\}$$, so it divides over $$M_\beta$$ (if a formula divides over $$A$$, then it also divides over $$\langle A \rangle$$) and hence over $$X$$, so $$p$$ divides over $$X$$.

It remains to show that the conclusion is preserved when we take the reduct back to $$L$$. The key thing to check is that if an $$L$$-formula divides over $$X$$ in $$\mathfrak{C}^+$$, then it divides over $$X$$ in $$\mathfrak{C}$$.

• Ahh, that's a very very nice argument, thank you; the use of Skolem functions for this purpose is a really good trick to remember for the future. Just to make sure, your last sentence doesn't rely on anything special about $\mathfrak{C}^+$, right? For any expansion $L\subseteq L^*$, if two tuples have the same $L^*$-type over $X$, then they will in particular have the same $L$-type over $X$, so the same witnesses of dividing will work in the reduct. Dec 17, 2020 at 16:53
• @AtticusStonestrom Yep, that's correct. Slogan: "Dividing is preserved under reduct (as long as the dividing formula is contained in the reduct language), but not necessarily under expansion." Dec 17, 2020 at 17:02