8
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ To you edit, is the language finite? Or at least is the arity of the relations/functions bounded? $\endgroup$
    – Asaf Karagila
    Nov 19, 2012 at 8:04
  • 1
    $\begingroup$ Then it is impossible to find such sentence. $\endgroup$
    – Asaf Karagila
    Nov 19, 2012 at 8:34
  • 2
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Nov 19, 2012 at 9:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – user642796
    Nov 19, 2012 at 9:55
  • 1
    $\begingroup$ @Matt N.: that is important because the result is not correct if we look at languages without equality. $\endgroup$ Nov 19, 2012 at 16:51

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Nov 19, 2012 at 16:18
  • $\begingroup$ 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? $\endgroup$ Nov 19, 2012 at 16:23
  • $\begingroup$ @Asaf: Thanks! The main motivation in CW is to let other people edit it to improve anything that I didn't make clear enough. $\endgroup$ Nov 19, 2012 at 16:36
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 19, 2012 at 16:41
  • 1
    $\begingroup$ @Matt N.: because $|M| = n$. $\endgroup$ Nov 20, 2012 at 11:56
6
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Nov 17, 2012 at 12:55
  • $\begingroup$ @MattN.: if a model satisfies $T$ then it satisfies all its consequences, so you can assume closure without loss of generality. $\endgroup$
    – tomasz
    Nov 17, 2012 at 12:55
  • $\begingroup$ @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. $\endgroup$
    – tomasz
    Nov 17, 2012 at 12:58
  • $\begingroup$ Is $\varphi_L' = \bigwedge T$? $\endgroup$ Nov 18, 2012 at 8:51
  • 1
    $\begingroup$ @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. $\endgroup$
    – tomasz
    Nov 18, 2012 at 13:07
4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .