Par récurrence sur $n \geqslant 1$, on définit des applications $f_n : M_n(X) \to M$ comme suit: on pose $f_1 = f$; pour $n \geqslant 2$, l’application $f_n$ est définie par $f_n(w.w') = f_p(w).f_{n-p}(w')$ pour $p = 1, 2, \ldots, n-1$ et $(w, w')$ dans $M_p(X) \times M_{n-p}(X)$. Soit $g$ l’application de $M(X)$ dans $M$ dont la restriction à $M_n(X)$ est $f_n$ pour tout entier $n \geqslant 1$. Il est clair que $g$ est l’unique morphisme de $M(X)$ dans $M$ qui prolonge $f$.

Soit $u$ une application de $X$ dans un ensemble $Y$. D’après la prop. 1, il existe un homomorphisme et un seul de $M(X)$ dans $M(Y)$ qui coïncide avec $u$ sur $X$. On le notera $M(u)$. Si $v$ est une application de $Y$ dans un ensemble $Z$, l’homomorphisme $M(v) \circ M(u)$ de $M(X)$ dans $M(Z)$ coïncide avec $v \circ u$ sur $X$, d’où

Supposons $u$ injective. Lorsque $X$ est vide, $M(X)$ est vide, donc $M(u)$ est injective. Si $X$ est non vide, il existe une application $v$ de $Y$ dans $X$ telle que $v \circ u$ soit l’application identique de $X$ (E, II, p. 18, prop. 8); l’application $M(v) \circ M(u) = M(v \circ u)$ est l’application identique de $M(X)$, donc $M(u)$ est injective.

Lorsque $u$ est surjective, il existe une application $w$ de $Y$ dans $X$ telle que $u \circ w$ soit l’application identique de $Y$ (E, II, p. 18, prop. 8). Alors $M(u) \circ M(w) = M(u \circ w)$ est l’application identique de $M(Y)$, donc $M(u)$ est surjective.

Enfin, si $u$ est bijective, elle est injective et surjective, donc $M(u)$ a les mêmes propriétés.

Soit $S$ une partie de $X$. D’après la prop. 2, l’injection de $S$ dans $X$ se prolonge en un isomorphisme de $M(S)$ sur un sous-magma $M'(S)$ de $M(X)$. On identifiera les magmas $M(S)$ et $M'(S)$ au moyen de cet isomorphisme. Alors $M(S)$ est le sous-magma de $M(X)$ engendré par $S$.

Soient $X$ un ensemble, et $(u_\alpha, v_\alpha)_{\alpha \in I}$ une famille de couples d’éléments de $M(X)$. Soit $R$ la relation d’équivalence sur $M(X)$ compatible avec la loi de $M(X)$ et engendrée par les $(u_\alpha, v_\alpha)$ (I, p. 12). Le magma $M(X)/R$ s’appelle le magma défini par $X$ et les relateurs $(u_\alpha, v_\alpha)_{\alpha \in I}$. Soit $h$ le morphisme canonique de $M(X)$ sur $M(X)/R$. Alors $M(X)/R$ est engendré par $h(X)$.

Soient $N$ un magma, et $(n_x)_{x \in X}$ une famille d’éléments de $N$. Soit $k$ le morphisme de $M(X)$ dans $N$ tel que $k(x) = n_x$ pour tout $x \in X$ (prop. 1). Si $k(u_\alpha) = k(v_\alpha)$ pour tout $\alpha \in I$, il existe un morphisme $f : M(X)/R \to N$ et un seul tel que $f(h(x)) = n_x$ pour tout $x \in X$ (I, p. 12, prop. 9).

Soit $g$ un homomorphisme de $Mo(X)$ dans $M$ prolongeant $f$. Si $w = (x_i)_{1 \leq i \leq n}$ est un mot, on a $w = \prod_{i=1}^n x_i$ dans le monoïde $Mo(X)$, d’où

dans le monoïde $M$ (I, p. 4, formule (2)). Ceci prouve l’unicité de $g$.

Posons $h(w) = \prod_{i=1}^n f(x_i)$ pour tout mot $w = (x_i)_{1 \leq i \leq n}$. Le théorème d’associativité (I, p. 4, th. 1) et la définition du produit dans $Mo(X)$ entraînent $h(ww') = h(w)h(w')$. Par convention, le produit vide $h(e)$ est l’élément neutre de $M$ et l’on a $h(x) = f(x)$ pour $x \in X$. Donc $h$ est un homomorphisme de $Mo(X)$ dans $M$ prolongeant $f$.

Soit $u : X \to Y$ une application. D’après la prop. 3, il existe un homomorphisme et un seul de $Mo(X)$ dans $Mo(Y)$ qui coïncide avec $u$ sur $X$; on le note $Mo(u)$. Il transforme un mot $(x_i)_{1 \leq i \leq n}$ en le mot $(u(x_i))_{1 \leq i \leq n}$. Comme dans le cas des magmas (I, p. 78), on établit la formule $Mo(v \circ u) = Mo(v) \circ Mo(u)$ pour toute application $v : Y \to Z$, et l’on montre que $Mo(u)$ est injective (resp. surjective, bijective) s’il en est ainsi de $u$. Pour toute partie $S$ de $X$, on identifiera $Mo(S)$ au sous-monoïde de $Mo(X)$ engendré par $S$.

Soient $X$ un ensemble, et $(u_\alpha, v_\alpha)_{\alpha \in I}$ une famille de couples d’éléments de $Mo(X)$. Soit $R$ la relation d’équivalence sur $Mo(X)$ compatible avec la loi de $Mo(X)$ et engendrée par les $(u_\alpha, v_\alpha)$ (I, p. 12). Le monoïde $Mo(X)/R$ s’appelle le monoïde défini par $X$ et par les relateurs $(u_\alpha, v_\alpha)_{\alpha \in I}$. Soit $h$ le morphisme canonique de $Mo(X)$ sur $Mo(X)/R$. Alors $Mo(X)/R$ est engendré par $h(X)$.

Soient $N$ un monoïde, et $(n_x)_{x \in X}$ une famille d’éléments de $N$. Soit $k$ le morphisme de $Mo(X)$ dans $N$ tel que $k(x) = n_x$ pour tout $x \in X$ (I, p. 79, prop. 3). Si $k(u_\alpha) = k(v_\alpha)$ pour tout $\alpha \in I$, il existe un morphisme de magmas $f : Mo(X)/R \to N$ et un seul tel que $f(h(x)) = n_x$ pour tout $x \in X$ (I, p. 12, prop. 9); comme $k$ est unifière, $f$ est un morphisme de monoïdes.

b) Soient $M'$ un monoïde, et $f_i : M_i \to M'$ (pour $i \in I$) des homomorphismes tels que $f_i \circ h_i$ soit indépendant de $i \in I$. Il existe un homomorphisme $f : M \to M'$ et un seul tel que $f_i = f \circ \varphi_i$ pour tout $i \in I$.

Dans la suite, nous ferons l’hypothèse suivante:

(A) Pour tout $i \in I$, il existe une partie $P_i$ de $M_i$ contenant $e_i$, telle que l’application $(a, p) \mapsto h_i(a).p$ de $A \times P_i$ dans $M_i$ soit bijective.

Elle entraîne que les homomorphismes $h_i$ sont injectifs. Soit $x \in M$; on appelle décomposition de $x$ toute suite finie $\sigma = (a; i_1, \ldots, i_n; p_1, \ldots, p_n)$ avec $a \in A$, $i_\alpha \in I$ et $p_\alpha \in P_{i_\alpha}$ pour $1 \leq \alpha \leq n$, satisfaisant à

L’entier $n \geq 0$ s’appelle la longueur de la décomposition $\sigma$ et se note $l(\sigma)$; la suite $(e)$ est une décomposition de longueur 0 de l’élément neutre de $M$. On dit que la décomposition $\sigma$ est réduite si l’on a $i_\alpha \neq i_{\alpha+1}$ pour $1 \leq \alpha < n$ et $p_\alpha \neq e_{i_\alpha}$ pour $1 \leq \alpha \leq n$.

A) Unicité d’une décomposition réduite :

Notons $\Sigma$ l’ensemble des suites $\sigma = (a; i_1, \ldots, i_n; p_1, \ldots, p_n)$ avec $n \geq 0$, $a \in A$, $i_\alpha \in I$ et $p_\alpha \in P_{i_\alpha} - \{e_{i_\alpha}\}$ pour $1 \leq \alpha \leq n$, telles que $i_\alpha \neq i_{\alpha+1}$ pour $1 \leq \alpha < n$. On note $\Phi$ l’application de $\Sigma$ dans $M$ définie par

Une décomposition réduite de $x \in M$ est un élément $\sigma$ de $\Sigma$ tel que $\Phi(\sigma) = x$.

Pour tout $i \in I$, soit $\Sigma_i$ le sous-ensemble de $\Sigma$ formé des suites $(e; i_1, \ldots, i_n; p_1, \ldots, p_n)$ avec $i \neq i_1$ lorsque $n > 0$. Soient

dans $\Sigma_i$ et $\xi$ dans $M_i$; posons $\xi = h_i(a) \cdot p$ avec $a \in A$ et $p \in P_i$, et

Il est immédiat que $\Psi_i$ est une bijection de $M_i \times \Sigma_i$ sur $\Sigma$.

Soient $i \in I$ et $x \in M_i$; comme $\Psi_i$ est bijective, on définit une application $f_{i, x}$ de $\Sigma$ dans lui-même par

De plus, pour $a \in A$, on note $f_a$ l’application de $\Sigma$ dans lui-même définie par

Il est clair que $f_{i, e_i}$ est l’application identique de $\Sigma$ et que l’on a $f_{i, xx'} = f_{i, x} \circ f_{i, x'}$ pour $x, x'$ dans $M_i$ et $f_{i, h_i(a)} = f_a$ pour $a \in A$ et $i \in I$.

On peut alors appliquer la prop. 4 (I, p. 80) au cas où $M'$ est le monoïde des applications de $\Sigma$ dans lui-même, avec la loi de composition $(f, f') \mapsto f \circ f'$, et où $f_i$ est l’homomorphisme $x \mapsto f_{i,x}$ de $M_i$ dans $M'$; il existe donc un homomorphisme $f$ de $M$ dans $M'$ tel que $f_{i,x} = f(\varphi_i(x))$ pour $i \in I$ et $x \in M_i$. Soit

dans $\Sigma$. Les formules (5) à (7) entraînent par récurrence sur $n$ la relation c’est-à-dire $\sigma = f(\Phi(\sigma))(e)$. Ceci prouve que $\Phi$ est injective.

B) Existence d’une décomposition: Soit D l’ensemble des éléments de M admettant une décomposition. On a $e \in D$ et $M$ est engendré par $\bigcup_{i \in I} \varphi_i(M_i)$, donc par $h(A) \cup \bigcup_{i \in I} \varphi_i(P_i)$. On a $D . \varphi_i(P_i) \subset D$ pour tout $i \in I$; pour prouver que l’on a $D = M$, il suffit donc de prouver la relation $D . h(A) \subset D$. Ceci résulte du lemme plus précis suivant :

C) Fin de la démonstration: Soit $x \in M$ et soit $n$ le minimum des longueurs des décompositions de $x$. Nous allons prouver que toute décomposition $\sigma$ de $x$ de longueur $n$ est réduite. Ceci établira l’existence d’une décomposition réduite de $x$; l’unicité de la décomposition réduite entraîne alors $l(\sigma') > l(\sigma)$ pour toute décomposition $\sigma' \neq \sigma$ de $x$.

Le cas $n = 0$ étant trivial, supposons $n > 0$. Soit $\sigma = (a; i_1, \ldots, i_n; p_1, \ldots, p_n)$ une décomposition de $x$ de longueur $n$. S’il existait un entier $\alpha$ avec $1 \leq \alpha \leq n$ et $p_\alpha = e_{i_\alpha}$, la suite $(a; i_1, \ldots, i_{\alpha-1}, i_{\alpha+1}, \ldots, i_n; p_1, \ldots, p_{\alpha-1}, p_{\alpha+1}, \ldots, p_n)$ serait une décomposition de $x$ de longueur $n - 1$, ce qui est exclus. Supposons qu’il existe un entier $\alpha$ avec $1 \leq \alpha < n$ et $i_\alpha = i_{\alpha+1}$, et posons $p_\alpha p_{\alpha+1} = h_{i_\alpha}(a') . p'_\alpha$ avec $a' \in A$ et $p'_\alpha \in P_{i_\alpha}$; d’après le lemme 1, il existe des éléments $a'' \in A$, $p'_1 \in P_{i_1}, \ldots, p'_{\alpha-1} \in P_{i_{\alpha-1}}$ tels que

et la suite

est une décomposition de $x$ de longueur $n - 1$, ce qui est contradictoire.

On a bien prouvé que $\sigma$ est réduite. C. Q. F. D.

Tout d’abord $h$ est injectif: si $h(a) = h(a')$, alors $(a)$ et $(a')$ sont deux décompositions réduites d’un même élément de $M$, d’où $a = a'$. Soit $i \in I$; on a $h(A) = \varphi_i(h_i(A)) \subset \varphi_i(M_i)$; l’unicité des décompositions réduites entraîne

d’où $\varphi_i(M_i - h_i(A)) = \varphi_i(M_i) - h(A)$.

L’injectivité des homomorphismes $\varphi_i$ et la relation $\varphi_i(M_i) \cap \varphi_j(M_j) \subset h(A)$ pour $i \neq j$ sont alors conséquences du fait suivant: pour $i, j$ dans $I$, $x$ dans $M_i - h_i(A)$ et $y$ dans $M_j - h_j(A)$, la relation $\varphi_i(x) = \varphi_j(y)$ entraîne $i = j$ et $x = y$. En effet, posons $x = h_i(a) . p$ et $y = h_j(b) . q$ avec $a, b$ dans $A$, $p$ dans $P_i - \{ e_i \}$ et $y$ dans $P_j - \{ e_j \}$. On a $\varphi_i(x) = h(a) \varphi_i(p)$ et $\varphi_j(y) = h(b) \varphi_j(q)$, donc $(a; i; p)$ et $(b; j; q)$ sont deux décompositions réduites d’un même élément de $M$. On en déduit $i = j$, $a = b$ et $p = q$, d’où $x = h_i(a)p = h_j(b)q = y$.

C. Q. F. D.

Lorsque l’hypothèse (A) est remplie, nous identifierons chaque monoïde $M_i$ à un sous-monoïde de $M$ au moyen de $\varphi_i$; de même, nous identifierons $A$ à un sous-monoïde de $M$ par $h$. Alors $M$ est engendré par $\bigcup_{i \in I} M_i$ et l’on a $M_i \cap M_j = A$ pour $i \neq j$. Tout élément de $M$ s’écrit de manière unique sous la forme $a . \prod_{\alpha=1}^n p_\alpha$ avec $a \in A$, $p_1 \in P_{i_1} - \{ e \}$, $\ldots$, $p_n \in P_{i_n} - \{ e \}$ et $i_\alpha \neq i_{\alpha+1}$ pour $1 \leq \alpha < n$. Enfin, si $M'$ est un monoïde et $(f_i : M_i \to M')$ (pour $i \in I$) une famille d’homomorphismes dont les restrictions à $A$ sont toutes un même homomorphisme de $A$ dans $M'$, il existe un’homomorphisme $f : M \to M'$ et un seul dont la restriction à $M_i$ est $f_i$ pour tout $i \in I$.

L’hypothèse (A) est vérifiée dans deux cas importants:

a) On a $A = \{ e \}$. Dans ce cas, on a une famille $(M_i)_{i \in I}$ de monoïdes et $M$ s’appelle la somme monoïdale de cette famille. Chaque $M_i$ est identifié à un sous-monoïde de $M$, et $M$ est engendré par $\bigcup_{i \in I} M_i$; de plus, on a $M_i \cap M_j = \{ e \}$ pour $i \neq j$. Tout élément de $M$ s’écrit de manière unique sous la forme $x_1 \ldots x_n$ avec $x_1 \in M_{i_1} - \{ e \}$, $\ldots$, $x_n \in M_{i_n} - \{ e \}$ et $i_\alpha \neq i_{\alpha+1}$ pour $1 \leq \alpha < n$. Enfin, pour toute famille d’homomorphismes $(f_i : M_i \to M')$, il existe un homomorphisme unique $f : M \to M'$ dont la restriction à $M_i$ est $f_i$ pour tout $i \in I$.

b) On a une famille de groupes $(G_i)_{i \in I}$ contenant comme sous-groupe un même groupe $A$ et $h_i$ est l’injection de $A$ dans $G_i$. La somme de la famille $(G_i)_{i \in I}$ amalgamée par $A$ est alors un groupe $G$: en effet, le monoïde $G$ est engendré par $\bigcup_{i \in I} \varphi_i(G_i)$ et tout élément de $\bigcup_{i \in I} \varphi_i(G_i)$ admet un inverse dans $G$ (cf. I, p. 16, cor. 1); on le note $*_A G_i$ ou $G_1 *_A G_2$ lorsque $I = \{1, 2\}$. Lorsque $A$ est réduit à l’élément neutre, on dit aussi que $G$ est le produit libre de la famille $(G_i)_{i \in I}$ de groupes, et on le note $* G_i$ (ou $G_1 * G_2$ lorsque $I = \{1, 2\}$).¹