Łoś-Vaught Test

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be a satisfiable $\mathcal L$-theory with no finite models.

Let $T$ be $\kappa$-categorical for some infinite cardinal $\kappa \ge \left|{\mathcal L}\right|$.


Then $T$ is complete.


Proof

We prove the contrapositive.

The main idea is that if such a theory $T$ is incomplete, we can construct size $\kappa$ models which disagree on a sentence.


Suppose $T$ is not complete.

By the definition of complete, this means that there is some sentence $\phi$ such that both $T \not \models \phi$ and $T \not \models \neg \phi$.

This in turn means that both $T \cup \left\{{\neg \phi}\right\}$ and $T \cup \left\{{\phi}\right\}$ have models.

Since $T$ has no finite models, this means that $T \cup \left\{{\neg \phi}\right\}$ and $T \cup \left\{{\phi}\right\}$ both have infinite models.

We have that $\kappa$ is infinite and greater than the cardinality of the language.

We also have that these theories have infinite models.

From the Upward Löwenheim-Skolem Theorem one can prove that there are size $\kappa$ models $\mathcal M_{\neg \phi}$ and $\mathcal M_{\phi}$ of $T \cup \left\{{\neg \phi}\right\}$ and $T \cup \left\{{\phi}\right\}$ respectively.

In particular, $\mathcal M_{\neg\phi}$ and $\mathcal M_\phi$ are models of $T$ which disagree about the sentence $\phi$.

Such models cannot be isomorphic since isomorphisms preserve the truth of sentences.

Thus, $T$ is not $\kappa$-categorical.

$\blacksquare$


Source of Name

This entry was named for Jerzy Maria Michał Łoś and Robert Lawson Vaught.

This result is also known as Vaught's Test.