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:
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