3.4. Monoïdes

Monoïdes de transformations

Une transformation d'un ensemble E est une fonction f de E dans E.
Le monoïde de transformations plein de E est l'ensemble EE de toutes les transformations of E, vu comme une algèbre avec deux opérations: la constante Id, et l'opération binaire ০ de composition.
Un monoïde de transformations de E est un ensemble M de transformations de E formant une {Id,০}-algèbre, M ∈ Sub{Id,০}EE : L'ensemble des endomorphismes d'un objet fixe dans une catégorie concrète est un monoïde de transformations. Tout monoïde de transformations peut se voir comme une catégorie concrète à un seul objet.

Trajectoires

Pour tout ensemble de transformations LEE, vu comme ensemble de symboles de fonctions interprété dans E,

xE, 〈{x}〉L = {f(x)|f∈〈L{Id,০}}
XE, 〈XL = ⋃f∈〈L{Id,০} f[X] = ⋃xX 〈{x}〉L

Comme sera formalisé plus tard, la raison est que les deux ont la même signification : l'ensemble de tous les composés de tout nombre de fonctions dans L, appliqué à tout xX. Mais voici une simple preuve, notant A=〈XL, M=〈L{Id,০} et K={f(x) | (f,x)∈M×X}:
Preuve de AK
IdEMXK
gL, ∀yK, ∃(f,x)∈M×X, y=f(x) ∧ gfMg(y) = gf(x)∈K
K ∈ SubLE
Preuve de KA
L ⊂ {fEE| A ∈ Sub{f}E} = End{A}E ∈ Sub{Id,০}EE
M ⊂ End{A}E
fM, XA ∈ Sub{f}Ef[X] ⊂ A. ∎
La trajectoire d'un élément xE par un monoïde de transformations M de E, est l'ensemble qu'il engendre:

〈{x}〉M = {f(x)|fM} ⊂ E

Monoïdes

Un monoïde est une algèbre se comportant comme un monoïde de transformations, mais sans préciser d'ensemble que ses éléments peuvent transformer. Comme les symboles Id and ০ perdent leur interprétation naturelle, ils sont respectivement renommés e et •. Ainsi, le concept de monoïde est la théorie à un seul type et

Les deux égalités dans le dernier axiome peuvent se considérer séparément, formant deux concepts différents

S'il existe des éléments neutres à gauche et à droite alors ils sont égaux : e = ee' = e' ce qui en fait l'élément neutre de • (l'unique élément neutre à gauche ou à droite). L'existence d'un élément neutre à droite implique l'unicité de celui éventuel à gauche, mais sans élément neutre à droite, plusieurs éléments neutres à gauche peuvent coexister (et de même en échangeant les côtés).
De toute opération associative sur un ensemble E on peut former un monoïde en ajoutant l'élément neutre e comme élément supplémentaire, E'=E⊔{e}, auquel l'interprétation de • s'étend comme déterminé par les axiomes de neutralité (préservant l'associativité), mais où tout élément neutre qui pouvait exister dans E perd son statut d'élément neutre dans E'.
L'élément neutre assurant la surjectivité de •, tout plongement entre monoïdes est injectif.
Toute {e,•}-sous-algèbre d'un monoïde est un monoïde, appelé donc un sous-monoïde.

Régularité

Un élément x est dit régulier à gauche pour une opération • si la composition à gauche par x est injective: ∀y,z, xy = xzy = z.
De même il est régulier à droite si yx = zxy = z.
Si un élément neutre à droite e est régulier à gauche alors c'est l'unique élément neutre à droite : ee' = e = eee' = e.
Une opération est dite régulière si tous ses éléments sont réguliers des deux côtés.
Par exemple le monoïde de l'addition dans {0,1, plusieurs} n'est pas régulier car 1+plusieurs = plusieurs+plusieurs.
Tout sous-monoïde d'un monoïde régulier est régulier.

Commutants et centralisateurs

Le commutant d'une partie AE pour une opération binaire • dans E, se définit par

C(A) = {xE|∀yA, xy = yx}.

C'est une correspondance de Galois: ∀A,BE, BC(A) ⇔ AC(B). On dit que A,B commutent, chaque élément de A commutant avec chaque élément de B.

Si • est associative alors ∀AE, C(A) ∈ SubF. (Proof: ∀x,yC(A), (∀zA, xyz = xzy = zxy) ∴ xyC(A))

Les commutants dans les monoïdes sont appelés des centralisateurs. Ce sont plus précisément des sous-monoïdes comme évidemment eC(A).
On peut le comprendre dans le cas de monoïdes de transformations MXX par le fait que c'est une intersection de sous-monoïdes: AM, CM(A) = M ∩ EndA X.
Ce concept sera généralisé aux clones d'opérations de toutes arités.

Une operation binaire • dans un ensemble E, est dite commutative si C(E) = E, autrement dit x,yE, xy = yx.

Si AC(A) et 〈A=E alors • est commutative.
Preuve: AC(A)∈ SubFE=C(A) ⇒ AC(E) ∈ SubFC(E) = E.∎
Pour les monoïdes les conditions AC(A) et 〈A{e,•}=E suffisent.

Autres concepts de sous-monoïdes et morphismes

Modifier la formalisation des monoïdes en remplaçant le statut de e comme constante par ∃e dans l'axiome de neutralité, affaiblirait les concepts de sous-monoïdes et morphismes (les rendant moins sélectifs) comme suit.
Pour tout monoïde (M,e,•), tout ensemble X avec une opération binaire ▪, et tout morphisme de composition f ∈ Mor{•}(M,X), Si la cible forme un monoïde (X,e',▪) alors (par unicité du neutre dans A)

f ∈ Mor{e}(M,X) ⇔ a = e'e'AA ∈ Sub{e, ▪} X

mais ces formules équivalentes peuvent être fausses, sauf si a est régulier d'un côté (aa = a = ae'a = e').

Anti-morphismes. L'opposé d'un monoïde est le monoïde de même ensemble de base mais où la composition est remplacée par sa transposée. Un anti-morphisme de (M,e,•) vers (X,e',▪) est un morphisme f d'un monoïde vers l'opposé de l'autre (ou de manière équivalente vice-versa):

f(e) = e'
a,bM, f(ab) = f(b)▪f(a)


Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Morphisms of relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Algebraic terms and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory