When are bi-embeddable structures isomorphic?

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

Question 1: How can we tell when has the SB property?

So, for instance, when and 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 is all of the models of some first-order theory  and 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  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 is a model of which is elementarily embeddable into every other model of . Some theories have prime models, others do not. Naturally if one has a prime model of a theory , one would like to know whether it is unique (up to isomorphism).

“Theorem 2” If 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 and be two prime models of . Then, by definition, is elementarily embeddable into , and also is elementarily embeddable into . So they must be isomorphic, right?

But this argument only works if we somehow know that 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 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 , there is some such that , but there is not necessarily a uniform bound on for all in ). 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 or for some prime power , 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 can be classified by a bounded set of cardinal-number invariants which are preserved by embeddings in , then we should expect 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 for a complete theory , where  is the number of isomorphism types of models of  with cardinality . 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  is a first-order theory without the Schröder-Bernstein property. Is there an infinite collection of models of  which are pairwise elementarily bi-embeddable but pairwise non-isomorphic?

Question 6: Suppose  is a complete first-order theory with the Schröder-Bernstein property. Is it true that any expansion of  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 and which “look very similar” and yet are not isomorphic. If and “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 is a countable first-order theory. If  is not classifiable (either unstable, or not superstable, or DOP, or else OTOP), then  does not have the SB property. If is unstable, DOP, or OTOP, then 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 -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 -equivalent, non- isomorphic models of of power ” (Annals of Pure and Applied Logic 34 (1987), no. 3, 291-310). Note that is a very powerful non-first-order logic (allowing infinitely long conjuctions and disjunctions, among other things), so two models that are -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!