Category Archives: Model Theory

Interpretations

(This started as an answer on Math.Stackexchange. This version has been lightly edited and expanded. Also posted at my blog.)

Throughout this post, theory means first-order theory. In fact, we are concerned with theories that are recursively presented, though the abstract framework applies more generally. Thanks to Fredrik Engström Ellborg for suggesting in Google+ the reference Kaye-Wong, and to Ali Enayat for additional references and many useful conversations on this topic.

1.

Informally, to say that a theory T interprets a theory S means that there is a procedure for associating structures \mathcal N in the language of S to structures \mathcal M in the language of T in such a way that if \mathcal M is a model of T, then \mathcal N is a model of S.

Let us be a bit more precise, and do this more syntactically to reduce the requirements of the metatheory: One can take “the theory T interprets the theory S to mean that there are

  1. A map i that assigns formulas in the language of T to the symbols of the language \mathcal L of S, and
  2. A formula \mathrm{Dom}(x) in the language of T,

with the following properties: We can extend i to all \mathcal L-formulas recursively: i(\phi\land\psi)=i(\phi)\land i(\psi), etc, and i(\forall x\phi)=\forall x(\mathrm{Dom}(x)\to i(\phi)). It then holds that T proves

  1. \exists x\,\mathrm{Dom}(x), and
  2. i(\phi) for each axiom \phi of S (including the axioms of first-order logic).

Here, T,S are taken to be recursive, and so is i.

If the above happens, then we can see i as a strong witness to the fact that the consistency of T implies the consistency of S.

Two theories are mutually interpretable iff each one interprets the other. By the above, this is a strong version of the statement that they are equiconsistent.

Two theories are bi-interpretable iff they are mutually interpretable, and in fact, the interpretations i from T is S and j from S in T can be taken to be “inverses” of each other, in the sense that T proves that \phi and j(i(\phi)) are equivalent for each \phi in the language of T, and similarly for S, \psi and i(j(\psi)). In a sense, two theories that are bi-interpretable are very much “the same”, only differing in their presentation.

2.

A good example illustrating this notion occurs when formalizing the idea of finitary mathematics. We can show that the two standard formalizations, \mathsf{PA} and \mathsf{ZFfin}, are bi-interpretable, where \mathsf{ZFfin} is the variant of \mathsf{ZF} resulting from replacing the axiom of infinity with its negation, and where foundation is stated as the axiom scheme of \epsilon-induction.

If we do not take the precaution of stating foundation this way, then the resulting theory \mathsf{ZFfin}' is mutually interpretable with \mathsf{PA}, but it is not immediately clear whether they are bi-interpretable, see section 3 for this. (Similar issues, curiously, occur with NFU and appropriate fragments of set theory.) The problem is related to the existence of transitive closures, see section 4  for more details.

The standard interpretation of \mathsf{ZFfin} inside \mathsf{PA} goes by defining n\mathrel E m iff, writing m in base 2, the nth number from the right is 1. That is, m=(2k+1)2^n+s for some k and some s<2^n. From Gödel’s work on the incompleteness theorems, we know that this is definable inside \mathsf{PA}, see here for some details and references. This interpretation goes back to Ackermann:

Wilhelm Ackermann. Die Widerspruchsfreiheit der allgemeinen Mengenlehre, Math. Ann. 114 (1937), 305–315.

In the other direction, the interpretation goes by realizing that in \mathsf{ZFfin} we can still define \omega and ordinal arithmetic, and the result is a model of \mathsf{PA}. But this is not the inverse. To obtain the inverse, we work in \mathsf{ZFfin}, and compose this with a definable bijection p:V\to\mathsf{ORD}, namely

p(x)=\sum \{2^{p(y)}\mid y\in x\}.

(Of course, V stands here for “V_\omega”, the universe, and \mathsf{ORD} stands for “\omega”.) The paper Kaye-Wong explains all this and provides additional references. This inverse interpretation is due to Mycielski, who published it in Russian:

Jan Mycielski. The definition of arithmetic operations in the Ackermann model. Algebra i Logika Sem. 3 (5-6), (1964), 64–65. MR0177876 (31 #2134).

Mycielski’s result remained “hidden” until attention was drawn to it in the survey

Richard Kaye and Tin Lok Wong. On interpretations of arithmetic and set theory. Notre Dame Journal of Formal Logic 48 (4), (2007), 497–510. MR2357524 (2008i:03075).

(The pdf linked to above has some additional information than the version published at the Journal.)

3.

On the difference between mutual interpretability and bi-interpretability, see this nice post by Ali Enayat to the FOM list. Ali shows there that \mathsf{ZF} and \mathsf{ZFC}, which are obviously mutually interpretable, are not bi-interpretable. The proof goes by noticing that if T and S are bi-interpretable, then the class of groups arising as \mathrm{Aut}(\mathcal M) for \mathcal M\models T coincides with the class of groups of the form \mathrm{Aut}(\mathcal N) for \mathcal N\models S.

However, \mathsf{ZF} admits a model with an automorphism of order 2, and this is not possible for \mathsf{ZFC}. (Additional details are given at the link.)

This naturally leads to the question of whether \mathsf{ZFfin}' and \mathsf{PA} (or, equivalently, \mathsf{ZFfin}) are bi-interpretable, that is, whether a more clever interpretation than Ackermann’s may get rid of the issues that forced us to adopt \epsilon-induction.

That this is not the case, meaning, the theories are mutually interpretable, but not bi-interpretable, was shown recently in

Ali Enayat, James H. Schmerl, and Albert Visser. \omega-models of finite set theory. In Set theory, arithmetic, and foundations of mathematics: theorems, philosophies, Juliette Kennedy, and Roman Kossak, eds. Lect. Notes Log., vol. 36, Assoc. Symbol. Logic, La Jolla, CA, 2011, pp. 43–65. MR2882651 (2012m:03132).

In fact, in Theorem 5.1, they show that \mathsf{ZFfin}' and \mathsf{PA} are not even sententially equivalent. This is a weaker notion than bi-interpretability:

Recall that if we have an interpretation i from T in S, then to each model \mathcal M of S we associate a model i(\mathcal M) of T. That T and S are bi-interpretable gives us interpretations i from T in S, and j from S in T such that for any model \mathcal M of S, the model j(i(\mathcal M)) is isomorphic to \mathcal M, and for any model \mathcal N of T, the model i(j(\mathcal N)) is isomorphic to \mathcal N.

We say that T and S are sententially equivalent when the interpretations i and j can be chosen to satisfy the weaker demand than i(j(\mathcal N)) and \mathcal N are elementarily equivalent, and similarly for j(i(\mathcal M)) and \mathcal M.

Their proof that this property fails for \mathsf{PA} and \mathsf{ZFfin}' ultimately traces back to the fact that no arithmetically definable model of \mathsf{PA} that is non-standard can be elementarily equivalent to the standard model. This is a result of Dana Scott. On the other hand, there are many arithmetically definable \omega-models of \mathsf{ZFfin}'. In section 4 we illustrate a very general method for producing such examples; further details can be seen in the Enayat-Schmerl-Visser paper.

4.

This section was originally an answer at Math.Stackexchange.

Let \mathsf{ZF}^{\lnot\infty} be the theory resulting from replacing in \mathsf{ZF} the axiom of infinity by its negation, but leaving foundation as the axiom stating that any non-empty set x has an element disjoint from x. This theory is not strong enough to prove the existence of transitive closures. This is the reason why \mathsf{ZFfin} is usually formulated with foundation (regularity) replaced by its strengthening of \epsilon-induction, namely the scheme that for every formula \phi(x,\vec y) adds the axiom

\forall \vec y\,(\forall x\,(\forall z\in x\,\phi(z,\vec y)\to\phi(x,\vec y)\to\forall x\,\phi(x,\vec y)).

Over the base theory \mathsf{BT} consisting of (the empty set exists), extensionality, pairing, union, comprehension, and replacement, one can prove that for any x, there is a transitive set containing x iff there is a smallest such set, that is, there is a transitive set containing x iff its transitive closure exists.

Over \mathsf{BT} plus foundation, the scheme of \epsilon-induction is equivalent to the statement \mathsf{TC} that every set is contained in a transitive set.

Unfortunately, as I claimed above, \mathsf{ZF}^{\lnot\infty} cannot prove the existence of transitive closures. To see this, start with (V_\omega,\in), the standard model of \mathsf{ZF}^{\lnot\infty}. Let

 \omega^\star=\{\{n+1\}\in V_\omega\mid n\in\omega\}.

Define F:V_\omega\to V_\omega by

 F(n)=\{n+1\},F(\{n+1\})=n

for n\in\omega, and F(x)=x for x\notin\omega\cup\omega^\star. Now define a new “membership” relation by

x\in_F y\Longleftrightarrow x\in F(y)

for x,y\in V_\omega. It turns out that

(V_\omega,\in_F)\models\mathsf{ZF}^{\lnot\infty}+\lnot\mathsf{TC}.

In fact, \emptyset is not contained in any transitive set in this structure. (Note that \emptyset is not the empty set of this model.)

All this and much more is discussed in Kaye-Wong. The result that \mathsf{ZF}^{\lnot\infty} is consistent with \lnot\mathsf{TC}, and the proof just sketched, are due to Mancini. For additional details, Kaye-Wong refers to

Antonella Mancini and Domenico Zambella. A note on recursive models of set theories, Notre Dame Journal of Formal Logic, 42 (2), (2001), 109-115. MR1993394 (2005g:03061).

In fact, if F:V_\omega\to V_\omega is any bijection, then defining \in^F as above gives a model of \mathsf{ZF}^{\lnot\infty}, except possibly for foundation. Many examples can be produced starting from this idea.

5.

Let me close by mentioning a very recent paper by Ali Enayat,

Ali Enayat. Some interpretability results concerning \mathsf{ZF}. Preprint.

Here, Ali extends the result mentioned above that \mathsf{ZF} and \mathsf{ZFC} are not bi-interpretable. In fact, he shows that no two distinct extensions of \mathsf{ZF} are bi-interpretable. (And some more.)

This should be contrasted with the situation for mutually interpretability. The development of forcing and inner model theory in fact has provided us with a plethora of examples of mutually interpretable such extensions.

Advertisements

Model theoretic stability and definability of types, after A. Grothendieck

It had happened more than once that combinatorial model theoretic dividing lines introduced by Shelah were invented independently in different fields of mathematics. This curious note by Itai Ben Yaacov gives another example of this phenomenon:

We point out how the “Fundamental Theorem of Stability Theory”, namely the equivalence between the “non order property” and definability of types, proved by Shelah in the 1970s, is in fact an immediate consequence of Grothendieck’s “Critères de compacité” from 1952. The familiar forms for the defining formulae then follow using Mazur’s Lemma regarding weak convergence in Banach spaces.

In a meeting in Kolkata in January 2013, the author asked the audience who had first defined the notion
of a stable formula and when, and to the expected answer replied that, no, it had been Grothendieck, in
the fifties.

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.

“Model theory and applications to geometry”, Satellite workshop associated with LC 2013, Lisbon, 18th-19th of July 2013

The aim of the workshop is to give the opportunity to the people attending Logic Colloquium 2013 and to all the people interested, to hear more about the recent developments in model theory and its applications and connections to real geometry.

List of confirmed speakers:

Raf Cluckers (Université de Lille and KULeuven)
Georges Comte (Université de Savoie – Chambéry)
Antongiulio Fornasiero (Seconda Università di Napoli)
Isaac Goldbring (UIC)
François Loeser (Université Pierre et Marie Curie)
Chris Miller (Ohio State University)
Giovanni Morando (Università di Padova)
Jean-Philippe Rolin (Université de Bourgogne)

You can find information about travelling and accommodation on the webpage of the workshop: http://ptmat.fc.ul.pt/~tservi/Workshop%202013/

REGISTRATION: if you are planning on attending this event, please contact tamara.servi@gmail.com

We hope to see you in Lisbon!

The Model Theory Group at CMAF
Universidade de Lisboa

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

Large cardinals in AECs: back to the road.

(This was originally posted by Andrés Villaveces in avn va – עולם)

The connections between Model Theory and Large Cardinals have recently been given a very interesting boost (and twist) in the work of Will Boney, a graduate student at Carnegie Mellon University.

Boney builds his results on a line originally opened in the papers by Makkai and Shelah ([MaSh:285] Categoricity of theories in L_{\kappa\omega}, with \kappa a compact cardinal — Annals Pure and Applied Logic 47 (1990) 41-97) and Kolman and Shelah ([KoSh:362] Categoricity of Theories in L_{\kappa,\omega}, when \kappa is a measurable cardinal. Part 1 — Fundamenta Math 151 (1996) 209-240) and a follow-up by Shelah ([Sh:472] Categoricity of Theories in L_{\kappa^* \omega}, when \kappa^* is a measurable cardinal. Part II — Fundamenta Math 170 (2001) 165-196): use of strongly compact ultrafilters to get relatively strong “compactness-like” properties, uses of measurable embeddings to get reasonable independence notions.

But Boney seems to go much further: by taking seriously the consequences of the presence of the embeddings and ultrafilters, he provides

  • a Łoś Theorem for Abstract Elementary Classes – under strongly compact cardinals \kappa: closure under (\kappa-complete) ultrapowers of models in the AEC, connections between realization of types inside monster models of the class, in both the ultrapower and the “approximations”
  • a duality (under categoricity at some \kappa – no large card. hypotheses here) between tameness and type shortness. Tameness can be regarded as a strong coherence property over domains, for types, type shortness is the analog but switching the coherence from domains of the types to realizations of the type
  • under a proper class of strongly compact cardinals, nothing less than a version of the Shelah Conjecture (eventual Categoricity Transfer from a Successor, for AECs) – Boney essentially gets tameness and type shortness of such classes; the meat of the proof really is there
  • under smaller large cardinals (measurables, weakly compacts, etc.), he gets different, weaker results, by using ultrapower techniques allowing him to gain control of properties of the class – reflection properties become crucial for model theoretic properties other than categoricity (stability, amalgamation, uniqueness of limit models!)
  • finally, his results open up many questions that puzzle one: what is the actual strength of Shelah’s Conjecture? where can the counterexamples started by Hart and Shelah (and refined by Baldwin and Kolesnikov) be pushed?

Here is also a skeleton for a Seminar Lecture in our Logic Seminar in Bogotá (in Spanish).