Franklin's Notes


Generated submodel

In Model Theory for First-order Logic , if $\mathfrak{A}$ is a model for $\mathscr{L}$ and $X$ is a nonempty subset of $A$, then the submodel generated by $X$ is the submodel $\mathfrak{B}\subset\mathfrak{A}$ whose universe $B$ is equal to In other words, $\mathfrak{B}$ is the "smallest" submodel of $\mathfrak{A}$ whose universe contains the set $X\subset A$. The functions and relations of $\mathfrak{B}$ may be defined by the restriction of the functions and relations of $\mathfrak{A}$ to the set $B\subset A$. Additionally, $\mathfrak{B}$ necessarily contains all constants of $\mathfrak{A}$, since all submodels of $\mathfrak{A}$ contain its constants. The universe $B$ can also be expressed as follows: for clearly this set is contained in the universes of all submodels of $\mathfrak{A}$ which contain $X$, but it is itself also the universe of a submodel of $\mathfrak{A}$.

Chang and Kiesler use generated submodels to define weaker versions of equivalence between models , which can be usefil for proving elementary equivalence of models. He defines the relationships $\equiv_n$ recursively as follows:

As a simple minimalist example, consider the models $\mathfrak{A}=\langle A, 0\rangle$ and $\mathfrak{B}=\langle B,0\rangle$, where $0\in A$ and $0\in B$. If $A={0}$ and $B={0,1}$, then $\mathfrak{A}\equiv_0\mathfrak{B}$ because the submodel of $\mathfrak{B}$ generated by its constants is precisely $\mathfrak{B}$, however, $\mathfrak{A}\not\equiv_1\mathfrak{B}$ because the expansion of $\mathfrak{B}$ which includes $1$ as a constant is not isomorphic to any expansion of $\mathfrak{A}$ (in particular, because $A$ does not contain any $2$ distinct elements). Similarly, if $|A|=n$ and $|B|=n+1$, then we will have that $\mathfrak{A}\equiv_{n-1}\mathfrak{B}$ but $\mathfrak{A}\not\equiv_{n}\mathfrak{B}$.

Theorem 1. If $\mathfrak{A}$, $\mathfrak{B}$ are models of some language $\mathscr{L}$ and $\mathfrak{A}\equiv_n\mathfrak{B}$, then every sentence of $\mathscr{L}$ in prenex form with at most $n$ quantifiers has the same truth value in $\mathfrak{A}$ and $\mathfrak{B}$.

Proof. First, we verify the base case in which $\mathfrak{A}\equiv_0\mathfrak{B}$. If this equivalence holds, then the submodels of $\mathfrak{A}$ and $\mathfrak{B}$ generated by their constants are isomorphic (or they have no constants). Interpretations of all terms taking the form $t[c_1\cdots c_k]$ must be in these submodels, and since all atomic formulas take one of the two forms $t_1\equiv t_2$ or $R(t_1\cdots t_m)$, we have that all atomic sentences must have the same truth values in these submodels. Additionally, since all sentences without quantifiers are simply sentential combinations of atomic sentences, we have that they must also have the same truth values in these generated submodels. Thus, we have that $\mathfrak{A}\equiv_0\mathfrak{B}$ implies that the quantifier-less sentences of $\mathscr{L}$ have the same truth values in $\mathfrak{A}$ and $\mathfrak{B}$, verifying the base case.

Now, suppose that the claim holds for case $n$, and we shall show that this implies its truth for case $n+1$. Suppose that $\mathfrak{A}\equiv_{n+1}\mathfrak{B}$. Let $\varphi$ be a formula in prenex form with $n$ quantifiers and one free variable, so that $\exists v ~ \varphi(v)$ is a sentence in prenex form with $n+1$ quantifiers. If $\exists v ~ \varphi(v)$ holds in $\mathfrak{A}$, then there is some $x\in A$ for which $\varphi[x]$ holds. This means that if a constant symbol $c_x$ is added to the language with interpretation $x$ in $\mathfrak{A}$, then $\varphi(c_x)$ is a sentence in this new language in prenex form with $n$ quantifiers, and it holds in $(\mathfrak{A},x)$. However, since $\mathfrak{A}\equiv_{n+1}\mathfrak{B}$, there exists $y\in B$ such that all sentences in prenex form with $n$ quantifiers have the same truth value in $(\mathfrak{A},x)$ and $(\mathfrak{B},y)$. Thus, there exists $y\in B$ such that $\varphi[y]$ holds, and we have that $\exists v ~ \varphi(v)$ holds in $\mathfrak{B}$.

We have shown that $\exists v ~ \varphi(v)$ holding in $\mathfrak{A}$ implies that it holds in $\mathfrak{B}$. From this, we may prove several other things:

To summarize, we now have that:

But all formulas in prenex form with at most $n+1$ quantifiers can be written in the form $\exists v ~ \varphi(v)$ or $\forall v ~ \psi(v)$ for some formula $\varphi$ or $\psi$ with at most $n$ quantifiers. Hence, the claim for $\equiv_{n+1}$ is entailed by the claim for $\equiv_n$, and the result follows by induction. $\blacksquare$

Since every sentence has at most finitely many quantifiers, we have the following consequence of the above theorem:

Theorem 2. If two models satisfy $\mathfrak{A}\equiv_n\mathfrak{B}$ for all $n\in\mathbb N$, then they are elementarily equivalent .

This is a powerful tool for proving that two models are elementarily equivalent. In essence, all that is necessary to show that two models $\mathfrak{A},\mathfrak{B}$ are equivalent is to show that given any finite sequence of elements $x_1,x_2,...,x_n\in A\cup B$, it is possible to find elements $y_1,y_2,...,y_n\in A\cup B$ such that the elements $x_i,y_i$ are in opposite universes (i.e. $(x_i,y_i)$ is either in $A\times B$ or $B\times A$) for all $i$, and such that the submodels generated by the constant symbols of the expansions of $\mathfrak{A},\mathfrak{B}$ obtained by adding these elements as corresponding interpretations of the same constant symbol are isomorphic to each other.

Let's look at an example: consider $\mathfrak{A}=\langle\mathbb{N},\leq\rangle$ and $\mathfrak{B}=\langle\mathbb{Z},\leq\rangle$. These models are not elementarily equivalent - for instance, the sentence is true in $\mathfrak{A}$ but not in $\mathfrak{B}$. This means that $\mathfrak{A}\not\equiv_n\mathfrak{B}$ for some value of $n$. Let's figure out exactly where this breaks down.

Clearly, we have that $\mathfrak{A}\equiv_0\mathfrak{B}$, because neither model has any constants, meaning that their submodels generated by constant symbols are empty and therefore trivially isomorphic. We also have that $\mathfrak{A}\equiv_1\mathfrak{B}$. Why is this the case? Given any element $a\in\mathbb N$, the submodel of $(\mathfrak{A},a)$ generated by the set of constant symbols ${a}$ simply has universe ${a}$ (since there are no function symbols), and similarly for $\mathfrak{B}$. No matter what element $b\in\mathbb Z$ we choose, the models $\langle {a},\leq, a\rangle$ and $\langle {b},\leq, b\rangle$ will be trivially isomorphic.

However, $\mathfrak{A}\not\equiv_2\mathfrak{B}$. Suppose we choose to adjoin $0$ as a constant to $\mathfrak{A}$, obtaining the expansion $(\mathfrak{A},0)$, and simultaneously choose some $b\in\mathbb Z$ as the corresponding constant to form the expansion $(\mathfrak{B},b)$. No matter what $b\in\mathbb Z$ we choose, it will never be the case that $(\mathfrak{A},0)\equiv_1 (\mathfrak{B},b)$. For if we then choose to adjoin $b'=b-1$ to $(\mathfrak{B},b)$ as a constant, obtaining the expansion $(\mathfrak{B},b,b')$, there is no way to choose a corresponding constant $a'\in\mathbb N$ for which the two constant-generated models are isomorphic, because $0$ corresponds to $b$, and $b'$ is less than $b$, but there is no $a'\in\mathbb N$ with $a'$ less than $0$.

model-theory

first-order-logic

back to home page