I was trying to understand strong homomorphisms conceptually but I was having some difficulties and thought that concrete examples would be useful.

I think I understand the definitions but it felt too abstract and had a hard time really feeling a had a grasp of it and I was hoping an example would help.

I was particularly interested in understanding the difference between homomorphism, strong homomorphism and isomorphism (and why an IFF condition on the relation did NOT imply the homomorphism was bijective).

Recall the definition of homomorphism:

  • $(a_1,\dots,a_m) \in R^{\mathcal{A}} \implies (ha_1,\dots,ha_m) \in R^{ \mathcal{B} }$
  • $h(F^{\mathcal{A}}(a_1, \dots , d_n ) ) = F^{\mathcal{B}}(ha_1, \dots , ha_m )$

for different L-structures $\mathcal{A} = (A, (R^{\mathcal A})_{R \in L^r}, (F^{\mathcal A})_{F \in L^f} )$, $\mathcal{B} = (B, (R^{\mathcal B})_{R \in L^r}, (F^{\mathcal B})_{F \in L^f} )$.

Being strong only adds requirement that the relation becomes an IFF (as far as I know).

  • $(a_1,\dots,a_m) \in R^{\mathcal{A}} \iff (ha_1,\dots,ha_m) \in R^{ \mathcal{B} }$

intuitively for me I decided to expand what that really means:

  • $(a_1,\dots,a_m) \in R^{\mathcal{A}} \implies (ha_1,\dots,ha_m) \in R^{ \mathcal{B} }$

AND also:

  • $(ha_1,\dots,ha_m) \in R^{ \mathcal{B} } \implies (a_1,\dots,a_m) \in R^{\mathcal{A}} $

but then I noticed that considering the contrapositive of the second statement would yield 1 definition of strong homomorphism only in terms of the LHS (i.e. a consistent way to think about it):

  • $(a_1,\dots,a_m) \not \in R^{\mathcal{A}} \implies (ha_1,\dots,ha_m) \not \in R^{ \mathcal{B} }$

which actually made sense (in an abstract sense). If we don't have a relation hold in the original set, then it won't hold in the target set. Intuitively I imagined that everywhere were A didn't have a tuple wrt its relation then it wouldn't be in the target set either. I guess it makes sense because we could have some additional relations in B that weren't related at all by the homomorphism. I did try constructing an example with discrete sets and then considering a binary relation and then shading the table $A \times A$ and $ B \times B $ such that I could get a strong homomorphism by coloring out entries in the table B and a only a homomorphism by inducing relations on B unrelated to the original relation on A.

However, it felt really artificially created. If you have one that is more natural (and hence easier to remember, something like "yes of course"), that would be awesome.

Artificially created ones are also welcome, especially if they are small and simple to understand.

Something that is still slightly foggy is why this IFF on relations does not induce a bijection on the two sets. I guess it's because even though they might have "matching relation tables" (thinking of the relations as binary tuples we coloring in when its present or not) it does not mean that the tables must be of the same size? It's still too abstract for me to really be convinced I get it...


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.