1
$\begingroup$

I know the following fact (it can be proved using induction on the length of $\Phi$):

Let $\mathfrak{A,B}$ be algebraic structures (their domains are $A,B$), let $f:\mathfrak A\rightarrow\mathfrak B$ be their isomorphism and let $\Phi(x_1,\dots,x_n)$ be a formula, $a_1,\dots,a_n\in A$. Then $\mathfrak A\models\Phi(a_1,\dots,a_n)\Longleftrightarrow\mathfrak B\models\Phi(fa_1,\dots,fa_n)$.

I want to weaken this statement. My new version is (in the accepted notation):

Let $f:\mathfrak A\rightarrow\mathfrak B$ be a surjective homomorphism. Then $\mathfrak A\models\Phi(a_1,\dots,a_n)\Longrightarrow\mathfrak B\models\Phi(fa_1,\dots,fa_n)$.

The motivation for surjectivity is: let $\Phi=\forall x\Psi$.

$\mathfrak A\models\Phi(a_1,\dots,a_n)$ means that for every interpretation $\gamma:\{x\}\cup FV(\Phi)\rightarrow A$ such that $\gamma x_i=a_i, i\in\{1,\dots,n\},$ we have $\mathfrak A\models\Psi(x_1,\dots,x_n,x)[\gamma]$. Since $\Psi$ is shorter than $\Psi$, we can conclude that $\mathfrak B\models\Psi(fx_1,\dots,fx_n,fx)[f\circ\gamma]$.

The last thing we need to say that $\mathfrak B\models\Phi(fx_1,\dots,fx_n)$, as far as I understand, is surjectivity of $f$. Otherwise there may exist interpretation $\Gamma:\{x\}\cup FV(\Phi)\rightarrow B$ such that $\Gamma(x_i)=b_i, i\in\{1,\dots,n\}, \Gamma(x)=b$ and $f^{-1}(b_i)\ne\varnothing=f^{-1}(b), i\in\{1,\dots,n\},$ in which $\mathfrak B\nvDash\Psi(b_1,\dots,b_n,b)$.

Am I right? Or it is possible to omit surjectivity somehow?

$\endgroup$
1
  • 2
    $\begingroup$ Surjectivity is needed if $\Phi$ is a $\forall$ statement, but not if it is an $\exists$ statement. $\endgroup$ – Geoffrey Trang Feb 5 at 15:45
3
$\begingroup$

Let $f:\mathfrak A\rightarrow\mathfrak B$ be a surjective homomorphism. Then $\mathfrak A\models\Phi(a_1,\dots,a_n)\Longrightarrow\mathfrak B\models\Phi(fa_1,\dots,fa_n)$.

This is false. Your argument works for the inductive step of adding a universal quantifier, but not for the inductive step of adding a negation.

We say that a map $f:\mathfrak A\rightarrow\mathfrak B$ preserves a formula $\Phi(x_1,\dots,x_n)$ if $\mathfrak A\models\Phi(a_1,\dots,a_n)\Longrightarrow\mathfrak B\models\Phi(fa_1,\dots,fa_n)$.

If $f$ is not injective, it will fail to preserve the formula $\lnot(x_1=x_2)$. And if $f$ is an injective homomorphism which is not an embedding, then it will fail to preserve the formula $\lnot R(x_1,\dots,x_n)$ for some relation symbol $R$. So if a surjective homomorphism preserves all formulas, it must also be an injective embedding, so it must be an isomorphism!

Of course, there is a wider class of maps that preserve all formulas, namely the elementary embeddings. But for a general theory, there is not a much cleaner characterization of elementary embeddings than "those embeddings which preserve all formulas". A major reason to prove that a theory of interest has quantifier elimination (or is model-complete) is to obtain a more concrete understanding of the elementary embeddings between its models.

On the other hand, though surjective homomorphisms fail to preserve all formulas, we can characterize those formulas which are preserved by surjective homomorphisms. These are exactly the formulas which are equivalent to a positive formula: one built from atomic formulas using $\land$, $\lor$, $\forall$, and $\exists$ (but not $\lnot$).

And you ask about removing surjectivity. The formulas which are preserved by all homomorphisms are exactly those which are equivalent to a positive existential formula: one built from atomic formulas using $\land$, $\lor$, and $\exists$ (but not $\lnot$ or $\forall$).

These are two examples of a whole world of "preservation theorems" in model theory, which link up syntactic properties of formulas with semantic relationships between models. Good references are the model theory textbooks by Chang and Keisler and by Hodges.

$\endgroup$
1
  • $\begingroup$ Thank you very much for such an irrefragable answer! $\endgroup$ – Maxim Nikitin Feb 6 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.