SOPn | fff

Tag Archives: SOPn

Some counterexamples for forking, dividing, invariance

Posted on 15/04/2013 by Artem Chernikov | Leave a comment

At the end of my paper with Itay Kaplan “Forking and dividing in NTP2 theories” we had asked several questions, admittedly without giving them much thought. Since 2008 when the paper went in circulation, some people had actually shown interest in those questions. By now two of them are known to have negative answers, one due to Gabriel Conant and one by myself, with very easy examples. I’d like to have them written down for a reference somewhere, so I’ve thought this might be an appropriate place.

Question 1. (rephrased as more elaborate latex is not available here): Is it true that in a simple theory, every type has a global Lascar-invariant extension.

I recall that a complete global type ${p\left(x\right)\in S\left(\mathbb{M}\right)}$ is Lascar-invariant over a small set ${A}$ if whenever ${\phi\left(x,a\right)\in p}$ and ${b}$ has the same Lascar strong type over ${A}$ as ${a}$ , then ${\phi\left(x,b\right)\in p}$ . Having the same Lascar strong type means that ${a}$ is equivalent to ${b}$ with respect to every equivalence relation with boundedly many classes which is ${\mbox{Aut}\left(\mathbb{M}/A\right)}$ -invariant.

This property is true in the random graph, for example – any type can be extended to a global one without adding any new edges. This is also true in any extensible NIP theory, say in any stalbe theory, any ${o}$ -minimal theory (e.g. real closed fields) or any ${C}$ -minimal theory (e.g. algebraically closed valued fields), as well as in any theory with definable Skolem functions (e.g. ${p}$ -adics). A theory is extensible if every type does not fork over its domain. However, the crucial point is that this property need not be preserved in reducts of the theory, which immediately gives an easy simple counterexample.

Example. Let ${T}$ be the reduct of the random graph given by the ternary relation ${R(x,y,z)}$ which holds if and only if ${x\neq y\neq z}$ and the number of edges between vertices in the set ${\left\{ x,y,z\right\} }$ is odd.

Claim.

${T}$ is supersimple of ${SU}$ -rank ${1}$ . Thus, Lascar strong type is determined by the strong type.
For any set ${A}$ , ${\mbox{acl}(A)=A}$ .
All pairs of different elements have the same type over ${\emptyset}$ .
Let ${M\models T}$ and ${p\in S(M)}$ . Then ${p}$ is not Lascar-invariant over ${\emptyset}$ .

Proof: (1) is because ${T}$ is definable on the set of singletons in the random graph, which is supersimple of ${SU}$ -rank 1. Now it is a well-known fact that Lascar strong type is determined by the strong type in supersimple theories.

(2) is easy to see, and (3) is by back-and-forth.

(4) Assume ${p}$ is Lascar-invariant over ${\emptyset}$ , thus invariant over it by (1) and (2). Let ${a\models p}$ , then by (3) either ${\models R(a,b,c)}$ for all ${b\neq c\in M}$ or ${\models\neg R(a,b,c)}$ for all ${b\ne c\in M}$ . In the first case, let ${b\neq c\neq d\in M}$ satisfy ${\neg R(b,c,d)}$ . Then it is easy to see that ${\not\models R(a,b,c)\land R(a,c,d)\land R(a,b,d)}$ — a contradiction. In the other case, take ${b,c,d}$ satisfying ${R(b,c,d)}$ and check that ${\not\models\neg R(a,b,c)\land\neg R(a,c,d)\land\neg R(a,b,d)}$ — a contradiction again. $\Box$

Thus, by (4) the unique type over the empty set has no global Lascar-invariant extension.

There are various modifications of the question which still make sense, and also one can ask if this property holds in particular algebraic structures of interest. I have some things to say about it, but not this time.

Question 2. “Can similar results be proved for NSOP theories?”

Here “similar results” refers to the main result of the paper, that is that in an NTP2 theory a formula divides over an extension base if and only if it forks over it. Now, Gabe shows in “Forking and dividing in Henson graphs” that it is not the case for the triangle-free random graph. From my own experience, triangle-free random graph seems to demonstrate the failure of all the phenomena which holds for NTP2 theories.

Example. Let ${T}$ be the theory of the triangle-free random graph, and let ${b_{0}\neq b_{1}\neq b_{2}\neq b_{3}}$ . Let ${\phi\left(x,b_{0}b_{1}b_{2}b_{3}\right)=\bigvee_{i<j<4}\left(xRb_{i}\land xRb_{j}\right)}$ .

Claim.

${xRb_{i}\land xRb_{j}}$ divides over ${\emptyset}$ for any ${i<j}$ .
${\phi\left(x,b_{0}b_{1}b_{2}b_{3}\right)}$ does not divide over ${\emptyset}$ .
${\emptyset}$ is an extension base.
${T}$ is ${\mbox{SOP}_{3}}$ but ${\mbox{NSOP}_{4}}$ .
However, forking and dividing are the same for complete types.

See Gabe’s article for details and for the general case of Henson graphs.

Still the following part of the question remains open:

Problem.

Is forking=dividing for complete types?
Is forking equal to dividing for formulas in NTP1 over models?

On the SOPn hierarchy inside NTP2

Posted on 14/04/2013 by Artem Chernikov | 8 comments

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 Comments

Posted in General, Model Theory

Tagged Artem Chernikov, classification theory, NTP1, NTP2, open question, simple theories, SOPn, tree property