7
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.