Exercise 7, § 7

Let $M_x$ be the free magma constructed on a set $\{x\}$ with one element. (a) For every $y \in M_x$, now prove 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. exerc. 6). (b) If $y \in M_x, z \in M_x$, put $y \circ z = f_y(z)$. Now prove that the law of composition $(y, z) \mapsto y \circ z$ makes $M_x$ a monoid, with identity element x, isomorphic to the monoid End($M_x$) of endomorphisms of $M_x$. (c) Let N be the set of monogenic submagmas of $M_x$ distinct from $M_x$. An element y of $M_x$ is said to be primitive if $M_y$ is a maximal element of N. Now prove 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$. Now prove that, if $y \in P, z \in P, y \neq z$, one has $M_y \cap M_z = \varnothing$ (use exerc. 6). (e) Let Mo(P) be the free monoid constructed on P. If one endows $M_x$ with the monoid structure defined in b), the injection $P \to M_x$ extends to a homomorphism $p : Mo(P) \to M_x$. Now prove that $p$ is an isomorphism. (If $z \in M_x$, one will prove by induction on $l(z)$ that one has $z \in \operatorname{Im}(p)$. On the other hand, if $y_1, \ldots, y_n, z_1, \ldots, z_m$ are elements of P such that $p(y_1 \ldots y_n) = p(z_1 \ldots z_m)$, one has $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_2}(p(z_2 \ldots z_m))$; whence $p(y_2 \ldots y_n) = p(z_2 \ldots z_m)$, and one deduces that $y_1 \ldots y_n = z_1 \ldots z_m$ by reasoning by induction on $\sup(n, m)$).