Exercise 7, § 7

Let $M_x$ be the free magma constructed on a set $\{x\}$ with one element.

(a) For all $y \in M_x$, show that there exists a unique endomorphism $f_y$ of $M_x$ such that $f_y(x) = y$; it is an isomorphism of $M_x$ onto the submagma $M_y$ generated by $y$ (cf. Exercise 6).

(b) If $y, z \in M_x$, we write $y \circ z = f_y(z)$. Show that the law of composition $(y, z) \mapsto y \circ z$ makes $M_x$ into a monoid with identity element $x$ which is isomorphic to the monoid $\mathrm{End}(M_x)$ of endomorphisms of $M_x$.

(c) Let $N$ be the set of monogenous submagmas of $M_x$ distinct from $M_x$. An element $y$ of $M_x$ is called primitive if $M_y$ is a maximal element of $N$. Show that $xx, x(x(xx))$ are primitive whereas $x, (xx)(xx)$ are not.

(d) Let $P$ be the set of primitive elements of $M_x$. Show that, if $y, z \in P, y \neq z$, then $M_y \cap M_z = \varnothing$ (use Exercise 6).

(e) Let $\mathrm{Mo}(P)$ be the free monoid constructed on $P$. If $M_x$ is given the monoid structure defined in (b), the injection $P \to M_x$ can be extended to a homomorphism $p : \mathrm{Mo}(P) \to M_x$. Show that $p$ is an isomorphism.

(If $z \in M_x$, show by induction on $l(z)$ that $z \in \mathrm{Im}(p)$. On the other hand, if $y_1, \ldots, y_n, z_1, \ldots, z_m \in P$ are such that $p(y_1 \ldots y_n) = p(z_1 \ldots z_m)$, then $M_{y_1} \cap M_{z_1} \neq \varnothing$, whence $y_1 = z_1$ and $f_{y_1}(p(y_2 \ldots y_n)) = f_{y_1}(p(z_2 \ldots z_m))$; whence $p(y_2 \ldots y_n) = p(z_2 \ldots z_m)$ and it follows that $y_1 \ldots y_n = z_1 \ldots z_m$ arguing by induction on $\sup(n, m)$.)