2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The fact that a substructure is elementary says exactly that it satisfies the same formulas. $\endgroup$ – Captain Lama May 7 at 14:56
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is extremely clear. It was partially the lack of parameters confusing me, because all the definitions I have use parameters, so that explanation is useful. $\endgroup$ – probablystuck May 7 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.