Demystifying DOP

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 T has a-models, which are models in which every strong type over a finite subset of the model is realized. Being \aleph_1-saturated implies being an a-model which in turn implies being \aleph_0-saturated, and both implications are strict. The reader can mentally replace “a-model” with “\aleph_1-saturated model” in what follows and nothing much will change.

For a stable theory T, there is a beautiful theory of a-models (developed by Shelah in (6)). In particular, over any subset X of an a-model M of T, there is always an a-prime model over X (that is, an  a-model N containing X such that for any other a-model N' containing X, there is an elementary embedding of N into N' fixing X pointwise). Furthermore, the a-prime model over X is unique up to isomorphism over X.

An important situation is when the a-prime model M over X is a-minimal over X: this just means that there is no other a-model containing X which is properly contained in M. This is never true if X = \emptyset and always true if X is itself and a-model (in which case M = X).

Definition: A complete, stable, first-order theory T has NDOP if whenever M_0, M_1, M_2 are a-models of T such that M_0 \prec M_1, M_0 \prec M_2, and M_1 does not fork with M_2 over M_0, then the a-prime model over M_1 \cup M_2 is a-minimal over M_1 \cup M_2. “T has DOP” just means that T 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 T be any complete stable (first-order) theory in which there is an infinite definable group G. That is, there are formulas in the language of T, \varphi(x) and \psi(x,y), such that, in any model M of T, \varphi(M) is an infinite group with the group operation interpreted by \psi(M \times M). I’ll call this group “G” regardless of the underlying model M.

Now we define another theory T' which has the same language as T except with two new unary predicates P_1, P_2 and one new function symbol \pi. The theory T' will say that the points satisfying P_1 form a model of T, that the predicate P_2 is disjoint from P_1, that \pi maps P_2 surjectively onto G such that each point in G has infinitely many preimages, and that \pi is the identity map when restricted to P_1. Finally, the predicate P_2 will have no more definable structure than what is imposed by the projection map \pi. More precisely, we can assume without loss of generality that the language of T is relational (it has no function symbols), and then declare that all the basic relations in the language of T hold only on tuples from P_1. (Or if you know about multi-sorted logic: think of P_1 and P_2 as two sorts, P_1 being a sort for a model of T, and P_2 being a structureless sort that merely projects onto G.)

It’s routine to check that this T' is complete and stable, and if T has elimination of quantifiers, then so will T'.

T' has DOP: To check that T' does not satisfy the definition of NDOP above, consider any three a-models M_0 \subseteq M_1, M_2 such that M_1 does not fork with M_2 over M_0, and furthermore the sets G(M_1) \setminus G(M_0) and G(M_2) \setminus G(M_0) are nonempty. Let M be some a-prime model over M_1 \cup M_2. Pick points a \in G(M_1) \setminus G(M_0) and b \in G(M_2) \setminus G(M_0). Then within M, the set \pi^{-1}(a \cdot b) is an infinite set, call it I. Now if I' \subseteq I is any infinite proper subset, we can take an a-prime model M' over M_1 \cup M_2 \cup I', and it can be checked that M' is another a-prime model over M_1 \cup M_2 but that M' does not contain any elements from I \setminus I'. Therefore M 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 T which is NDOP and has an infinite definable group, then build an expansion T'' of the theory T' constructed above in which there is a commuting system of definable bijections between the fibers \pi^{-1}(a).)

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 T' is a “cover” of T 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 T such that whenever T 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 T falls on the wild side of any one of the dichotomies, then we have a “many-model theorem:” for any cardinal \kappa \geq |T|, there are 2^{\kappa} nonisomorphic a-models of T of cardinality \kappa (which is a priori the maximum number of nonisomorphic size-\kappa models that T 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 T is unstable, or stable with DOP, then it has “many a-models” (2^{\kappa} nonisomorphic a-models of size \kappa for every \kappa \geq |T|).

It is a fun exercise to try to verify the result above for the examples T' constructed in the previous section. The basic idea is that even in an a-model, one can choose the cardinalities of the fibers \pi^{-1}(a) independently as a varies among elements of G, 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 T 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: T is deep if there is an infinite increasing elementary chain M_0 \prec M_1 \prec \ldots of a-models such that \textup{tp}(M_{n+1} / M_n) is orthogonal to any type over M_{n-1}. In the result above, “independent trees” are trees where every branch is finite and each non-root node M is independent over its predecessor from the collection of all the non-descendents of M. 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 T, 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 T is stable and p is a stationary nonalgebraic type, is p 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 T is countable, stable, and NDOP, then for any collection of a-models \mathcal{T} = \langle M_\alpha : \alpha < \kappa \rangle which are independent over a common “root” a-model, any a-prime model over \mathcal{T} is a-minimal over \mathcal{T}.

Another recent result showing the unexpected power of NDOP:

Theorem (Laskowski-Shelah, (4)): If T is countable, stable, nonsuperstable, NDOP, and shallow, then there is an “abelian group witness to non-superstability:” that is, a descending chain \langle G_n : n < \omega \rangle of definable abelian groups such that [G_n : G_{n+1}] is always infinite and \bigcap_{n < \omega} G_n is connected with regular generic type.

I believe even the following is still open (it was said to be so in (2)):

Question: If T is countable, stable, and deep, then does T 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.

References

  1. 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.
  2. Hernandez, Alejandro, “\omega_1-saturated Models of Stable Theories,” Doctoral dissertation for the University of California, Berkeley, 1992.
  3. 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
  4. Michael C. Laskowski and S. Shelah, “A trichotomy for countable, stable, unsuperstable theories,” Transactions of the AMS363 (2011), 1619-1629, http://www2.math.umd.edu/~laskow//Pubs/laskowskishelah.pdf
  5. Anand Pillay, Geometric Stability Theory, Oxford University Press, 1996.
  6. S. Shelah, Classification Theory (revised edition), North Holland, Amsterdam, 1990.

7 responses to “Demystifying DOP

  1. 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 P_1, 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 a,b 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 \omega, 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 G_{n+1} in G_n.

    “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!

    “DIDIP/NDIDIP”
    Who should we blame for these acronyms? 🙂

    • John Goodrick

      @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.

  2. John Goodrick

    Hi Artem,

    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) 🙂

  3. John Goodrick

    (The non-structure questions are a bit harder to answer, I will say something more about that later…)

  4. No, my concern is the sentence “It’s routine to check that this T' is complete and stable”. I don’t quite see why the way you had defined T' 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 T (which without loss of generality defines a group) and expand it to a model of T' by taking P_1 to be that particular submodel naming which destroys stability.

    • John Goodrick

      @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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s