One of the more forbidding definitions from “advanced model theory” is that of the DOP/NDOP dichotomy (NDOP is just the negation of DOP). Even among model theorists, this is one of the less-appreciated facets of Shelah’s stability theory: while concepts like “stable,” “superstable,” and “(non-)forking” permeate the field these days, my impression is that DOP remains a slightly mysterious phenomenon to many people.
In this post, I want to argue that there is an easy way to produce examples of DOP and that having (or not having) DOP has many interesting consequences for the saturated models of a theory. Meanwhile I will review the definition of DOP (assuming a basic familiarity with concepts from stable theories).
The definition of DOP
DOP (“Dimensional Order Property” — pronounced [IPA: dɒp], rhymes with “top”) was originally defined by Shelah in (6), and one can find may equivalent definitions in the literature (for example, see (1) and (5)). It is unfortunate that the “official” definition one often sees is a bit clumsy, when there is a more natural way to define it, given below (following the exposition of (3)).
Any theory has a-models, which are models in which every strong type over a finite subset of the model is realized. Being -saturated implies being an a-model which in turn implies being -saturated, and both implications are strict. The reader can mentally replace “a-model” with “-saturated model” in what follows and nothing much will change.
For a stable theory , there is a beautiful theory of a-models (developed by Shelah in (6)). In particular, over any subset of an a-model of , there is always an a-prime model over (that is, an a-model containing such that for any other a-model containing , there is an elementary embedding of into fixing pointwise). Furthermore, the a-prime model over is unique up to isomorphism over .
An important situation is when the a-prime model over is a-minimal over : this just means that there is no other a-model containing which is properly contained in . This is never true if and always true if is itself and a-model (in which case ).
Definition: A complete, stable, first-order theory has NDOP if whenever are a-models of such that , , and does not fork with over , then the a-prime model over is a-minimal over . “ has DOP” just means that does not have NDOP.
How to make your own example of DOP in one easy step
Most “simple” examples of stable theories that one can think of will not have DOP: the theory of an infinite set in the empty language, the theory of an algebraically closed field (in some fixed characteristic), any complete theory of an abelian group, any nonmultidimensional theory.
Let be any complete stable (first-order) theory in which there is an infinite definable group . That is, there are formulas in the language of , and , such that, in any model of , is an infinite group with the group operation interpreted by . I’ll call this group “” regardless of the underlying model .
Now we define another theory which has the same language as except with two new unary predicates and one new function symbol . The theory will say that the points satisfying form a model of , that the predicate is disjoint from , that maps surjectively onto such that each point in has infinitely many preimages, and that is the identity map when restricted to . Finally, the predicate will have no more definable structure than what is imposed by the projection map . More precisely, we can assume without loss of generality that the language of is relational (it has no function symbols), and then declare that all the basic relations in the language of hold only on tuples from . (Or if you know about multi-sorted logic: think of and as two sorts, being a sort for a model of , and being a structureless sort that merely projects onto .)
It’s routine to check that this is complete and stable, and if has elimination of quantifiers, then so will .
has DOP: To check that does not satisfy the definition of NDOP above, consider any three a-models such that does not fork with over , and furthermore the sets and are nonempty. Let be some a-prime model over . Pick points and . Then within , the set is an infinite set, call it . Now if is any infinite proper subset, we can take an a-prime model over , and it can be checked that is another a-prime model over but that does not contain any elements from . Therefore is not a-minimal.
In conclusion, it is easy make simple examples of DOP, and they are really not so exotic: take your favorite infinite definable group, then just cover each point in the group by a structureless infinite set. With this recipe we can see that DOP is logically independent of superstability, being totally transcendental, or indeed having finite Lascar rank. Also, the “tame” property of NDOP is not preserved under reducts. (To see this, start with which is NDOP and has an infinite definable group, then build an expansion of the theory constructed above in which there is a commuting system of definable bijections between the fibers .)
We can probably also conclude that DOP/NDOP is not too interesting if one only cares about the structure of definable sets (as in much of contemporary research in model theory). But DOP/NDOP has a lot to do with the structure of saturated models, as I will explain in the last section.
(Digression: It’s easy to see that is a “cover” of in the sense of my previous post, https://ffbandf.wordpress.com/2013/05/17/the-model-theory-of-covers/. It is not a finite cover, but it is a split cover.)
For Thomas the Doubter: DOP is a useful dividing line for the classifiablity of saturated models
(This part can be read independently of the previous parts, just to get some motivation for studying DOP.)
A long-standing open problem in stability theory is to prove a version of Shelah’s famous “Main Gap” theorem from (6) for a-models of countable theories. Briefly, the idea is this: try to define a set of “tame/wild” dichotomies for complete theories such that whenever is on the tame side of every dichotomy, then we have a nice way to decompose all a-models into trees of smaller a-models, providing a way to classify all a-models; and when falls on the wild side of any one of the dichotomies, then we have a “many-model theorem:” for any cardinal , there are nonisomorphic a-models of of cardinality (which is a priori the maximum number of nonisomorphic size- models that could have). On the other hand, the existence of sufficiently nice tree decompositions should give us a smaller upper bound on the number of nonisomorphic a-models.
Astonishingly, even decades after Shelah proved the Main Gap for non-a-models in (6), the Main Gap for a-models is still open. This is surprising because conventional wisdom in stability theory says that saturated models are more tractable than ordinary models: they are supposed to be the well-behaved models, without the irregularities or asymmetries caused by failing to realize types over small sets. One of the best attempts to resolve it was in Alejandro Hernandez’s Ph.D. thesis (2) (unfortunately never published), and some intriguing partial results were obtained recently by Laskowski and Shelah in the articles (3) and (4).
I’ll summarize some of the partial results that are known.
Theorem (Shelah, (6)): If is unstable, or stable with DOP, then it has “many a-models” ( nonisomorphic a-models of size for every ).
It is a fun exercise to try to verify the result above for the examples constructed in the previous section. The basic idea is that even in an a-model, one can choose the cardinalities of the fibers independently as varies among elements of , and in this way encode arbitrary linear orderings (indeed, arbitrary binary relations) within a-models. (This explains why it is the “Dimensional Order Property:” by making reference to “dimensions” (sizes of fibers, in the example), one can define arbitrary orderings.)
Theorem (Laskowski-Shelah, (3)) If is countable, stable, NDOP, and shallow, then all a-prime models over independent trees of a-models are a-minimal.
“Shallow”/“deep” is another Shelahian dichotomy: is deep if there is an infinite increasing elementary chain of a-models such that is orthogonal to any type over . In the result above, “independent trees” are trees where every branch is finite and each non-root node is independent over its predecessor from the collection of all the non-descendents of . The very definition of DOP implies that there is an obstacle to a-prime models over independent trees being minimal; the theorem says that for countable , there is only one other such obstacle, deepness.
We do not assume that each node of an independent tree is prime over its predecessor plus the realization of a regular type; this is one of the most startling gaps in our knowledge of stable, non-superstable theories:
Question: If is stable and is a stationary nonalgebraic type, is nonorthogonal to a regular type?
A key step in the Laskowski-Shelah result above is to first prove it for the special case of trees of height 1, using a little bit of descriptive set theory (!):
Theorem (Laskowski-Shelah, (3)): If is countable, stable, and NDOP, then for any collection of a-models which are independent over a common “root” a-model, any a-prime model over is a-minimal over .
Another recent result showing the unexpected power of NDOP:
Theorem (Laskowski-Shelah, (4)): If is countable, stable, nonsuperstable, NDOP, and shallow, then there is an “abelian group witness to non-superstability:” that is, a descending chain of definable abelian groups such that is always infinite and is connected with regular generic type.
I believe even the following is still open (it was said to be so in (2)):
Question: If is countable, stable, and deep, then does necessarily have many nonisomorphic a-models?
Finally, here is a question which is so speculative that people seem reluctant to even conjecture an answer, although it seems to be on everyone’s mind:
Question: For countable stable theories, are there any tame/wild dichotomies that are relevant to the classifiablity of a-models other than “deep/shallow” and “DOP/NDOP”? That is, if a theory is countable, shallow, and NDOP, then will it necessarily have fewer than the maximum number of a-models?
Note that there have been other dichotomies proposed, such as DIDIP/NDIDIP, and it has been shown that DIDIP implies many a-models; but a result of Laskowski and Shelah from (3) show that for countable stable theories, NDOP plus shallow implies NDIDIP. Furthermore, the OTOP/NOTOP dichotomy is irrelevant for a-models. Hernandez in (2) posited other hypothetical dichotomies for a-models, but as far as I know it was never determined whether or not his proposed new properties are logically independent of the other previously-defined dichotomies.
- Bouscaren, Elisabeth. “DOP and n-tuples of models,” Logic Colloquium’88: Proceedings of the Colloquium Held in Padova, Italy August 22-31, 1988. North-Holland, 1989.
- Hernandez, Alejandro, “-saturated Models of Stable Theories,” Doctoral dissertation for the University of California, Berkeley, 1992.
- Michael C. Laskowski and S. Shelah, “Decompositions of saturated models of stable theories,” Fundamenta Mathematicae, 191 (2006), 95–124, http://www2.math.umd.edu/~laskow//Pubs/satstable.pdf
- Michael C. Laskowski and S. Shelah, “A trichotomy for countable, stable, unsuperstable theories,” Transactions of the AMS, 363 (2011), 1619-1629, http://www2.math.umd.edu/~laskow//Pubs/laskowskishelah.pdf
- Anand Pillay, Geometric Stability Theory, Oxford University Press, 1996.
- S. Shelah, Classification Theory (revised edition), North Holland, Amsterdam, 1990.
It’s nice to finally learn the definition 🙂
I think it is not so surprising that people are not familiar with this property today. In a way in the first-order setting unstable theories are at the center of attention, where classifying models is quite hopeless — one tries to be able to say something at least about types. Forking is still a meaningful technical tool, and stability arises more in the local form, as some stable relation in an unstable theory.
A couple of comments/questions:
I don’t understand the example: nothing seems to prevent us from naming an arbitrary model by , and there are definitely examples of stable theories in which naming some submodel destroys stability. Perhaps you mean adding new sorts?
Also, how do you know that there are as wanted?
“This is surprising because conventional wisdom in stability theory says that saturated models are more tractable than ordinary models”.
In fact, how does one normally prove many a-models from some non-structure? I think the usual technique of Skolemizing something combinatorial like linear orders or trees does not normally allow to produce models of saturation larger that , but I guess it still works for realizing strong types over finite sets?
Can you give a quick idea of how to encode linear orders with sizes of fibers?
Typo: the index of in .
“Question: If T is stable and p is a stationary nonalgebraic type, is p nonorthogonal to a regular type?”
It is very surprising that this is not known!
Who should we blame for these acronyms? 🙂
@Artem: Shelah does, in fact, have methods to produce many models of arbitrary degrees of saturation in unstable theories, using a somewhat strange notion of isolation. The relevant reference is Theorem VIII.3.2 of his Classification Theory.
Thanks for the comments.
As for the example I gave, let me see if I can answer your questions:
“What prevents us from naming an arbitrary model by P1?” Well, I in the definition of NDOP I should have said that M_0 was an *elementary* submodel of M_1 and M_2. Blame the usual convention in “classical stability theory” of Skolemizing the language (since here we only care about models, not definable sets…) Was this your concern?
“How do you know there are a, b as wanted?” Let’s just pick the M_1 and M_2 to have larger interpretations of the group G (I will edit the post to make that clearer).
Not sure who is responsible for the acronyms… but actually I kind of like DIDIP. And maybe we should replace “stable” with “NOP” (Not Order Property) 🙂
(The non-structure questions are a bit harder to answer, I will say something more about that later…)
No, my concern is the sentence “It’s routine to check that this is complete and stable”. I don’t quite see why the way you had defined ensures this. My point is that there are stable theories in which adding a predicate for a certain elementary submodel destroys stability. Now I don’t see why we can’t start with a model of such a theory (which without loss of generality defines a group) and expand it to a model of by taking to be that particular submodel naming which destroys stability.
@Artem: But the way I define the new theory T’, the predicate P_1 is *not* an elementary submodel! Really, one should think of models of T’ as having two disjoint sorts, P_1 and P_2 (for some reason I thought it would be better in my post to avoid talking about multi-sorted logic…). The sort of P_1 is a model of T, the sort of P_2 has no definable structure other than what is trivially induced by the “many-to-one” projection map pi from P_2 onto the group G. (I’ll edit the definition of T’ in the post now to explain this, since I see that I didn’t explain clearly enough what I had in mind.)
Now unless I am missing something silly, there should be no way to define an infinite linear ordering in either of the sorts P_1 or P_2, unless there was already a way to define an ordering in the original theory T… Basically, if the theory T has q.e., then T’ will have q.e. as well, and then it’s not hard to check what I’m claiming.
Now it’s clear, thanks.