An $\omega$-categorical theory $T$ with no finite models is complete.

categorical-logiclogicmodel-theory

I'm trying to understand the following proof of this result, but I don't understand:

  1. where the assumption that $T$ has no finite models is used;

  2. why the final step is valid.

Take two models $\mathcal{M},\mathcal{N}$ of $T$, and suppose $\mathcal{M}\models\phi$. We need to show $\mathcal{N}\models\phi$ (the proof works exactly the same if $\mathcal{M}\not\models \phi$).

By the definition I have of $\omega$-categorical, $T$ must be in a countable language with an infinite model. So, by the Downward Lowenheim Skolem theorem, $\mathcal{M},\mathcal{N}$ both have countable elementary substructures, $\mathcal{M}',\mathcal{N}'$. Since $T$ is $\omega$-categorical, $\mathcal{M}'$ is isomorphic to $\mathcal{N}'$.

Thus far I am fine, but the proof then concludes "by elementarily, $\mathcal{N}\models\phi$". This is the step that I don't follow. What I have thought of is: "by the Tarski-Vaught test, $\mathcal{M}\models \phi$ precisely when $\mathcal{M}' \models \phi$, which is precisely when $\mathcal{N}'\models\phi$, and if $\mathcal{N}'\models\phi$ then $\mathcal{N}$ models $\phi$ since $\mathcal{N}'$ is a substructure", but I'm not comfortable with this.

Best Answer

You use the fact that $T$ has no finite models because you apply Löwenheim-Skolem to $\mathcal{M}$ and $\mathcal{N}$, which you can only do if they are infinite structures (Löwenheim-Skolem does not apply to finite structures).

For the second question: this follows directly from the definition of an elementary embedding. An embedding $f: \mathcal{M}' \to \mathcal{M}$ is elementary if for all tuples $a \in \mathcal{M}'$ and every formula $\varphi(x)$ we have that $\mathcal{M}' \models \varphi(a)$ if and only if $\mathcal{M} \models \varphi(f(a))$.

In this case we do not even need any parameters. That is, we are only interested in sentences. So particularly, having an elementary embedding $f: \mathcal{M}' \to \mathcal{M}$ means that for every sentence $\varphi$ we have $\mathcal{M}' \models \varphi$ if and only if $\mathcal{M} \models \varphi$.

The proof of Löwenheim-Skolem uses the Tarski-Vaught test to show that the embeddings obtained in that proof are elementary. After that, you need not concern yourself with the Tarski-Vaught test, it is the fact that we have elementary embeddings that is useful.

So if $f: \mathcal{M'} \to \mathcal{M}$ and $g: \mathcal{N'} \to \mathcal{N}$ are the elementary embeddings obtained from Löwenheim-Skolem ($\mathcal{M'}$ and $\mathcal{N'}$ both countable), then the argument should go as follows. Suppose that $\mathcal{M} \models \varphi$, then $\mathcal{M'} \models \varphi$ because $f$ is an elementary embedding. So by isomorphism of $\mathcal{M'}$ and $\mathcal{N'}$ (which we have by $\omega$-categoricity) we must have $\mathcal{N'} \models \varphi$. Then because $g$ is an elementary embedding, we find $\mathcal{N} \models \varphi$.

Related Question