# How many elementary embeddings can there be?

If $T$ is a complete first-order theory and $\kappa$ is a cardinal, let $\mathrm{Mod}_\kappa(T)$ be (a skeleton of) the category of $\kappa$-small models of $T$ (i.e. of cardinality $<\kappa$), with elementary embeddings as morphisms. What are the possible cardinalities of (the set of morphisms of) $\mathrm{Mod}_\kappa(T)$? And more specifically: what are the possible cardinalities of the hom-sets $\mathrm{Hom}_{\mathrm{Mod}_\kappa(T)}(M,N)$ for various $M,N \in \mathrm{Mod}_\kappa(T)$.

From a categorical perspective, this is a natural variant on classification theory and the question of the number of nonisomorphic models, which is about the cardinality of the set of objects of $\mathrm{Mod}_\kappa(T)$. It also provides a variation on Vaught's conjecture to consider.

For example, suppose the language is countable and $\kappa = \aleph_1$ and there is an infinite model. There's an obvious upper bound on $|\mathrm{Mod}_\kappa(T)|$ of $2^{\aleph_0}$, which is attained in all the examples I can think of (but I'm not actually a model theorist!). There's also a topology on the homsets given by pointwise convergence, with respect to which composition is continuous, which is a metric topology in the case of countable models, so it's tempting to try to construct perfect sets of embeddings.

It is a fact (following from the Ehrenfeucht–Mostowski theorem) that for every complete theory $T$ and for every $\lambda \geq |T|$, there is $M \models T$ with $|M| = \lambda$ and $M$ having $2^\lambda$-many automorphisms (assuming $T$ has infinite models). So if I'm understanding your question correctly then what you denote as $\mbox{Mod}_\kappa(T)$ always has cardinality $2^{<\kappa}$, at least for $\kappa > |T|$.

PS: (simplified example) To partially address your second question: for every cardinal $\lambda$ (possibly $\lambda$ finite or $0$) there are $M \equiv N$ structures in a countable language such that there are exactly $\lambda$ elementary embeddings from $M$ to $N$. Let $\mathcal{L}$ be the language with infinitely many constant symbols $(c_m: m < \omega)$ and let $T$ say that they are all distinct. For $\lambda > 0$, let $M$ be the model with exactly one unsorted element and let $N$ be the model with exactly $\lambda$ unsorted elements; then there are $\lambda$ elementary embeddings from $M$ to $N$. For $\lambda = 0$ let $M$ have 1 unsorted element and let $N$ have no unsorted elements.

PPS: On the other hand if $M, N$ are countable then the possibilities are exactly $0, 1, 2, \ldots, \aleph_0, 2^{\aleph_0}$. From the above examples we have seen these are all possible, on the other hand the space of elementary embeddings from $M$ to $N$ is a Polish space (completely metrizable space) so either is countable or has a perfect subset. (The subtleties of Vaught's conjecture are that we are looking at models up to isomorphism, so an equivalence relation on a Polish space.)

• Ah, Ehrenfeucht–Mostowski models. That’s much simpler than my argument. – Emil Jeřábek Dec 5 '16 at 15:56
• Great! This is just the sort of answer I was hoping for! – Tim Campion Dec 5 '16 at 16:03
• I've modified the example in the PS, the previous example was buggy. – Douglas Ulrich Dec 5 '16 at 16:04

While far from being a solution of the general problem, let me confirm that if $T$ is any theory in a countable language that has an infinite model, then $|\mathrm{Mod}_{\aleph_1}(T)|=2^{\aleph_0}$.

We may assume $T$ is complete. Let $S_n(T)$ be the space of complete $n$-types of $T$ (dual to the Lindenbaum algebra of $T$ in $n$ variables). Being a second-countable Boolean space, each $S_n(T)$ is either countable, or it has cardinality $2^{\aleph_0}$. There are two cases to consider.

Case 1: $|S_n(T)|=2^{\aleph_0}$ for some $n\in\omega$.

Then $T$ has $2^{\aleph_0}$ nonisomorphic countable models (as each $n$-type is realized in a countable model, but one such model can only realize countably many types). Thus, $\mathrm{Mod}_{\aleph_1}(T)$ even has $2^{\aleph_0}$ distinct objects.

Case 2: $|S_n(T)|\le\aleph_0$ for all $n\in\omega$ ($T$ is small in model-theoretic terminology).

Then $T$ has a countable saturated model $A$. It suffices to show that there are $2^{\aleph_0}$ elementary embeddings $A\to A$. (They could even be made automorphisms by a minor modification of the argument.)

Let us enumerate $A=\{a_n:n\in\omega\}$, and let $S$ be the tree of all sequences $\langle b_i:i<n\rangle\in A^{<\omega}$ such that the partial mapping $a_i\mapsto b_i$ $(i<n)$ is elementary. Every infinite branch of $S$ gives an elementary embedding $A\to A$.

By saturation, every finite partial elementary self-map of $A$ extends to an elementary embedding of the whole $A$, hence $S$ has no finite branches. In fact, we claim that the tree is perfect, i.e., every $\sigma\in S$ has an extension that splits. This will ensure that $S$ has $2^{\aleph_0}$ infinite branches. For this, it is enough to show that for any finite set $A_0=\{a_i:i<n\}$, there are two elements $u\ne v$ in $A$ with the same type over $A_0$. This in turn follows from saturation, and the pigeonhole principle: since $A$ is infinite, for every finite set of formulas $\phi_0(x_0,\dots,x_{n-1},y),\dots,\phi_m(x_0,\dots,x_{n-1},y)$, there is an infinite set $U\subseteq A$ such that $$\phi_j(a_0,\dots,a_{n-1},u)\leftrightarrow\phi_j(a_0,\dots,a_{n-1},v)$$ for all $u,v\in U$.

• Thanks! Your methods are a bit more familiar to me than the Ehrenfeucht-Mostowski Theorem, so I appreciate the perspective. – Tim Campion Dec 5 '16 at 16:04