The uncountable spectra of countable theories

Bradd Hart, Ehud Hrushovski and Michael C. Laskowski

Review from Zentralblatt MATH:

The paper provides a full and final list of uncountable spectra of complete, countable first-order theories $T$ (with infinite models), and answers in this way a very old and deep question in model theory. Indeed the spectrum problem goes back to the Löwenheim-Skolem Theorem, ensuring that such a theory $T$ has at least one model in each infinite power $\lambda$, and hence raising the problem of counting how many models of power $\lambda$ $T$ has for every $\lambda$ up to isomorphism. Let $I(T,\lambda)$ denote this cardinal number; $\lambda \mapsto I(T,\lambda)$ (for every infinite $\lambda$) is called the spectrum function of $T$.

In this framework, Morley proved in the sixties his Categoricity Theorem, saying that, if $I(T, \lambda) = 1$ for some uncountable $\lambda$, then the same is true for every uncountable $\lambda$ (actually the countable case $\lambda = \aleph_0$ is a little isolated when computing spectra, and deserves a somewhat separate analysis). Morley also conjectured that, for every $T$, the spectrum function is not decreasing for $\lambda > \aleph_0$. This was positively answered by Shelah some years later. But what Shelah did was much more formidable. On the one hand, he aimed to classify all the possible spectrum functions; but, on the other hand, he emphasized that this counting program cannot ignore, and actually does reflect some structure/nonstructure properties of the models of $T$. Accordingly Shelah found some fundamental dividing lines (superstability, presentability, shallowness, prime models over pairs) about $T$. If $T$ does not satisfy these conditions, then $I(T,\lambda) = 2^{\lambda}$ for every uncountable $\lambda$: this is viewed as a negative fact, forbidding any reasonable structure theory for models. Otherwise, if $T$ satisfies these assumptions, then the spectrum function obtains lower and upper bounds (excluding $I(T,\lambda)= 2^{\lambda}$ for every uncountable $\lambda$) and the models of $T$ can be classified in the following sense: each of them is the top of a suitable well-founded (possibly non-unique) tree of countable submodels. Shelah also provided a list of all the spectrum functions of classifiable theories $T$ whose depth $d$ is infinite (the depth of $T$ is the supremum of the depths of decomposition trees of models of $T$). The finite depth case was still open.

The paper under review fills this gap by providing sharper bounds in this case, and consequently accomplishing the full list of all the possible uncountable spectra (examples of theories with each of these spectra were given a in preliminary related paper). Here are some some details of the analysis pursued in the paper.

As already said, $T$ is a classifiable theory of finite depth $d$. The leading idea is to single out new dividing lines, mainly checking how far $T$ is from being totally trascendental and, sometimes, finer criteria. Basically, for $n \le d$, one deals with chains of length $n$ of countable models of $T$ $$ M_0 \subseteq \ldots \subseteq M_{n-1} $$ such that, for $0<i<n-2$, $M_{i+1}$ has weight 1 over $M_i$ and is independent from $M_i$ over $M_{i-1}$. Also one considers $na$-substructure $M \subseteq_{na} N$: this means that, for every formula $\varphi(x, y)$, tuple $a$ from $M$ and finite subset $F$ of $M$, if $\varphi (N, a) - M \not = \emptyset$, then $\varphi (M, a) - acl (F) \not = \emptyset$. A chain $\overline{\cal M}$ as before is called an $na$-chain when each $M_i$ is an $na$-substructure of the monster model ${\cal C}$. Now look at the set $R(\overline{\cal M})$ of the types over $M_{n-1}$ that are regular and orthogonal to $M_{n-2}$ (they are called relevant regular) and define such a type $p$ to be totally transcendental (tt) over $\overline{\cal M}$ when there exists some strongly regular relevant $q$ non-orthogonal to $p$ with a prime model over $M_{n-1}$ and any realization of $q$. At this point, call $T$ locally tt over $\overline{\cal M}$ if every type in $R(\overline{\cal M})$ is tt over $\overline{\cal M}$, and say that $T$ has a trivial failure over $\overline{\cal M}$ if some trivial $p$ in $R(\overline{\cal M})$ is not tt over $\overline{\cal M}$. Notice that a tt theory $T$ is locally tt over any chain.

The paper is mainly devoted to proving that these conditions -- the existence or the absence of a relevant type failing to be tt, and whether there is a trivial type of this kind -- lie among the significant dividing lines for the spectra. Indeed nice lower bounds are obtained for $I(T, \lambda)$ (and for an uncountable $\lambda$) when $T$ is not locally tt over some chain of length $n$, or even $T$ admits a trivial failure. The proof of these results is the core of the paper, and the crucial step towards the determination of the possible spectra. The strategy is as follows. First of all, one defines the key notions of diverse and diffuse families of leaves over an $na$-chain $\overline{\cal M}$ of length $n$ (a leaf is a chain $\overline{\cal N}$ of length $n+1$ extending $\overline{\cal M}$ up to $\overline{\cal M}$-isomorphism). When examining why $T$ could fail to be locally tt over a chain, one realizes that a failure over a chain of length $n$ implies the existence of a diverse family of leaves of continuum size over some $na$-chain of length $n$, and a trivial failure yields in this way a diffuse family. At this point, one sees how to build many non-isomorphic models when such a diverse, or diffuse family occurs. Then this analysis is applied to obtain the new lower (and upper) bounds and, at last, to compute the uncountable spectra.

It is worth underlining that the paper uses, in addition to a deep model-theoretic machinery, also notions and tools from descriptive set theory. Indeed a connection with set theory is not surprising, as the spectrum problem itself makes sense only within the set-theoretic framework. But here this relationship gets stronger and more substantial because the new dividing lines partition complete theories into Borel sets (with respect to their natural topology); this led to applying techniques from descriptive set theory in the main proof.

The paper is very well organized, and as deep as readable. A clear introduction first summarizes the history of the spectrum problem from Löwenheim-Skolem to Shelah, and reports Shelah's work; then it explains the genesis of this paper, as well as the plan and the basic lines of the proof. Each section is equipped with a preliminary paragraph, introducing its content and its aim.

Reviewed by C.Toffalori

Keywords: totally transcendental theory; uncountable spectra of countable first-order theories; spectrum function; classifiable theories; finite depth; trivial failure; diverse family of leaves; diffuse families of leaves; non-isomorphic models; Borel sets

Classification (MSC2000): 03C45 03E15

Full text of the article:

• PDF file (368 kilobytes)