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

### Effectiveness and free elements

A left action of *M* on *X* is said *effective* if this morphism from *M*
to *X*^{X} 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}

### Trajectories

For any set of transformations *L* ⊂ *E*^{E}, seen
as a set of function symbols interpreted in *E*, ∀*x*∈*E*,
〈{*x*}〉_{L} = {*f*(*x*)|*f*∈〈*L*〉_{{Id,০}}}

∀*X*⊂*E*, 〈*X*〉_{L} =
⋃_{f∈〈L〉{Id,০}} *f*[*X*]
= ⋃_{x∈X} 〈{*x*}〉_{L}

Denoting *A* = 〈*X*〉_{L}, *M* = 〈*L*〉_{{Id,০}} and *K* = {*f*(*x*) | (*f*,*x*)∈*M*×*X*},
the claim is that *A* = *K*. As we shall formalize later, both *A* and *K*
mean the set of all composites of any number of functions in *L*, applied to any
*x*∈*X*.

Proof of *A* ⊂ *K*
Id_{E}∈*M* ∴ *X*⊂*K*

∀*g*∈*L*, ∀*y*∈*K*, ∃(*f*,*x*)∈*M*×*X*,
*y*=*f*(*x*) ∧ *g*০*f*∈*M* ∴ *g*(*y*) =
*g*০*f*(*x*)∈*K*

*K*
∈ Sub_{L}*E*

Proof of *K* ⊂ *A*
*L* ⊂ {*f*∈*E*^{E}| *A* ∈
Sub_{{f}}*E*} = End_{{A}}*E*
∈ Sub_{{Id,০}}*E*^{E}

*M* ⊂ End_{{A}}*E*

∀*f*∈*M*,
*X* ⊂ *A* ∈ Sub_{{f}}*E*
∴ *f*[*X*] ⊂ *A*. ∎

The *trajectory* of an element *x*∈*E* by a transformation monoid
*M* of *E*, is the set it generates:
〈{*x*}〉_{M} = {*f*(*x*)|*f*∈*M*} ⊂ *E*

For a monoid *M*, Inv *M* is made of unions of trajectories of tuples.
Other cases come down to this as ∀*L*⊂*E*^{E}, Inv *L*
= Inv 〈*L*〉_{{Id,০}}, so that closures can be written
End_{Inv(n)L} *E* =
{*g*∈*E*^{E}| ∀*x*∈*E*^{n},
∃*f*∈〈*L*〉_{{Id,০}}, *f*০*x*=*g*০*x*}.

End_{Inv L} *E* =
{*g*∈*E*^{E}| ∀*n*∈ℕ,∀*x*∈*E*^{n},
∃*f*∈〈*L*〉_{{Id,০}}, *f*০*x*=*g*০*x*}.

### 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. Initial and final objects

3.9. Algebraic terms

3.10. Term algebras

3.11. Integers and recursion

3.12. Presburger Arithmetic

4. Model Theory