3
$\begingroup$

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.

  • 3
    I think you need some additional assumptions. Consider $M \subsetneq N$ with $f$ the inclusion map, with a one-element relation $P(x)$ that is true for all of $M$ but false for $N-M$. Then $\forall x P(x)$ is true for $M$ but false for $N$.2011-12-06

1 Answers 1

1

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.

  • 0
    Just do the easy induction... this is something that you must do in order to become comfortable with basic model theoretic arguments. It will be a good exercise.2011-12-08