2 Monoïdes

Définition 2.0.1

Un monoïde est un ensemble $M$ muni d’un loi de composition interne, disons notée multiplicativement, et d’un élément $e$ tels que :

la multiplication est associative : $∀ x\; y\; z, x(yz) = (xy)z$
$e$ est neutre à gauche : $∀ x, ex = x$
$e$ est neutre à droite : $∀ x, xe = x$

On dit qu’un monoïde est commutatif si $∀ x\, y, xy = yx$.

On utilise aussi le symbole d’addition pour la loi de composition interne de certains monoïdes commutatifs (mais jamais si la loi n’est pas commutative). L’élément neutre $e$ est souvent noté $1$ ou $1_M$ en notation multiplicative ou bien $0$ ou $0_M$ en notation additive.

Lorsque le contexte est clair, on utilise presque toujours la synecdoque « Soit $M$ un monoïde » plutôt que « Soit $(M, ×, 1)$ un monoïde ».

La structure de monoïde est trop pauvre pour fournir à elle seule une théorie intéressante. On ne l’introduit que pour regrouper des arguments communs à la théorie des groupes et des anneaux ainsi que pour des constructions intermédiaires. Cependant on peut déjà donner des exemples naturels de monoïdes qui ne sont pas des groupes.

Exemple 2.0.2

$(ℕ, +, 0)$, $(ℕ, ×, 1)$ et $(ℤ, ×, 1)$ sont des monoïdes commutatif. Pour tout ensemble $X$, l’ensemble des fonctions de $X$ dans $X$, muni de la composition et de l’identité, est un monoïde qui n’est commutatif que si $X$ a au plus un élément.

Définition 2.0.3

Soit $M$ un monoïde et $x$ un élément de $M$. On dit que $x$ est simplifiable à gauche si $y ↦ xy$ est injective de $M$ dans $M$. On dit qu’il est simplifiable à droite si $y ↦ yx$ est injective. On dit que $x$ est inversible s’il existe $x'$ tel que $xx' = x'x = 1$. On dit aussi que $x$ est une unité de $M$. L’ensemble des unités de $M$ est noté $M^×$.

Lemme 2.0.4

Soit $M$ un monoïde. Si $x ∈ M$ est inversible alors il n’existe qu’un seul élément $x'$ tel que $xx' = 1$ ou $x'x = 1$. On l’appelle l’inverse de $x$ et on le note $x⁻¹$ (ou $-x$ en notation additive). On a $xx⁻¹ = x⁻¹x = 1$. Dans ce cas $x$ est simplifiable à gauche et à droite.

Preuve ▼

Soit $x$ un élément inversible de $M$. L’hypothèse fournit $x'$ tel $xx' = x'x = 1$. Si $xx'' = 1$ alors on calcule $x'' = 1x'' = (x'x)x'' = x'(xx'') = x'1 = x'$. De même si $x''x = 1$ on peut calculer $x'' = x''1 = x''(x'x) = (x''x)x' = 1x' = x'$. On peut maintenant utiliser la notation $x⁻¹$. L’élément $x$ est simplifiable à gauche car la multiplication à gauche par $x⁻¹$ est inverse de la multiplication à gauche par $x$, et de même pour la droite.

Exemple 2.0.5

L’élément neutre d’un monoïde est toujours inversible : il est son propre inverse. Dans $(ℕ, ×)$, le neutre $1$ est le seul inversible. Dans $(ℚ, ×)$ tous les éléments sauf zéro sont inversibles. Les inversibles dans les fonctions d’un ensemble dans lui-même sont les bijections.

L’exemple précédent montre qu’il ne faut pas confondre les notations $ℕ^×$ et $ℕ^*$, même si elles coïncident dans le cas de $ℚ$, ou plus généralement dans le cas des corps.

Définition 2.0.6

Un morphisme de monoïdes entre $M$ et $N$ est une application $f \! :M → N$ telle que :

$f(1) = 1$
$∀ x\, y, f(xy) = f(x)f(y)$.

Lemme 2.0.7

Soit $f \! :M → N$ un morphisme de monoïdes.

$∀ x ∈ M^×, f(x) ∈ N^× \text{ et } f(x)⁻¹ = f(x⁻¹)$.
Si $f$ est bijectif alors $f⁻¹$ est automatiquement un morphisme de monoïdes. On dit alors que $f$ est un isomorphisme entre $M$ et $N$.

De plus une composée de morphismes de monoïdes est un morphisme de monoïdes.

Preuve ▼

Soit $x$ dans $M^×$. On a $f(x⁻¹)f(x) = f(x⁻¹x) = f(1_M) = 1_N$. On montre de même que $f(x)f(x⁻¹) = 1_N$. Ainsi $f(x)$ est inversible, d’inverse $f(x⁻¹)$.

Supposons $f$ bijectif. Soit $x$ et $y$ dans $N$. On calcule

\begin{align*} f⁻¹(xy) & = f⁻¹\Big(f\big (f⁻¹(x)\big )f\big (f⁻¹(y)\big )\Big) \\ & = f⁻¹\Big(f\big (f⁻¹(x)f⁻¹(y)\big )\Big) \\ & = f⁻¹(x)f⁻¹(y). \qedhere \end{align*}

Soit $f \! :M → N$ et $g \! :N → P$ des morphismes des monoïdes. Soit $x$ et $y$ dans $M$. On a $g(f(xy)) = g(f(x)f(y)) = g(f(x))g(f(y))$ et $g(f(1)) = g(1) = 1$ donc $g ∘ f$ est un morphisme de monoïdes.

Définition 2.0.8

Un quotient d’un monoïde $M$ est un monoïde $N$ muni d’un morphisme de monoïdes $π \! :M → N$ surjectif.

Lemme 2.0.9

Soit $M$ un monoïde et $π \! :M → N$ un quotient d’ensembles. Soit $∼$ la relation d’équivalence associée à $π$. Il existe une structure de monoïde sur $N$ telle que $π$ soit un morphisme de monoïde si et seulement si la loi de composition interne de $M$ est compatible avec la relation d’équivalence produit sur $M × M$. La structure de monoïde sur $N$ est alors unique. De plus si $M$ est commutatif alors $N$ l’est aussi.

Pour tout quotient de monoïde $π \! :M → N$ et tout morphisme de monoïdes $φ \! :M → P$ qui est compatible avec $∼$, la fonction $\barφ \! :N → P$ induite par $φ$ est automatiquement un morphisme de monoïdes.

Preuve ▼

Supposons qu’on a une loi de composition interne sur $N$. L’application $π$ est un morphisme si et seulement si le diagramme suivant commute (les flèches horizontales représentent les loi de composition) :

$\begin{tikzcd} M × M \rar \dar{π × π} & M \dar{π} \\ N × N \rar & N \end{tikzcd}$

Ainsi la structure de monoïde cherchée ne peut exister que si la loi de $M$ descend au quotient. Le corollaire 1.0.13 donne le critère d’existence annoncé et assure l’unicité de la loi descendue.

On suppose maintenant cette condition de compatibilité. On pose $1_N = π(1_M)$. Il s’agit bien d’un élément neutre dans $N$ car tout élément de $N$ est de la forme $π(m)$ et $1_Nπ(m) = π(1_M)π(m) = π(1_Mm) = π(m)$ et de même pour $π(m)1_N$. Dans la suite on notera simplement $1$ les neutres de $M$ et de $N$.

Pour l’associativité, la surjectivité de $π$ montre qu’il suffit de calculer, pour tout $x$, $y$ et $z$ dans $M$,

\[ (π(x)π(y))π(z) = π(xy)π(z) = π((xy)z) = π(x(yz)) = π(x)π(yz) = π(x)(π(y)π(z)). \]

Supposons un instant que $M$ est commutatif et montrons que $N$ l’est aussi. La surjectivité de $π$ montre qu’il suffit de calculer, pour tous $x$ et $y$ dans $M$, $π(x)π(y) = π(xy) = π(yx) = π(y)π(x)$.

Supposons maintenant que $φ \! :M → P$ est un morphisme de monoïdes compatible avec $∼$, de sorte qu’il descend en fonction $\barφ \! :N → P$. On contemple le diagramme suivant où $m_M$, $m_P$ et $m_N$ sont les multiplications de $M$, $P$ et $N$ respectivement.

$\begin{tikzcd} [column sep=small] M × M \ar[rrr, "m_M"] \ar[dd, swap, "φ × φ"] \ar[dr, "π × π"] &[.5cm] &[1.5cm] &[1cm] M \ar[dd, "φ"] \ar[dl, swap, "π"]\\ & N × N \rar{m_N} \ar[dl, "\bar φ × \bar φ"] & N \ar[dr, swap, "\bar φ"]& \\ P × P \ar[rrr, swap, "m_P"] & & & P \end{tikzcd}$

Comme $φ$ est un morphisme, le grand rectangle commute. Par hypothèse sur $φ$, les deux petits triangles commutent. Comme $π$ est un morphisme, le trapèze du haut commute. Le but est de montrer que le trapèze du bas commute : $m_P ∘ (\barφ × \barφ) = \barφ ∘ m_N$. Comme $π × π$ est surjective, il suffit de vérifier cette égalité précomposée par $π × π$. On calcule en regardant le diagramme et en tenant compte des commutations déjà établies.

\begin{align*} m_P ∘ (\barφ × \barφ) ∘ (π × π) & = m_P ∘ (φ × φ) \\ & = φ ∘ m_M \\ & = \barφ ∘ π ∘ m_M \\ & = \barφ ∘ m_N ∘ (π × π). \end{align*}

De plus $\barφ(1) = \barφ(π(1)) = φ(1) = 1$.

Exemple 2.0.10

L’ensemble $ℕ × ℕ$, munie de l’addition composante par composante est un monoïde (noté additivement), de neutre $(0, 0)$. La relation d’équivalence définie par $(a, b) ∼ (a', b')$ si $a + b' = a' + b$ est compatible avec l’addition. Le lemme précédent assure que le quotient $(ℕ × ℕ)/∼$, noté $ℤ$, est muni d’une unique structure de monoïde additif telle que la projection canonique $π$ est un morphisme. L’application $j \! :ℕ → ℤ$ qui envoie $n$ sur $π(n, 0)$ est un morphisme de monoïdes (comme composée de morphismes) appelé inclusion de $ℕ$ dans $ℤ$. On vérifie facilement que tous les éléments de $ℤ$ sont inversibles (toujours pour l’addition). Cet exemple sera considérablement généralisé dans le chapitre 4.

Définition 2.0.11

Un sous-monoïde d’un monoïde $M$ est une partie $N$ de $M$ telle que :

$1 ∈ N$
$N$ est stable par multiplication : $∀ x\; y ∈ M, x ∈ N \text{ et } y ∈ N ⇒ xy ∈ N$

On note alors $N ≤ M$.

Exemple 2.0.12

Pour tout monoïde $M$, $\{ 1\} $ et $M$ sont des sous-monoïdes de $M$. Dans $(ℤ, ×)$, $ℕ$ est un sous-monoïde.

La définition ci-dessus est écrite pour assurer que la structure de monoïde sur $M$ se restreint en structure de monoïde sur $N$.

Lemme 2.0.13

Soit $M$ et $M'$ des monoïdes, $N ⊂ M$, $N' ⊂ M'$ et $f \! :M → M'$ un morphisme.

Si $N ≤ M$ alors $f(N) ≤ M'$. En particulier $\operatorname{im}(f) ≤ M'$.
Si $N' ≤ M'$ alors $f⁻¹(N') ≤ M$.
L’intersection d’une famille de sous-monoïdes de $M$ est un sous-monoïde de $M$.

Preuve ▼

Soit $N$ un sous-monoïde de $M$. Comme $1 ∈ N$, on obtient $f(1) ∈ f(N)$, c’est à dire $1 ∈ f(N)$. Soit $x$ et $y$ dans $f(N)$. On obtient $x₀$ et $y₀$ tels que $x = f(x₀)$ et $y = f(y₀)$. On a alors $xy = f(x₀)f(y₀) = f(x₀y₀)$ donc $xy ∈ f(N)$.

Soit $N'$ un sous-monoïde de $M'$. Comme $1 ∈ N'$ et que $f(1) = 1$, $1 ∈ f⁻¹(N')$. Soit $x$ et $y$ dans $f⁻¹(N')$. Ainsi $f(x)$ et $f(y)$ sont dans $N'$ donc $f(x)f(y)$ aussi, c’est à dire $f(xy) ∈ N'$.

Soit $ℋ$ une famille de sous-monoïde de $M$ et $K$ l’intersection des éléments de $ℋ$. Tous les éléments de $ℋ$ contiennent $1$ donc leur intersection $K$ aussi. Soit $x$ et $y$ dans $K$. Pour tout $N ∈ ℋ$, $x$ et $y$ sont dans $N$ donc $xy$ aussi. Ainsi $xy$ est dans $K$.

Remarque 2.0.14 Intermède vacuiste

intersection d’une famille de parties Le dernier point du lemme 2.0.13 autorise l’intersection de la famille vide de sous-monoïdes de $M$. De quel sous-monoïde s’agit-il ? On pourrait imaginer que ce soit une question de convention, mais alors on pourrait légitimement douter de la validité de la démonstration dans ce cas. En fait il n’y a aucun problème de définition ici. Tous les ensembles intervenant dans cette démonstration sont des parties de $M$ et l’opération d’intersection est parfaitement définie de $𝒫(𝒫(M))$ dans $𝒫(M)$ par la règle

\[ ∀ x ∈ M, \left(x ∈ ⋂_{N ∈ ℋ} N ⇔ ∀ N ∈ ℋ, x ∈ N\right) \]

qui stipule sans aucune ambigüité que $⋂_{N ∈ ∅} N = M$. On peut aussi vérifier que cette intersection vérifie bien la propriété universelle attendue d’un opérateur de borne inférieure : $∀ K ∈ 𝒫(M), \big (K ⊂ ⋂_{N ∈ ℋ} N ⇔ ∀ N ∈ ℋ, K ⊂ N\big )$.

Définition 2.0.15

Le sous-monoïde engendré par une partie $S$ d’un monoïde $M$ est l’intersection de tous les sous-monoïdes de $M$ contenant $S$ :

\[ ⟨S⟩ = ⋂_{N ≤ M,\, S ⊂ N} N. \]

Si $⟨S⟩ = M$, on dit que $S$ engendre $M$, ou bien que $S$ est une partie génératrice de $M$.

Le lemme suivant rassemble les propriétés formelles des sous-monoïdes engendrés.

Lemme 2.0.16

sous-monoïde engendré Soit $S$ une partie d’un monoïde $M$.

$⟨S⟩$ est un sous-monoïde de $M$ qui contient $S$.
Pour tout $N ≤ M$, $⟨S⟩ ≤ N ⇔ S ⊂ N$ (ainsi $⟨S⟩$ est le plus petit sous-monoïde de $M$ qui contient $S$). Cette propriété universelle caractérise $⟨S⟩$.
L’application $⟨\cdot ⟩$ est croissante : $∀ S\; S', S ⊂ S' ⇒ ⟨S⟩ ⊂ ⟨S'⟩$.
Pour tout morphisme $f \! :M → M'$, $⟨f(S)⟩ = f(⟨S⟩)$.

Preuve ▼

Le premier point découle directement du lemme 2.0.13 et le second de la propriété universelle de l’intersection (cf. remarque 2.0.14). Montrons que la propriété universelle caractérise $⟨S⟩$. Supposons qu’un sous-monoïde $K$ vérifie aussi cette propriété. Comme $K$ contient $S$, la propriété universelle de $⟨S⟩$ assure que $⟨S⟩ ⊂ K$. De même, comme $⟨S⟩$ contient $S$, la propriété de $K$ assure que $K ⊂ ⟨S⟩$.

Les troisième et quatrième points découlent de façons complètement formelle des deux premiers (bien sûr on peut aussi donner une démonstration à partir de la définition, mais les raisonnements suivants sont des exemples d’énoncés bien plus généraux portant sur les applications entre ensembles ordonnés et peuvent être copiés sans aucune altération lors de l’étude des sous-groupes, sous-anneaux, idéaux ou sous-algèbres engendrés par une partie).

Pour le troisième point, soit $S$ et $S'$ des parties de $M$ avec $S ⊂ S'$. Le premier point donne $S' ⊂ ⟨S'⟩$ donc $S ⊂ ⟨S'⟩$ par transitivité puis $⟨S⟩ ⊂ ⟨S'⟩$ par le second point.

Montrons le dernier point. Il suffit de montrer que $f(⟨S⟩)$ vérifie la propriété universelle de $⟨f(S)⟩$. Tout d’abord il s’agit bien d’un sous-monoïde d’après le lemme 2.0.13. Soit $N'$ un sous-monoïde de $M'$. Le même lemme 2.0.13 assure que $f⁻¹(N')$ est un sous-monoïde de $N$. On a donc :

\begin{align*} f(S) ⊂ N’ & ⇔ S ⊂ f⁻¹(N’) \\ & ⇔ ⟨S⟩ ⊂ f⁻¹(N’) \text{ d'après la prop univ de $⟨S⟩$} \\ & ⇔ f(⟨S⟩) ⊂ N’ \end{align*}

Ce qui est bien la propriété universelle de $⟨f(S)⟩$.

Lorsque tout le reste a échoué, on peut aussi utiliser la description explicite du lemme suivant.

Lemme 2.0.17

Soit $S$ une partie d’un monoïde $M$. Les éléments du sous-monoïde engendré par $S$ sont tous les produits (finis) d’éléments de $S$ :

\[ ⟨S⟩ = \Big\{ s₁⋯sₖ \; ;\; k ∈ ℕ, s \! :\{ 1, \dots , k\} → S \Big\} . \]

où le cas $k = 0$ correspond au produit vide, c’est à dire au neutre de $M$.

Preuve ▼

L’ensemble $N$ du membre de droite contient $1$ par définition et il est stable par multiplication. C’est donc un sous-monoïde qui contient $S$. De plus tout sous-monoïde contenant $S$ contient nécessairement $N$ car il doit contenir $1$ et $S$ et être stable par multiplication. Donc $N$ vérifie la propriété universelle de $⟨S⟩$ donc $N = ⟨S⟩$ d’après le lemme précédent.