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, and
As usual we are in a very big and saturated monster model of a complete first-order theory .
Definition. A formula has if there is a tree of tuples and such that:
• is consistent for any
• is inconsistent for any mutually incomparable .
Otherwise we say that is , and is if every formula is.
Definition. A formula has if there is an array of tuples such that is -inconsistent for every and is consistent for any . Otherwise we say that is , and is 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. is simple if and only if it is both and .
These tree properties were introduced and studied by Shelah in  and . re-appeared on the scene after it arose in the work on forking and dividing in NIP theories in  and was studied further in  and . re-appears in . I will probably return to these in future postings.
2. On the hierarchy inside
We recall the definition of for 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 . A formula has if there are tuples such that:
- There is an infinite chain: for all
- There are no cycles of length : .
2. has if and only if it has .
4. By Shelah’s theorem we see that restricting to theories, the last 2 items coincide.
The following are standard examples showing that the hierarchy is strict for :
Example. [7, Claim 2.8]
1. The usual example of a theory which is not-simple and is the model companion of the theory of a parametrized family of equivalence relations with infinitely many infinite classes (see ).
2. For , let be the model completion of the theory of directed graphs (no self-loops or multiple edges) with no directed cycles of length . Then it has but not .
3. For odd , the model completion of the theory of graphs with no odd cycles of length , has but not .
4. Consider the model companion of a theory in the language saying:
- if then .
It eliminates quantifiers.
However, all these examples have .
(1) It is immediate that the formula has .
(2) Let . For we choose sequencese such that and for all , and these are the only edges around — it is possible as no directed cycles are created. Now for any , if there is , then we would have a directed cycle of length — a contradiction. On the other hand, given and there has to be an element as there are no directed cycles created. Thus has .
(3) and (4) Similar.
This naturally leads to the following question (which I originally asked in ):
Question: Is the hierarchy strict for theories? Note that the strictness of the implication is open even in general.
Even an example of a non-simple theory with and 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?
- 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
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?
Perhaps dichotomies given by nonforking spectra seem more in line with SOP_n – doesn’t Rudin-Keisler seem unrelated? Am I missing something crucial?
@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.
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.
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 - עולם
@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.
@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.