Model Theory: Homomorphism preserves positive L-formulas

994 Views Asked by At

A formula $\varphi$ of a language $L$ is positive iff it can be obtained from atomic formulas by using $\vee, \wedge$. Let $M,N$ be $L$-structures and $f: M \rightarrow N$ be an $L$-homomorphism. How to show that for every positive $L$-formula $\varphi$ such that $M \models \varphi$, we have $N \models \varphi$.

I know that we can prove the base case for atomic formulas, and then the inductive step we need to show that homomorphisms preserve both finite and arbitrary joins and meets. But I do not know how to do this to get a neat proof. Any help is greatly appreciated.

1

There are 1 best solutions below

3
On

As ted points out, the hypothesis of your question is slightly off. It is not true in general that a homomorphism will preserve much beyond the quantifier-free formula. However, if you alter your hypothesis to assume that $\varphi$ is in fact a $\exists_1^+$-formula, then you can prove that it will be preserved under homomorphisms. A $\exists_1^+$-formula is exactly what you describe as a positive formula, except that it does not contain any occurrences of the symbol $\forall$.

Another thing you can do is to assume that your homomorphism $f$ is in fact surjective, in which case $f$ will preserve all positive formula. You can prove this by induction on the construction of the positive formulae.