# 3.5. Actions of monoids

### Left actions

After monoids were deprived of their role as sets of transformations,
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 (thus an embedding):∀*a*,*b*∈*M*, (∀*x*∈*X*,
*a*·*x* = *b*·*x*) ⇒ *a*=*b*

letting *e*
and • be definable from (i.e. unique for) 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 the concrete category *M*
with object *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 left action of *M* on *X*; the ⇐ is implied by
(∀*a*∈*M*, *a*•*e* = *a*). This last axiom of monoid (beyond those
of left action of *M* on itself), comes conversely as a particular case of this ⇐ when
*X*=*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 like a left action with
sides switched: 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 amounts to a left action of the opposite monoid, and defines an anti-morphism from *M* to *X*^{X}.

The commutation of 2 submonoids of *X*^{X} looks like an
associativity formula when written as acting by opposite sides on *X*:
*a*∈*M* left acting on *X* commutes with *b*∈*N*
right acting on *X* when ∀*x*∈*X*,
(*a*⋅*x*)⋅*b* = *a*⋅(*x*⋅*b*)

### Representation theorem

The axioms of monoid actually suffice to give all
properties of transformation monoids, and even all properties of
monoids of endomorphisms:
**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 essentially repeats the above formulas on acts as algebraic structures,
transposed :
Let *L* and *X* be two copies of *M*.

Give *L* the right action on *X* copied from the
composition in *M*.

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
making both actions on opposite sides commute.

*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*⋅*k*⋅*s* = *u*⋅*x*)
∴ *g* = *f*(*u*) ∎

The last formula just needs *k* to be a generating element both sides, to
bijectively (if also free) identify *L* and *X* as copies of *M*,
but such a *k* is not necessarily unique.
### 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

3.9. Term algebras

3.10. Integers and recursion

3.11. Presburger Arithmetic

4. Model Theory