# 3.5. Actions of monoids

### Left actions

After monoids, introduced as sets of transformations, were deprived of this role,
it can be given back to them as follows.

A *left action* of a monoid (*M*,*e*, •) on a set *X*, is an operation ⋅ :
*M*×*X* → *X* such that
- ∀
*x*∈*X*, *e* ⋅ *x* = *x*;
- ∀
*a*,*b*∈*M*, ∀*x*∈*X*,
(*a* • *b*) ⋅ *x* = *a* ⋅ (*b* ⋅ *x*).

Seing *M* as a set of function symbols, an *M*-algebra (*X*, ⋅)
satisfying these axioms is called an *M*-set.

In curried view, a left action of *M* on *X* is a
{*e*,•}-morphism from *M* to the full transformation monoid *X*^{X}.
### Effectiveness and free elements

A left action is said *effective* if this morphism is
injective:∀*a*, *b* ∈ *M*, (∀*x*∈ *X*,
*a*·*x* = *b*·*x*) ⇒ *a*=*b*

letting *e*
and • be defined by (= unique for) the axioms on the given action, like the axioms for functions ensured the sense
of the definitions of Id and ০ from 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.**
Any transformation monoid *M* of a set *E* acts by restriction on any *M*-stable
subset *A* of *E*, i.e. any preserved *A*⊂*E* in a concrete category where
*M* = End *E*. Thus, the monoid of endomorphisms of any typed system *E*=
∐_{i∈I} *E*_{i},
acts on every type *E*_{i} it contains.
### Acts as algebraic structures

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)}.

So in the formula ∀*g*∈*X*^{M}, ∀*x*∈*X*,
*g*=*h*_{x} ⇔
(*g*∈Mor_{M}(*M*,*X*) ∧ *g*(*e*)=*x*)

the ⇒ expresses the axioms of action; the converse is implied by the last axiom of monoid
beyond the copies of both axioms of action, which comes as a particular case once *X*
is replaced by *M* : (Id_{M} ∈
Mor_{M}(*M*,*M*) ∧ Id_{M}(*e*)=*e*)
⇒ *h*_{e} = Id_{M}

### Right actions

A *right action* of a monoid *M* on a
set *X*, 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 an anti-morphism from *M* to *X*^{X}.
### 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*).
Such *A*,*B* are said to commute with each other as each element of *A*
commutes with each element of *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

In monoids, commutants are called *centralizers*; they are sub-monoids, as *e*
commutes with all elements, which can be seen in any transformation monoid
*M*⊂*E*^{E}as
∀*A*⊂*M*, *C*_{M}(*A*) = *M* ∩
End_{A} E.

This concept will be later generalized to clones
of operations with all arities.

If *A*⊂*C*(*A*) and 〈*A*〉_{{e,•}}=*E*
then # is commutative.

When 2 monoids acting on the same set *X* commute with each other
in *X*^{X}, this commutation appears as an associativity law
when seeing them as acting on a different side: *a*∈*M* left
acting on *X* commutes with *b*∈*N*
right acting on *X* when ∀*x*∈*X*,
(*a**x*)*b* = *a*(*xb*)

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

The proof is linked to the above formulas on acts, as will be used
in the end of 3.7 for a wider result; let us write it separately.
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.
### Trajectories by commutative monoids

Let a monoid *M* act on a set *X*, and let *k*∈*X*.
The trajectory *Y* of *k* by *M* is
stable by *M*, thus defines a morphism of monoid from *M* to
*Y*^{Y} with image a transformation monoid *N* of *Y*.

Forgetting *M* and *X*, we have a monoid *N* with an effective action
on *Y* generated by *k*.

Now if *N* is commutative (which is the case if *M* is commutative) then *k*
is free for the action of *N* (thus *Y* can be seen as a copy of *N*).

The proof is easy and left as an exercise.

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