Monoïdes libres et groupes libres

Je propose ici une version (j'espère) sans étourderies de l'exercice que j'ai proposé dans le fil "Objets libres"; avec 2 corrections: l'une utilisant une description explicite du monoïde libre sur un ensemble, l'autre utilisant uniquement la définition de monoïde libre.

Je rappelle avant tout la définition de monoïde (resp. groupe) libre sur un ensemble $X$, et la description explicite du monoïde libre sur un ensemble $X$. J'admets (faits démontrés dans l'autre fil) que ladite description vérifie bien la définition de monoïde libre; et le fait que deux monoïdes libres sur un ensemble sont isomorphes (avec un unique isomorphisme respectant ledit ensemble).

Un monoïde (resp. groupe) libre sur un ensemble $X$ est un couple $(M,i)$ où $M$ est un monoïde (resp. groupe), $i: X\to M$ une application (ensembliste) tel que pour tout monoïde (resp. groupe) $N$ et toute application $j: X\to N$ il existe un unique morphisme de monoïdes (resp. groupes) $f: M\to N$ tel que $f\circ i = j$.

Si $X$ est un ensemble, alors $\displaystyle\coprod_{n\in \N} X^n$ muni de la concaténation est un monoïde libre sur $X$ (l'élément neutre étant l'unique élément de $X^0$, c'est-à-dire la suite vide).


Partie I : Faits généraux sur les congruences de monoïdes.

On appelle une congruence sur un monoïde $M$ une relation d'équivalence $R$ telle que $xRx', yRy' \implies (xy)R(x'y')$.
Si $R$ est une congruence, il y a une unique structure de monoïde sur $M/R$ telle que la projection canonique $\pi: M\to M/R$ soit un morphisme de monoïde. En notant $[x] = \pi(x)$ la classe de $x$ modulo $R$, elle est définie par $[x][y] = [xy]$, cette définition étant licite par définition de congruence; l'élément neutre étant $[1]$ ($1$ neutre de $M$).

$M/R$ jouit de la propriété universelle suivante: si $f:M\to N$ est un morphisme de monoïdes tel que $xRy \implies f(x)=f(y)$, alors $f$ se factorise uniquement par $M/R\to N$ (qui caractérise à isomorphisme près $M/R$).

Il est facile de voir qu'une intersection quelconque de congruences est une congruence (en prenant l'intersection vide égale à $M^2$), en particulier pour tout $X\subset M^2$ il existe une plus petite congruence contenant $X$, notée $\langle X\rangle$ et appelée "congruence engendrée par $X$". Lorsque ça ne mène pas à des confusions, on se permettra l'abus de noter $M/X$ au lieu de $M/\langle X\rangle$.

Exemple : Sur $(\N,+)$, la relation de congruence modulo $2$ est une congruence. Le monoïde quotient est un groupe isomorphe à $\Z/2\Z$.

Partie II : Le groupe libre sur un ensemble

Soit $A$ un ensemble, on veut prouver qu'il existe un groupe libre sur $A$ (/ décrire le groupe libre sur $A$).

On pose $E= A\times\{1, -1\}$. On note $j:A\to E$ l'application $a\mapsto (a,1)$ et $l: A\to E$ l'application $a\mapsto (a,-1)$: $E= j(A)\coprod l(A)$.

Soit $(M,i)$ un monoïde libre sur $E$, je note $\times$ sa multiplication et $e$ son neutre; et $X= \{(i\circ j(a)\times i\circ l(a), e)\mid a\in A\}\cup\{(i\circ l(a)\times i\circ j(a), e) \mid a\in A\}$; et $R=\langle X\rangle$. Je note $\pi: M\to M/R$ la projection canonique.

Alors $(M/R, \pi\circ i\circ j)$ est un groupe libre sur $A$.

Lemme: $M/R$ est un groupe
Je fournis deux preuves de ce fait : l'une en utilisant la description explicite de $M$, l'autre utilisant uniquement sa propriété universelle.

Preuve 1:
Notons $t: E\to E$ l'involution $(a,1)\mapsto (a,-1), (a,-1)\mapsto (a,1)$. Je prétends qu'alors pour toute suite $(s_1,...,s_n) \in E^n$, $((s_1,...,s_n)\times (t(s_n),...,t(s_1)), e)$ et $((t(s_n),...,t(s_1))\times (s_1,...,s_n),e)$ sont dans $R$.

On le prouve par récurrence sur $n$ : pour $n=0$ il s'agit de dire que $(e,e) \in R$, ce qui est évident car $R$ est une relation d'équivalence.
Pour $n=1$, cela vient de ce que $X\subset R$.
Le passage $n\to n+1$ se fait de la manière suivante : je suppose la propriété vraie au rang $n$; soit $(s_1,...,s_{n+1})$ une suite à valeurs dans $E$. Alors $(s_{n+1}\times t(s_{n+1}),e)\in R$ (d'après le cas $n=1$). Donc, comme $R$ est une congrence, $((s_1,...,s_n)\times s_{n+1}\times t(s_{n+1}), (s_1,...,s_n))\in R$; donc par définition de $\times$, $((s_1,...,s_n,s_{n+1})\times t(s_{n+1}), (s_1,...,s_n))\in R$. De même, $R$ étant une congruence, $((s_1,...,s_n,s_{n+1})\times t(s_{n+1})\times (t(s_n),...,t(s_1)), (s_1,...,s_n)\times (t(s_n),...,t(s_1)))\in R$.

On applique alors la définition de $\times$ à gauche, puis l'hypothèse de récurrence et la transitivité de $R$ pour obtenir $((s_1,...,s_{n+1})\times (t(s_{n+1}),...,t(s_1)), e)\in R$. On fait exactement de même pour l'autre sens.
On conlut par récurrence.

Ainsi pour tout $s\in M$, il existe $z\in M$ tel que $(s\times z, e)\in R$. Comme $\pi: M\to M/R$ est surjective, cela suffit à prouver que $M/R$ est un groupe.

Preuve 2 : Soit $U\subset M/R$ l'ensemble des inversibles (qui est un groupe) : $U=\{x\in M/R \mid \exists y, xy = yx = e\}$ (je note aussi $e$ le neutre de $M/R$ en espérant que cet abus ne dérangera pas). Je note $k:U\to M/R$ le morphisme d'inclusion.
Je reprends la notation $t:E\to E$ de la preuve $1$.
Puisque pour $s\in E$, $(s\times t(s), e), (t(s)\times s, e)\in R$, on a que $\pi\circ i$ est à valeurs dans $U$, i.e. se factorise par $k$: disons qu'on a $h:E\to U$ telle que $k\circ h = \pi\circ i$.
$U$ étant en particulier un monoïde, l'application $h: E\to U$ permet (par définition de monoïde libre) d'obtenir un morphisme $m:M\to U$ tel que $m\circ i = h$. Alors $k\circ m\circ i = k\circ h = \pi\circ i$. Donc les compositions de $k\circ m, \pi :M\to M/R$ avec $i$ coïncident : par unicité dans la définition de monoïde libre, $k\circ m = \pi$. En particulier, $\pi$ étant surjective, $k$ l'est aussi. Mais $k$ est l'inclusion $U\to M/R$, sa surjectivité signifie simplement que $U=M/R$: donc $M/R$ est un groupe.

Pour moi la preuve 2 est la plus claire et la plus élégante et elle ne nécessite que de savoir que $(M,i)$ est un monoïde libre: si des extraterrestres ont une autre construction du monoïde libre, ces derniers comprendront la preuve 2 sans travail supplémentaire; pour comprendre la preuve 1, iels devront travailler sur l'un des résultats que j'ai admis au début.

A noter que la preuve 2 est infiniment plus claire si on dessine les diagrammes qui vont avec, mais \xymatrix ne marche pas...

Bref, $M/R$ est un groupe, et on a une application $A\to M/R$ qui est la composition $A\to E\to M\to M/R$, plus précisément $\pi\circ i \circ j$. Je la note $b$.
Alors $(M/R, b)$ est un groupe libre sur $A$. Avant la preuve, comprendre d'où ça vient : on est parti d'un monoïde libre sur $A$ et des éléments supplémentaires qui jouent le rôle des futurs inverses des éléments de $A$. L'ensemble $X$ que j'ai décrit et la congruence associée sont juste un moyen de décréter que ce sont effectivement des inverses; et c'est le plus petit truc qu'on peut faire pour les forcer à être des inverses: c'est donc le groupe libre.

Bon, une vraie preuve maintenant (que je fais sans la description de $M$ parce que là elle n'apporte rien; en fait l'utiliser permettrait uniquement de reprouver ce que j'ai admis au début, à savoir que c'est un monoïde libre).

Soit $G$ un groupe dont je note $\star$ la multiplication et $1$ le neutre; $q: A\to G$ une application. En posant $f(j(a)) = q(a)$ et $f(l(a)) = q(a)^{-1}$ on obtient une application $f: E\to G$ telle que $f\circ j = q$, et $f\circ j(a) \star f\circ l(a) = 1$.

$G$ est un groupe donc en particulier un monoïde, donc on obtient un morphisme $r: M\to G$ tel que $r\circ i = f$.

Soit $a\in A$. Alors $r(i(j(a))\star r(i(l(a))= f(j(a))\star f(l(a)) = 1=r(e)$, et similairement $r(i(l(a))\star r(i(j(a))= f(l(a))\star f(j(a)) = 1=r(e)$; de sorte que $X\subset \{(x,y)\in M \mid r(x) = r(y)\}$.
Or il est clair que $\{(x,y)\in M \mid r(x) = r(y)\}$ est une congruence sur $M$, et comme $R$ est la plus petite congruence contenant $X$, $R\subset \{(x,y)\in M \mid r(x) = r(y)\}$. Donc par propriété universelle du quotient (décrit en partie I), $r$ se factorise uniquement par $d:M/R \to G$.

Maintenant, $d\circ b = d\circ \pi\circ i\circ j= r\circ i \circ j = f\circ j = q$ (à nouveau, dessiner un diagramme rend la chose infiniment plus claire).

Quant à l'unicité, si $v: M/R \to G$ vérifie $v\circ b = q$, alors $v\circ \pi\circ i\circ j = q$. On ait que $\pi\circ i\circ l (a)$ est l'inverse de $\pi\circ i\circ j (a)$ pour $a\in A$ , de sorte que cette égalité impose $v\circ \pi \circ i = f$ (par définition de $f$ et par un peu de théorie élémentaire des groupes)
Seulement, $v\circ \pi $ est un morphisme de monoïdes, et sa composition avec $i$ coïncide avec celle de $r$: $(M,i)$ étant un monoïde libre sur $E$, cela impose $v\circ \pi = r$. Mais alors la composition de $v$ avec $\pi$ coïncide avec celle de $d$, donc par propriété universelle du quotient (ou si c'est plus clair pour toi, parce que $\pi$ est surjective), cela impose $v= d$.

Conclusion : on a montré que pour tout groupe $G$ et application $q:A\to G$, il existe un unique morphisme de groupes $d:M/R\to G$ tel que $d\circ b = q$. En d'autres termes, $(M/R,b)$ est bien un groupe libre sur $A$: c'est ce qu'on voulait démontrer.

Quelques idées de généralisation :

Si tu fais bien attention, tu verras que je n'ai essentiellement rien utilisé de spécifique aux groupes ou aux monoïdes. C'est parce que ce qui est fait ici peut se faire dans un plus grand cadre. En fait, si tu as un type d'algèbres, c'est-à-dire une famille $(f_i)_{i\in I}$ de symboles fonctionnels, disons d'arités finies $(n_i)_{i\in I}$, un ensemble d'équations reliant ces symboles fonctionnels (par exemple pour les monoïdes on a deux symboles fonctionnels : $e$, d'arité nulle, et $\times$, d'arité $2$, et comme équations on a $x\times e = x, e\times x = x$, etc.) et que tu regardes la classe (catégorie si ce mot ne te fait pas peur - il ne devrait pas) des ensembles munis d'opérations correspondant aux $f_i$ et vérifiant ces équations, alors tu peux toujours t'interroger sur les trucs libres (où un truc est un de ces ensembles munis d'opérations et vérifiant ces équations). En particulier, il existe toujours des trucs libres sur n'importe quel ensemble (!!).
Plus spécifiquement, comment relier les monoïdes libres et les groupes libres ? Bon ici comme les groupes ont un symbole fonctionnel de plus ($\iota$, pour l'inversion), il faut considérer en fait les "monoïdes muni d'une involution" libres: c'est mon $M$.
En fait rajouter des symboles fonctionnels te fait augmenter la taille de $A$ (c'est le passage de $A$ à $E$) et rajouter des équations te fait quotienter par une bonne congruence (c'est la passage de $M$ à $M/R$): tu peux généraliser ça à besoin/envie

Pour aller encore plus loin, on est ici face à une adjonction entre la catégorie des ensembles et la catégorie des monoïdes (resp. groupes, trucs); et on peut étudier plus généralement ces adjonctions, et voir ce que "algèbre" peut vouloir dire au plus général (il est par exemple possible de traiter des espaces compacts Hausdorffs comme d'objets algébriques)