By induction on $n \geqslant$, mappings $f_n : M_n(X) \to M$ are defined as follows: let f_1 = f; for n \geq 2, the mapping f_n is defined by $f_n(w.w') = f_p(w).f_{n-p}(w')$ for $p = 1, 2, \ldots, n-1$ and $(w, w')$ in $M_p(X) \times M_{n-p}(X)$. Let $g$ be the mapping of $M(X)$ into $M$ which induces $f_n$ on $M_n(X)$ for every integer $n \geq 1$. Clearly $g$ is the unique morphism of $M(X)$ into $M$ which extends $f$.

Let $u$ be a mapping of $X$ into a set $Y$. By Proposition 1, there exists one and only one homomorphism of $M(X)$ into $M(Y)$ which coincides with $u$ on $X$. It will be denoted by $M(u)$. If $v$ is a mapping of $Y$ into a set $Z$, the homomorphism $M(v) \circ M(u)$ of $M(X)$ into $M(Z)$ coincides with $v \circ u$ on $X$, whence

Suppose $u$ is injective. When $X$ is empty, $M(X)$ is empty, hence $M(u)$ is injective. If $X$ is non-empty, there exists a mapping $v$ of $Y$ into $X$ such that $v \circ u$ is the identity mapping of $X$ (Set Theory, II, § 3, no. 8, Proposition 8); the mapping $M(v) \circ M(u) = M(v \circ u)$ is the identity mapping of $M(X)$ and hence $M(u)$ is injective.

When $u$ is surjective, there exists a mapping $w$ of $Y$ into $X$ such that $u \circ w$ is the identity mapping of $Y$ (Set Theory, II, § 3, no. 8, Proposition 8). Then $M(u) \circ M(w) = M(u \circ w)$ is the identity mapping of $M(Y)$ and hence $M(u)$ is surjective.

Finally, if $u$ is bijective, it is injective and surjective and hence $M(u)$ has the same properties.

Let $S$ be a subset of $X$. By Proposition 2 the injection of $S$ into $X$ can be extended to an isomorphism of $M(S)$ onto a submagma $M'(S)$ of $M(X)$. The magmas $M(S)$ and $M'(S)$ are identified by means of this isomorphism. Then $M(S)$ is the submagma of $M(X)$ generated by $S$.

Let $X$ be a set and $(u_\alpha, v_\alpha)_{\alpha \in I}$ be a family of ordered pairs of elements of $M(X)$. Let $R$ be the equivalence relation on $M(X)$ compatible with the law of $M(X)$ and generated by the $(u_\alpha, v_\alpha)$ (§ 1, no. 6). The magma $M(X)/R$ is called the magma defined by $X$ and the relators $(u_\alpha, v_\alpha)_{\alpha \in I}$. Let $h$ be the canonical morphism of $M(X)$ onto $M(X)/R$. Then $M(X)/R$ is generated by $h(X)$.

Let $N$ be a magma and $(n_x)_{x \in X}$ a family of elements of $N$. Let $k$ be the morphism from $M(X)$ to $N$ such that $k(x) = n_x$ for all $x \in X$ (Proposition 1). If $k(u_\alpha) = k(v_\alpha)$ for all $\alpha \in I$, there exists one and only one morphism $f : M(X)/R \to N$ such that $f(h(x)) = n_x$ for all $x \in X$ (§ 1, no. 6, Proposition 9).

Let $g$ be a homomorphism of $\mathrm{Mo}(\mathbf{X})$ into $M$ extending $f$. If $w = (x_i)_{1 \leq i \leq n}$ is a word, then $w = \prod_{i=1}^n x_i$ in the monoid $\mathrm{Mo}(\mathbf{X})$, whence

in the monoid $M$ (§ 1, no. 2, formula (2)). This proves the uniqueness of $g$.

Let $h(w) = \prod_{i=1}^n f(x_i)$ for every word $w = (x_i)_{1 \leq i \leq n}$. The associativity theorem (§ 1, no. 3, Theorem 1) and the definition of product in $\mathrm{Mo}(\mathbf{X})$ imply $h(ww') = h(w)h(w')$. By convention the empty product $h(e)$ is the identity element of $M$ and $h(x) = f(x)$ for $x \in \mathbf{X}$. Hence $h$ is a homomorphism of $\mathrm{Mo}(x)$ into $M$ extending $f$.

Let $u : \mathbf{X} \to \mathbf{Y}$ be a mapping. By Proposition 3, there exists one and only one homomorphism of Mo(X) into Mo(Y) which coincides with u on X; it is denoted by Mo(u). It maps a word $(x_i)_{1 \leq i \leq n}$ to the word $(u(x_i))_{1 \leq i \leq n}$. As in the case of magmas (no. 1), the equation Mo(v \circ u) = Mo(v) \circ Mo(u) is established for every mapping $v : Y \to Z$ and it can be shown that Mo(u) is injective (resp. surjective, bijective) if u is. For every subset S of X, Mo(S) is identified with the submonoid of Mo(X) generated by S.

Let X be a set and $(u_\alpha, v_\alpha)_{\alpha \in I}$ be a family of ordered pairs of elements of Mo(X). Let R be the equivalence relation on Mo(X) compatible with the law on Mo(X) and generated by the $(u_\alpha, v_\alpha)$ (§ 1, no. 6). The monoid Mo(X)/R is called the monoid defined by X and the relators $(u_\alpha, v_\alpha)_{\alpha \in I}$. Let h be the canonical morphism of Mo(X) onto Mo(X)/R. Then Mo(X) is generated by h(X).

Let N be a monoid and $(n_x)_{x \in X}$ a family of elements of N. Let k be the morphism of Mo(X) into N such that $k(x) = n_x$ for all $x \in X$ (Proposition 3). If $k(u_\alpha) = k(v_\alpha)$ for all $\alpha \in I$, there exists one and only one magma morphism $f : Mo(X)/R \to N$ such that $f(h(x)) = n_x$ for all $x \in X$ (§ 1, no. 6, Proposition 9); as k is unital, f is a monoid morphism.

(b) Let $M'$ be a monoid and $f' : M_i \to M'$ (for $i \in I$) homomorphisms such that $f_i \circ h_i$ is independent of $i \in I$. There exists one and only one homomorphism $f : M \to M'$ such that $f_i = f \circ \phi_i$ for all $i \in I$.

In what follows we shall make the following hypothesis:

(A) For all $i \in I$, there exists a subset $P_i$ of $M_i$ containing $e_i$ such that the mapping $(a, p) \mapsto h_i(a).p$ of $A \times P_i$ into $M_i$ is bijective.

It implies that the homomorphisms $h_i$ are injective. Let $x \in M$; every finite sequence $\sigma = (a; i_1, \ldots, i_n; p_1, \ldots, p_n)$ with $a \in A, i_\alpha \in I$ and $p_\alpha \in P_{i_\alpha}$ for $1 \leq \alpha \leq n$, satisfying

is called a decomposition of $x$. The integer $n \geq 0$ is called the length of the decomposition $\sigma$ and is denoted by $l(\sigma)$; the sequence $(e)$ is a decomposition of length 0 of the identity element of $M$. The decomposition $\sigma$ is called reduced if $i_\alpha \neq i_{\alpha+1}$ for $1 \leq \alpha < n$ and $p_\alpha \neq e_{i_\alpha}$ for $1 \leq \alpha \leq n$.

(A) Uniqueness of a reduced decomposition:

Let $\Sigma$ denote the set of sequences $\sigma = (a; i_1, \ldots, i_n; p_1, \ldots, p_n)$ with $n \geq 0$, $a \in A, i_\alpha \in I$ and $p_\alpha \in P_{i_\alpha} - \{e_{i_\alpha}\}$ for $1 \leq \alpha \leq n$, such that $i_\alpha \neq i_{\alpha+1}$ for $1 \leq \alpha < n$. Let $\Phi$ denote the mapping of $\Sigma$ into $M$ defined by

A reduced decomposition of $x \in M$ is an element $\sigma$ of $\Sigma$ such that $\Phi(\sigma) = x$.

For all $i \in I$, let $\Sigma_i$ be the subset of $\Sigma$ consisting of the sequences $(e; i_1, \ldots, i_n; p_1, \ldots, p_n)$ with $i \neq i_1$ when $n > 0$. Let

be in $\Sigma_i$ and $\xi$ in $M_i$; let $\xi = h_i(a) \cdot p$ with $a \in A$ and $p \in P_i$, and

It is immediate that $\Psi_i$ is a bijection of $M_i \times \Sigma_i$ onto $\Sigma$.

Let $i \in I$ and $x \in M_i$; as $\Psi_i$ is bijective, a mapping $f_{i,x}$ of $\Sigma$ into itself is defined by

Further, for $a \in A, f_a$ denotes the mapping of $\Sigma$ into itself defined by

Clearly $f_{i,e_i}$ is the identity mapping of $\Sigma$ and $f_{i,xx'} = f_{i,x} \circ f_{i,x'}$ for $x, x'$ in $M_i$ and $f_{i,h_i(a)} = f_a$ for $a \in A$ and $i \in I$.

Then Proposition 4 may be applied to the case where $M'$ is the monoid of mappings of $\Sigma$ into itself with law of composition $(f,f') \mapsto f \circ f'$ and where f_i is the homomorphism $x \mapsto f_{i,x}$ of $M_i$ into $M'$; then there exists a homomorphism $f$ of $M$ into $M'$ such that $f_{i,x} = f(\phi_i(x))$ for $i \in I$ and $x \in M_i$. Let

be in $\Sigma$. Formulae (5) to (7) imply by induction on $n$ the relation that is $\sigma = f(\Phi(\sigma))(e)$. This proves that $\Phi$ is injective.

(B) Existence of a decomposition:

Let $D$ be the set of elements of $M$ admitting a decomposition. Then $e \in D$ and $M$ is generated by $\bigcup_{i \in I} \phi_i(M_i)$ and hence by $h(A) \cup \bigcup_{i \in I} \phi_i(P_i)$. Then $D.\phi_i(P_i) \subset D$ for all $i \in I$; to prove that $D = M$, it thus suffices to prove the relation $D.h(A) \subset D$. This follows from the following more precise lemma:

(C) End of the proof:

Let $x \in M$ and let $n$ be the minimum of the lengths of decompositions of $x$. We shall prove that every decomposition $\sigma$ of $x$ of length $n$ is reduced. This will establish the existence of a reduced decomposition of $x$; the uniqueness of the reduced decomposition then implies $l(\sigma') > l(\sigma)$ for every decomposition $\sigma' \neq \sigma$ of $x$.

The case $n = 0$ being trivial, suppose $n > 0$. Let

be a decomposition of $x$ of length $n$. If there existed an integer $\alpha$ with $1 \leq \alpha \leq n$ and $p_\alpha = e_{i_\alpha}$, the sequence

would be a decomposition of $x$ of length $n - 1$, which is excluded. Suppose that there exists an integer $\alpha$ with $1 \leq \alpha < n$ and $i_{\alpha} = i_{\alpha + 1}$ and let

with $a' \in \mathbf{A}$ and $p'_{\alpha} \in P_{i_{\alpha}}$; by Lemma 1 there exists elements $a'' \in \mathbf{A}$, such that and the sequence is a decomposition of $x$ of length $n - 1$, which is a contradiction.

We have thus proved that $\sigma$ is reduced.

First $h$ is injective: if $h(a) = h(a')$, then $(a)$ and $(a')$ are two reduced decompositions of the same element of $M$, whence $a = a'$. Let $i \in I$; then $h(\mathbf{A}) = \phi_{i}(h_{i}(\mathbf{A})) \subset \phi_{i}(M_{i})$; the uniqueness of reduced decompositions implies

whence $\phi_{i}(M_{i} - h_{i}(\mathbf{A})) = \phi_{i}(M_{i}) - h(\mathbf{A})$.

The injectivity of the homomorphisms $\phi_{i}$ and the relation

for $i \neq j$ are then consequences of the following fact: for $i, j$ in $I$, $x$ in $M_{i} - h_{i}(\mathbf{A})$ and $y$ in $M_{j} - h_{j}(\mathbf{A})$, the relation $\phi_{i}(x) = \phi_{j}(y)$ implies $i = j$ and $x = y$. Let $x = h_{i}(a) \cdot p$ and $y = h_{j}(b) \cdot q$ with $a, b$ in $\mathbf{A}$, $p$ in $P_{i} - \{e_{i}\}$ and $y$ in $P_{j} - \{e_{j}\}$. Then $\phi_{i}(x) = h(a)\phi_{i}(p)$ and $\phi_{j}(y) = h(b)\phi_{j}(q)$ and hence $(a; i; p)$ and $(b; j; q)$ are two reduced decompositions of the same element of $M$. It follows that $i = j, a = b$ and $p = q$, whence $x = h_{i}(a)p = h_{j}(b)q = y$.

When hypothesis (A) is fulfilled, we shall identify each monoid $M_{i}$ with a submonoid of $M$ by means of $\phi_{i}$; similarly, we shall identify $\mathbf{A}$ with a submonoid of $M$ by $h$. Then $M$ is generated by $\bigcup_{i \in I} M_{i}$ and $M_{i} \cap M_{j} = \mathbf{A}$ for $i \neq j$.

Every element of $M$ can be written uniquely in the form $a \prod_{\alpha = 1}^{n} p_{\alpha}$ with $a \in \mathbf{A}, p_{1} \in P_{i_{1}} - \{e\}, \ldots, p_{n} \in P_{i_{n}} - \{e\}$ and $i_{\alpha} \neq i_{\alpha + 1}$ for $1 \leq \alpha < n$. Finally, if $M'$ is a monoid and $(f_{i}: M_{i} \to M')$ (for $i \in I$) a family of homomorphisms whose restrictions to $\mathbf{A}$ are the same homomorphism of $\mathbf{A}$ into $M'$, there exists one and only one homomorphism $f: M \to M'$ inducing $f_{i}$ on $M_{i}$ for all $i \in I$.

Hypothesis (A) is satisfied in two important cases:

(a) $A = \{e\}$. In this case, there is a family $(M_i)_{i \in I}$ of monoids and $M$ is called the monoidal sum of this family. Each $M_i$ is identified with a submonoid of $M$ and $M$ is generated by $\bigcup_{i \in I} M_i$; further, $M_i \cap M_j = \{e\}$ for $i \neq j$. Every element of $M$ may be written uniquely in the form $x_1 \ldots x_n$ with

and $i_\alpha \neq i_{\alpha+1}$ for $1 \leq \alpha \leq n$. Finally, for every family of homomorphisms $(f_i : M_i \to M')$, there exists a unique homomorphism $f : M \to M'$ whose restriction to $M_i$ is $f_i$ for all $i \in I$.

(b) There is a family of groups $(G_i)_{i \in I}$ containing as subgroup the same group $A$ and $h_i$ is the injection of $A$ into $G_i$. The sum of the family $(G_i)_{i \in I}$ amalgamated by $A$ is then a group $G$ : the monoid $G$ is generated by $\bigcup_{i \in I} \phi_i(G_i)$ and every element of $\bigcup_{i \in I} \phi_i(G_i)$ admits an inverse in $G$ (cf. § 2, no. 3, Corollary 1 to Proposition 4); it is denoted by $*_A G_i$ or $G_1 *_A G_2$ when $I = \{1, 2\}$. When $A$ consists of the identity element, it is also said that $G$ is the free product of the family $(G_i)_{i \in I}$ of groups and it is denoted by $* G_i$ (or $G_1 * G_2$ if $I = \{1, 2\}$).†