4

On pg. 26 of Mathematical Logic notes of Lou van den Dries, there is a definition, however as a beginner I do not understand the difference between $homomorphism$ and $strong$ $homomorphism$. Could you give me specific examples for both so that I can grasp the definition? (I do not understand Two definitions of strong homomorphism, too.)

Community
  • 1
Tedebbur
  • 353

1 Answers1

7

A homomorphism preserves relations: if a relation holds in the "source," it also holds in the "target." A strong homomorphisms preserves relations and failures of relations: if a relation fails in the source, it also has to fail in the target!

For example, let $G$ be a graph on two vertices $a$ and $b$, with no edges; and let $H$ be a graph on two vertices $c$ and $d$, with an edge from $c$ to $d$. (Formally: our language has a single binary relation symbol $R$. $G$ has universe $\{a, b\}$, and $R^G=\emptyset$; and $H$ has universe $\{c, d\}$, and $R^H=\{(c, d)\}$.) Then the map $a\mapsto c, b\mapsto d$ is a homomorphism from $G$ to $H$, but not a strong homomorphism.

Noah Schweber
  • 245,398
  • 2
    Note that we only see the distinction between homomorphism and strong homomorphism at the level of relations: if our language only has function/constant symbols (e.g. groups, rings, fields, . . .), then homomorphisms and strong homomorphisms are the same thing. – Noah Schweber Oct 28 '16 at 01:55
  • To be precise, in your example you are talking about directed graphs. – Eric Wofsey Oct 28 '16 at 01:56
  • @Eric Wofsey Does it have to be directed? I mean, can it be still an example if the graph is not directed? I want to say, yes. – Tedebbur Oct 28 '16 at 13:36
  • 1
    @Serpenche: Sure, if you let $R(x,y)$ be a binary relation that says "there is an edge between $x$ and $y$". You would just have $R^H={(c,d),(d,c)}$ instead then, since the edge goes both ways. – Eric Wofsey Oct 28 '16 at 22:17