Complete first order theory with finite model is categorical

Question

I am trying to prove that if $T$ is a complete first order theory that has a finite model then it has exactly one model up to isomorphism. To this end, I assumed that $T$ is complete with a finite model $M_n$. Then I assumed that $M_m$ was another model of size $m \geq n$. We know that if a theory has two finite models with different cardinalities then the theory is incomplete hence $m = n$. Now two things remain to be shown: one is that any two models of finite size $n$ are isomorphic and the other is that every infinite model is also isomorphic to this finite model (is this even possible? but we clearly need to do something about the infinite case)

Thanks for helping me finish this proof. For the record: this is an exercise in Just/Weese, page 84.

Edit

I'm looking for a sentence $\varphi$ such that if $M_n \models \varphi$ then $M_n \cong M_m$. There are no assumptions on the language. But I think it's not possible to have a finite model for an infinite language so the language must be finite.

Edit 2

After some more thinking, if there is a finite model $M$ of size $n$, let $$ \varphi = \exists v_1, \dots , v_n ((v_1 \neq v_2) \land \dots \land (v_{n-1} \neq v_n)) \land \lnot \exists v_{n+1} ((v_{n+1} \neq v_1) \land \dots \land (v_{n+1} \neq v_n))$$ that is, $\varphi$ says that the model has exactly $n$ elements. Since $T$ is complete, either $\varphi$ or $\lnot \varphi$ is provable from $T$. Since we have a model in which $\varphi$ is true we therefore know that $T \vdash \varphi$. Hence any model of $T$ must have exactly $n$ elements.

Now the question is, how do I show that any two $n$-element models of $T$ must be isomorphic?

Answer 1

I will assume (without loss of generality) that $T$ is closed under consequences, that is if $T\vdash \varphi$, then $\varphi\in T$.

First, assume that the language $L$ is finite. In this case, show that for any model $M$ with $n$ elements, there is a sentence of the form $$\varphi_L=\exists x_1,\ldots, x_n\left( \left (\forall x \left(\bigvee x=x_j\right)\right)\wedge \varphi_L'(x_1,\ldots,x_n)\right)$$such that if $N\models \varphi$, then $N\cong M$. Obviously if $M\models T$, then $\varphi_L\in T$

Then proceed with the following:

1. Consider $T$ in arbitrary language $L$, and an $n$-element model $M$ of $T$.
2. Notice that for any finite $L'\subseteq L$ we have $\varphi_{L'}\in T$ such that for any $N\models \varphi_{L'}$ we have $M\vert _{L'}\cong N\vert_{L'}$, so for any finite $L'\subseteq L$ there is a bijection between $M$ and $N$ which preserves all functions, relations and constants from $L'$, along with its inverse.
3. Write $\textrm{Iso}_{L'}(M,N)$ for the set of all such bijections. Notice that it is a finite set!
4. Show that $\bigcap_{L'\subseteq L}\textrm{Iso}_{L'}(M,N)$ (intersection over all finite $L'$) is nonempty for any $N\models T$, and that its elements are isomorphisms.

As for your edit, a single sentence will never be enough for an infinite language, because it will only say something about finitely many symbols. Even in the trivial case of $L=\{p_n\vert n\in\omega \}$ with $p_n$ unary relation symbols, $T$ the theory of $M$ where $\lvert M\rvert=\{*\}$ and each $p_n^M=\emptyset$ no single sentence will suffice (because no matter what it might be, there will be an $n_0$ such that $p_{n_0}$ does not occur within it, and then it will not imply that $\exists x p_{n_0}(x)$ nor its negation).

If a sentence can be expressed in language $L'\subseteq L$, then you can't infer from it anything nontrivial about interpretations of symbols of $L\setminus L'$.

Answer 2

Regarding your previous edit, without any assumptions on the language it is not possible to ensure that a single formula describes your finite structure.

Consider the language $L$ with equality and a single $n$-ary function symbol $F_n$ for each $n \geq 1$ (and no other non-logical symbols). Take $M$ to be the $L$-structure $( \{ 0 , 1 \} , f_1 , f_2 , \ldots )$ where $$f_n ( a_1 , \ldots , a_n ) = a_n$$ for all $n \geq 1$ and $a_1 , \ldots , a_n \in \{ 0,1 \}$. Define $T = \mathrm{Th}(M)$, the set of all $L$-sentences true in $M$. Clearly $T$ is complete and has a finite model.

However I claim that $T$ is not finitely axiomatizable (meaning that given any single $L$-sentence $\varphi \in T$ there is a structure $N$ such that $N \models \varphi$ but $N \not\models T$; such an $N$ is clearly not isomorphic to $M$).

Given any such sentence $\varphi$, note that it contains only finitely many of the function symbols, so say that $k \geq 1$ is such that $F_n$ does not appear in $\varphi$ for any $n \geq k$. Define a structure $N = ( \{ 0,1 \} , g_1 , g_2 , \ldots )$ so that

• $g_n = f_n$ for $n < k$; and
• $g_n ( a_1, \ldots , a_n ) = a_1$ for $n \geq k$, and $a_1 , \ldots , a_n \in \{ 0,1 \}$.

It should be clear that $N \models \varphi$, however $N \not\models ( \forall x_1 ) \cdots ( \forall x_k ) ( f_k ( x_1 , \ldots , x_k ) = x_k )$.

Answer 3

Here is an alternative way of looking at tomasz's answer. I realized after thinking it up that my method based on compactness is basically his method, so I just typed this up as a community wiki answer.

Suppose that $N$ and $M$ are two models of $T$. We know they both have size $n$, and we want to make an isomorphism between them.

For any finite sublanguage $L$, if we let $N^L$ and $M^L$ be the reducts of those structures to the language $L$, then $N^L \cong M^L$. This is because, for a finite language, we can encode the entire atomic diagram of $M^L$ as a single purely existential sentence. For example, if $L$ has a single binary relation symbol $R$, and $|M|$ has two elements, the sentence might be $$ (\exists x_1)(\exists x_2)[ (x_1 \not = x_2) \land Rx_1x_2 \land \lnot Rx_1x_1 \land Rx_2x_2 \land \lnot Rx_2x_1] $$ depending on how $R$ is interpreted in $M$. Since $T$ is complete and $M$ satisfies this sentence, both $M^L$ and $N^L$ satisfy this sentence, so we can form the isomorphism between them by just finding the sequence $(x_1, x_2)$ in each model that works, and then sending $x_1^M$ to $x_1^N$ and $x_2^M$ to $x_2^M$. The same thing can be done for any finite language. There will be $n$ quantifiers when $|M| = n$, and there will be many, many clauses, depending on how many symbols are in the finite language and on their arities.

Now assume for a contradiction that $N \not \cong M$ in the original language of $T$. Then for every bijection $f\colon |M| \to |N|$, there is some finite sublanguage $L_f$ such that $f$ is not an isomorphism between $M^{L_f}$ and $N^{L_f}$. Let $L'$ be the union of the languages $L_f$ over all bijections $f$ from $|M|$ to $|N|$. Then $L'$ is a finite language, because there are only finitely many of those bijections. Thus there is some isomorphism from $M^{L'}$ to $N^{L'}$ from above. But we chose $L'$ so that no bijection from $|M|$ to $|N|$ is such an isomorphism, which is a contradiction. Hence $N \cong M$ as desired.