# 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. – Haskell Curry Oct 14 '12 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. – Hagen von Eitzen Oct 14 '12 at 17:26
Hi @HaskellCurry, I just modified my post justifying the doubt you have, thanks for noticing – Camilo Arosemena Oct 14 '12 at 21:29

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.

-

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. – Camilo Arosemena Nov 27 '13 at 0:24
Second, it is way easier to prove Vaught's result you mention using the ommiting types theorem. – Camilo Arosemena Nov 27 '13 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 ... – Emil Jeřábek Nov 27 '13 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. – Emil Jeřábek Nov 27 '13 at 12:31