# Complete first order theory with finite model is categorical

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?

-
To you edit, is the language finite? Or at least is the arity of the relations/functions bounded? –  Asaf Karagila Nov 19 '12 at 8:04
Then it is impossible to find such sentence. –  Asaf Karagila Nov 19 '12 at 8:34
Take an infinite language which has one $n$-ary relation for every $n$, and the theory states that every two points stand in the relation. And that there exists only $k$ points in the universe for a fixed $k$. Infinite language; infinite theory; finite model. –  Asaf Karagila Nov 19 '12 at 9:51
When we speak about the cardinality of a model/structure, we only talk about the size of the underlying set (the universe or domain of discourse or some other euphemism) and completely ignore the constants, functions and relations. –  Arthur Fischer Nov 19 '12 at 9:55
@Matt N.: that is important because the result is not correct if we look at languages without equality. –  Carl Mummert Nov 19 '12 at 16:51

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

-
Actually, the book defines the set of all sentences provable from $T$ separately from $T$. So in order to stick to the book one would have to assume that $T$ is not closed under consequences. But I presume there is a way out. –  Matt N. Nov 17 '12 at 12:55
@MattN.: if a model satisfies $T$ then it satisfies all its consequences, so you can assume closure without loss of generality. –  tomasz Nov 17 '12 at 12:55
@MattN.: Then again, in hindsight, I don't think I really used that anywhere in the proof, anyway. :) I will leave it in just in case, and for simplicity. –  tomasz Nov 17 '12 at 12:58
Is $\varphi_L' = \bigwedge T$? –  Matt N. Nov 18 '12 at 8:51
@MattN.: No! It's a finite formula. Quantifier-free. Recall the definition of an isomorphism. It only needs to be a homomorphism that has an inverse homomorphism, you don't need to make it elementary, it only turns out to be such a posteriori. –  tomasz Nov 18 '12 at 13:07

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

-

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.

-
I think that you shouldn't have CW'd this answer. It's another perspective on tomasz' approach, and it is valuable on its own. I was struggling to write this answer cleanly, but you managed to do that nicely. –  Asaf Karagila Nov 19 '12 at 16:18
Thank you so much for this nice and clear answer! I have two last remaining question: where you write "... we can encode the entire atomic diagram of $M$...", did you mean $M^L$? And: the formula $\varphi_L'$ mentioned in tomasz's answer -- is this the formula that you give as an example and that depends on the sublanguage involved? –  Matt N. Nov 19 '12 at 16:23
@Asaf: Thanks! The main motivation in CW is to let other people edit it to improve anything that I didn't make clear enough. –  Carl Mummert Nov 19 '12 at 16:36
@Matt N.: yes, my example shows how to write $\phi_L$ in that case. The main things that would have to be clarified to make my argument more rigorous are how to define that sentence in general, and the claim in the second sentence of the final paragraph about the existence of a finite sublanguage. –  Carl Mummert Nov 19 '12 at 16:41
@Matt N.: because $|M| = n$. –  Carl Mummert Nov 20 '12 at 11:56