fff

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.

Interpretations

Posted on 18/08/2013 by andrescaicedo | 4 comments

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

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

A map $i$ that assigns formulas in the language of $T$ to the symbols of the language $\mathcal L$ of $S$ , and
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

$\exists x\,\mathrm{Dom}(x)$ , and
$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.

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 $n$ th 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.)

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.

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.

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.

4 Comments

Posted in Model Theory

Éric Jaligot, 1972 – 2013

Posted on 22/07/2013 by Artem Chernikov | 2 comments

Page à la mémoire d’Eric Jaligot

2 Comments

Posted in General

Tagged Eric Jaligot

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

Posted on 07/07/2013 by Artem Chernikov | 1 comment

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 deﬁnability 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 deﬁning 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 ﬁrst deﬁned the notion
of a stable formula and when, and to the expected answer replied that, no, it had been Grothendieck, in
the ﬁfties.

1 Comment

Posted in Classification theory, Model Theory

Tagged definability of types, Grothendieck, Shelah, stability

Demystifying DOP

Posted on 31/05/2013 by John Goodrick | 7 comments

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

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, “ $\omega_1$ -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.

7 Comments

Posted in General

Tagged amalgamation, classification theory, DOP, finite covers, Model theory

The model theory of covers

Posted on 17/05/2013 by John Goodrick | 2 comments

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

G. Ahlbrandt and M. Zielger, “What’s so special about $(\mathbb{Z}/{4 \mathbb{Z}})^{\omega}$ ?”, Archive for Mathematical Logic 31 (1991), 115-132.
Greg Cherlin, Leo Harrington, and Alistair Lachlan, “ $\aleph_0$ -categorical, $\aleph_0$ -stable structures”, Ann. Pure Appl. Logic 28 (1985), 103-135.
David Evans, “Finite Covers,” talk at the ESF Conference on Model Theory, Bedlewo, Poland, August 2009 (http://www.uea.ac.uk/~h120/Bedlewo09.pdf).
David Evans, “Splitting of finite covers of $\aleph_0$ -categorical structures”, J. London Math. Soc. (2) 54 (1996), 210-226.
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.
Ehud Hrushovski, “Totally categorical structures”, Trans. Am. Math. Soc. 313 (1989), 131-159.
Ehud Hrushovski, “Groupoids, imaginaries and internal covers”, Turkish J. of Math. (2012), http://arxiv.org/abs/math/0603413
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.

2 Comments

Posted in General

Tagged amalgamation, classification theory, finite covers, Model theory

MALOA “final” conference in Luminy

Posted on 09/05/2013 by Artem Chernikov | 2 comments

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:

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

2 Comments

Posted in Conferences, General, Model Theory

Tagged Artem Chernikov, conference, connected component, de Finetti, Forking, Luminy, MALOA, NIP, stability, VC density

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

Posted on 09/05/2013 by Artem Chernikov | Leave a comment

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

Postdoc in model theory (Caserta, Italy)

Posted on 17/04/2013 by Artem Chernikov | 3 comments

I think that we might use this platform to spread information about upcoming meetings and position openings. The following is a message from Paola D’Aquino (Paola.DAQUINO@unina2.it)

Dear All,
there is a two year postdoc position in model theory in my department in Caserta. It will be advertised by end of April and the deadline for applying is around end of May. It’s not required to have a Ph.D. by the
deadline for application. The salary is 25,000 per year before taxes. If you know of anyone who can be interested they can write to me for more information.
Best wishes,
Paola

3 Comments

Posted in postdocs

Tagged positions, postdoc

Some counterexamples for forking, dividing, invariance

Posted on 15/04/2013 by Artem Chernikov | Leave a comment

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.

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.

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

${xRb_{i}\land xRb_{j}}$ divides over ${\emptyset}$ for any ${i<j}$ .
${\phi\left(x,b_{0}b_{1}b_{2}b_{3}\right)}$ does not divide over ${\emptyset}$ .
${\emptyset}$ is an extension base.
${T}$ is ${\mbox{SOP}_{3}}$ but ${\mbox{NSOP}_{4}}$ .
However, forking and dividing are the same for complete types.