3.5. Actions de monoïdes

Actions à gauche

Après avoir privé les monoïdes de leur rôle d'ensembles de transformations, on peut le leur redonner comme suit.
Une action à gauche d'un monoïde (M,e, •) sur un ensemble X, est une opération ⋅ : M×XX telle que Voyant M comme ensemble de symboles de fonctions, une M-algèbre (X, ⋅) satisfaisant ces axiomes est appelé un M-ensemble.
En vue curryfiée, une action à gauche de M sur X est un {e,•}-morphisme de M vers le monoïde de transformations plein XX.

Effectivité et éléments libres

Une action à gauche est dite effective si ce morphisme est injectif (donc un plongement):

a,bM, (∀xX, a·x = b·x) ⇒ a=b

rendant e et • définissable par (= unique pour) l'action donnée, tout comme les axiomes des functions assuraient le sens des définitions of Id and ০ en termes de l' évaluateur de fonction.
Un élément xX d'un M-ensemble, est libre si la fonction qu'il définit de M dans X est injective. l'existence d'un élément libre implique que l'action est effective:

(∃xX, ∀abM, a·xb·x) ⇒ (∀abM, ∃xX, a·xb·x)

Exemple général. Tout monoïde de transformations M sur un ensemble E agit par restriction sur tout ensemble M-stable A de E, autrement dit tout AE conservé dans la catégorie concrète M d'objet E. Donc, le monoïde d'endomorphismes de tout système typé E= ∐iI Ei, agit sur tout type Ei qu'il contient.

Actions comme structures algébriques

Donnons à M, X des structures de M-algèbres par des operations • : M×MM et ⋅ : M×XX. Notant alors ∀xX, hx = (Maax), on a directement par définitions

hx(e) = xex = x
hx ∈ MorM(M,X) ⇔ ∀a,bM, (ab)⋅x = a⋅(bx)
he = IdM ⇔ (∀aM, ae = a) ⇒ ∀g∈MorM(M,X), g=hg(e).

Donc dans la formule

gXM, ∀xX, g=hx ⇔ (g∈MorM(M,X) ∧ g(e)=x)

le ⇒ exprime les axiomes d'action à gauche de M sur X; le ⇐ est impliqué par (∀aM, ae = a). Ce dernier axiome de monoïde (au-delà de ceux d'action à gauche de M sur lui-même), vient réciproquement comme cas particulier de ce ⇐ quand X=M :

(IdM ∈ MorM(M,M) ∧ IdM(e)=e) ⇒ he = IdM

Actions à droite

Le concept d'action à droite d'un monoïde M sur un ensemble X, diffère de l'action à gauche par l'échange des côtés: c'est une opération ⋅ : X × MX telle que
Il équivaut à une action à gauche du monoïde opposé, et définit un anti-morphisme de M vers XX.
La commutation de 2 sous-monoïdes de XX ressemble à une formule d'associativité quand on les voit comme agissant par les côtés opposés sur X: aM agissant à gauche sur X commute avec bN agissant à droite sur X quand

xX, (ax)⋅b = a⋅(xb)

Théorème de representation

Il s'avère que les axiomes de monoïde suffisent à donner toutes les propriétés des monoïdes de transformation, et même toutes les propriétés des monoïdes d'endomorphismes:

Théorème. Pour tout monoïde M il existe un langage L de symboles de fonctions et une L-algebre X telle que le monoïde EndL X soit isomorphe à M.

La preuve répète en substance les formules ci-dessus sur les actions comme structures algébriques, transposées :

Soient L et X des copies de M.
Donnons à L l'action à droite sur X copiée de la composition dans M.
Soit f ∈ Mor(M, XX) représentant l'action à gauche de M sur X aussi copiée de la composition dans M.
Im f ⊂ EndL X par associativité de sorte que les deux actions de côtés opposés commutent.
f est injective car la copie k de e dans X est libre.
EndL X ⊂ Im f car
g∈EndLX, ∃uM, g(k) = uk ∴ (∀xX, ∃sL, ks = xg(x) = g(ks) = g(k)⋅s = uks = ux) ∴ g = f(u) ∎
Pour la dernière formule il suffit que k soit générateur des deux côtés, pour identifier bijectivement (s'il est aussi libre) L et X comme copies de M, mais un tel k n'est pas nécessairement unique.

Trajectoires des monoïdes commutatifs

Soit un monoïde M agissant sur un ensemble X, et soit kX. La trajectoire Y de k par M est stable par M, donc définit un morphisme de monoïde de M vers YY d'image un monoïde de transformations N de Y.
Oubliant M et X, on a un monoïde N avec une action effective sur Y engendrée par k.
Maintenant si N est commutative (ce qui est le cas si M est commutative) alors k est libre pour l'action de N (donc Y peut se voir comme copie de N).
La preuve est facile et laissée en exercice.
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. Monoïdes
3.5. Actions of monoïdes
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