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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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