# 3.5. Actions of monoids

### Left actions

Now let us give back to monoids their role as sets of transformations.

A *left action* of a monoid (*M*,*e*, •) on a set *X*, is an operation ⋅ from
*M*×*X* to *X* satisfying the axioms:
- ∀
*x*∈*X*, *e* ⋅ *x* = *x*;
- ∀
*a*,*b*∈*M*, ∀*x*∈*X*,
(*a* • *b*) ⋅ *x* = *a* ⋅ (*b* ⋅ *x*).

This turns *X* into an *M*-algebra (where *M*
is seen as a set of function symbols), called an *M*-set.
### Effectiveness and free elements

A left action of *M* on *X* can be seen by currying as a
{*e*, •}-morphism from *M* to *X*^{X}. A left action is said *effective* if this morphism is
injective:∀*a*, *b* ∈ *M*, (∀*x*∈ *X*,
*a*·*x* = *b*·*x*) ⇒ *a*=*b*

letting
the axioms of action be usable as definitions of *e* and • from the action, in the same
way the definitions of Id and ০ are re-expressible (from their initial
expressions via the axioms for function) as
determined by the function evaluator.

An element *x*∈*X* of an *M*-set, is *free* if the function it defines from *M* to *X*
is injective. The existence of a free element implies that the
action is effective:
(∃*x*∈*X*,
∀*a*≠*b*∈*M*, *a*·*x*≠*b*·*x*)
⇒ (∀*a*≠*b*∈*M*, ∃*x*∈*X*,
*a*·*x*≠*b*·*x*)

**General example.**
The monoid of endomorphisms of any typed system *E*=
∐_{i∈I} *E*_{i},
acts on every type *E*_{i} it contains, by
the morphism of monoid from End(*E*) to
*E*_{i}^{Ei}
defined by restricting to *E*_{i} each endomorphism
of *E*.
### Right actions

As the concept of monoid is formally symmetric between left and
right, transposing
"composition" (switching positions of arguments), leads to the
similar concept of *right action* of a monoid *M* on a
set *X*: it is an operation ⋅ : *X* × *M* → *X*
such that

- ∀
*x*∈ *X*, *x* ⋅ *e* = *x*;
- ∀
*a*,*b* ∈ *M*, ∀ *x* ∈ *X*,
(*x* ⋅ *a*) ⋅ *b* = *x *⋅ (*a*
• *b*)

It defines a function *f* : *M* → *X*^{X} that is not
exactly a morphism of monoid but let us call it an anti-morphism,
which means a morphism where one monoid is replaced by its *opposite*,
i.e. seen with its composition transposed :

*f*(*e*)=Id_{X}

∀*a*,*b*∈*M*, *f*(*a* • *b*) =
*f*(*b*) ০ *f*(*a*)

### Commutants

The *commutant* of any subset *A*⊂*E* for a binary operation # in *E*,
is defined as
*C*(*A*) = {*x*∈*E*|∀*y*∈*A*,
*x*#*y *= *y*#*x*}.

This is a Galois connection:
∀*A*,*B*⊂*E*, *B*⊂*C*(*A*) ⇔ *A*⊂*C*(*B*).

A binary operation # in a set *E*, is called
*commutative* when *C*(*E*) = *E*, i.e.
∀*x*,*y*∈*E*, *x*#*y*
= *y*#*x*.
**Proposition.** For any associative
operation # on a set *E*, ∀*A*⊂*E*,

*C*(*A*) ∈ Sub_{#}*F*
- If
*A*⊂*C*(*A*) and 〈*A*〉_{#}=*E* then # is commutative

Proof:
- ∀
*x,y*∈*C*(*A*), (∀*z*∈*A*, (*x*#*y*)#*z*
= *x*#*z*#*y* = *z*#(*x#y*)) ∴ *x*#*y*∈*C*(*A*)
*A*⊂*C*(*A*)∈ Sub_{#}*F*
⇒ *E*=*C*(*A*)
⇒ *A*⊂*C*(*E*) ∈ Sub_{#}*F* ⇒
*C*(*E*) = *E*.

### Centralizers

As *e* commutes with all elements, the commutant of a subset
of a monoid, is a sub-monoid. In this case the word "*centralizer*"
is used instead of "commutant".

By definitions, the centralizer of any *G* ⊂ *E*^{E}, is its monoid
of endomorphisms End_{G} E. The concept of centralizer will be later
generalized from this unary case (sets of transformations) to clones
of operations with all arities.

When 2 actions of monoids on the same set *X* commute with each
other, it can be formally convenient to see them acting on a
different side: the commutation
between *a*∈*M* acting on the left and *b*∈*N* acting on the right
on *X* is written ∀*x*∈*X*,
(*a**x*)*b* = *a*(*xb*)

which formally looks like an associativity law.

**Remark.** Let *M*, *X* be given structures of *M*-algebras by any
operations • : *M*×*M* → *M* and ⋅ : *M*×*X* → *X*. Then denoting
∀*x*∈*X*, *h*_{x} = (*M*∋*a* ↦ *a* ⋅ *x*), we have
directly from definitions
*h*_{x}(*e*) = *x* ⇔ *e* ⋅ *x* = *x*

*h*_{x} ∈ Mor_{M}(*M*,*X*) ⇔ ∀*a*,*b*∈*M*,
(*a* • *b*) ⋅ *x* = *a* ⋅ (*b* ⋅ *x*)

*h*_{e} = Id_{M} ⇔
(∀*a*∈*M*, *a* • *e* = *a*) ⇒ ∀*g*∈Mor_{M}(*M*,*X*),
*g*=*h*_{g(e)}.

Let us verify that both axioms of monoid suffice to gather all
properties of transformation monoids, and even all properties of
monoids of endomorphisms.
**Representation theorem.** For any monoid *M* there exists a language
*L* of function symbols and an *L*-algebra *X*
such that the monoid End_{L} *X* is
isomorphic to *M*.

Proof:

Let *L* and *X* be two copies of *M*.

Give *L* the right action on *X* copied from the
composition in *M* (whose axioms of monoid give those of
action).

Let *f* ∈ Mor(*M*, *X*^{X})
represent the left action of *M* on *X* also copied
from the composition in *M*.

Im *f* ⊂ End_{L} *X* by associativity
of the operation from which both actions on opposite sides are
copied.

*f* is injective because the copy *k* of *e* in *X*
is a free element.

End_{L} *X* ⊂ Im *f* because

∀*g*∈End_{L}*X*, ∃*u*∈*M*, *g*(*k*)=*u**k*
∴ (∀*x*∈*X*, ∃*s*∈*L*,
*k**s*=*x* ∴ *g*(*x*)=*g*(*k**s*)=*g*(*k*)*s*=*u**ks*=*ux*)
∴ *g*=*f*(*u*) ∎

The bijections identifying *L* and *X* as copies of *M*,
finally do not play any special role: while they are definable from
*k*, this *k* itself may be not unique in the role its
plays here.

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. Categories

3.7. Algebraic terms and term algebras

3.8. Integers and recursion

3.9. Arithmetic with addition

4. Model Theory