# Théorie des groupes/Groupes libres : théorème de Nielsen-Schreier

Dans ce chapitre, on va démontrer le théorème de Nielsen-Schreier, selon lequel tout sous-groupe d'un groupe libre est lui-même un groupe libre. La longueur du chapitre tient surtout à ce qu'on est entré dans des minuties dont on espère qu'elles aideront le lecteur à se sentir en terrain solide.
Pour un ensemble X, nous définirons, comme au chapitre Groupes libres, premiers éléments, le groupe libre F(X) construit sur X comme l'ensemble des mots signés réduits sur X, muni de la loi de groupe « juxtaposition suivie de réduction ».
Comme au chapitre Groupes libres, premiers éléments, nous noterons ${\widetilde {X}}$ la base canonique de F(X), c'est-à-dire l'ensemble des ((x, 1)), où x parcourt X. Donc ${\widetilde {X}}\cup ({\widetilde {X}})^{-1}$ est l'ensemble de ce que nous appelons les lettres signées sur X, autrement dit l'ensemble des mots signés (réduits) de longueur 1 sur X.
Pour un mot signé $v=((x_{1},\epsilon _{1}),\ldots ,(x_{r},\epsilon _{r}))$ et un mot signé $w=((y_{1},\zeta _{1}),\ldots ,(y_{s},\zeta _{s}))$, nous utiliserons de nouveau la notation $v_{\mathrm {juxt} }w$ pour désigner le mot signé
    $((x_{1},\epsilon _{1}),\ldots ,(x_{r},\epsilon _{r}),(y_{1},\zeta _{1}),\ldots ,(y_{s},\zeta _{s}))$
(non forcément réduit, même si $v$ et $w$ le sont).

## Segments initiaux et parties schreiériennes

Soit X un ensemble. Pour un élément $v=((x_{1},\epsilon _{1}),\ldots ,(x_{r},\epsilon _{r}))$ de F(X), on définit un segment initial de v comme un mot signé (réduit) de la forme $((x_{1},\epsilon _{1}),\ldots ,(x_{s},\epsilon _{s}))$ avec $0\leq s\leq r$.
Nous dirons qu'un segment initial de w est un segment initial propre de w s'il est distinct de w.
Si v, w sont des éléments de F(X), si v est un segment initial de w, nous dirons aussi que w commence par v. (Nous avons déjà employé cette expression dans le cas où v est de longueur 1.)
Dire que $v$ est un segment initial de $w$ revient à dire qu'il existe un mot signé $v'$ tel que $w=v_{\mathrm {juxt} }v'$. Le mot signé vide et w lui-même sont des segments initiaux de w. Si $r\geq 1,$ le plus long segment initial propre de $((x_{1},\epsilon _{1}),\ldots ,(x_{r},\epsilon _{r}))$ est $v=((x_{1},\epsilon _{1}),\ldots ,(x_{r-1},\epsilon _{r-1})).$
Soit X un ensemble. Si $v$, $w$ sont des éléments de F(X) (mot signés sur X), s'il existe un élément $v'$ de F(X) tel que $w=v'_{\mathrm {juxt} }v$, nous dirons que w finit par v.
Soit X un ensemble.
Nous dirons qu'une partie S de F(X) est schreiérienne si elle est non vide et que, pour tout élément w de longueur $\geq 1$ de S, le plus long segment initial propre de w appartient lui aussi à S.
Cela revient à dire que S n'est pas vide et que, pour tout élément w de S, tout segment initial de w appartient lui aussi à S.
D'après la seconde des caractérisations qu'on vient de donner d'une partie schreiérienne, il est clair que toute partie schreiérienne de F(X) comprend l'élément 1 de F(X), c'est-à-dire le mot signé vide.

## Transversales droites de Schreier

Soient X un ensemble et H un sous-groupe de F(X). Si une transversale droite T de H dans F(X) est une partie schreiérienne de F(X), on dit habituellement que T est une transversale droite de Schreier de H dans F(X).
Soient X un ensemble, soit F(X) le groupe libre construit sur X, soit H un sous-groupe de F(X). Il existe une transversale droite de Schreier de H dans F(X).
Démonstration. Dans la présente démonstration, on dira simplement « classe à droite » pour « classe à droite de H dans F(X) ».
Pour toute classe à droite C, définissons la longueur de C comme le plus petit nombre naturel n tel que C comprenne un élément (mot signé) de longueur n.
Pour tout nombre naturel n, désignons par $Cl_{n}$ l'ensemble des classes à droite de longueur n. (Il est possible que $Cl_{n}$ soit vide. Si H est d'indice fini dans F(X), il n'y a qu'un nombre fini de classes à droite, donc les longueurs de ces classes ne prennent qu'un nombre fini de valeurs.)
Soit n un nombre naturel, soit $T_{n}$ une partie de F(X) possédant les propriétés suivantes :
    (1) tout élément de $T_{n}$ est de longueur n et appartient à une classe à droite de longueur n;
    (2) pour toute classe à droite C de longueur n, il existe un et un seul élément de $T_{n}$ qui appartient à C.
Soit maintenant K une classe à droite de longueur n + 1 (s'il en existe). Nous allons prouver
    (thèse 3) qu'il existe dans K un mot signé de longueur n + 1 dont le plus long segment initial propre (autrement dit le segment initial de longueur n) appartient à $T_{n}$.
Choisissons dans K un élément de longueur n + 1, soit
    $((x_{1},\epsilon _{1}),\ldots ,(x_{n+1},\epsilon _{n+1}))=x_{1}^{\epsilon _{1}}\cdots x_{n+1}^{\epsilon _{n+1}}.$
Prouvons que
    (thèse 4) la classe à droite $Hx_{1}^{\epsilon _{1}}\cdots x_{n}^{\epsilon _{n}}$ est de longueur n.
Puisqu'elle comprend un élément de longueur n (l'élément $x_{1}^{\epsilon _{1}}\cdots x_{n}^{\epsilon _{n}}$), cette classe est de longueur $\leq n.$ Si elle était de longueur $\neq n,$ elle comprendrait donc un élément w de longueur < n.
Pour un tel élément w, on aurait
    $wx_{n+1}^{\epsilon _{n+1}}\in Hx_{1}^{\epsilon _{1}}\cdots x_{n}^{\epsilon _{n}}x_{n+1}^{\epsilon _{n+1}}=K$
donc K serait de longueur $\leq$ long(w) + 1 < n + 1, ce qui contredirait l'hypothèse long(K) = n + 1. Cette contradiction prouve notre thèse (4).
Nous pouvons donc faire $C=Hx_{1}^{\epsilon _{1}}\cdots x_{n}^{\epsilon _{n}}$ dans l'hypothèse (2). Nous trouvons que
    (5) $T_{n}$ comprend un élément $((y_{1},\zeta _{1}),\ldots ,(y_{n},\zeta _{n}))=y_{1}^{\zeta _{1}}\cdots y_{n}^{\zeta _{n}}$ de longueur n qui appartient à $Hx_{1}^{\epsilon _{1}}\cdots x_{n}^{\epsilon _{n}}$.
Il en résulte :
    (6) $y_{1}^{\zeta _{1}}\cdots y_{n}^{\zeta _{n}}x_{n+1}^{\epsilon _{n+1}}\in Hx_{1}^{\epsilon _{1}}\cdots x_{n}^{\epsilon _{n}}x_{n+1}^{\epsilon _{n+1}}=K.$
Puisque la classe à droite K est supposée de longueur n + 1, son élément $y_{1}^{\zeta _{1}}\cdots y_{n}^{\zeta _{n}}x_{n+1}^{\epsilon _{n+1}}$ est de longueur au moins n + 1, ce qui n'est possible que s'il est de longueur n + 1 exactement (autrement dit : s'il est réduit).
Donc $y_{1}^{\zeta _{1}}\cdots y_{n}^{\zeta _{n}}x_{n+1}^{\epsilon _{n+1}}$ est un mot signé réduit de longueur n + 1 qui, d'après (6), appartient à K et dont, d'après (5), le segment initial de longueur n appartient à $T_{n}$.
Nous avons donc démontré notre thèse (3), à savoir que si $T_{n}$ satisfait aux hypothèses (1) et (2), alors toute classe à droite K de longueur n + 1 comprend un mot signé de longueur n + 1 dont le plus long segment initial propre appartient à $T_{n}$.
D'après l'axiome du choix, il existe donc une application $f_{n+1}$ de $Cl_{n+1}$ dans F(S) telle que, pour toute classe à droite K de longueur n + 1,
    (7) $f_{n+1}(K)$ soit un mot signé de longueur n + 1 appartenant à K
et
    (8) le plus long segment initial propre de $f_{n+1}(K)$ appartienne à $T_{n}.$
Désignons par $T_{n+1}$ l'image de l'application $f_{n+1}$.
Alors, d'après (7) et (8),
    (9) tout élément de $T_{n+1}$ est un mot signé de longueur n + 1 et appartient à une classe à droite de longueur n + 1 ;
    (10) pour toute classe à droite K de longueur n + 1, il existe un et un seul élément de $T_{n+1}$ qui appartient à K ;
    (11) pour tout élément v de $T_{n+1}$, le plus long segment initial propre de v appartient à $T_{n}.$
Les deux premières de ces trois propriétés sont les analogues de (1) et (2) avec n + 1 au lieu de n. D'après la théorie des ensembles, nous pouvons donc construire inductivement, en partant de $T_{0}=\{1\},$ une suite infinie
    $(T_{n})_{n\in \mathbb {N} }$
possédant les propriétés suivantes :
    (12) tout élément de $T_{n}$ est de longueur n et appartient à une classe à droite de longueur n ;
    (13) pour toute classe à droite C de longueur n, il existe un et un seul élément de $T_{n}$ qui appartient à C ;
    (14) pour tout élément v de $T_{n+1}$, le plus long segment initial propre de v appartient à $T_{n}.$
Prouvons que $\bigcup _{n\in \mathbb {N} }T_{n}$ est alors une transversale droite de Schreier de H dans F(X).
* Prouvons d'abord que c'est une transversale droite de H dans F(X).
    Soit C une classe à droite ; notons $l$ sa longueur.
** D'après (13), il existe un et un seul élément de $T_{l}$ qui appartient à C.
** D'après (12), pour tout nombre naturel $n$ distinct de $l$, aucun élément de $T_{n}$ n'appartient à C (car si w est un élément de $T_{n}$, alors la classe à droite de w est de longueur $n\not =l$ et est donc distincte de C).
    On a donc bien :
       il existe un et un seul élément de $\bigcup _{n\in \mathbb {N} }T_{n}$ qui appartient à C.
* Prouvons que cette transversale droite est schreiérienne.
    Soit w un mot signé non vide appartenant à $\bigcup _{n\in \mathbb {N} }T_{n}$. Autrement dit, w appartient à $T_{r}$ pour un certain $r\geq 1$.
    D'après (14), le plus long segment initial propre de w appartient alors à $T_{r-1}\subseteq \bigcup _{n\in \mathbb {N} }T_{n}.$
Ceci achève la démonstration du lemme 1. ◻

## Théorème de Nielsen-Schreier dans F(X)

On va maintenant démontrer le théorème de Nielsen-Schreier, selon lequel tout sous-groupe d'un groupe libre est libre. Quelques lemmes qu'on utilisera à cette fin serviront encore à démontrer un autre théorème, le théorème de Howson.
Soient X un ensemble, T une partie schreiérienne de F(X), w un élément de F(X) n'appartenant pas à T. Il existe au moins un segment initial de w qui n'appartient pas à T (à savoir w), donc nous pouvons considérer le plus court segment initial de w n'appartenant pas à T.
Soient X un ensemble, T une partie schreiérienne de F(X), $w=((x_{1},\epsilon _{1})\ldots ,(x_{n},\epsilon _{n}))$ un élément de F(X) n'appartenant pas à T.
Le plus court segment initial de w n'appartenant pas à T est l'unique segment initial
    $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))$
de w tel que
    (i) $r\geq 1$ ;
    (ii) $((x_{1},\epsilon _{1})\ldots ,(x_{r-1},\epsilon _{r-1}))\in T;$
    (iii) $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))\notin T.$
Autrement dit, le plus court segment initial de w n'appartenant pas à T est l'unique segment initial de w de la forme
    $t_{\mathrm {juxt} }x$,
avec $t\in T,x\in {\tilde {X}}\cup ({\tilde {X}})^{-1},t_{\mathrm {juxt} }x\notin T.$
Il est clair que si $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))$ désigne le plus court segment initial de w n'appartenant pas à T, les conditions (i), (ii) et (iii) sont satisfaites. (La condition (i) est satisfaite parce que, comme on l'a noté, toute partie schréiérienne de F(X) comprend le neutre de F(X).)
Il reste à prouver que si un segment initial $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))$ de w satisfait aux conditions (i), (ii) et (iii), ce segment est le plus court segment initial de w n'appartenant pas à T.
Soit v un segment initial de w strictement plus court que $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))$ ; il s'agit de prouver que v appartient à T. Or v est un segment initial de $((x_{1},\epsilon _{1})\ldots ,(x_{r-1},\epsilon _{r-1})).$ Puisque, d'après l'hypothèse (ii), $((x_{1},\epsilon _{1})\ldots ,(x_{r-1},\epsilon _{r-1}))$ appartient à T et puisque T est schreiérienne, v appartient à T, comme annoncé.
Soient X un ensemble, T une partie schreiérienne de F(X), w un élément de F(X). Il existe au moins un segment initial de w qui appartient à T (à savoir le segment initial vide), donc nous pouvons considérer le plus long segment initial de w qui appartient à T.
Soit X un ensemble, soit T une partie schreiérienne de F(X), soit $w=((x_{1},\epsilon _{1})\ldots ,(x_{n},\epsilon _{n}))$ un élément de F(X) n'appartenant pas à T.
Le plus long segment initial de w appartenant à T est l'unique segment initial
    $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))$
de w possédant les propriétés suivantes :
    (i) $r\leq n-1;$
    (ii) $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))\in T;$
    (iii) $((x_{1},\epsilon _{1})\ldots ,(x_{r+1},\epsilon _{r+1}))\notin T.$
Si w' désigne le plus court segment initial de w n'appartenant pas à T, le plus long segment initial de w appartenant à T est le plus long segment initial propre de w'.
Il est clair que si $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))$ désigne le plus long segment initial de w appartenant à T, les conditions (i), (ii) et (iii) sont satisfaites.
Il reste à prouver que si un segment initial $((x_{1},\epsilon _{1})\ldots ,(x_{r},\epsilon _{r}))$ de w satisfait aux conditions (i), (ii) et (iii), ce segment est le plus court segment initial de w n'appartenant pas à T.
Soit s un nombre naturel tel que $r<s\leq n$ ; il s'agit de prouver que
    $((x_{1},\epsilon _{1})\ldots ,(x_{s},\epsilon _{s}))$ n'appartient pas à T. Or $((x_{1},\epsilon _{1})\ldots ,(x_{r+1},\epsilon _{r+1}))$ est un segment initial de $((x_{1},\epsilon _{1})\ldots ,(x_{s},\epsilon _{s}))$ et, d'après l'hypothèse (iii), n'appartient pas à T. Puisque T est schreiérienne, il en résulte que $((x_{1},\epsilon _{1})\ldots ,(x_{s},\epsilon _{s}))$ n'appartient pas à T, comme annoncé.
Nous avons ainsi démontré la première assertion de l'énoncé. La seconde résulte de la première et du lemme 2.
Soient X un ensemble, T une partie schreiérienne de F(X), soit w un élément de F(X) n'appartenant pas à T.
Nous définirons la lettre signée pivot de w (relativement à T) comme la dernière lettre signée du plus court segment initial de w n'appartenant pas à T.
(Ce n'est pas une dénomination standard.)
Soient X un ensemble, T une partie schreiérienne de F(X), w un élément de F(X) n'appartenant pas à T. La lettre signée pivot de w (relativement à T) est l'unique lettre signée x telle que w admette un segment initial de la forme $t_{\mathrm {juxt} }x$ avec $t\in T$ et $t_{\mathrm {juxt} }x\notin T.$
Démonstration. C'est une conséquence immédiate du lemme 2.
$h_{t,x}$
${\overline {w}}$
$Y$
Soient X un ensemble et ${\tilde {X}}$ la base canonique de F(X). Soient H un sous-groupe de F(X) et T une transversale droite de Schreier de H dans F(X).
* Pour tout élément t de T et tout élément $x\in {\tilde {X}}$, nous désignerons par $h_{t,x}$ l'unique élément de H tel que
    $tx\in h_{t,x}T.$
* Pour tout élément w de F(X), nous noterons ${\overline {w}}$ l'unique élément de T qui appartient à la classe à droite de w modulo H.
* Nous considérerons l'ensemble
    $Y:=\{h_{t,x}\mid t\in T,x\in {\tilde {X}},h_{t,x}\neq 1\}$.
$Y\cup Y^{-1}$
Avec les notations ci-dessus, on a :
    1° $h_{t,x}=tx({\overline {tx}})^{-1}.$
Soient t un élément de T et x un élément de ${\tilde {X}}$ tels que
    $h_{t,x}\not =1.$
Alors
    2° $h_{t,x}\notin T,(h_{t,x})^{-1}\notin T;$
    3° $h_{t,x}=t_{\mathrm {juxt} }x_{\mathrm {juxt} }({\overline {tx}})^{-1}$
    (ou encore : $tx=t_{\mathrm {juxt} }x$ et $x({\overline {tx}})^{-1}=x_{\mathrm {juxt} }({\overline {tx}})^{-1}$) ;
    4° le plus long segment initial de $h_{t,x}$ appartenant à T est t ;
    5° la lettre signée pivot de $h_{t,x}$ (par rapport à T) est x ;
    6° le plus long segment initial de $(h_{t,x})^{-1}$ appartenant à T est ${\overline {tx}}$ ;
    7° la lettre signée pivot de $(h_{t,x})^{-1}$ (par rapport à T) est $x^{-1}.$
Démonstration.
Soit w un élément de F(X). Puisque T est une transversale droite de H dans F(X),
    (1) w s'écrit d'une et une seule façon sous la forme $w=ht$ avec h dans H et t dans T.
Alors
    (2) h est l'unique élément de H tel que $w\in hT.$
D'autre part, t appartient à Hw, donc, dans les notations de l'énoncé, ${\overline {w}}=t,$ donc $w({\overline {w}})^{-1}=wt^{-1}=h.$ Donc, d'après (2), $w({\overline {w}})^{-1}$ est l'unique élément h de H tel que $w\in hT.$ En faisant w = tx, nous obtenons l'assertion 1° de l'énoncé.
Soient t un élément de T et x un élément de ${\tilde {X}}$ tels que
    (3) $h_{t,x}\not =1.$
Puisque $h_{t,x}$ appartient à H et que $H\cap T=\{1\}$ (ceci parce que T est une transversale droite de H dans F(X) et que T, étant schreiérienne, comprend l'élément 1), nous avons donc
    $h_{t,x}\notin T.$
De même,
    $(h_{t,x})^{-1}\notin T.$
Nous avons donc prouvé l'assertion 2° de l'énoncé (ce qui nous permet de parler de la lettre signée pivot de $h_{t,x}$ et de celle de $(h_{t,x})^{-1}$).
L'hypothèse (3), à savoir $h_{t,x}\neq 1,$ signifie (par définition de $h_{t,x}$)
    (4) $tx\notin T.$
D'après 1°, $h_{t,x}^{-1}t=1{\overline {tx}}x^{-1}$ d'où, d'après (3) et l'unicité affirmée en (1) :
    (5) ${\overline {tx}}x^{-1}\notin T.$
D'après (4) (et puisque t appartient à T qui est schreiérienne), tx n'est pas un segment initial de t donc
    (6) $tx=t_{\mathrm {juxt} }x.$
De même, d'après (5), ${\overline {tx}}x^{-1}$ n'est pas un segment initial de ${\overline {tx}}$ donc ${\overline {tx}}$ ne finit pas par x, si bien que
    $({\overline {tx}})^{-1}$ ne commence pas par $x^{-1}$
ou encore :
    (7) $x({\overline {tx}})^{-1}=x_{\mathrm {juxt} }({\overline {tx}})^{-1}$.
D'après (6), (7) et l'assertion 1° de l'énoncé,
    (8) $h_{t,x}=t_{\mathrm {juxt} }x_{\mathrm {juxt} }({\overline {tx}})^{-1},$
ce qui prouve l'assertion 3°.
Nous avons vu en (4) que tx n'appartient pas à T. Puisque t appartient à T, l'assertion 3° de l'énoncé et les lemmes 3 et 4 montrent donc que le plus long segment initial de $h_{t,x}$ appartenant à T est égal à t et que la lettre signée pivot de $h_{t,x}$ (par rapport à T) est x, ce qui prouve les assertions 4° et 5° de l'énoncé.
En passant aux inverses dans la relation (8), nous trouvons
    (9) $h_{t,x}^{-1}={\overline {tx}}_{\mathrm {juxt} }x^{-1}\ _{\mathrm {juxt} }t^{-1}.$
Nous avons vu en (5) que ${\overline {tx}}x^{-1}$ n'appartient pas à T. Puisque ${\overline {tx}}$ appartient à T, la relation (9) et les lemmes 3 et 4 montrent donc que le plus long segment initial de $h_{t,x}^{-1}$ appartenant à T est égal à ${\overline {tx}}$ et que la lettre signée pivot de $h_{t,x}^{-1}$ (par rapport à T) est $x^{-1}$, ce qui prouve les assertions 6° et 7° de l'énoncé.
$(t,x,\epsilon )\mapsto$
$h_{t,x}^{\epsilon }$
Avec les notations ci-dessus, soient t, u des éléments de T et x, y des éléments de ${\tilde {X}}$ tels que
    $h_{t,x}\not =1$ et $h_{u,y}\not =1.$
Soient $\epsilon$ et $\eta$ des éléments de $\{1,-1\}\subset \mathbb {Z} .$
On suppose que
    (i) le plus long segment initial de $h_{t,x}^{\epsilon }$ appartenant à T est égal au plus long segment initial de $h_{u,y}^{\eta }$ appartenant à T
et que
    (ii) la lettre signée pivot de $h_{t,x}^{\epsilon }$ (par rapport à T) est égale à la lettre signée pivot de $h_{u,y}^{\eta }$ (par rapport à T).
(D'après le lemme 3, seconde assertion, les hypothèses (i) et (ii) reviennent à dire que le plus court segment initial de $h_{t,x}^{\epsilon }$ n'appartenant pas à T est égal au plus court segment initial de $h_{u,y}^{\eta }$ n'appartenant pas à T.)
Alors
    1° $\epsilon =\eta$ ;
    2° x = y ;
    3° t = u.
Posons x = ((x', 1)) et y = ((y', 1)), avec x' et y' dans X.
D'après le lemme 5, assertions 5° et 7°, la lettre signée pivot de $h_{t,x}^{\epsilon }$ (par rapport à T) est égale à $x^{\epsilon }=((x',\epsilon ))$ et la lettre signée pivot de $h_{u,y}^{\eta }$ (par rapport à T) est $y^{\eta }=((y',\eta )).$ D'après l'hypothèse (ii) de l'énoncé, nous avons donc
    $((x',\epsilon ))=((y',\eta )),$
d'où
    (1) $\epsilon =\eta$
et
    (2) x = y,
ce qui prouve les assertions 1° et 2° de l'énoncé.
D'après (1), nous avons
    (3) ou bien $\epsilon =\eta =1$ ou bien $\epsilon =\eta =-1.$
* Supposons d'abord
       (hyp. 4) $\epsilon =\eta =1.$
    Alors l'hypothèse (i) de l'énoncé signifie que
       le plus long segment initial de $h_{t,x}$ appartenant à T est égal au plus long segment initial de $h_{u,y}$ appartenant à T.
    D'après le lemme 5, assertion 4°, cela revient à dire que t = u, ce qui achève de démontrer l'énoncé dans l'hypothèse (4).
* Si maintenant l'hypothèse (4) n'est pas satisfaite, alors, d'après (3),
       $\epsilon =\eta =-1.$
    Donc l'hypothèse (i) de l'énoncé signifie que
       le plus long segment initial de $h_{t,x}^{-1}$ appartenant à T est égal au plus long segment initial de $h_{u,y}^{-1}$ appartenant à T.
    D'après le lemme 5, assertion 6°, cela revient à dire que
       (5) ${\overline {tx}}={\overline {uy}},$
    où, pour tout élément w de F(X), ${\overline {w}}$ désigne l'unique élément de T appartenant à Hw.
    Nous avons vu en (2) que y = x, donc notre résultat (5) peut s'écrire
       ${\overline {tx}}={\overline {ux}},$
    d'où
       Htx = Hux
       Ht = Hu,
    Comme t et u appartiennent à la transversale T, on a donc t = u, ce qui achève de démontrer l'énoncé.
$Y\cup Y^{-1}$
Avec les notations ci-dessus, si r est un nombre naturel > 0, si $y_{1},\dots ,y_{r}\in Y$, si $\epsilon _{1},\dots ,\epsilon _{r}\in \{1,-1\}\subset \mathbb {Z} ,$ si le mot signé dans Y
    $((y_{1},\epsilon _{1}),\ldots ,(y_{r},\epsilon _{r}))$
est réduit (sur Y), alors
    l'élément $y_{1}^{\epsilon _{1}}\cdots y_{r}^{\epsilon _{r}}$ de F(X) commence (une fois explicité dans F(X)) par le plus court segment initial de $y_{1}^{\epsilon _{1}}$ n'appartenant pas à T.
Rappelons que d'après le lemme 5, assertion 2°, pour tout $y\in Y$, $y^{\pm 1}\notin T,$ de sorte qu'il est légitime de parler du plus court segment initial de $y_{1}^{\epsilon _{1}}$ n'appartenant pas à T.
On raisonne par récurrence sur r. Pour r = 1, l'énoncé est banal. Supposons que r est au moins égal à 2 et que l'énoncé est vrai pour r - 1 au lieu de r.
Pour $i$ de 1 à r, soient $t_{i}\in T$ et $x_{i}\in {\tilde {X}}$ tels que $y_{i}=h_{t_{i},x_{i}}$.
    (1) Notons $t'_{2}\ _{\mathrm {juxt} }x'_{2}=t'_{2}x'_{2}$, avec $t'_{2}\in T,x'_{2}\in {\tilde {X}}\cup ({\tilde {X}})^{-1},t'_{2}x'_{2}\notin T,$ le plus court segment initial de $y_{2}^{\epsilon _{2}}$ n'appartenant pas à T.
Par hypothèse de récurrence sur r, $y_{2}^{\epsilon _{2}}\cdots y_{r}^{\epsilon _{r}}$ commence par $t'_{2}\ _{\mathrm {juxt} }x'_{2}.$ On peut donc écrire
    (2) $y_{2}^{\epsilon _{2}}\cdots y_{r}^{\epsilon _{r}}=(t'_{2}\ _{\mathrm {juxt} }x'_{2})_{\mathrm {juxt} }w,$
avec $w\in F(X).$
Alors
    (3) $y_{1}^{\epsilon _{1}}\ y_{2}^{\epsilon _{2}}\cdots y_{r}^{\epsilon _{r}}=h_{t_{1}^{\epsilon _{1}},x_{1}}\star (t'_{2}\ _{\mathrm {juxt} }{x'_{2}}_{\mathrm {juxt} }w),$
où $\star$ désigne la loi de groupe de F(X). D'après le lemme 5, assertion 3°, $y_{1}^{\epsilon _{1}}$ est de la forme
    (4) $y_{1}^{\epsilon _{1}}=t'_{1}\ _{\mathrm {juxt} }x'_{1}\ _{\mathrm {juxt} }{t''_{1}}^{-1},$ avec $t'_{1},t''_{1}\in T,x'_{1}\in {\tilde {X}}\cup ({\tilde {X}})^{-1},t'_{1}x'_{1}\notin T,t''_{1}(x''_{1})^{-1}\notin T.$
Le résultat (3) s'écrit alors
    (5) $y_{1}^{\epsilon _{1}}\ y_{2}^{\epsilon _{2}}\cdots y_{r}^{\epsilon _{r}}=({{t'_{1}}\ _{\mathrm {juxt} }}{x'_{1}\ _{\mathrm {juxt} }}{t''_{1}}^{-1})\star ({t'_{2}}\ _{\mathrm {juxt} }{x'_{2}}_{\mathrm {juxt} }w).$
Supposons que l'énoncé soit faux, c'est-à-dire que
    (hyp. 6) $y_{1}^{\epsilon _{1}}\cdots y_{r}^{\epsilon _{r}}$ ne commence pas par le plus court segment initial de $y_{1}^{\epsilon _{1}}$ n'appartenant pas à T.
D'après (4) et le lemme 2, cela revient à dire que
    $y_{1}^{\epsilon _{1}}\cdots y_{r}^{\epsilon _{r}}$ ne commence pas par $t'_{1}\ \mathrm {juxt} x'_{1},$
ce qui, d'après (5), revient à dire que
    $({{t'_{1}}\ _{\mathrm {juxt} }}{x'_{1}\ _{\mathrm {juxt} }}{t''_{1}}^{-1})\star ({t'_{2}}\ _{\mathrm {juxt} }{x'_{2}}_{\mathrm {juxt} }w)$ ne commence pas par $t'_{1}\ \mathrm {juxt} x'_{1}.$
Vu la définition de la loi de groupe $\star$ de F(X), il faut donc que
    (7) ${t'_{2}}\ _{\mathrm {juxt} }{x'_{2}}_{\mathrm {juxt} }w$ commence par ${t''_{1}}\ _{\mathrm {juxt} }{x'_{1}}^{-1}.$
On a vu en (4) que $t''_{1}$ appartient à T et que $t''_{1}(x''_{1})^{-1}$ n'appartient pas à T, donc, d'après (7) et le lemme 2,
    (8) ${t''_{1}}\ _{\mathrm {juxt} }{x'_{1}}^{-1}$ est le plus court segment initial de ${t'_{2}}\ _{\mathrm {juxt} }{x'_{2}}_{\mathrm {juxt} }w$ n'appartenant pas à T.
D'autre part, d'après (1), $t'_{2}$ appartient à T et $t'_{2}x'_{2}$ n'appartient pas à T, donc, d'après le lemme 2, le plus court segment initial de ${t'_{2}}\ _{\mathrm {juxt} }{x'_{2}}_{\mathrm {juxt} }w$ n'appartenant pas à T est ${t'_{2}}\ _{\mathrm {juxt} }x'_{2}.$ La comparaison de ceci avec (8) donne
    (9) ${t''_{1}}\ _{\mathrm {juxt} }{x'_{1}}^{-1}={t'_{2}}\ _{\mathrm {juxt} }x'_{2}.$
D'après (4) et le lemme 2, le membre gauche de (9) est le plus court segment initial de $y_{1}^{-\epsilon _{1}}$ n'appartenant pas à T et, d'après (1), le membre droit de (9) est le plus court segment initial de $y_{2}^{\epsilon _{2}}$ n'appartenant pas à T. La relation (9) signifie donc que
    le plus court segment initial de $y_{1}^{-\epsilon _{1}}$ n'appartenant pas à T et le plus court segment initial de $y_{2}^{\epsilon _{2}}$ n'appartenant pas à T sont égaux.
D'après le lemme 6, on a donc
    (10) $-\epsilon _{1}=\epsilon _{2}$
et $t_{1}=t_{2},x_{1}=x_{2},$, ces deux égalités entraînant évidemment
    (11) $y_{1}=y_{2}.$
Les résultats (10) et (11) contredisent l'hypothèse (2), selon laquelle le mot signé $((y_{1},\epsilon _{1}),\ldots ,(y_{r},\epsilon _{r}))$ sur Y est réduit. Cette contradiction prouve que notre hypothèse (6) est fausse, donc l'énoncé est vrai.
Avec les notations ci-dessus, $Y$ est une base du groupe H.
Démonstration.
D'après le lemme de Schreier (chapitre « Classes modulo un sous-groupe »), $Y\cup \{1\}$ est une partie génératrice de H. Donc
    Y est une partie génératrice de H.
Si l'on ôte l'élément 1 d'une partie génératrice d'un groupe, on obtient encore une partie génératrice de ce groupe (le sous-groupe engendré par une partie A contient $A\cup \{1\}$, donc, par minimalité du sous-groupe engendré par $A\cup \{1\}$, le sous-groupe engendré par $A\cup \{1\}$ est contenu dans le sous-groupe engendré par A).
D'après la définition d'une partie libre donnée au chapitre Groupes libres, premiers éléments, une partie d'un groupe G est une partie libre de G si et seulement c'est une base du sous-groupe de G qu'elle engendre. Donc, pour prouver que Y est une base de H, il suffit de prouver que
    (thèse 1) Y est une partie libre de F(X).
Soient r un nombre naturel $\geq 1,y_{1},\dots ,y_{r}\in Y$, $\epsilon _{1},\dots ,\epsilon _{r}\in \{1,-1\}\subset \mathbb {Z} ,$ tels que
    (hyp. 2) le mot signé $((y_{1},\epsilon _{1}),\ldots ,(y_{r},\epsilon _{r}))$ sur Y soit réduit.
Pour prouver notre thèse (1), il s'agit de prouver que
    (thèse 3) $y_{1}^{\epsilon _{1}}\cdots y_{r}^{\epsilon _{r}}\neq 1$ dans F(X).
Rappelons à nouveau (preuve du lemme 7) que les $y_{i}^{\pm 1}$ n'appartiennent pas à T, donc on peut parler du plus court segment initial de $y_{1}^{\epsilon _{1}}$ n'appartenant pas à T. D'après le lemme 7,
    (4) $y_{1}^{\epsilon _{1}}\cdots y_{r}^{\epsilon _{r}}$ commence (une fois explicité dans F(X)) par le plus court segment initial de $y_{1}^{\epsilon _{1}}$ n'appartenant pas à T.
Puisque ce segment initial n'appartient pas à T, il est distinct de 1, donc le résultat (4) entraîne la thèse (3), donc le lemme 8 est démontré. ◻

## Théorème de Nielsen-Schreier dans un groupe libre quelconque

On va maintenant introduire quelques définitions qui permettront d'étendre ce lemme 8 aux groupes libres généraux au lieu des groupes libres F(X). C'est un petit travail assez trivial, sur lequel on peut passer rapidement.
Soient L un groupe libre, X une base de L, v et w des éléments de L. Nous dirons que v est un segment initial de w relativement à la base X de L si, l'expression réduite de w dans la base X étant ${x_{1}}^{\epsilon _{1}}\cdots {x_{n}}^{\epsilon _{n}}$, v est un des éléments ${x_{1}}^{\epsilon _{1}}\cdots {x_{r}}^{\epsilon _{r}}$, avec $0\leq r\leq n$.
Remarques. 1. Toujours dans l'hypothèse où X est une base de L, désignons par $\sigma _{X}$ l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X qui représente a dans la base X de L (voir chapitre Groupes libres, premiers éléments, énoncé 6). Pour des éléments v, w de L, dire que v est un segment intial de w relativement à la base X de L revient à dire que $\sigma _{X}(v)$ est un segment initial de $\sigma _{X}(w)$ dans le premier sens de l'expression « segment initial ».
2. Soient v et w des éléments du groupe libre F(X) construit sur l'ensemble X. Dire que v est un segment initial de w relativement à la base canonique ${\tilde {X}}$ de F(X) revient à dire que v est un segment initial de w dans le premier sens de l'expression « segment initial ».
Soient $v=((x_{1},\epsilon _{1}),\ldots ,(x_{r},\epsilon _{r}))$ et $w=((y_{1},\zeta _{1}),\ldots ,(y_{n},\zeta _{n}))$. Alors $v=((x_{1},1))^{\epsilon _{1}}\cdots ((x_{r},1))_{r}^{\epsilon }))$ et $w=((y_{1},1))^{\zeta _{1}}\cdots ((y_{n},1))_{n}^{\epsilon }))$, où les membres droits sont calculés selon la loi de groupe de F(X). Donc, si $\sigma _{\tilde {X}}$ désigne l'isomorphisme de F(X) sur $F({\tilde {X}})$ qui à tout élément u de F(X) (mot signé sur X) fait correspondre le mot signé sur ${\tilde {X}}$ qui représente u dans la base ${\tilde {X}}$ de F(X), nous avons
    $\sigma _{\tilde {X}}(v)=(((x_{1},1),1))^{\epsilon _{1}}\cdots (((x_{r},1),1))^{\epsilon _{r}},$
où le membre droit est calculé dans le groupe $F({\tilde {X}})$. Autrement dit,
    $\sigma _{\tilde {X}}(v)=(((x_{1},1),\epsilon _{1}),\ldots ,((x_{r},1),\epsilon _{r})).$
De même,
    $\sigma _{\tilde {X}}(w)=(((y_{1},1),\zeta _{1}),\ldots ,((y_{n},1),\zeta _{n})).$
Donc, d'après la remarque 1, v est un segment initial de w relativement à la base ${\tilde {X}}$ de F(X) si et seulement si $(((x_{1},1),\epsilon _{1}),\ldots ,((x_{r},1),\epsilon _{r}))$ est un segment initial de $(((y_{1},1),\zeta _{1}),\ldots ,((y_{n},1),\zeta _{n}))$ au premier sens de l'expression « segment initial ». Ceci revient clairement à ce que $((x_{1},\epsilon _{1}),\ldots ,(x_{r},\epsilon _{r}))$ soit un segment initial de $((y_{1},\zeta _{1}),\ldots ,(y_{n},\zeta _{n}))$ au premier sens de l'expression « segment initial », autrement dit à ce que v soit un segment initial de w au premier sens de l'expression « segment initial ».
Soient L un groupe libre, X une base de L, S une partie de L. Nous dirons que S est une partie schreiérienne de L relativement à la base X de L si S n'est pas vide et que, pour tout élément w de S, tout segment initial de w relativement à la base X appartient à S.
Remarques. 1. Dans les mêmes hypothèses, désignons de nouveau par $\sigma _{X}$ l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X représentant a dans la base X. D'après la première remarque sur la définition d'un segment initial relativement à une base, dire que S est une partie schreiérienne de L relativement à la base X de L revient à dire que $\sigma _{X}(S)$ est une partie schreiérienne de F(X) dans le premier sens de l'expression « partie schreiérienne ».
2. D'après la seconde remarque sur la définition d'un segment initial relativement à une base, dire qu'une partie S du groupe libre F(X) construit sur X est une partie schreiérienne de F(X) relativement à la base ${\tilde {X}}$ revient à dire que S est une partie schreiérienne de F(X) au premier sens de l'expression « partie schreiérienne ».
Soient L un groupe libre, X une base de L et K un sous-groupe de L. Il existe une transversale droite de K dans L qui est schreiérienne par rapport à la base X de L. (Nous dirons « transversale droite de Schreier de K dans L relativement à la base X ».)
Désignons par $\sigma _{X}$ l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X représentant a dans la base X. D'après le lemme 1, il existe une transversale droite T de $\sigma _{X}(K)$ dans F(X) qui est une partie schreiérienne de F(X) au premier sens de l'expression « partie schreiérienne ». Alors, d'après la première remarque sur la définition d'une partie schreiérienne relativement à une base, ${\sigma _{X}}^{-1}(T)$ est une partie schreiérienne de L relativement à la base de X. D'autre part, puisque T est une transversale droite de $\sigma _{X}(K)$ dans F(X), ${\sigma _{X}}^{-1}(T)$ est une transversale droite de K dans L (cela tient simplement à ce que ${\sigma _{X}}^{-1}$ est un isomorphisme).
Donc ${\sigma _{X}}^{-1}(T)$ est une transversale droite de Schreier de K dans L relativement à la base X.
Soient L un groupe libre, X une base de L, K un sous-groupe de L et U une transversale droite de Schreier de K dans L relativement à la base X. Pour u dans U et x dans X, désignons par $k_{u,x}$ l'unique élément de K tel que
    $ux\in k_{u,x}U.$
Alors l'ensemble
    $\{k_{u,x}|u\in U,x\in X,k_{u,x}\not =1\}$
est une base du groupe K.
D'après la remarque 2 suivant la définition d'une partie schreiérienne relativement à une base, le lemme 8 est un cas particulier du lemme 10. On aurait pu rédiger la démonstration du lemme 8 de façon qu'elle fournisse tout de suite l'énoncé général, mais on va déduire l'énoncé général de l'énoncé particulier.
Désignons de nouveau par $\sigma _{X}$ l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X représentant a dans la base X. Alors (pour u dans U et x dans X) $\sigma _{X}(k_{u,x})$ est l'unique élément de $\sigma _{X}(K)$ tel que
    $\sigma _{X}(ux)\in \sigma _{X}(k_{u,x})\sigma _{X}(U),$
autrement dit tel que
    $\sigma _{X}(u)\sigma _{X}(x)\in \sigma _{X}(k_{u,x})\sigma _{X}(U).$
Donc, si on pose $H=\sigma _{X}(K)$ et $T=\sigma _{X}(U)$,
    T est une transversale droite de Schreier (au premier sens) de H dans F(X)
et
    $\sigma _{X}(k_{u,x})=h_{\sigma _{X}(u),\sigma _{X}(x)},$
où, comme au lemme 8, $h_{t,\sigma _{X}(x)}$ désigne l'unique élément de H tel que
    $t\sigma _{X}(x)\in h_{t,\sigma _{X}(x)}T.$
D'après le lemme 8, les $h_{t,\sigma _{X}(x)},$ avec $t\in T,x\in X,h_{t,\sigma _{X}(x)}\not =1,$ forment une base de $H=\sigma _{X}(K).$ En passant aux images par ${\sigma _{X}}^{-1},$ on trouve que
    les $k_{{\sigma _{X}}^{-1}(t),x},$ avec $t\in T,x\in X,k_{{\sigma _{X}}^{-1}(t),x}\not =1,$ forment une base du groupe K.
Puisque les ${\sigma _{X}}^{-1}(t)$ avec $t\in T$ sont les $u\in U,$ cela revient à dire que les $k_{u,x},$ avec $u\in U,x\in X,k_{u,x}\not =1,$ forment une base du groupe K, ce qu'il fallait démontrer.
Tout sous-groupe d'un groupe libre est un groupe libre.
Démonstration. C'est une conséquence immédiate du lemme 10.
Remarques. 1. On déduit immédiatement du lemme 8 que tout sous-groupe de F(X) est un groupe libre, ce qui est un cas particulier du théorème de Nielsen-Schreier. Puisque tout groupe libre est isomorphe à un groupe F(X), on en déduit facilement le théorème de Nielsen-Schreier dans sa forme générale. Donc, si on ne s'intéressait qu'au théorème de Nielsen-Schreier, on pourrait se passer de ce qui suit le lemme 8 et précède l'énoncé 11. Néanmoins, le lemme 10 n'est pas sans intérêt, car il permet de traiter directement des groupes libres qui ne sont pas du type F(X) (voir les exercices).
2. On verra dans les exercices que le rang d'un sous-groupe d'un groupe libre L peut être strictement supérieur au rang de L (ce qui rompt l'analogie entre les bases d'un groupe et les bases d'un espace vectoriel).