Lowenheim–Skolem Theorems

Downward Lowenheim–Skolem–Tarski Theorem

If a set of sentences $\Sigma$ in the language $\mathcal{L}$ has a model, then it has a model of cardinality at most $|\mathcal{L}|$.

Proof. Since $\Sigma$ has a model it is consistent. The Completeness Theorem then gives a model of cardinality at most $|\mathcal{L}|$. $\square$

Upward Lowenheim–Skolem–Tarski Theorem

If a set of sentences $\Sigma$ in the language $\mathcal{L}$ has an infinite model, then it has models of every cardinality $\kappa \ge |\mathcal{L}|$.

Proof. Let ${\mathcal{L}}^{\ast }$ be the expanded language ${\mathcal{L}}^{\ast }=\mathcal{L}\cup \{c_j:j\in K\},$ where the $c_j$ are new and distinct constant symbols, and the index set $K$ has cardinality $\kappa$. Note that $|{\mathcal{L}}^{\ast }|=\kappa$. Define ${\Sigma }^{\ast }=\Sigma \cup \{c_j\ne c_k:j\ne k\}.$ If $F$ is any finite subset of $\{c_j\ne c_k:j\ne k\}$ then $\Sigma \cup F$ has a model and so is consistent. Through compactness theorem, ${\Sigma }^{\ast }$ has a model, it follows that ${\Sigma }^{\ast }$ is consistent. (The assumption of infinite model is used in the construction of model of $\Sigma \cup F$.) By the Completeness Theorem, ${\Sigma }^{\ast }$ has a model $\mathfrak{A}$ of cardinality at most $\kappa$, and by ${\Sigma }^{\ast }=\Sigma \cup \{c_j\ne c_k:j\ne k\}$, the construction, for the sentence $c_j\ne c_k$, we get correspondingly $\mathfrak{A}(c_j)\ne \mathfrak{A}(c_k)$ in the model, so the cardinality is at least $\kappa$. Hence the cardinality of $\mathfrak{A}$ is precisely $\kappa$. By ignoring the interpretations of the new symbols $c_k$ we obtain a model $\mathfrak{A}$ of $\Sigma$ in the language $\mathcal{L}$ and which has cardinality $\kappa$. $\square$