On the SOPn hierarchy inside NTP2

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

8 responses to “On the SOPn hierarchy inside NTP2”

John Goodrick | 15/04/2013 at 12:23 | Reply

I’ve always wondered (and maybe this could be good material for a future post), are there particular motivations for studying the SOP_n hierarchy, other than that we have the nice collection of examples you listed in this post? For example, my very naïve first questions would be: could this relate to other known dividing lines, e.g. Rudin-Keisler order or dichotomies given by nonforking spectra?
Andrés Villaveces | 15/04/2013 at 14:49 | Reply

Perhaps dichotomies given by nonforking spectra seem more in line with SOP_n – doesn’t Rudin-Keisler seem unrelated? Am I missing something crucial?
John Goodrick | 16/04/2013 at 08:27 | Reply

@Andrés: No, I don’t think you’re missing anything I’m not seeing, my first comment was hasty and, as I said, very naïve!

In fact, Rudin-Keiser can’t have much to do with the SOP_n hierarchy, since SOP_3 is already known to imply maximality in the RK-ordering; I guess the only hope would be that the dividing line between SOP_2 and SOP_3, if it is indeed strict, might somehow be related.

Actually there is some discussion of this in Malliaris and Shelah, “Constructing regular ultrafilters from a model-theoretic point of view” (http://arxiv.org/pdf/1204.1481v1.pdf): see in particular Theorem F and Remark 4.1 there.
Artem Chernikov | 16/04/2013 at 10:21 | Reply

Yes, SOP_n for large n has nothing to do with Keisler order, while the small n’s might have smth to do with it, as well as with existence of universal models (in a certain sense). In fact I’m not sure what properties might characterize SOP_n for large n, maybe some weak forms of amalgamation. For example, it is known that SOP_2 implies failure of the usual independence theorem (like in simple theories). Now, there are weaker amalgamation statements known to hold in larger contexts, maybe they have something to do with it. Anyway, I personally think that SOP_2=TP1 is the most important dividing line there.

Concerning the non-forking spectrum of a theory, I think it is orthogonal to its SOP_n complexity. Because of the one hand we have the random graph, which is simple (thus NSOP_n for all n), but its non-forking spectrum is maximal f_T(k,l)=2^l. On the other hand, dense linear order is SOP_n for all n, but its non-forking spectrum is bounded and quite small – f_T(k,l)=dedk. Of course, to justify my orthogonality claim fully one would have to show that all pairs of the form (SOP_n complexity,Non-forking spectrum) which make sense are consistent. The standard examples – triangle free graphs, etc, have the same maximal spectrum as the random graph. I might write a post about non-forking spectra and some questions around it.
Andrés Villaveces | 17/04/2013 at 23:14 | Reply

But your two “prototypical situations” for non-forking spectrum (random graph, etc. on the one hand, DLO on the other hand) seem so far to follow the NSOP_n/SOP_n divide… do you have other examples for your claim of orthogonality of the two complexities?
Pingback: Un seminario tri-direccional | avn va - עולם
Gabe Conant | 28/05/2013 at 23:51 | Reply

@Artem. Following your recommendation, I also tried to make sense of Shelah’s 7.12 example. As described, I believe he has not defined a complete theory. It also doesn’t have quantifier elimination in the given language. I tried some guesses at how to complete the theory, but they all either added TP2 or made it simple. I haven’t looked back at it in a while, but I still think from time to time that I would like to know what he had in mind with this example.
Artem Chernikov | 29/05/2013 at 07:39 | Reply

@John: In fact it seems that already SOP_2=TP_1 implies maximality in the Keisler’s order (http://arxiv.org/abs/1208.5424).

@Andres: Well, these are just examples where one function is maximal and the other one is minimal, both ways. Showing that they are truly orthogonal would require a lot of examples, which I think do exist, but I’m not quite motivated to look at it.

@Gabe: In fact I had mentioned this question to Saharon once, but nothing followed, so I guess it could well just be a mistake.

On the SOPn hierarchy inside NTP2

8 responses to “On the SOPn hierarchy inside NTP2”

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Set Theory Talks

tags

Meta

On the SOPn hierarchy inside NTP2

Share this:

Like this:

Related

8 responses to “On the SOPn hierarchy inside NTP2”

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Set Theory Talks

tags

Meta