# Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms

I want to prove that $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ is not always true.

If $L_1 = (ab)^*$ and $L_2 = (ba)^*$ with mapping $H(a) = 1$ and $H(b) = 1$, $H(\epsilon) = 2$, then $H(L_1 \cap L_2) = 2$ while $H(L_1) \cap H(L_2) = (11)^*$.

Is the above example correct to prove the above statement? Is it allowed to map two symbols to one same symbol?

• A homomorphism always satisfies $H(\epsilon) = \epsilon$. Other than that, the proof works. I explained in detail what a homomorphism is in my answer. – Yuval Filmus Jan 19 '18 at 12:38

Given two finite non-empty alphabets $\Sigma,\Delta$, a homomorphism is a mapping $h\colon \Sigma^* \to \Delta^*$ that satisfies the following two properties:

• $h(\epsilon) = \epsilon$.
• $h(xy) = h(x) h(y)$.

(Actually the first property follows from the second, since it implies that $h(\epsilon) = h(\epsilon \epsilon) = h(\epsilon) h(\epsilon)$, and so $h(\epsilon) = \epsilon$.)

It is not hard to show that $h$ is determined by its value on letters of $\Sigma$. Indeed, if $w = \sigma_1\ldots \sigma_n$, where $\sigma_1,\ldots,\sigma_n \in \Sigma$, then $h(w) = h(\sigma_1) \ldots h(\sigma_n)$. Conversely, if $h_0\colon \Sigma \to \Delta^*$, then the mapping $h(\sigma_1 \ldots \sigma_n) = h_0(\sigma_1) \ldots h_0(\sigma_n)$ defines a homomorphism. In formal language theory, one often identifies $h$ and $h_0$.

• So the mapping need not be one to one right ? – Rajesh R Jan 19 '18 at 13:14
• I gave a complete definition. Any mapping that satisfies this definition is a homomorphism. – Yuval Filmus Jan 19 '18 at 13:15
• Ok, after applying the definition, it seems that homomorphism need not be one to one. But this answer says it has to be one to one cs.stackexchange.com/questions/43779/… – Rajesh R Jan 19 '18 at 13:22
• Hendrik meant that $h(w)$ is single-valued, whereas $h^{-1}(w)$ is many-valued, i.e., a set of words rather than a single word. – Yuval Filmus Jan 19 '18 at 13:26
• Ohh. I thought that he meant the function or mapping has to be injective. – Rajesh R Jan 19 '18 at 13:29