tree property

In this post I would like to popularize a certain question around Shelah’s classification theory of unstable (and even non-simple) theories.

1. Tree properties of the first and second kind, ${\mbox{NTP}_{1}}$ and ${\mbox{NTP}_{2}}$

As usual we are in a very big and saturated monster model ${\mathbb{M}}$ of a complete first-order theory ${T}$ .

Definition. A formula ${\phi(x,y)}$ has ${\mbox{TP}_{1}}$ if there is a tree ${\left(a_{\eta}\right)_{\eta\in\omega^{<\omega}}}$ of tuples and ${k\in\omega}$ such that:
• ${\left\{ \phi(x,a_{\eta|i})\right\} _{i\in\omega}}$ is consistent for any ${\eta\in\omega^{\omega}}$
• ${\left\{ \phi(x,a_{\eta_{i}})\right\} _{i<k}}$ is inconsistent for any mutually incomparable ${\eta_{0},...,\eta_{k-1}\in\omega^{<\omega}}$ .
Otherwise we say that ${\phi(x,y)}$ is ${\mbox{NTP}_{1}}$ , and ${T}$ is ${\mbox{NTP}_{1}}$ if every formula is.

Definition. A formula ${\phi(x,y)}$ has ${\mbox{TP}_{2}}$ if there is an array ${\left(a_{\alpha,i}\right)_{\alpha,i<\omega}}$ of tuples such that ${\left\{ \phi(x,a_{\alpha,i})\right\} _{i<\omega}}$ is ${2}$ -inconsistent for every ${\alpha<\omega}$ and ${\left\{ \phi(x,a_{\alpha,f(\alpha)})\right\} _{\alpha<\omega}}$ is consistent for any ${f:\,\omega\rightarrow\omega}$ . Otherwise we say that ${\phi(x,y)}$ is ${\mbox{NTP}_{2}}$ , and ${T}$ is ${\mbox{NTP}_{2}}$ if every formula is.

It is an easy exercise to see that each of this properties implies the usual tree property, that is the failure of simplicity. An important insight of Shelah is that failure of simplicity always occurs in one of these two explicit ways.

Theorem. ${T}$ is simple if and only if it is both ${\mbox{NTP}_{1}}$ and ${\mbox{NTP}_{2}}$ .

These tree properties were introduced and studied by Shelah in [1] and [2]. ${\mbox{NTP}_{2}}$ re-appeared on the scene after it arose in the work on forking and dividing in NIP theories in [3] and was studied further in [4] and [5]. ${\mbox{NTP}_{1}}$ re-appears in [6]. I will probably return to these in future postings.

2. On the ${\mbox{NSOP}_{n}}$ hierarchy inside ${\mbox{NTP}_{2}}$

We recall the definition of ${\mbox{SOP}_{n}}$ for ${n\geq2}$ from [7,Definition 2.5], another hierarchy introduced by Shelah in order to study non-simple theories without the strict order property:

Definition. 1. Let ${n\geq3}$ . A formula ${\phi\left(x,y\right)}$ has ${\mbox{SOP}_{n}}$ if there are tuples ${\left(a_{i}\right)_{i\in\omega}}$ such that:

There is an infinite chain: ${\models\phi\left(a_{i},a_{j}\right)}$ for all ${i<j<\omega}$
There are no cycles of length ${n}$ : ${\models\neg\exists x_{0}\ldots x_{n-1}\bigwedge_{j=i+1\left(\mod n\right)}\phi\left(x_{i},x_{j}\right)}$ .

2. ${\phi\left(x,y\right)}$ has ${\mbox{SOP}_{2}}$ if and only if it has ${\mbox{TP}_{1}}$ .
3. ${\mbox{SOP}\Rightarrow \mbox{SOP}_{n+1}\Rightarrow \mbox{SOP}_{n}\Rightarrow\ldots\Rightarrow\mbox{SOP}_{3}\Rightarrow\mbox{SOP}_{2}\Rightarrow \mbox{not simple}}$ .
4. By Shelah’s theorem we see that restricting to ${\mbox{NTP}_{2}}$ theories, the last 2 items coincide.

The following are standard examples showing that the ${\mbox{SOP}_{n}}$ hierarchy is strict for ${n\geq3}$ :

Example. [7, Claim 2.8]
1. The usual example of a theory which is not-simple and ${\mbox{NSOP}_{3}}$ is the model companion of the theory of a parametrized family of equivalence relations with infinitely many infinite classes (see [8]).
2. For ${n\geq3}$ , let ${T_{n}}$ be the model completion of the theory of directed graphs (no self-loops or multiple edges) with no directed cycles of length ${\leq n}$ . Then it has ${\mbox{SOP}_{n}}$ but not ${\mbox{SOP}_{n+1}}$ .
3. For odd ${n\geq3}$ , the model completion of the theory of graphs with no odd cycles of length ${\leq n}$ , has ${\mbox{SOP}_{n}}$ but not ${\mbox{SOP}_{n+1}}$ .
4. Consider the model companion of a theory in the language ${\left(<_{n,l}\right)_{l\leq n}}$ saying:

${x<_{n,m-1}y\rightarrow x<_{n,m}y}$ ,
${x<_{n,n}y}$ ,
${\neg\left(x<_{n,n-1}x\right)}$ ,
if ${l+k+1=m\leq n}$ then ${x<_{n,l}y\,\land\, y<_{n,k}z\,\rightarrow\, x<_{n,m}z}$ .

It eliminates quantifiers.

However, all these examples have ${\mbox{TP}_{2}}$ .
Proof:
(1) It is immediate that the formula ${E\left(x;y,i\right)}$ has ${\mbox{TP}_{2}}$ .
(2) Let ${\phi\left(x,y_{1}y_{2}\right)=xRy_{1}\land y_{2}Rx}$ . For ${i\in\omega}$ we choose sequencese ${\left(a_{i,j}b_{i,j}\right)_{j\in\omega}}$ such that ${\models R\left(a_{i,j},b_{i,k}\right)}$ and ${R\left(b_{i,j},a_{i,k}\right)}$ for all ${j<k\in\omega}$ , and these are the only edges around — it is possible as no directed cycles are created. Now for any ${i}$ , if there is ${c\models\phi\left(x,a_{i,0}b_{i,0}\right)\land\phi\left(x,a_{i,1}b_{i,1}\right)}$ , then we would have a directed cycle ${c,b_{i,0},a_{i,1}}$ of length ${3}$ — a contradiction. On the other hand, given ${i_{0}<\ldots<i_{n}}$ and ${j_{0},\ldots,j_{n}}$ there has to be an element ${a\models\bigwedge_{\alpha\leq n}\phi\left(x,a_{i_{\alpha},j_{\alpha}}b_{i_{\alpha},j_{\alpha}}\right)}$ as there are no directed cycles created. Thus ${\phi\left(x,y_{1}y_{2}\right)}$ has ${\mbox{TP}_{2}}$ .
(3) and (4) Similar.

This naturally leads to the following question (which I originally asked in [4]):

Question: Is the ${\mbox{SOP}_{n}}$ hierarchy strict for ${\mbox{NTP}_{2}}$ theories? Note that the strictness of the implication ${\mbox{SOP}_{3}\Rightarrow \mbox{SOP}_{2}}$ is open even in general.

Even an example of a non-simple theory with ${\mbox{NSOP}}$ and ${\mbox{NTP}_{2}}$ is missing. In [2, §7, Exercise 7.12] Shelah suggests an example of such a theory as an exercise. However, I couldn’t make sense of the suggested example. Perhaps someone else would?

References

Saharon Shelah, “Simple unstable theories”, Ann. Math. Logic, http://dx.doi.org/10.1016/0003-4843(80)90009-1
Saharon Shelah, “Classification theory and the number of nonisomorphic models”, North-Holland Publishing Co., 1990
Artem Chernikov and Itay Kaplan, “Forking and dividing in NTP2 theories”, J. Symbolic Logic, 2012
Artem Chernikov, “Theories without the tree property of the second kind”, http://arxiv.org/abs/1204.0832
Itai Ben Yaacov and Artem Chernikov, “An independence theorem for NTP2 theories”, arXiv:1207.0289
Byunghan Kim and Hyeung-Joon Kim, “Notions around tree property 1”, Annals of Pure and Applied Logic, 2011
Saharon Shelah, “Toward classifying unstable theories”, Ann. Pure Appl. Logic, 1996
Saharon Shelah and Alex Usvyatsov, “More on SOP1 and SOP2”, arXiv:math/0404178

Tag Archives: tree property

On the SOPn hierarchy inside NTP2

Recent Posts

Recent Comments

Archives

Set Theory Talks

tags

Meta