In Enderton p. 96, the homomorphism theorem implies (I state only the essential): Let $h:\cal{A} \rightarrow {\cal B}$ be an epimorphism (i.e., a surjective homomorphism). For any sentence $\alpha$ not containing the equality symbol: $\vDash_{\cal A} \alpha \text{ iff } \vDash_{\cal B} \alpha$. On the other hand, Lyndon’s Positivity Theorem, as stated, for example by B. Rossman, implies that a sentence $\alpha$ that is not equivalent to a positive sentence (a sentence without the negation symbol), will not be preserved by at the least one epimorphism $h$. This seems to be a contradiction, but it's not. Let $P$ be a predicate symbol in the signature. For $h$ to be a homomorphism in Enderton, it is required on $P$ that $$\langle a_1, \ldots, a_n\rangle \in P^{\cal A} \Leftrightarrow \langle h(a_1), \ldots, h(a_n)\rangle \in P^{\cal B},$$ whereas being a homomorphism in the statement of Lyndon's theorem requires $$\langle a_1, \ldots, a_n\rangle \in P^{\cal A} \Rightarrow \langle h(a_1), \ldots, h(a_n)\rangle \in P^{\cal B}.$$ Moreover, they are not over the same logic. Lyndon's theorem is within FOL without equality as discussed here, whereas Enderton's homomorphism theorem is within FOL with equality. However, this last point is not the key issue, because it's easy to see what's happen with the homomorphism theorem within a logic without equality.

Is there a way to see what's going on here? In which applications the definition of homomorphism used in Enderton is useful? For example, does it have some significance in theory of database where Lyndon's theorem is useful? The proof of the homomorphism theorem in Enderton is very easy. It's not a deep theorem, but it does not mean that it cannot be useful. Lyndon's Positivity theorem is not easy to prove. I haven't gone trough the proof. I don't have any intuition about what's going on.

Note: The definition of homomorphism used in Enderton is the one obtained when you represent predicates as functions that return True or False and use the same criteria on these functions as on any other functions, except that you naturally fix the homomorphism to be the identity function on the shared value True and False. In computer science, seeing a predicate as a function that returns a truth value is very natural. Therefore, it would be surprising that Enderton's definition, which I suspect existed way before Enderton, has no useful applications. Another way, of putting this is that Enderton definition requires that, if the predicate fails in the source, it must also fail in the target, which is a natural requirement.

  • 3
    $\begingroup$ Enderton's definition of homomorphism doesn't sound right. $\endgroup$ Jan 30 at 9:28
  • $\begingroup$ OK, let's make one thing clear. The definition is a definition and it might not be as useful as another, which is part of the question, but it cannot be wrong or not right. $\endgroup$
    – Dominic108
    Jan 30 at 17:51
  • 2
    $\begingroup$ Let's put it this way. The "strong" condition doesn't seem natural (it treats equality differently than the other predicates). It would be interesting to see a natural example. Note also that you obtain strong homomorphisms from weak homomorphisms by expanding the $L$ with the negations of the relations in $L$. $\endgroup$ Jan 31 at 8:36
  • $\begingroup$ Examples of useful application is part of the question. $\endgroup$
    – Dominic108
    Feb 1 at 17:24
  • $\begingroup$ Logic is a model of deductive thought or computing process. True, False is a common way of evaluating the world. This suggests, though it's not self-referentiall, that the language can have functions that return True or False. Thus far, every thing is natural. When you do not consider these functions as any other functions, it becomes special. For example, the real numbers can also be an auxiliary structure, just as the booleans True and False. It would be special, though perhaps useful in some applications, not to consider the functions that return real numbers as any other functions. $\endgroup$
    – Dominic108
    Feb 2 at 14:48


Your Answer

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

Browse other questions tagged or ask your own question.