# A theory with exactly $n$ countable models, for each $n>1$

For each $n>1$ we shall construct a first-order theory $T_n$ with exactly n countable models. Let $n>1$, consider the language $L_n=\left\{{R,c_1,...,c_n}\right\}$, where $R$ is a binary relation symbol, and each $c_n$ is a distinct constant symbol. Put $$\phi=\forall{x}\forall{y}(x\neq{c_1}\wedge{y\neq{c_2,...c_n}}\longrightarrow{¬Rxy})$$ and $$\psi=\forall{x}\forall{y}\forall{z}(x\neq{y}\wedge{x\neq{z}\wedge{y\neq{z}\wedge{Rxy}}}\longrightarrow{¬Rxz}).$$ Set $$T_n=\left\{{c_i\neq{c_j}:i\neq{j}}\right\}\cup\left\{{\phi,\psi}\right\}.$$ It is clear that $T_n$ is consistent, and thus by Lowenheim-Skolem theorem $T_n$ has a countable model. Let $\mathcal{M}$ be a countable model of $T_n$, then since $\mathcal{M}\models{\phi}$ we must have that either $R^{\mathcal{M}}=\emptyset$ or $R^{\mathcal{M}}=\left\{{(c_1,c_{n_1}),...,(c_1,c_{n_m})}\right\}$, but since $\mathcal{M}\models{\psi}$ we get that if $R^{\mathcal{M}}\neq{\emptyset}$, then $\left |{R^{\mathcal{M}}}\right |=1$.

Therefore we must have that either $R^{\mathcal{M}}=\emptyset$ or $R^{\mathcal{M}}=\left\{{(c_1,c_m)}\right\}$ for some $m\leq{n}$. It is clear that if $\mathcal{M}$ and $\mathcal{N}$ are models of $T_n$ with $R^{\mathcal{M}}=\emptyset$ and $R^{\mathcal{N}}=\emptyset$, then $\mathcal{M}\simeq{\mathcal{N}}$.

And also if $R^{\mathcal{M}}=\left\{{(c_1,c_i)}\right\}$ and $R^{\mathcal{N}}=\left\{{(c_1,c_j)}\right\}$, then $\mathcal{M}\simeq{\mathcal{N}}$ if and only if $i=j$, for $\mathcal{M}\models{c_i\neq{c_j}}$ for $i,j\in{\left\{{2,...,n}\right\}}$ with $i\neq{j}$

By Lowenheim-Skolem theorem each case has a countable model.

Thus $T_n$ has exactly $n$ countable models.

I would like to see others examples.

Thanks

• Hi Camilo. You say that $R^{\mathcal{M}} = \{ (c_{1},c_{m}) \}$ and $R^{\mathcal{N}} = \{ (c_{1},c_{m}) \}$ imply $\mathcal{M} \cong \mathcal{N}$. However, one can have $R^{\mathcal{M}} = \{ (c_{1},c_{i}) \}$ and $R^{\mathcal{N}} = \{ (c_{1},c_{j}) \}$, where $i,j \in \{ 2,\ldots,n \}$ are distinct. After all, $\mathcal{M}$ and $\mathcal{N}$ are different models, so there is no need to stick to a single $c_{m}$ for both. Oct 14, 2012 at 17:17
• Isn't that exactly Camilo's argument? There are exactly $n-1$ countable models with nonempty rlation and another countable model with empty relation. Oct 14, 2012 at 17:26
• Hi @HaskellCurry, I just modified my post justifying the doubt you have, thanks for noticing Oct 14, 2012 at 21:29

While this is not mandated in the original question, it is more interesting to ask for which finite $n$ there exists a complete theory with exactly $n$ countable models up to isomorphism.

For $n=1$, we can take the theory of dense linear orders (or any other $\omega$-categorical theory, for that matter).

For $n\ge3$, there is an elegant construction due to Ehrenfeucht. Let $D_k$ ($k\ge1$) be the theory of densely $k$-coloured linear orders: that is, its language consists of a binary predicate $<$, and unary predicates $P_1,\dots,P_k$, and its axioms state that $<$ is a linear order without end-points, each element satisfies exactly one of the predicates $P_1,\dots,P_k$, and for each $i=1,\dots,k$, the set of elements satisfying $P_i$ is dense. Using a similar zig-zag argument as for dense linear orders, it is easy to show that $D_k$ is complete, $\omega$-categorical, and it has elimination of quantifiers.

Now, let $T_{k+2}$ be an extension of $D_k$ in a language with extra constants $\{c_n:n\in\omega\}$, and axioms $\{c_n<c_m:n<m\}\cup\{P_1(c_n):n\in\omega\}$. By quantifier elimination for $D_k$, the theory $T_{k+2}$ is complete. Let $A,B$ be countable models of $T_{k+2}$. We can construct a partial isomorphism by mapping $c_n^A$ to $c_n^B$, each interval $(c_n,c_{n+1})_A$ onto $(c_n,c_{n+1})_B$, and similarly for the unbounded interval $(-\infty,c_0)$: indeed, all these intervals are countable models of $D_k$, hence they are isomorphic. Conversely, any isomorphism of $A$ and $B$ must look like that. Thus, the isomorphism type of $A$ is uniquely determined by the isomorphism type of the “remainder” $$A^*=\{a\in A:\forall n\in\omega\,c_n^A<a\}.$$ This remainder may be empty, or it may be nonempty with no least element (in which case it is the unique countable model of $D_k$), or it may have a least element $a$: in the last case, $(a,\infty)$ is the unique countable model of $D_k$, and the only choice we have is the colour of $a$. Thus, in total, $T_{k+2}$ has exactly $k+2$ countable models up to isomorphism.

Curiously, a theorem of Vaught states that the remaining case, $n=2$, is in fact impossible: there is no complete theory with exactly two countable models.

An outline of the proof is as follows. If $T$ has only two countable models, it has only countably many complete $n$-types for every $n<\omega$, hence it has an atomic model $A$, and a countable saturated model $S$. Since $T$ is not $\omega$-categorical, it has a nonprincipal complete $n$-type $p(\vec x)$ for some $n$. First, notice that $p$ is realized in $S$ but not in $A$, hence $A\not\simeq S$, hence every countable model of $T$ is isomorphic to $A$ or to $S$. Consider the theory $T'=T+p(\vec c)$, where $\vec c$ are new constants. If $M,N$ are countable models of $T'$, their reducts to the language of $T$ must be isomorphic to $S$, hence they are saturated (this property is preserved by expansion with extra constants). Since $T'$ is complete, this implies $M\simeq N$. Thus, $T'$ is $\omega$-categorical, and as such it has only finitely many complete $n$-types for every $n$. But then the same must hold for $T$, a contradiction.

• It is easier to show $T_{k+2}$ is complete by restricting the language; $T_{k+2}\upharpoonright\{c_0,\ldots,c_n\}$ is $\omega$-categorical, and thus complete. Nov 27, 2013 at 0:24
• Second, it is way easier to prove Vaught's result you mention using the ommiting types theorem. Nov 27, 2013 at 0:25
• As for completeness of $T_{k+2}$: I believe you are just using a different name for exactly the same proof. The $\omega$-categoricity of $T_{k+2}\restriction\{c_0,\dots,c_k\}$ and quantifier elimination for $D_k$ are both proved by the same zig-zag argument showing that a finite partial isomorphism between two countable models of $D_k$ can be extended to a full isomorphism. As for your second comment, I am using the omitting types theorem for the existence of an atomic model. It’s true that I only need that $A$ omits $p$ rather than all nonprincipal types, but the proof is the same, and ... Nov 27, 2013 at 12:26
• ... I think it is worthwhile to point out that $A$ has a more structural property than just omitting one particular type. If you had in mind something else, I’d be happy to hear more details, it’s perfectly possible I’m missing something. Nov 27, 2013 at 12:31

Let $L_n$ be the language with $n$ nullary predicate symbols (aka primitive propositions) $P_1, \ldots, P_n$, and $T_n$ be the theory with $\forall x \forall y (x=y)$ as one axiom and another axiom asserting that exactly one of the $P_i$ is true. Clearly a model is just a choice of $i$, so there are $n$ models.

If you don't like nullary predicates, use unary predicates instead, and have the second axiom assert that exactly one of the $n$ sentences $\forall x(P_i(x))$ is true.

Our theory $T_n$ is over the predicate calculus with equality. The language has a unary predicate symbol $Q$, a binary predicate symbol $\lt$, and no other non-logical symbols. We now describe the axioms of $T_n$.

(i) If $Q$ fails at $x$ or at $y$, then neither $x\lt y$ nor $y\lt x$ holds.

(ii) Under $\lt$, the objects that satisfy $Q$ form a (non-empty) densely ordered set with no first or last element.

(iii) There are at most $n-1$ objects that satisfy $\lnot Q$.

Since the theory of densely ordered sets with no first or last element is $\omega$-categorical, we are done.

For the sake of completeness, let me add the simplest example: the language has no nonlogical symbols, and $T_n$ is the sentence "there are at most $n$ elements".

If you want a theory with exactly $n$ countably infinite models, this is easily modified: our language has a single unary predicate $U$, and $T_n$ says "there are infinitely many elements outside $U$" (more precisely, for each $k$ we put the sentence "there are at least $k$-many elements outside $U$" into $T_n$) and additionally "$U$ has size at most $n$."