Tag Archives: Model theory

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.

Leave a comment

Posted on 25/08/2013 by John Goodrick in General

Tagged Model theory

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

“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

Leave a comment

Posted in Announcements, Conferences, Model Theory

Tagged Applications of Model Theory, conference, Lisbon, Model theory

Large cardinals in AECs: back to the road.

Posted on 25/03/2013 by a v n | Leave a comment

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

Leave a comment

Posted in Model Theory

Tagged abstract elementary classes, Andrés Villaveces, large cardinals, Model theory

When are bi-embeddable structures isomorphic?

Posted on 22/04/2012 by John Goodrick | Leave a comment

Let $(\textbf{K}, \textbf{Mor})$ be a class of algebraic structures $\textbf{K}$ with a distinguished class of morphisms $\textbf{Mor}$ between them. We say that the class has the Schröder-Bernstein (SB) property if any two elements of $\mathbf{K}$ which are bi-embeddable with respect to $\mathbf{Mor}$ are isomorphic.

Question 1: How can we tell when $(\textbf{K}, \textbf{Mor})$ has the SB property?

So, for instance, when $\textbf{K} = \textbf{Sets}$ and $\textbf{Mor}$ is all injective functions, then this class will have the SB property by the usual Cantor-Schröder-Bernstein theorem. The reader should try to think of examples which do not have the SB property, and check whether or not his or her favorite categories have SB.

The model-theoretic angle here is that we will concentrate on the case where $\textbf{K}$ is all of the models of some first-order theory $T$ and $\textbf{Mor}$ is the class of all elementary embeddings between them (that is, the maps which preserve the truth of all first-order formulas). If this is true, then we will say that the theory $T$ has the SB property.

But why is the Schröder-Bernstein property interesting? One could easily come up with a list of other strange, never-before-studied properties that some theories have and others do not, so what makes the Schröder-Bernstein property worth studying?

In this post I’ll try to explain a bit about why I am interested in this property as well as give some partial answers to Question 1 in model theory.

The naturality of considering the Schröder-Bernstein property

When many people first hear about it, the interest in studying the Schröder-Bernstein property seems evident. Others are skeptical. Partly for the skeptics, I’ll explain what made me first start thinking about it (within model theory).

A prime model of a theory $T$ is a model $M$ of $T$ which is elementarily embeddable into every other model of $T$ . Some theories have prime models, others do not. Naturally if one has a prime model of a theory $T$ , one would like to know whether it is unique (up to isomorphism).

“Theorem 2” If $T$ has a prime model, then it this prime model is unique.

Here is the “proof” of this statement that occurred to me as a grad student, and must have occurred to hundreds of other students before me: let $M$ and $N$ be two prime models of $T$ . Then, by definition, $M$ is elementarily embeddable into $N$ , and also $N$ is elementarily embeddable into $M$ . So they must be isomorphic, right?

But this argument only works if we somehow know that $T$ has the SB property, and (to me, as I write this) it seems no easier to prove that a given theory has the SB property than to show that it has a unique prime model. I now know about the famous, famously difficult result of Shelah that totally transcendental theories have unique prime models, as well as his examples showing that there exist theories with nonisomorphic prime models (see Shelah, “On uniqueness of prime models,” Journal of Symbolic Logic 44 (1979) no. 2, 215-220). For me, trying to repair this too-hasty argument for “Theorem 2” is what got me thinking about SB for theories.

Schröder-Bernstein and classifiability

Probably the very first time I thought about the Schröder-Bernstein property (in a totally different context than logic) was while reading Irving Kaplansky’s book Infinite Abelian Groups many years ago. In this book, Kaplansky at one point asks the following question (to paraphrase): say we have a system for classifying all objects of a certain type — say, abelian groups — up to isomorphism, using some sorts of “invariants.” How do we know if this system is really useful or enlightening? After all, we always have the “trivial classification system” of associating each object to its isomorphism class! This is silly, but the interesting question is: how do we know that our classification system is really better than the trivial classification system?

In a neat bit of parallel evolution (I doubt Kaplansky was influenced much by Shelah, or vice versa), Kaplansky basically answers this by saying that we should come up with test questions to which any good classification scheme should give a definite “Yes” or “No” answer. Crucially, these test questions should be phrased in terminology which is independent of our supposed classification system, so that we know that the system can answer “real questions” about the classified objects themselves as opposed to merely solving problems that arise from the internal complexity of our classifying scheme.

One of Kaplansky’s test questions was:

Question 3: If G and H are two abelian groups such that each one is isomorphic to a direct summand of the other, then are G and H isomorphic?

(Clearly this is a case of Schröder-Bernstein with $\textbf{Mor}$ being all injections whose images are direct summands. If we instead considered all injective group maps, then Question 3 would have many simple counterexamples, as the reader should verify.)

Somewhat surprisingly, the answer to Question 3 is “No,” with a counterexample so complex that Kaplansky himself could not find it. But the details of this do not matter to us here. What’s important to note is that we can know that Question 3 is true for certain classes of abelian groups using classification schemes.

For instance, as Kaplansky explains in his book, the answer to Question 3 is “Yes” if G and H are both countable abelian torsion groups (that is, for each element $g \in G$ , there is some $n \in \mathbb{N}$ such that $n g = 0$ , but there is not necessarily a uniform bound on $n$ for all $g$ in $G$ ). This is immediate using Ulm invariants. Another example, much simpler to explain in a blog post, is if G and H are finitely-generated abelian groups: then each one is a direct sum of indecomposable summands that are isomorphic to either $\mathbb{Z}$ or $\mathbb{Z} / p^k \mathbb{Z}$ for some prime power $p^k$ , and we just have to count the number of summands of each type to prove the result.

Thinking about examples like the ones above leads to the following intuition, partly justifying the study of the SB property (and I won’t try to make this too precise here):

Idea 4: If the objects in $\mathbf{K}$ can be classified by a bounded set of cardinal-number invariants which are preserved by embeddings in $\mathbf{Mor}$ , then we should expect $(\mathbf{K}, \mathbf{Mor})$ to have the SB property.

These cardinal-number invariants could be things like the number of direct summands belonging to a certain isomorphism class, or they could be dimensions (as for a vector space).

Famously, Shelah’s primary test question (which he used to help justify the development of his “classification theory,” now usually called stability theory) was to compute all possible spectrum functions $I(T, \kappa)$ for a complete theory $T$ , where $I(T, \kappa)$ is the number of isomorphism types of models of $T$ with cardinality $\kappa$ . But we could ask whether Shelahian stability theory is also useful for answering other test questions.

I’ll end this section with a couple of very naïve test questions of my own which I think that the classification theory for models should eventually be able to give definite answers to. But even though I have been thinking off and on about them for years now, I still cannot answer them except in certain special cases.

Question 5: Suppose $T$ is a first-order theory without the Schröder-Bernstein property. Is there an infinite collection of models of $T$ which are pairwise elementarily bi-embeddable but pairwise non-isomorphic?

Question 6: Suppose $T$ is a complete first-order theory with the Schröder-Bernstein property. Is it true that any expansion of $T$ by new constant symbols also has the Schröder-Bernstein property?

Schröder-Bernstein and stability theory

Now I’ll explain a few cases where I know that the Schröder-Bernstein property does not hold. Before giving precise statements, here is another vague generality to motivate the discussion:

Idea 7: If a class of structures is not easily classifiable, then often it is because it contains two objects $A$ and $B$ which “look very similar” and yet are not isomorphic. If $A$ and $B$ “look sufficiently similar,” then often they will be bi-embeddable, thus giving a counterexample to the Schröder-Bernstein property.

So we might expect that those theories which Shelah calls unclassifiable to not have the SB property. And it turns out that this is true! One result from my thesis was:

Theorem 8: Suppose that $T$ is a countable first-order theory. If $T$ is not classifiable (either unstable, or not superstable, or DOP, or else OTOP), then $T$ does not have the SB property. If $T$ is unstable, DOP, or OTOP, then $T$ has an infinite collection of pairwise-bi-embeddable, pairwise nonisomorphic models.

Maybe I will try to explain what this “classifiability” is all about in a future post; it is a fascinating and complicated subject. But a simple example of an unclassifiable (unstable) theory is the theory of all dense linear orderings without endpoints, and it is a fun exercise to construct counterexamples by hand (HINT: by quantifier elimination, any injective order-preserving map will be elementary).

A simple example of a theory which is classifiable yet still does not have the SB property is the theory of all equivalence relations with infinitely many classes, each of which is infinite. For this example, the word “classifiable” naïvely makes sense because any model is “classified” simply by a list of cardinal numbers (that is, the cardinalities of each of the equivalence classes). Again, it is interesting to construct one’s own counterexamples to the SB property here, and to compare this with Idea 4 above (note I was very careful to add the word “bounded,” and in this example there is no fixed prior bound on the length of the list of cardinals classifying a model).

Further reading

I’ll wrap up this post now since it’s already longer than I planned, and I could try to develop various of the ideas here in more detail in future posts. But I should at least give some references to precise theorems and proofs for those who are interested.

Before my thesis (finished in 2007), I am not aware of anyone else attempting a systematic study of the SB property within model theory other than T. A. Nurmagambetov in a pair of articles from the 1980’s (“The mutual embeddability of models” (in Russian), from The Theory of
Algebraic Structures, Karagand. Gos. Univ., 1985, pp. 109–
115, and “Characterization of $\omega$ -stable theories with a bounded number of dimensions,” Algebra i Logika 28 (1989), no. 5, 388–396.) In these articles, Nurmagambetov only considered totally transcendental theories, and he showed that in this case the SB property is equivalent to nonmultidimensionality.
An interesting variation on Idea 7 comes from Shelah’s paper “Existence of many $L_{\infty,\lambda}$ -equivalent, non- isomorphic models of $T$ of power $\lambda$ ” (Annals of Pure and Applied Logic 34 (1987), no. 3, 291-310). Note that $L_{\infty,\lambda}$ is a very powerful non-first-order logic (allowing infinitely long conjuctions and disjunctions, among other things), so two models that are $L_{\infty,\lambda}$ -equivalent really do look quite similar. Shelah establishes the property in the title for any theory which is not superstable or which has DOP or OTOP. However, this does not, as far as I know, have obvious consequences for bi-embeddability.

In joint work with Chris Laskowski, we treated special cases of the SB property for theories in the papers “The Schröder-Bernstein property for weakly minimal theories” and “The Schröder-Bernstein property for a-saturated models.” The first paper only considers weakly minimal theories, but we give a complete characterization of the SB property in this context in terms of weak orthogonality of types, and we show that given a failure of SB for one of these theories, one can construct and infinite family of pairwise bi-embeddable, pairwise non-isomorphic structures. The second paper linked above was written with a broader audience in mind (especially the first section) and it gives a complete answer to when a theory has an expansion by constants with the SB property as well as a partial answer to when the sufficiently saturated models have the SB property.

For me, the way in which one can manage to prove such results is much more interesting than merely listing the statements of the theorems themselves… but maybe more about this later!

Leave a comment

Posted in Model Theory, Schröder-Bernstein properties

Tagged bi-embeddability, John Goodrick, Model theory, Schröder-Bernstein property

Tag Archives: Model theory

Map of the Universe

Demystifying DOP

The model theory of covers

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

Large cardinals in AECs: back to the road.

When are bi-embeddable structures isomorphic?

Recent Posts

Recent Comments

Archives

Set Theory Talks

tags

Meta