# Is an inverse homomorphism always a homomorphism?

Given a homomorphism $h: \Sigma \rightarrow \Delta^*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image $\delta$), is the inverse homomorphism $h^{-1}$ a homomorphism?

Since a homomorphism maps every symbol of the input alphabet to one word from the output alphabet, the inverse transformation to $h$ is a substitution $\sigma: \delta \mapsto \Sigma$ (which maps one symbol to a whole language - alphabet $\Sigma$).

What would be an inverse homomorphism to $h': a \mapsto \epsilon, \forall a \in \Sigma$ or would such a transformation even exist?

EDIT: The question should have rather stated: "Is there always an inverse homomorphism?" There obviously isn't since only isomorphisms have their inverse homomorphisms.

• Ever heard the phrase "forgetful functor" before? – Pseudonym Jun 20 '15 at 23:54

If all letters map to the same letter $\delta$, then the inverse $h^{-1}(w) = \{w\mid h(x) = w\}$ is only defined (nonempty) when $w\in\delta^*$ and would consist of all strings in $\Sigma$ that have the same length as $w$. This is not an homomorphism, as these have only one image for each input. (Except for the very special case that $|\Sigma| = |\Delta| = 1$.)

The inverse is a substitution, mapping the letter $\delta$ to the set $\Sigma$ and all other letters in $\Delta$ to the empty set.

Obviously homomorphism $h'$ maps all strings to the empty string. Thus the inverse maps the empty string to $\Sigma^*$ and all other strings to the empty set. Silly mapping, but it is a finite state transduction (finite state automaton mapping with output).

Let me explicitly answer the question from the title. No. An homomorphism is one-to-one [meaning single valued], an inverse homomorphism in many cases is one-to-many [many-valued]. (If the inverse morphism is one-to-at-most-one [injective] again it usually is not a morphism, but the morphism is called a coding, because it can be "decoded").

• My mind must have been totally blown away, thank you. – Kyselejsyreček Jun 20 '15 at 12:52

The expression "closed under inverse homomorphism" is often used in formal languages: see for instance this question and this needs a clarification. As Hendrik Jan pointed out in his answer, a homomorphism is a map, but an "inverse homomorphism" is usually not.

To make the definition of "inverse" correct, one needs to view a homomorphism $h : A^* \to B^*$ as a relation on $A^* \times B^*$, whose graph is $$\{(x, h(x)) \in A^* \times B^*\mid x \in A^*\}$$ Now, the inverse of $h$ as a relation is the relation $h^{-1}$ defined by its graph as follows $$\{(h(x), x) \in B^* \times A^* \mid x \in A^*\}$$ and hence, for $y \in B^*$, $h^{-1}(y) = \{x \in A^* \mid h(x) = y \}$.