4

I'm taking a college course about first order logics right now and the teacher emphasised the difference between a homomorphism and a strong homomorphism. He also asked us to provide a example of a injective homomorphism that isn't an embedding which is a injective strong homomorphism.

So the difference between a regular homomorphism and a strong homomorphism is that for a regular homomorphism if a relation holds in the source structure it also has to hold in the images of those elements, and the other way is not required. A strong homomorphism also demands that if a relation is true (or false) in the image it also has to be true (or false) in the source. So for a function $h:A\rightarrow B$ to be a strong homomorphism the following has to be true: $R^A(a_1,...,a_n)$ IFF $R^B(h(a_1),...,h(a_n))$

The problem is that since it has to be an injection and a homomorphism (so if $R^A(a_1,...,a_n)$ then $R^B(h(a_1),...,h(a_n))$) I always also make a function for which if $R^B(h(a_1),...,h(a_n))$ then $R^A(a_1,...,a_n)$ also holds true and i get a strong homomorphism.

I already tried it with the usual sets $N,Z,Q$ and relations $<,>,=$ but it seems like something more abastract is needed for this one.

Can someone please give me a hint and prefereably not a complete answer? Thanks in advance!

Indinellow
  • 41

2 Answers2

3

The hydrophobic-polar protein folding model is actually an example of this. The function $h$ maps the space $\{0,1,2,\dots,n-1\}$ to $\mathbb Z\times\mathbb Z$ and the relations express that the Euclidean distance is 1 in each space.

The weak homomorphism property says that the protein folding must map amino acids that are adjacent in the protein to adjacent locations in $\mathbb Z\times\mathbb Z$.

The counterexamples to strong homomorphism in this case are exactly the places where two amino acids are next to eachother (and can form a bond) without having polypeptide bonds, i.e., without being next to each other in the sequence.

A minimal example: $$\begin{eqnarray}0 & \to & 1\\ & & \downarrow\\ 3 &\leftarrow &2\\ \end{eqnarray}$$ Here $0$ and $3$ are your desired counterexample.

Bjørn Kjos-Hanssen
  • 2,915
1

It should be possible to create a contrived example by picking the relations in the signature just for the purpose of satisfying the condition of homomorphism but not strong homomorphism. Try looking at finite sets, so that you can define a relation $R(x)$ on each element manually in order to control the properties.

Once you have a contrived finite example, that might help you construct examples from more natural mathematical objects, or understand why each of the examples you tried failed.

Chessanator
  • 5,448
  • I tried to keep this vague so it was just a hint. I can fill in some more details if needed. – Chessanator Feb 16 '19 at 12:57
  • Thank you. I have a follow up question. So the relations don't have to be the same on the two signatures? At least i don't see such a requirement anywhere in my books. If so it should be very easy to make weird signatures and relations to get what i want. My example would be the following: signature A is $N^3$ with a relation that checks the first two coordinates of a tuple, and the signature B is also $N^3$ but the relation only checks the first coordinate of the tuple. If i say the function h just changes the first two coordinates that should be the answer. – Indinellow Feb 16 '19 at 14:48