Cours 3: Structures algébriques, Catégories, Semi-groupes, Monoïdes libres/finis

Chapitre 3 : Structures algébriques

0. Catégories

Catégorie :

Il y a des :

  • objets : $E, F, G…$
  • flèches : $Hom(E,F)$ : on y manipule des applications $E⟶F$ qui sont compatibles avec la structure.

Exs :

  • $k$ un corps, la catégorie des $k$-ev :
    • objets : $k$-ev
    • $k$-applications linéaires : ${\cal L}(E,F)$
  • La catégorie des ensembles :
    • objets : ensembles
    • flèches : applications
  • Catégorie des catégories :
    • objets : catégories
    • flèches : foncteurs

$F : 𝒞⟶𝒞’$ foncteur.

Si $E$ est un objet, $F(E)$ objet.

Si $f ∈ Hom_𝒞(E,G)$, $F(f)∈ Hom_𝒞(F(E),F(G))$

Ex de foncteur :

$𝒞$ : cat des $k$-ev \(F(E) = E^* = L(E, k)\)

Si $f∈Hom_𝒞(E,F) = L(E,F), 𝜆 : F ⟶ k$

$F(f) = {}^tf∈L(F^,E^)$ : foncteur contravariant.

${}^tf(𝜆) = 𝜆\circ f$

Ex : $f$ injective ?

Elle l’est si elle l’est sur les morphismes : on oublie les éléments.

$f$ injective ssi

\(\begin{cases} Hom_𝒞(H,E)⟶Hom_𝒞(H,F) \\ u \mapsto f\circ u \end{cases}\) injective

Pb universel : objet libre

Un ensemble, $E$ un objet.

$f$ une application d’ensembles.

$L(X)$ est libre sur $X$ si pour tout $E$ dans $𝒞$, pour tout $f: X ⟶E$, il existe un unique $\widehat{f}$ dans $Hom_𝒞(L(X),E)$ qui prolonge $f$.

Ex d’objet libre :

  • L’indéterminée $X$ peut être envoyée sur n’importe quoi, a priori (pas $\sqrt 2$ : on ne peut l’envoyer que sur un objet dont le carré vaut $2$).
  • Les ev sont des structures libres.

I. Semi-groupes et monoïdes

Semi-groupe :

Un semi-groupe est un ensemble muni d’une loi interne associative.

NB :

  • on peut y définir $x^n$.
  • on peut rajouter un élément neutre de manière artificielle pour créer un monoïde.
Monoïde :

Semi-groupe qui admet un élément neutre (= unifère).

i.e il existe un élément $1$ tq : $1x = x1= x, ∀x∈G$

Ex :

  • $(ℕ, +)$ : monoïde d’élément neutre 0.

  • Un élément $x$ d’un monoïde vérifiant $x^2=x$ est appelé un idempotent.

Ex: $1$ est idempotent.

Morphisme de monoïdes :

Une application $𝜑 : M_1 ⟶ M_2$ qui vérifie $∀x, y ∈ M_1, f(xy)= f(x)f(y)$

Isomorphisme de monoïde :

Morphisme bijectif.

Sous-monoïde :

Si $N ⊆ M$, $N$ monoïde pour la loi définie sur $M$.

\(∀x,y ∈ N, xy ∈ N\) et même élément neutre (si on a seulement l’existence d’un (éventuellement autre) élément neutre : on parle sous-semi-goupe).

Produit direct de monoïdes :

$M_1 \times M_2 : (m_1, m_2)(n_1, n_2) = (m_1 n_1, m_2 n_2)$

Prop : une intersection non vide de sous-monoïdes est un sous-monoïde.

Déf :

Soit $X$ une partie d’un monoïde.

Alors il existe un plus petit sous-monoïde de $M$ contenant $X$.

\[⟨X⟩ = \bigcap_{N \text{ ss-monoïde de M }} N\]

NB : $⟨X⟩$ est appelé ss-monoïde engendré par $X$.

Prop : \(⟨X⟩ = \{x_1 ⋯ x_n \}_{n∈ℕ, x_i ∈ X}\)

NB :

  • $⟨∅⟩ = {1}$
Partie génératrice de $M$ :

$X⊆M$, telle que $⟨X⟩=M$. ($X$ engendre $M$)

NB :

  • Structure quotient : l’idée, c’est qu’on cherche une relation d’éq. $\sim$, telle que la surjection canonique (qui à $x$ associe sa classe) soit une flèche de la catégorie de la structure.

Ex : Pour les groupes, on quotiente par un groupe distingué.

Congruence :

Une relation d’éq $\sim$ telle que \(m_1 \sim m_2 ⟹ ∀u,v ∈ M, um_1 v \sim u m_2 v\)

Prop : Une congruence $\sim$ sur $M$ est compatible avec la loi de monoïde, i.e : \(m_1 \sim m_2 ∧ n_1 \sim n_2 ⟹ m_1 n_1 \sim m_2 n_2\)

On peut définir sur $M/\sim$ une loi interne tq, en notant $𝜋$ la surjection canonique (qui à un élément associe sa classe), \(∀m_1, m_2 ∈ M, 𝜋(m_1 m_2) = 𝜋(m_1) 𝜋(m_2)\)

(le produit des classe de $m_1$ et de $m_2$ est la classe du produit : ne dépend pas des représentants choisis)

On sait alors que $M/\sim$ est muni d’une structure de monoïdes. Son élément neutre est la classe d’éq de $1$.

Monoïde quotient :

c’est $M/\sim$

Th : Soit $f: M⟶ N$ un morphisme de monoïdes, $\sim$ une congruence sur $M$ compatible avec $f$, i.e que $m_1 \sim m_2 ⟹ f(m_1) = f(m_2)$

Alors : il existe un morphisme de monoïdes $f$ de $M/\sim$ dans $N$ tq \(f = \widehat{f} \circ 𝜋\)

(cf. diagramme : il est commutatif)

Dém :

On définit $\widehat{f}(𝒞) = f(m)$ pour $m∈𝒞$ (indépendant du choix de $m$ dans $𝒞$)

On a aussi : \(∀m ∈M, \widehat{f}(𝜋(m)) = f(m)\)

et on vérifie que $\widehat{f}$ est un morphisme de monoïdes.

Cas particulier : Avec les mm notations, si : \(m_1 \sim m_2 ⟺ f(m_1) = f(m_2)\)

On vérifie que $\sim$ est une congruence, et elle est compatible avec $f$ par définition.

Donc $f$ se factorise par $M/\sim$ :

Dans ce cas, $\widehat{f}$ est injectif.

Dém : Si $\widehat{f}(𝒞_1) = \widehat{f}(𝒞_2)$ :

\(f(m_1) = \widehat{f}(𝒞_1) = \widehat{f}(𝒞_2) = f(m_2)\) (si $𝜋(m_i) = 𝒞_i$)

d’où : $m_1 \sim m_2$, soit : $𝒞_1 = 𝒞_2$

2. Monoïdes libres

Ensembles des mots sur un alphabet $𝛴$ :
\[𝛴^* ≝ \{(u_1, ⋯, u_n) \}_{u_i ∈ 𝛴, n ∈ℕ}\]

qu’on munit d’une loi interne naturelle de “concaténation” (qui est associative, et d’élément neutre $()$ (suite vide)).

Donc $𝛴^*$ est un monoïde.

NB : on emploiera les notations habituelles :

  • $a ≝ (a)$ (lettre)
  • $a_1 ⋯ a_n ≝ (a_1, ⋯, a_n)$

Un élément de $𝛴^*$ est appelé un mot.

Prop : $⟨𝛴⟩ = 𝛴^*$

Prop : Pour un monoïde $M$, et une application $f : 𝛴 ⟶ M$, il existe un unique morphisme de monoïdes $\widehat{f}$ de $𝛴^$ dans $M$ tq \(f = \widehat{f}\circ i\) ($i$ : injection de $𝛴$ dans $𝛴^$)

Dém : \(\widehat{f}(a_1⋯a_n) = f(a_1)⋯f(a_n)\) (nécessaire et suffisant)

Application “longueur” :

C’est l’unique prolongement de \(\begin{cases} 𝛴 ⟶ ℕ \\ a \mapsto 1 \end{cases}\) en un morphisme de $𝛴^*$ dans $ℕ$ (on le note $\vert \cdot\vert $).

NB :

  • $\vert uv\vert = \vert u\vert +\vert v\vert $
  • $\vert a_1 ⋯ a_n\vert = n$
Base :

$X ⊆ M$ est appelé base de $M$ si tout élément de $M$ se décompose de façon unique comme un produit d’éléments de $X$.

$𝛴$ est une base de $𝛴^*$, et c’est la seule (à cause de la longueur : il n’y a pas d’autre moyen de décomposer une lettre qu’avec une lettre).

Monoïde libre :

Monoïde isomorphe à un ss-monoïde de $𝛴^*$ qui admet une base.

Code :

une partie $X⊆M$ tq \(∀u_i, v_i ∈X, u_1 ⋯ u_n = v_1 ⋯ v_p ⟹ (n=p) ∧ (∀i, u_i = v_i)\)

NB : Soit $L$ un ss-monoïde de $𝛴^*$ :

on note $X$ les mots qui se décomposent de façon non triviale dans $L$ : \(X ≝ (L\backslash\{1\})^2\backslash(L\backslash\{1\})\) où \((L\backslash\{1\})^2 ≝ \{uv\}_{u, v ∈ L\backslash\{1\}}\)

Alors $L = ⟨X⟩$

Dém : Par réc sur la longueur : $u∈L ⟹ u ∈ ⟨X⟩$

Si $u ∉ X ∪ {1}, ∃v,w ∈ L\backslash{1}; u = vw ∧ \vert v\vert <\vert w\vert , \vert w\vert <\vert u\vert $

On applique l’hypothèse de réc à $v$ et $w$.

Prop : Soit $L$ un ss-mon. de $𝛴^*$. Alors $L$ est libre ssi \(∀w∈𝛴^*, ∃ u,v ∈ L; uw ∈ L ∧ wv ∈ L\) alors $w∈L$

Dém :

Sens Direct :

Si $L$ est libre de base $B$.

\[uw = b_1 ⋯b_p \\ wv = c_1 ⋯ c_s \\ u = b'_1 ⋯ b'_q \\ v = b''_1 ⋯ b''_r \\ uwv = b_1 ⋯ b_p b''_1 ⋯ b''_r \\ = b'_1 ⋯ b'_q c_1 ⋯ c_s\]

donc il y a unicité de la décomposition, en partic. :

$b_1 = b’_1 ∧ b’‘_r = c_s$

On pose $u = b_1 u’$, $v = v’c_s$

et on a :

\[u'w = b_2 ⋯ b_p ∈ L \\ wv' = c_1 ⋯ c_{s_1} ∈ L\]

on conclut par réc sur $\vert uv\vert $ que $w ∈L$

Réciproque : $L=⟨X⟩$

$X ≝ (L\backslash{1})^2\backslash(L\backslash{1})$

Soient $b_1 ⋯ b_p, c_1 ⋯ c_r ∈ X$ tq \(b_1 ⋯ b_p = c_1 ⋯ c_r\)

Supposons $\vert b_1\vert ≤ \vert c_1\vert $.

alors : \(c_1 = b_1 u, u∈𝛴^*\)

et : \(b_2 ⋯ b_p = u c_2 ⋯ c_s\)

$b_1 ∈ L$ et $b_1u ∈ L$

$c_2 ⋯ c_s ∈ L$ et $uc_2 ⋯ c_s ∈L$

donc $u∈L$

Or $c_1 ∈ X$, $c_1 = b_1u$, donc $u=1$

On conclut par réc sur $r+p$

Corollaire : Une intersection de ss-mon. libres de $𝛴^$ est un ss-mon libre de $𝛴^$.

Corollaire : Si $X⊆𝛴^*$, il existe un plus petit ss-mon. libre contenant $X$, appelé enveloppe libre de $X$.

Dém : $\bigcap\limits_{L \text{ss-mon libre de } 𝛴^*, X⊆L} L$

Th de défaut : Si $X⊆𝛴^*$ et on suppose $X$ fini. Soit $L$ l’enveloppe libre de $X$, $Y$ le code de $L$.

Alors si $X$ n’est pas code, $\vert Y\vert <\vert X\vert$

NB : c’est l’équivalent du th de la base extraite dans les ev.

Dém :

On suppose que $X$ n’est pas un code.

Soit $x ∈X$.

Il existe une décomposition unique de $x$ dans $Y^*$.

\[x= y_1 ⋯ y_p, y_i ∈ Y\]

On définit $f(x)=y_1$, $f : X ⟶ Y$.

Comme $X$ n’est pas un code, un élément de $X^*$ admet deux décompositions différentes :

\(x_1 ⋯ x_r = x'_1 ⋯ x'_s\) avec $x_1 ≠ x’_1$ (après simplification éventuelle).

En décomposant chacun des $x_i$ et $x’_i$ comme concaténation de d’éléments de $Y$, et cette écriture étant unique, pour $x_1 ⋯ x_r = x’_1 ⋯ x’_s$.

On a :

\[x_1 ⋯ x_s = x'_1 ⋯ x'_s = \underbrace{y_1 y_2 ⋯}_{y_i ∈ Y}\]

Alors \(\begin{cases} y_1 = f(x_1) \\ y_2 = f(x'_1) \end{cases}\)

Mq $f$ est surjective :

Supposons qu’il existe $y$ dans $Y$ non atteint par $f$.

Posons \(Z=(Y\backslash \{y\})Y^*\)

Tout élément de $X$ se décompose sur $Z^*$ : si $𝜀≠x∈X$,

\[𝜀 ≠ x = \underbrace{f(x)}_{≠ y} y_1 ⋯ y_p ∈ Z^+\]

$Z$ est un code :

$z_1 ⋯ z_m, z’1, ⋯, z’{m’} ∈ Z$ tq \(z_1 ⋯ z_m = z'_1, ⋯, z'_{m'}\)

  • $z_i = y_i y^{s_i}$, $y_i ∈ Y\backslash{y}, s_i ∈ℕ$
  • $z’_i = y’_i y^{t_i}$, $y’_i ∈ Y\backslash{y}, t_i ∈ℕ$

Alors comme \(\underbrace{y_1}_{≠y} y^{s_1} \underbrace{y_2}_{≠y} y^{s_2} ⋯ = \underbrace{y'_1}_{≠y} y^{t_1} \underbrace{y'_2}_{≠y} y^{t_2} ⋯\)

Donc

  • $m=m’$
  • $∀i, s_i = t_i ∧ y_i = y’_i$

donc $Z^$ est un ss-monoïde libre de $𝛴^$ :

\(X ⊆ Z^* ⊊ Y^*\) ($y ∉ Z^*$)

Contradiction avec le fait que $L$ soit le plus petit monoïde libre contenant $X$.

3. Monoïdes finis

Prop : Soit $M$ un monoïde fini à un générateur : \(M=⟨x⟩\)

Soient $m$ et $p$;

  • $p>0$
  • $m≥0$

$x^{m+p} = x^m$ (de tels $m$ et $p$ existent par le lemme des tiroirs).

Si $m+p$ est le plus petit possible, la structure de $M$ est donnée par le schéma suivant (“poêle à frire”).

digraph {
    rankdir=LR;
    xm[label="x^m=x^{m+p}"];
    xmplusun[label="x^{m+1}"];
    ⋯2[label="⋯"];
    xmpmoinsun[label="x^{m+p-1}"];
    𝜀 -> x;
x-> ⋯;
⋯ -> xm;
xm -> xmplusun;
xmplusun -> ⋯2;
⋯2 -> xmpmoinsun;
xmpmoinsun -> xm;
}
\[M= \{𝜀, x, ⋯, x^{m}=x^{m+p}, ⋯, x^{m+p-1}\}\]

NB :

  • $x^p$ : idempotent (si $p>m$), joue le rôle d’élément neutre dans le ss-monoïde ${x^{m}=x^{m+p}, ⋯, x^{m+p-1}}$

  • en fait : éléments idempotents : ce sont des éléments neutres pour des ss-monoïdes

Tout monoïde est un quotient d’un monoïde libre.

Leave a comment