Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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$. –  Ted Dec 6 '11 at 7:26
add comment

1 Answer 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.

share|improve this answer
    
Can you prove it under Ted's assumption ? I mean you follow your solution with your assumption so that I can understand the details of your proof. Thanks a lot. –  Alexander Razb Dec 7 '11 at 4:44
    
I edited the quesdtion, I removed $\exists$ and $\forall$. Anyone can give a proof ? –  Alexander Razb Dec 7 '11 at 23:33
    
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. –  student555 Dec 8 '11 at 8:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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