Exercise 3, Appendix 0

Let E be a set and let $f$ be a mapping of $E \times E$ into E ("internal law of composition"). Let S be a set of signs which is the disjoint union of E and the set consisting of the single element $f$. Put $n(f) = 1$, and $n(x) = 0$ for all $x \in E$.

(a) Let M be the set of significant words of $L_0(S)$. Show that there is a unique mapping $v$ of M into E satisfying the following conditions : (1) $v(x) = x$ for all $x \in E$; (2) if $A$ and $B$ are two significant words, then $v(fAB) = f(v(A), v(B))$.

(b) For each word $A = (s_i)_{0 \leqslant i \leqslant n}$ in $L_0(S)$ let $A^*$ be the word $(s_{i_k})$, where the $i_k$ are the indices $i$ such that $s_i \neq f$, arranged in ascending order. Two words $A$, $B$ of $L_0(S)$ are said to be similar if $A^* = B^*$. Show that if the law of composition $f$ is associative, i.e., if

then $v(A) = v(B)$ whenever $A$ and $B$ are similar significant words ("general theorem of associativity"). (A significant word

is said to be normal if $s_i = f$ for $i = 0, 2, 4, \ldots, 2n - 2$, and $s_i \neq f$ for the other indices. Show that every significant word is similar to a unique normal word $A'$, and prove that $v(A) = v(A')$ by induction on the length of $A$.)