In this chapter, we will dive deeper into models (but still basic things). It’s mainly about the relationship between models.

Elementarity and Tarski’s Test

In the previous discussion, we have introduced the thing called embedding. However, the property of it is still not good enough for us. Thus, we introduce a stronger property called elementarity.

Generally, a map $h:A\rightarrow B$ between the universes of two structures $\mathfrak{A}$ and $\mathfrak{B}$ is called elementary if for all $a_1,\cdots,a_n\in A$, $\mathfrak{A}\models \varphi(a_1,\cdots,a_n)\Leftrightarrow \mathfrak{B}\models \varphi(h(a_1),\cdots,h(a_n)).$ If it is an embedding, then we say it is an elementary embedding. Furthermore, we say $\mathfrak{A}$ is the elementary substructure of $\mathfrak{B}$ if it is a substructure, and $\mathfrak{B}$ is also called the elementary extension of $\mathfrak{A}$, denoted as $\mathfrak{A}\prec\mathfrak{B}$.

The nontriviality of this definition lies in the fact that it preserves the truth value of existential and universal propositions. For example, $(\mathbb{N},\le)$ is a substructure of $(\mathbb{Z},\le)$, but the sentence $\exists x(x\le 0)$ lives differently in those two structures. The following theorem characterizes this, which is called the Tarski’s Test. Consider an $L$-structure $\mathfrak{A}$ and a subset $B$ of its universe, then $B$ is the universe of an elementary substructure $\mathfrak{B}$ of $\mathfrak{A}$ if and only if every $L(B)$-formula $\varphi(x)$ which is satisfied in $\mathfrak{A}$ can be satisfied by an element of $B$.

The part of “only if” is almost obvious. We shall see each $\varphi(x)$ satisfied in $\mathfrak{A}$ implies $\mathfrak{A}\models\exists x\varphi(x)$, then by elementarity, this sentence holds in $\mathfrak{B}$, and then an element exists to satisfy $\varphi(x)$.

To prove the part of “if”, we need to construct a substructure based on the subset, and then verify the elementarity. We can assign the interpretation of each constant directly from $\mathfrak{A}$. By the condition, for any $f\in L$ and $a_1,\cdots,a_n\in A$, the formula $f(a_1,\cdots,a_n)=x$ is always satisfied by some element of $B$, hence the set is closed under $f^\mathfrak{A}$. The interpretation of relations can be inherited from $\mathfrak{A}$ naturally.

Finally, let’s check the fact that $\mathfrak{A}\models\psi\Leftrightarrow\mathfrak{B}\models\psi$ for all $L(A)$-sentences $\psi$. When $\psi$ is atomic, this is clear from the construction. When $\psi$ is of the form $\psi=\neg\varphi$ or $\psi=\varphi_1\wedge\varphi_2$, it is quite easy to check by the table of truth values. When $\psi$ is of the form of $\psi=\exists x\varphi(x)$, if $\psi$ holds in $\mathfrak{A}$, then there is some $a$ in $A$ that satisfies $\varphi(x)$, then by the condition, some $b$ exists in $B$ to satisfy $\varphi(x)$. Hence $\exists x\varphi(x)$ holds in $\mathfrak{B}$. Conversely, when some $b$ in $B$ satisfies $\varphi(x)$, then $\mathfrak{A}\models\varphi(b)$ vacuously. Hence $\mathfrak{A}\models\exists x\varphi(x)\Leftrightarrow\mathfrak{B}\models\exists x\varphi(x)$. With the discussion previously on the negation normal form, we can induce the elementarity of $\mathfrak{B}$.

Here the Tarski’s Test is proved. It’s quite useful to generate elementary substructures, but the usage of it will be shown later. Now, another proposition named after Tarski is going to be introduced, which concerns chains.

For the reader’s convenience, we introduce the idea of chains first. A partial order $(I,\le)$ is called directed if for all $i,j\in I$, there exists some $k\in I$ such that $i\le k$ and $j\le k$. A family of structures $(\mathfrak{A}_i)_{i\in I}$ is said to be directed if for all $i\le j\in I$, $\mathfrak{A}_i\subset\mathfrak{A}_j$. Moreover, it is called a chain if $(I,\le)$ is a linear order, and it is called elementary if we replace all the $\subset$ by $\prec$ in the definition.

The Tarski’s Chain Lemma asserts that, the union of an elementary directed family of structures is an elementary extension of all its members. To prove this, we assume $(\mathfrak{A}_i)_{i\in I}$ is the family and $\mathfrak{A}=\bigcup_{i\in I}\mathfrak{A}_i$. For all $i\in I$ and tuple $\bar{a} \in A_i$, we need to verify that $\mathfrak{A}_i\models\varphi(\bar{a})\Leftrightarrow\mathfrak{A}\models\varphi(\bar{a}).$

For the situation where $\varphi(\bar{x})$ is an atomic formula, negation or a conjunction, it’s quite easy to see. When it’s of the form $\varphi(\bar{x})=\exists y\psi(\bar{x},y)$, we can see $\varphi(\bar{a})$ holds in $\mathfrak{A}$ if and only if some $b\in A$ exists with $\mathfrak{A}\models\psi(\bar{a},b)$. By the directedness, there always exists some $j\in I$ such that $\mathfrak{A}_i\prec\mathfrak{A}_j$ and $b\in A_j$. Hence $\mathfrak{A}\models\exists y\psi(\bar{x},y)\Leftrightarrow\mathfrak{A}_j\models\exists y\psi(\bar{x},y)\Leftrightarrow\mathfrak{A}_i\models\exists y\psi(\bar{x},y).$

The Compactness Theorem

After introducing the idea of elementarity, we can talk about the so-called Löwenheim-Skolem Theorem. But before detailed introduction, an important theorem is going to be shown first, as a preliminary, which is the Compactness Theorem.

We say a theory $T$ is finitely satisfiable if every finite subset of $T$ is satisfiable. The Compactness Theorem says that each finitely satisfiable theory is consistent. To prove this, we need to construct a structure for the theory $T$. One way is to extend this theorem to a “better” one, which we call a finitely complete Henkin theory, and find a model for it.

An $L$-theory $T$ is informally defined as finitely complete if it is finitely satisfiable and for every $L$-sentence $\varphi$, either $\varphi \in T$ or $\neg\varphi\in T$. Adding a set $C$ of new constant symbols into $L$ to get a new language $L(C)$, an $L(C)$-theory $T'$ is called a Henkin theory if for every $L(C)$-formula $\varphi(x)$, there exists some $c\in C$ such that $\exists x\varphi(x)\rightarrow \varphi(c)\in T'.$ The elements of $C$ are called the Henkin constants of $T'$.

Choose an arbitrary $L$-theory $T$, we now extend it to a finitely complete Henkin theory. We first construct a set of Henkin constants. Let $C_0 = \emptyset$, then inductively, we define a set of new symbols $C_{i+1} = \{c_{\varphi(x)};\varphi(x) \text{ a } L(C_i)\text{-formula}\}$, where $\varphi$ here is used as indices to separate constants. Then we get an ascending chain $C_0\subset C_1\subset \cdots$. Let $C$ be the union of such a chain. Then for any $L(C)$-formula $\varphi(x)$, there is a unique constant in $C$ corresponding to it. Therefore, we construct a set $T^H$ of Henkin axioms for all $L(C)$-formula $\varphi(x)$ that $\exists x\varphi(x)\rightarrow \varphi(c_\varphi(x))$. It’s obvious for one to extend a model of $T$ to a model of $T\cup T^H$, and this theory is finitely satisfiable. We can find a maximal finitely satisfiable theory $T^*$ containing $T\cup T^H$ by Zorn’s Lemma. Finally, consider some $L(C)$-sentence $\varphi$. If neither $\varphi$ nor $\neg\varphi$ belongs to $T^*$, then there must be a finite subset $S$ of $T^*$ such that both $S\cup\{\varphi\}$ and $S\cup\{\neg\varphi\}$ are inconsistent, and this leads to the fact that $S$ is not satisfiable, which contradicts the finite satisfiability of $T^*$. Hence it is finitely complete.

Now, we can then prove that every finitely complete Henkin theory has a model. To construct such a model, we first construct a universe to interpret all the Henkin constants. For $c,d\in C$, we define a relation $c\sim d\Leftrightarrow (c = d)\in T^*$. This is definitely an equivalence relation, which leads to equivalence classes of $c\in C$, denoted by $a_c$. The universe we need is defined as $A=\{a_c;c\in C\}$.

To find a corresponding structure $\mathfrak{A}$, we define

$$f^\mathfrak{A}(a_{c_1},\cdots,a_{c_n})=a_{c_0}\Leftrightarrow f(c_1,\cdots,c_n)=c_0\in T^*,$$ $$R^\mathfrak{A}(a_{c_1},\cdots,a_{c_n})\Leftrightarrow R(c_1,\cdots,c_n)\in T^* .$$

Noting that $\mathfrak{A}$ is just an $L$-structure, let $\mathfrak{A}^*=(\mathfrak{A},a_c)_{c\in C}$. To see that it is a model of $T^*$, we need to verify for every $L(C)$-sentence $\varphi$ that $\mathfrak{A}^*\models\varphi\Leftrightarrow \varphi\in T^*.$ When $\varphi$ is of the form $c=d$ or $R(c_1,\cdots,c_n)$, it is clear from the definition.

When $\varphi$ is of the form $\psi(f(c_1,\cdots,c_n))$ for a function symbol $f\in L$ and a formula $\psi(x)$, there is some $c_0=f(c_1,\cdots,c_n)\in T^*$. Then $\mathfrak{A}^*\models\varphi\Leftrightarrow\mathfrak{A}^*\models\psi(c_0)$ and $\varphi\in T^*\Leftrightarrow \psi(c_0)\in T^*$. Since $c_0$ here is not a function, it actually follows from the definition with $\psi(c_0)\in T^*\Leftrightarrow\mathfrak{A}^*\models\psi(c_0)$. Hence $\mathfrak{A}^*\models\varphi\Leftrightarrow \varphi\in T^*$.

When $\varphi$ is a negation or a conjunction, it’s very easy to check.

When $\varphi=\exists x\psi(x)$, we have

$$\begin{align*} \mathfrak{A}^*\models\varphi &\Leftrightarrow \mathfrak{A}^*\models\psi(c)\text{ for some } c\in C\\ &\Leftrightarrow\psi(c)\in T^*\text{ for some } c\in C\\ &\Leftrightarrow\varphi\in T^*. \end{align*}$$

Then by induction on the complexity of $\varphi$, we have checked that $\mathfrak{A}^*$ is the model of $T^*$. And by simply forgetting the Henkin constants, we get a model of $T$, which is a finitely satisfiable theory. Therefore, every satisfiable theory is consistent, which is the statement of the Compactness Theorem.

Ultraproduct: Another Proof

The proof above is quite fabulous, but I would say, it’s not elegant. Here, another proof can be given with the idea of ultraproduct, which is more “algebraic”. One can simply skip since this is not the main thread.

Firstly, we need to define the idea of a filter. For a given set $I$, a filter $\mathcal{F}$ is a collection of subsets of $I$ ($\mathcal{F}\subset\mathcal{P}(I)) satisfying

1. $\emptyset\not\in\mathcal{F}$ and $I\in\mathcal{F}$,
2. For $A,B\in\mathcal{F}$, $A\cap B\in\mathcal{F}$,
3. For $A\in\mathcal{F}$ and $B\subset I$, $A\subset B$ implies $B\in\mathcal{F}$.

Simply put, the idea of filter defines the “inescapable” part of a set, which may relate to the idea of “almost everywhere”. Especially, if for any subset $A\subset I$, either $A\in\mathcal{F}$ or $I\setminus A\in\mathcal{F}$ holds, then we say it is an ultrafilter, which means we can accurately distinguish whether a part is “important”. And it’s clear that the ultrafilter is exactly the maximal filter of the ascending chain containing itself (because it contains exactly all the situations).

For a family of $L$-structures $\{\mathfrak{A}_i\}_{i\in I}$, there is a Cartesian product $A=\prod_{i\in I}A_i$. An ultrafilter $\mathcal{U}$ of $I$ defines an equivalence relation of $A$ by (most parts of entries are equal) $(a_i)_{i\in I}\sim (b_i)_{i\in I}\Leftrightarrow \{i\in I;a_i=b_i\}\in \mathcal{U}.$

Then the quotient set $A/\sim$ of equivalence classes $[(a_i)_{i\in I}]$ is the universe of an $L$-structure, called the ultraproduct, denoted as $\prod_{i\in I}\mathfrak{A}_i/\mathcal{U}$, by letting

1. for constants $c$, $c^{\prod_{i\in I}\mathfrak{A}_i/\mathcal{U}}=[(c^{\mathfrak{A}_i})_{i\in I}]$,
2. for functions $f$ and elements $[(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}]$, $f^{\prod_{i\in I}\mathfrak{A}_i/\mathcal{U}}\left([(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}]\right)=[(f^{\prod_{i\in I}\mathfrak{A}_i/\mathcal{U}}(a^1_i,\cdots,a^n_i))_{i\in I}]$,
3. for relations $R$ and elements $[(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}]$, $R^{\prod_{i\in I}\mathfrak{A}_i/\mathcal{U}}([(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}])\Leftrightarrow \{i\in I; R^{\mathfrak{A}_i}(a^1_i,\cdots,a^n_i)\}\in\mathcal{U}$.

These definitions seem to be complicated, but one will find it clear by realizing symbols are explained as the Cartesian product of what it is explained in “almost every” given structures.

With the definition of ultraproduct, we have the thing called Łos’s Theorem. Given a family of $L$-structures $\{\mathfrak{A}_i\}_{i\in I}$ and an ultrafilter $\mathcal{U}$ of $I$, the ultraproduct $\mathfrak{A}$ holds, for every $L$-formula $\varphi(x_1,\cdots,x_n)$ and $[(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}]\in A=\prod_{i\in I}A_i/\sim$, that $\mathfrak{A}\models\varphi([(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}])\leftrightarrow\{i\in I;\mathfrak{A}_i\models\varphi(a^1_i,\cdots,a^n_i)\}\in\mathcal{U}.$

Now, let’s think about the Compactness Theorem. If the $L$-theory $T$ is finitely satisfiable, then there is a set $I$ of the finite subsets of $T$, and for each finite subset $i$, there is a model $\mathfrak{A}_i$ of $i$.

Construct a class of subsets of $I$ that $S=\{I_\sigma=\{i\in I,\sigma\in i\};\sigma\in T\}$. It is clear that for the intersection of any finite elements of $S$ is not empty (this is the property called finite intersection property), then we can construct a filter containing $S$ on $I$ by $\mathcal{F}=\{A;A\subset I \text{ and } \exists A_1,\cdots,A_n\in S\text{ such that } A\supset A_1\cap \cdots\cap A_n\}.$

Therefore, there is an ultrafilter of $I$. Then, an ultraproduct can be constructed. And it is easy to check by Łos’s theorem that this ultraproduct is the model of $T$. Hence the Compactness Theorem is proved.

Final Preparations

It’s so close to the end of this chapter, the Löwenheim-Skolem Theorem. But still, we have some necessary lemmas to be prepared.

Recall that the symbol $\mathfrak{A}_A$ is the extended structure of the extended language $L(A)$. The models of $Th(\mathfrak{A}_A)$ are exactly the structures of the form $(\mathfrak{B},h(a))_{a\in A}$ for elementary embeddings $h:\mathfrak{A}\rightarrow\mathfrak{B}$.

It is vacuous that $(\mathfrak{B},h(a))_{a\in A}$ is a model of $Th(\mathfrak{A}_A)$. Suppose there is a model $\mathfrak{C}$. For each $a\in A$, choose $c\in \{c\in C;\mathfrak{C}\models\varphi(c)\text{ where }\varphi(x)\text{ is an }L(A)\text{-formula with }\mathfrak{A}\models\varphi(a) \}$, and then construct a function that $h(a)=c$. Then $h$ is an elementary embedding we need.

Now consider an $L$-structure $\mathfrak{A}$. Let $S$ be a subset of $A$. Then there is an elementary substructure $\mathfrak{B}$ containing $S$ and $|\mathfrak{B}|\le \max(|S|,|L|,\aleph_0)$. Here $|L|$ stands for the number of constants, functions and relations.

To prove this, we need to construct such a substructure. Let $S_0= S$, then inductively, let $S_{i+1}=S_i\cup\{a_\varphi\in A;\varphi\text{ a }L(A)\text{-structure and}\mathfrak{A}\models\varphi(a)\}$. Then the union of $S_n$, denoted as $B$, is the universe of a substructure $\mathfrak{B}$ by the Tarski’s Test.

Now we compute the cardinality of $B$. Since the construction of $\varphi(x)$ is a finite sequence of symbols in $L$, then we can assert that there are $\max(|L|,\aleph_0)$ many $L$-formulas. For each $n$, there are $\max(|S_n|,|L|,\aleph_0)$ many $L(S_n)$-formulas. Therefore inductively, there are $\max(|S|,|L|,\aleph_0)$ formulas. Hence $|\mathfrak{B}|\le \max(|S|,|L|,\aleph_0)$.

The Löwenheim-Skolem Theorem

Finally, we arrive at the climax of this chapter. Simply put, this theorem asserts that, in the context of the first-order logic, once an $L$-theory has an infinite model, then there is a model with cardinality of any infinite cardinal.

Formally, let $\mathfrak{A}$ be an infinite $L$-structure, $S$ a subset of $A$, $\kappa$ an infinite cardinal.

1. (Downward) If $\max(|S|,|L|)\le\kappa\le|A|$, then there is an elementary substructure $\mathfrak{B}$ of cardinality $\kappa$ containing $S$.
2. (Upward) If $|A|\le\kappa$, then there is an elementary extension $\mathfrak{B}$ of cardinality $\kappa$.

To prove the downward one, we choose a subset $S'$ of $A$ with cardinality exactly $\kappa$, then apply the result of the last section, an elementary substructure containing $S'$ exists.

To prove the upward one, we construct a set $C$ with cardinality $\kappa$. A theory can then be given as $Th(\mathfrak{A}_A)\cup\{\neg c=d;c\not= d\in C\}$. Obviously, it is finitely satisfiable, and then the Compactness Theorem implies a structure $\mathfrak{K}$ exists with cardinality greater than $\kappa$. By the result stated in the last section, $\mathfrak{A}\prec\mathfrak{K}$. Finally, by the downward part, we can obtain an elementary extension $\mathfrak{B}$ with exactly $|B|=\kappa$.