3.5. 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 une {Id,⚬}-algèbre M ∈
Sub{Id,⚬}EE de transformations de E :
L'ensemble End(E) des endomorphismes de tout objet E 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.
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
- Deux symboles d'operation
- un symbole de constante e nommé «élément neutre»
- une opération binaire • nommée «composition»
- Axiomes
- Associativité : ∀x,y,z, x•(y•z)
= (x•y)•z permettant de noter chaque terme
x•y•z
- Neutralité : ∀x, x•e = x
= e•x
Les 2 égalités dans l'axiome de neutralité peuvent être prises séparément,
formant 2 concepts différents :
- un élément neutre à gauche d'une opération binaire • est un
élément e tel que ∀x, e • x = x
- un élément neutre à droite de • est un élément e'
tel que ∀x, x•e' = x
S'il existe des éléments e neutre à gauche et e' neutre à droite alors ils
sont égaux : e = e•e' = 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 donc l'unicité d'un neutre à gauche, mais sinon plusieurs
éléments neutres à gauche pourraient coexister (et de même vice versa).
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 l'axiome de neutralité. Cela préserve l'associativité; mais tout élément qui était neutre
dans E perd son statut d'élément neutre dans E'.
Toute {e,•}-sous-algèbre d'un monoïde est un monoïde, appelé donc un
sous-monoïde.
Simplifiabilité
Un élément x est dit simplifiable à gauche pour une opération • si la transformation
•⃗(x) (dite composition à gauche par x) est injective: ∀y,z, x•y = x•z ⇒ y = z.
De même il est
simplifiable à droite si •⃖(x) est injective:
∀y,z, y•x = z•x ⇒ y = z.
Une opération est dite simplifiable si tous ses éléments sont simplifiables des deux
côtés.
Par exemple le monoïde de
l'addition dans {0,1, plusieurs} n'est pas simplifiable car 1+plusieurs = plusieurs+plusieurs.
Tout sous-monoïde d'un monoïde simplifiable est simplifiable.
L'existence d'un élément simplifiable à gauche implique l'unicité d'un élément neutre
à droite :
a•e' = a = a•e ⇒ e' = e.
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,▪)),
- son image est un monoïde (A,a,▪) où A = Im f
et a = f(e)
- f est un morphisme de monoïde de M
vers ce monoïde A.
Si la cible forme un monoïde (X,e',▪)
alors (par unicité du neutre dans A)
f ∈ Mor{e}(M,X) ⇔
a = e' ⇔
e' ∈ A ⇔ A ∈ Sub{e, ▪} X
mais ces formules équivalentes peuvent être fausses, sauf si a est simplifiable
d'un côté (a▪a = a = a▪e' ⇒ 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,b∈M, f(a•b) =
f(b)▪f(a)
Commutants et centralisateurs
Le commutant d'une partie A⊂E pour une opération binaire • dans E,
se définit par
C(A) = {x∈E|∀y∈A,
x•y = y•x}.
C'est une correspondance de Galois:
∀A,B⊂E, B⊂C(A) ⇔
A⊂C(B).
On dit que A et B commutent, chaque
élément de A commutant avec chaque élément de B.
Si • est associative alors ∀A⊂E,
C(A) ∈ Sub{•}F.
Preuve: ∀x,y∈C(A),
(∀z∈A, x•y•z = x•z•y =
z•x•y) ∴ x•y∈C(A).
Les commutants dans les monoïdes sont appelés des centralisateurs. Ce sont
plus précisément des sous-monoïdes comme évidemment e∈C(A).
On peut le comprendre comme une intersection de sous-monoïdes dans le cas d'un
monoïde de transformations M⊂XX :
∀A⊂M, CM(A) =
M ∩ EndA X
(Comparée à la correspondance
(End, Inv(2)), celle-ci vient par restriction de la relation de préservation
à l'ensemble des graphes de fonctions dans M).
Une operation binaire • dans un ensemble E, est dite
commutative si • = t•, autrement dit C(E) = E.
Si A⊂C(A) et 〈A〉{•} = E alors • est
commutative.
Preuve: A⊂C(A)∈ Sub{•}F
⇒ E = C(A)
⇒ A⊂C(E) ∈ Sub{•}F ⇒
C(E) = E.∎
Pour les monoïdes les conditions
A ⊂ C(A) et 〈A〉{e,•} = E suffisent.
Catégories
Le concept de monoïde a été introduit comme abstraction des
monoïdes de transformations (= catégories concrètes à un seul objet).
Maintenant, le concept de catégorie (aussi dite catégorie abstraite)
généralise cela aux pluralités d'objets : il diffère du concept de catégorie concrète, en
ôtant aux objets et aux morphismes les rôles respectifs d'ensembles et
de fonctions. Ainsi une categorie C est faite de:
- Une classe de ses "objets";
la catégorie est petite si cette classe est un ensemble;
- A tout couple d'objets (E,F) on donne un ensemble Mor(E,F) de
«morphismes de E vers F», habituellement vus comme deux à deux disjoints;
- A tout objet E on donne un symbole de constante
1E ∈ Mor(E,E);
- A tout triplet d'objets E,F,G on donne une opération de
"composition" (abusivement tous notés par le même symbole)
∘ :
Mor(F,G)×Mor(E,F) → Mor(E,G)
satisfaisant les 2 axiomes de neutralité et d'associativité, les
quantificateurs ∀C signifiant parcourir la classe des objets :
- ∀C E,F, ∀x∈Mor(E,F),
x∘1E = x = 1F∘x
- ∀C E,F,G,H, ∀x∈Mor(E,F),
∀y∈Mor(F,G),∀z∈Mor(G,H),
(z∘y)∘x = z∘(y∘x) ∈ Mor(E,H)
Suivant la commodité de présentation, la composition peut aussi s'écrire transposée,
par la notation point-virgule venant de l'informatique : ; = t∘ :
Mor(E,F)×Mor(F,G) → Mor(E,G)
x;y = y∘x
L'ensemble End(E) = Mor(E,E) des endomorphismes de tout
objet E, peut être vu comme un monoïde de deux manières opposées, par restriction de ∘ ou ;.
Le concept de catégorie opposée se définit comme les monoïdes opposés,
comme relisant la catégorie en échangeant les côtés, le Mor(E,F) de l'un
servant comme Mor(F,E) de l'autre. Pour tout concept relatif à une
catégorie donnée, son dual désignera le concept semblable suivant la même
définition reversant les côtés, ce qui revient à appliquer ce concept à la catégorie opposée ;
il sera généralement désigné en ajoutant le préfixe co- au nom du concept.
Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
2. Théorie
des ensembles
3. Algèbre
3.1. Correspondance
de Galois
3.2. Systèmes
relationnels et catégories concrètes
3.3. Algèbres
3.4. Morphismes particuliers
3.5. Monoïdes et catégories
3.6. Actions de monoïdes et de catégories
3.7. Inversibilité et groupes
3.8. Propriétés dans les catégories
3.9. Objets initiaux et finaux
3.10. Produits de systèmes
3.11. Bases
3.12. Composition des relations
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry
Other languages:
EN :
3.5. Monoids and categories