Quantifier Free Formula is Preserved by Superstructure

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal M, \mathcal N$ be $\mathcal L$-structures such that $\mathcal M$ is a substructure of $\mathcal N$.

Let $\map \phi {\bar x}$ be a quantifier-free $\mathcal L$-formula, and let $\bar a \in\mathcal M$.


Then $\mathcal M \models \map \phi {\bar a}$ if and only if $\mathcal N \models \map \phi {\bar a}$.


Proof

The proof is done by induction on complexity of formulas.


Note that since interpretations of terms with parameters from $\mathcal M$ are preserved when passing to superstructures, we have that $\map {t^\mathcal M} {\bar a} = \map {t^\mathcal N} {\bar a}$ whenever $t$ is an $\mathcal L$-term and $\bar a$ is in $\mathcal M$.


First, we verify the theorem for atomic formulas. This is the base for the inductive proof.


Suppose $\phi$ is $t_1 = t_2$ for terms $t_1$ and $t_2$:

We have $\mathcal M \models \map \phi {\bar a}$ if and only if $\mathcal M \models \map {t_1} {\bar a} = \map {t_2} {\bar a}$.

The right hand side of this holds if and only if $\map {t_1^\mathcal M} {\bar a} = \map {t_2^\mathcal M} {\bar a}$.

By the note above, this in turn holds if and only if $\map {t_1^\mathcal N} {\bar a} = \map {t_2^\mathcal N} {\bar a}$, which is equivalent to $\mathcal N \models \map \phi {\bar a}$.


Suppose $\phi$ is $R(t_1, \dots, t_n)$ where $R$ is a relation symbol and each $t_i$ is a term:

We have:

$\mathcal M \models \map \phi {\bar a}$ iff $\paren {\map {t_1^\mathcal N} {\bar a}, \dots, \map {t_n^\mathcal N} {\bar a} } \in R^\mathcal M$

Since $\mathcal M$ is a substructure of $\mathcal N$, the interpretation of $R$ in $\mathcal N$ must extend $R^\mathcal M$, so the right side of this statement is equiavlent to:

$\paren {\map {t_1^\mathcal N} {\bar a}, \dots, \map {t_n^\mathcal N} {\bar a} } \in R^\mathcal N$

By the note above, this in turn is equivalent to:

$\paren {\map {t_1^\mathcal N} {\bar a}, \dots, \map {t_n^\mathcal N} {\bar a} } \in R^\mathcal N$

which is the same as:

$\mathcal N \models \map \phi {\bar a}$


Having verified the theorem for the atomic formulas, we proceed with the inductive step of the proof.


Suppose the result holds for $\psi$, and consider $\neg \psi$:

We have $\mathcal M \models \neg \map \psi {\bar a}$ if and only if $\mathcal M \not \models \map \psi {\bar a}$.

By the inductive hypothesis, the right side of this statement is equivalent to $\mathcal N \not\models \map \psi {\bar a}$, and so the result follows.


Suppose the result holds for $\psi_1$ and $\psi_2$, and consider $\psi_1 \wedge \psi_2$:

We have $\mathcal M \models \map {\psi_1} {\bar a} \wedge \map {\psi_2} {\bar a}$ if and only if $\mathcal M \models \map {\psi_1} {\bar a}$ and $\mathcal M \models \map {\psi_2} {\bar a}$.

By the inductive hypothesis, the right side of this is equivalent to $\mathcal N \models \map {\psi_1} {\bar a}$ and $\mathcal N \models \map {\psi_2} {\bar a}$, and so the result follows, completing the proof.

$\blacksquare$