Category Archives: General

Link

Map of the Universe

I just stumbled across a very neat map of the known (model-theoretic) universe, created by UIC graduate student Gabriel Conant:

http://www.forkinganddividing.com/

I often used to dream of having some kind of reference for “Counterexamples in Model Theory,” and I’m really glad that something like this has finally been made.

Advertisements

Éric Jaligot, 1972 – 2013

Eric Jaligot

Page à la mémoire d’Eric Jaligot

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.

The model theory of covers

The aim of this post is to briefly summarize some of what is known (and the many things that remain unknown) about the model theory of covers (which includes finite covers and affine covers). Though the motivation comes from questions in “pure model theory”, there are intriguing connections with algebra and a lot of nice but surprisingly resistant open questions which I hope will be interesting to a wide audience.

Covers to understand totally categorical theories

A countable first-order theory T is totally categorical if for every infinite cardinal \kappa, T has precisely one model of cardinality \kappa up to isomorphism.

Early in the study of stable theories, some amazing results were proved about these theories, such as:

Theorem (Cherlin-Harrington-Lachlan) No totally categorical theory is finitely axiomatizable.

Theorem (Hrushovski) (a) Any totally categorical theory is “quasifinitely axiomatizable” (axiomatizable by a finite number of first-order sentences plus a finite number of sentences of the form “for every \overline{a}, \varphi(\overline{x}; \overline{a}) is infinite”).

(b) There are only countably many totally categorical theories (modulo bi-interpretability).

In fact, (a) and (b) above are true of \omega-stable, \omega-categorical theories in general.

In modern terminology (some of it explained below), here is what is going on in a totally categorical theory T: in T^{eq}, there is an \emptyset-definable strictly minimal set D (that is, strongly minimal, plus there are no nontrivial definable equivalence relations with domain D). The universe of any model M \models T can be constructed in finitely many stages as D = D_0 \subseteq D_1 \subseteq \ldots D_n, where each D_{i+1} is an \emptyset-definable set in T^{eq} which is a finite or affine cover of D_i and M is in \textup{dcl}(M_n). Furthermore, the full definable structure on D is either (i) completely trivial (the “disintegrated case”) or (ii) that of an infinite-dimensional projective space over a finite field (the “modular case”).

The definition of a cover

The dream is to develop a nice model theory for “covers of structures” \pi: M \rightarrow N, where \pi is a map between two multi-sorted structures M and N. The idea is that M and N may have completely different languages (indeed, that is the interesting case), but \pi should still “preserve definable structure”.

The first challenge is just to give a sufficiently general and useful definition of “cover”, which I will now try to do (this is essentially a variation of the definition of Evans from (3)).

Definition: Call a function \pi : M \rightarrow N a cover if it satisfies:

0. N is in the definable closure of the image of \pi;

1. The equivalence relation on M given by being in the same fiber of \pi is 0-definable in M;

2. The 0-definable n-ary relations on N are precisely the projections via \pi of the 0-definable relations on M; and

3. (“Stable embeddedness”) Every 0-definable family of definable sets \left\{R(\overline{x}, \overline{a}) : \overline{a} \in M\right\} in M projects via \pi onto a 0-definable family of definable sets in N.

Question: Do properties 0-3 define a good, sufficiently general notion of “cover”? Condition 0 probably isn’t logically necessary, given condition 2.

Definition: Call a cover finite if the fibers \pi^{-1}(a) are all finite. (“Locally finite” may be more accurate, but “finite cover” is now standard for this meaning.) Call a cover affine if there is a definable family (G_a : \varphi(a)) of vector spaces in N over a fixed finite field and definable regular actions of each G_a on the corresponding fiber \pi^{-1}(a).

Now given a definable family (G_a : \varphi(a)) of groups in some structure N, we would like to know what are the various ways to build a cover \pi: M \rightarrow N where the G_a act on the fibers.

There is one fairly obvious way to do this which works for any N, which is to build a split cover of N with structure groups (G_a : \varphi(a)) (sometimes in the work of Evans, this is called a principal cover). The idea is the following: M will be a structure containing N plus one new sort, call it P, which is a disjoint union of the groups G_a for each a \in \varphi(N), without the group structure. There are basic function symbols for the natural projection \pi : P \rightarrow \varphi(N) and for the left-regular action of each G_a on the corresponding fiber \pi^{-1}(a). That’s it; we add no other basic definable relations between elements of the fibers fibers. (Note that this is basically like the construction of a wreath product in permutation group theory.)

More generally, suppose that \pi: M \rightarrow N is a cover and that M and N are saturated models (a harmless assumption, if \textup{Th}(M) is stable). Then we have an exact sequence

1 \rightarrow K \rightarrow \textup{Aut}(M) \rightarrow \textup{Aut}(N) \rightarrow 1

between the automorphism groups. (The existence of the arrow \pi_*: \textup{Aut}(M) \rightarrow \textup{Aut}(N) induced by \pi : M \rightarrow N comes from condition 2 in the definition of cover, and the fact that it is surjective follows from saturation plus stable embeddedness.) Call K the kernel of the cover.

This cover is called split if there is a splitting s: \textup{Aut}(N) \rightarrow \textup{Aut}(M) which is a topological group map (under the usual topology for automorphism groups, where an open basis for the identity map is the collection of all pointwise stabilizers of finite sets); that is, \pi_* \circ s = \textup{id}. (If K is abelian, then there is always a continuous map s with this property, but it may not be a group map.)

So the cover splits just in case there is a closed subgroup H of \textup{Aut}(M) such that H \cap K = 1 and H K = \textup{Aut}(M). Thus the map \pi_* : \textup{Aut}(M) \rightarrow \textup{Aut}(N) restricts to an isomorphism from H onto \textup{Aut}(N).

Assuming the structures M, N are \aleph_0-categorical, the definable structure can be recovered (up to bi-interpretability) from the automorphism group, and we have a more enlightening way to think about splitting: the cover \pi: M \rightarrow N splits if and only if there is an expansion M' of M such that N and M' are bi-interpretable via \pi.

Evans in (4) found many cases of structures N where every finite cover of N with finite kernel splits, including basic examples such as the infinite structure in an empty language and a dense linear ordering, and also gave an example of an \aleph_0-categorical N where this is not the case. This should be compared with Hrushovski’s work in (7) where he related the splitting of finite covers with finite kernels in stable theories with definable groupoids: these covers will always split (modulo adding finitely many algebraic constants) if and only if all connected groupoids definable in the base structure with finite fundamental groups are definably equivalent to groups.

Question: How can one decide, in general, if all finite covers with finite kernel will split? Given a base structure N and a potential kernel K, when can one classify all finite covers of N with kernel K?

Old open questions on totally categorical theories

Question: What, exactly, do the disintegrated (geometrically “trivial”) totally categorical structures look like?

At first, this question sounds like it should be easy, and at least some people think that Hrushovski settled the question in his paper (6) by showing that these are essentially just Grassmanians over infinite indiscernible sets, obtained from the trivial structure in the empty language by gluing copies of finite structures above finite sets. However, what Hrushovski showed was only that this holds after naming a finite set of constants. See the groupoids in (7) and the structures in (5) for examples of nontrivial phenomena in this context.

Without naming constants, what Hrushovski proved was that these disintegrated, totally categorical structures M with strictly minimal set D can be analyzed by a finite chain of \emptyset-definable sets

M_0 \subseteq M_{1,0} \subseteq M_1 \subseteq M_{2,0} \subseteq M_2 \subseteq \ldots

where M_i is the intersection of the universe M with algebraic closures of i-element sets from D, (M_i / M_{i,0}) is a Grassmanian constructed by gluing independent copies of a finite structure over i-element subsets of D, and \textup{Aut}(M_{i,0} / M_{i-1}) is nilpotent of class i. Note that all of the extensions in this chain are certain sorts of finite covers (which generally will be non-split).

Question: Is \textup{Aut}(M_{i,0}/M_{i-1}) abelian?

For i = 2, the group \textup{Aut}(M_{2,0}/M_1) is connected with the definable groupoids studied in (7). For higher values of i, I suspect these will be connected with “higher-dimensional groupoids” of some sort.

Question: Can we say anything useful in general about the affine totally categorical theories?

Answering this last question would require understanding what affine covers can look like. Note that this case includes structures such as (\mathbb{Z} / {4 \mathbb{Z}})^{\omega}, which can be thought of as a nonsplit affine cover of an infinite-dimensional space over \mathbb{F}_2. As for results, I only know of some special cases proved by Ahlbrandt and Zielger in (1) which appear to only cover the case of spaces over \mathbb{F}_2 (!).

Hrushovski in (6) conjectures: “It seems clear that every \aleph_0-categorical, \aleph_0-stable structure of modular type is interpretable in a finite disjoint union of universal locally lexicographically ordered vector spaces over finite fields.” I have know idea if anybody else has pursued this. Having some kind of classification of modular, totally categorical structures would be quite interesting.

References

  1. G. Ahlbrandt and M. Zielger, “What’s so special about (\mathbb{Z}/{4 \mathbb{Z}})^{\omega}?”, Archive for Mathematical Logic 31 (1991), 115-132.
  2. Greg Cherlin, Leo Harrington, and Alistair Lachlan, “\aleph_0-categorical, \aleph_0-stable structures”, Ann. Pure Appl. Logic 28 (1985), 103-135.
  3. David Evans, “Finite Covers,” talk at the ESF Conference on Model Theory, Bedlewo, Poland, August 2009 (http://www.uea.ac.uk/~h120/Bedlewo09.pdf).
  4. David Evans, “Splitting of finite covers of \aleph_0-categorical structures”, J. London Math. Soc. (2) 54 (1996), 210-226.
  5. David Evans and Elisabetta Pastori, “Second cohomology groups and finite covers of infinite symmetric groups”, Journal of Algebra 330 (2011), 221–233, http://arxiv.org/abs/0909.0366.
  6. Ehud Hrushovski, “Totally categorical structures”, Trans. Am. Math. Soc. 313 (1989), 131-159.
  7. Ehud Hrushovski, “Groupoids, imaginaries and internal covers”, Turkish J. of Math. (2012), http://arxiv.org/abs/math/0603413
  8. W. M. Kantor, Martin W. Liebeck, and H. D. Macpherson, “\aleph_0-categorical structures smoothly approximated by finite substructures”, Proc. London Math. Soc. (3) 59 (1989), 439-463.

MALOA “final” conference in Luminy

I had just attended the final MALOA conference “Logic and interactions“.  MALOA was a European network, which is now essentially finished (though the “final” meeting was not the last one, there will be a workshop in Manchester soon). The meeting took place at CIRM in Luminy, a wonderful place not only for mathematical reasons:

Luminy(you can see some more photos here).

As MALOA was about logic, rather than model theory, the topics of the talks were quite diverse, ranging from purely algebraic model theory (definable valuations and height bound in arithmetic nullstellensatz) to proof theory and even “logical description for behaviour analysis in aerospace systems”. Not sure how productive this diversity is, but at least it is entertaining.

Some talks that I found of particular interest are:

  • Talks by Deirdre Haskell  and Chris Laskowski on NIP, VC-density and connections to probability and combinatorics (in general one could safely add to this list some more subjects including set theory). These all are quite fascinating topics which deserve some postings in the future. There are already some examples of importing ideas from combinatorics (e.g. the beautiful (p,q)-theorem of Alon, Kleitman and Matousek) to prove model-theoretic results (e.g. UDTFS for NIP theories), but I believe that many more connections remain to be discovered.
  • Todor Tsankov spoke about generalizations of de Finetti’s theorem. Classical de Finetti’s theorem from probability theory says that a sequence of random variables is exchangeable if and only if it is independent and identically distributed over its tail sigma-algebra. Various multi-dimensional generalizations of this characterization form the so-called exchangeability theory. This theorem can viewed as providing a classification of all probability measures on 2^{\mathbb{N}} invariant under the action of S_{\infty}. Now, in a general situation, given a permutation group G acting on a countable set M, one can’t really hope to give any kind of “classification” of G-invariant measures on 2^{\mathbb{N}} as we are in the context of the general ergodic theory. However, it appears that if the group G is sufficiently large compared to the index set, one can arrive at stronger results. Todor’s approach is to consider oligomorphic groups, i.e. such that the action of G on M^n has only finitely many orbits for each n. These groups are familiar to model theorists as automorphism groups of \omega-categorical structures. Todor provides a classification in the case when the underlying structure has trivial algebraic closure, and gives some promising partial results in the general case. In fact, this subject appears to have a lot to do with model theory. I am involved in a project together with Itai Ben Yaacov, of an abstract model theoretic approach to de Finetti’s theory in terms of the forking calculus, canonical bases and Morley sequences in the context of an arbitrary stable first-order theory, in the sense of continuous logic (which specializes to the classical case considering the theory of [0, 1]-valued random variables equipped with the L^1 metric).

Also I gave what was probably my last talk as a “student”. I spoke about some new results with Pierre Simon and Anand Pillay concerning definable topological dynamics in NIP theories. The slides are available here. We show that notions like definable (extreme) amenability of a definable group, as well as various model theoretic components, are not affected by adding externally definable sets to the picture (that is, passing to a Shelah’s expansion of a model). These facts appear to have some applications to the questions of Newelski on describing G/G^{00} in terms of the so-called Ellis group.

Some counterexamples for forking, dividing, invariance

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.

good forking

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.

  1. {T} is supersimple of {SU}-rank {1}. Thus, Lascar strong type is determined by the strong type.
  2. For any set {A}, {\mbox{acl}(A)=A}.
  3. All pairs of different elements have the same type over {\emptyset}.
  4. 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.

  1. {xRb_{i}\land xRb_{j}} divides over {\emptyset} for any {i<j}.
  2. {\phi\left(x,b_{0}b_{1}b_{2}b_{3}\right)} does not divide over {\emptyset}.
  3. {\emptyset} is an extension base.
  4. {T} is {\mbox{SOP}_{3}} but {\mbox{NSOP}_{4}}.
  5. 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.

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

On the SOPn hierarchy inside NTP2

In this post I would like to popularize a certain question around Shelah’s classification theory of unstable (and even non-simple) theories.

tree property

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

  1. Saharon Shelah, “Simple unstable theories”, Ann. Math. Logic, http://dx.doi.org/10.1016/0003-4843(80)90009-1
  2. Saharon Shelah, “Classification theory and the number of nonisomorphic models”, North-Holland Publishing Co., 1990
  3. Artem Chernikov and Itay Kaplan, “Forking and dividing in NTP2 theories”, J. Symbolic Logic, 2012
  4. Artem Chernikov, “Theories without the tree property of the second kind”, http://arxiv.org/abs/1204.0832
  5. Itai Ben Yaacov and Artem Chernikov, “An independence theorem for NTP2 theories”, arXiv:1207.0289
  6. Byunghan Kim and Hyeung-Joon Kim, “Notions around tree property 1”, Annals of Pure and Applied Logic, 2011
  7. Saharon Shelah, “Toward classifying unstable theories”, Ann. Pure Appl. Logic, 1996
  8. Saharon Shelah and Alex Usvyatsov, “More on SOP1 and SOP2”, arXiv:math/0404178