Homomorphism

A stronger form of relationship (than equivalence) between algebras which does assert such a structure preserving property is homomorphism. Suppose two algebras $\cal{A}$ and $\cal B$ as defined above are denoted by the same signature. The operations $\omega_{A_k} \in \Omega_A$ from algebra $\cal{A}$ and $\omega_{B_k} \in \Omega_B$ from algebra $\cal B$ of arity k can therefore be put into a one-to-one correspondence as noted above.

Consider a mapping $h : A \rightarrow B$ between the carrier sets A and B. Then his a homomorphism from algebra $\cal{A}$ to algebra $\cal B$if for every operation $\omega_A \in \Omega_A$ of arity k with corresponding operation $\omega_B \in \Omega_B$

$$h(\omega_A(a_1,a_2, \dots , a_k)) = \omega_B(h(a_1),h(a_2), \dots , h(a_k))$$ (10.1)

where $a_i \in A$ and $1 \le i \le k$. To be a homomorphism, this result must hold for all operations of every arity.

This rather formidable equation states the following. The outcome of applying an operation $\omega_A$ from $\cal{A}$ to values of the carrier of A and then finding the result when the mapping h is applied is the same as finding the transform of the values of A using h first and then applying the corresponding operation $\omega_B$ of $\cal B$.

(Note that the existence of a homomorphism from $\cal{A}$ to $\cal B$ does not imply that a homomorphism exists from $\cal B$ to $\cal{A}$ and that although, by convention, we talk about a homomorphism h from one algebra $\cal{A}$ to another algebra $\cal B$, and write $h : {\cal A} \rightarrow {\cal B}$, the mapping h is strictly a mapping between the carrier sets. Also $h : A \rightarrow B$is only well defined if the operations $\omega_A \in \Omega_A$ and $\omega_B \in \Omega_B$ are in one-to-one correspondence).

We can get a feel for the nature of homomorphisms and the meaning of equation (10.1) by looking at one particular homomorphism that has been used over the years to ease the effort involved in multiplying real numbers.

Consider the (homogeneous) algebras $\cal{A}$ and $\cal B$

${\cal A} = [\Real^+, \{ \times \}] \qquad ; \qquad {\cal B} = [\Real, \{ + \}]$

where $\Real$ is the set of real numbers, $\Real^+$ is the set of positive real numbers and $\times$ and + denote the familiar arithmetic operations of multiplication and addition respectively.

The mapping $h : \Real^+ \rightarrow \Real$ given by h(x) = log(x) where $x \in \Real^+$ is a homomorphism between $\cal{A}$ and $\cal B$ and we can formally prove this result by demonstrating that (10.1) holds. To start, we note that the two operations $\times$ and + have arity 2 so the arity constraint of (10.1) is satisfied. Furthermore, since each algebra has only the one operation, the correspondence between the operations of $\cal{A}$ and $\cal B$ is immediate and we can therefore take $\omega_A$ as $\times$ and $\omega_B$ as +respectively.

Using the familiar infix form for the operations $\times$ and +, the left-hand side of (10.1) is $h(a_1 \times a_2$), that is

$$log(a_1 \times a_2)$$

where $a_1, a_2 \in \Real^+$. The expression which corresponds to the right-hand side of (10.1) is

log(a₁) + log(a₂)

These two expressions are equal since $\forall a_1, a_2 \in \Real^+$, $log(a_1 \times a_2) = log(a_1) + log(a_2)$. It follows that the function $h : \Real^+ \rightarrow \Real$