1
$\begingroup$

I'm trying to prove the following: If $T$ is a first-order theory with the property that for every natural number $n$ there is a natural number $m>n$ such that $T$ has an $m$-element model then $T$ has an infinite model.

My thoughts: If $M$ is an $n$-element model then $\varphi_n = \exists v_1, \dots, v_n ((v_1 \neq v_2) \land \dots \land (v_{n-1} \neq v_n))$ is true in $M$. Can I use this to show that $T$ has an infinite model? How? Perhaps combine it with the compactness theorem somehow? Thanks for your help.

2 Answers 2

5

You are close.

Yes, this is what you need to do, but remember that inequality is not transitive. It is not enough to require $v_i\neq v_{i+1}$, but you need to have $\varphi_n=\bigwedge_{i\neq j.

If there are arbitrarily large finite models, then every finite collection of sentences of the form above is consistent with $T$, therefore $T\cup\{\varphi_n\mid n\in\omega\}$ is consistent and any model of that cannot be finite.

4

This is a standard fact. The result you are looking for is exactly the compactness theorem, but you can also do it directly. Just take an ultraproduct of a sequence $M_i$ of larger and larger finite models. Since every one of these models $T$, so does the ultraproduct, by Łoś's theorem.