# 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

The *opposite* of a monoid is the monoid with the same base set but
where composition is replaced by its transposed.
This symmetry of the concept of monoid, 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} which is not
a morphism but an *anti-morphism*, i.e. a morphism from one
monoid to the opposite of the other (or equivalently vice-versa):
*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

In monoids, commutants of subsets are sub-monoids (as *e* commutes with all elements). There,
the word "*centralizer*" is used instead of "commutant". This concept will be later
generalized further, from this unary case (acting as sets of transformations) to clones
of operations with all arities.

The centralizer of any *G* ⊂ *E*^{E}, is its monoid
of endomorphisms End_{G} E.

The above commutativity
result works with the weakened assumption 〈*A*〉_{{e,•}}=*E*.

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

3.7. Algebraic terms and term algebras

3.8. Integers and recursion

3.9. Arithmetic with addition

4. Model Theory