Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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