Monoïde/Composé d'une séquence

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Dans la suite, E désigne un monoïde et sa loi de composition est notée sous forme multiplicative, c'est-à-dire que nous écrirons $xy$ pour désigner le composé de $x$ et $y$. L'élément neutre sera noté 1.

Composé d'une séquence (finie) d'éléments d'un monoïde

Définissons récursivement le composé (« produit » dans notre notation) $\prod _{i=1}^{n}x_{i}=x_{1}\ldots x_{n}$ d'un n-uplet $(x_{i})_{1\leq i\leq n}$ d'éléments de E pour tout entier naturel n ou plus généralement, le composé $\prod _{i\in I}x_{i}$ d'une séquence d'éléments de E, c'est-à-dire d'une famille $(x_{i})_{i\in I}$ indexée par un ensemble fini totalement ordonné :

• le produit indexé par l'ensemble vide est égal à 1 ;
• si $\beta$ est le plus grand élément de $I$, $\prod _{i\in I}x_{i}=\left(\prod _{i\in I\setminus \{\beta \}}x_{i}\right)x_{\beta }$.

Pour les n-uplets, cette condition s'écrit :

$\prod _{i=1}^{n+1}x_{i}=\left(\prod _{i=1}^{n}x_{i}\right)x_{n+1}$

ou encore :

$x_{1}\ldots x_{n+1}=(x_{1}\ldots x_{n})x_{n+1}\quad (1)$.

La « généralisation » des n-uplets aux séquences n'est qu'un artifice de notation — si deux séquences $(x_{i})_{i\in I}$ et $(y_{j})_{j\in J}$ sont équivalentes (c'est-à-dire s'il existe un isomorphisme $\sigma$ d'ensembles ordonnés de $I$ sur $J$ tel que, pour tout $i\in I$, $y_{\sigma (i)}=x_{i}$) alors leurs composés sont égaux, or toute séquence est canoniquement équivalente à un n-uplet — mais elle aide à formuler le théorème d'associativité suivant :

Début d’un théorème

Théorème d'associativité

Soient E un monoïde, A et I deux ensembles finis totalement ordonnés, et $\left(A_{i}\right)_{i\in I}$ une famille de parties de A dont la réunion est A tout entier (on n'exclut pas que certains des ensembles considérés soient vides). On suppose que si i et j sont deux éléments de I tels que i < j, alors a < b pour tout $a\in A_{i}$ et tout $b\in A_{j}$. Pour toute séquence $\left(x_{a}\right)_{a\in A}$ d'éléments de E indexée par A, on a

$\prod _{a\in A}x_{a}=\prod _{i\in I}\prod _{a\in A_{i}}x_{a}$.

Fin du théorème

Un corollaire est que pour tout (n + 1)-uplet $(x_{1},\ldots ,x_{n+1})$ d'éléments de E,

$x_{1}\ldots x_{n+1}=x_{1}(x_{2}\ldots x_{n+1})\quad (2)$.

Cette formule (2), ou la formule (1) précédente, est couramment présentée — jointe à la définition du produit du 0-uplet comme étant égal à 1 — comme définition de $x_{1}\ldots x_{n}$ par récurrence sur n. Le corollaire permet de prouver l'équivalence de ces deux définitions, par récurrence sur le nombre de facteurs.

Si le monoïde E est commutatif, on peut définir le composé d'une famille finie d'éléments de E sans préciser un ordre sur l'index de cette famille, car on prouve que le composé, tel que défini ci-dessus, est alors indépendant de l'ordre choisi. Plus généralement, si E est un monoïde non forcément commutatif, si $(x_{i})_{i\in I}$ est une famille d'éléments de E dont tous les éléments commutent l'un avec l'autre, le produit des éléments de cette famille ne dépend pas de l'ordre choisi. C'est le « théorème de commutativité ». Ce théorème revient à dire que si $(x_{i})_{i\in I}$ est une famille finie d'éléments d'un monoïde qui commutent tous l'un avec l'autre, si $\sigma$ est une permutation de l’ensemble $I$, $\prod _{i\in I}x_{i}=\prod _{i\in I}x_{\sigma (i)}$. Plus généralement, si $(x_{i})_{i\in I}$ est une famille finie d'éléments d'un monoïde qui commutent tous l'un avec l'autre, si $\sigma$ est une bijection d'un ensemble $J$ sur $I$, $\prod _{i\in I}x_{i}=\prod _{j\in J}x_{\sigma (j)}.$

Le lemme suivant est utilisé dans le chapitre « Produit direct et somme restreinte » du cours sur les groupes :

Début d'un lemme

Lemme

Soient M un monoïde et x₁, … , x_n, y₁, … , y_n des éléments de M. Si, pour tous indices i > j, x_i commute avec y_j, alors

x₁…x_n y₁…y_n = x₁ y₁…x_n y_n.

Fin du lemme

Démonstration

Preuve par récurrence sur n. Si n = 0, les deux membres de la thèse sont égaux à 1, donc la thèse est vraie dans ce cas. Supposons que n soit un nombre naturel > 0 et que la thèse soit vraie pour n – 1 au lieu de n, et prouvons que la thèse est vraie pour n.

Puisque x_n commute avec chacun des éléments y₁, … , y_n-1, nous pouvons remplacer, dans le premier membre de la thèse, x_n y₁…y_n-1 par y₁…y_n-1 x_n, donc

x₁…x_n y₁…y_n = x₁…x_n-1 y₁…y_n-1 x_n y_n.

Par hypothèse de récurrence, nous pouvons remplacer dans le second membre x₁…x_n-1 y₁…y_n-1 par x₁ y₁…x_n-1 y_n-1, d'où la thèse.

 

Remarque

C'est vrai a fortiori dans l'hypothèse plus forte où tous les éléments x₁, … , x_n, y₁, … , y_n commutent deux à deux. Dans ce cas, l'énoncé est un cas particulier du théorème de commutativité.