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×XX such that 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 XX.

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 × MX such that
It amounts to a left action of the opposite monoid, and defines an anti-morphism from M to XX.

The commutation of 2 submonoids of XX looks like an associativity formula when written as acting by opposite sides on X: aM left acting on X commutes with bN right acting on X when

xX, (ax)⋅b = a⋅(xb)

Effectiveness and free elements

A left action of M on X is said effective if this morphism from M to XX is injective (thus an embedding):

a,bM, (∀xX, 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 xX 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:

(∃xX, ∀abM, a·xb·x) ⇒ (∀abM, ∃xX, a·xb·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 AE in the concrete category M with object E. Thus, the monoid of endomorphisms of any typed system E= ∐iI Ei, acts on every type Ei it contains.

Acts as algebraic structures

Let M, X be given structures of M-algebras by any operations • : M×MM and ⋅ : M×XX. Then denoting ∀xX, hx = (Maax), we have directly from definitions

hx(e) = xex = x
hx ∈ MorM(M,X) ⇔ ∀a,bM, (ab)⋅x = a⋅(bx)
he = IdM ⇔ (∀aM, ae = a) ⇒ ∀g∈MorM(M,X), g=hg(e).

So in the formula

gXM, ∀xX, g=hx ⇔ (g∈MorM(M,X) ∧ g(e)=x)

the ⇒ expresses the axioms of left action of M on X; the ⇐ is implied by (∀aM, ae = 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 :

(IdM ∈ MorM(M,M) ∧ IdM(e)=e) ⇒ he = IdM


For any set of transformations LEE, seen as a set of function symbols interpreted in E,

xE, 〈{x}〉L = {f(x)|f∈〈L{Id,০}}
XE, 〈XL = ⋃f∈〈L{Id,০} f[X] = ⋃xX 〈{x}〉L

Denoting A = 〈XL, 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 xX.
Proof of AK
gL, ∀yK, ∃(f,x)∈M×X, y=f(x) ∧ gfMg(y) = gf(x)∈K
K ∈ SubLE
Proof of KA
L ⊂ {fEE| A ∈ Sub{f}E} = End{A}E ∈ Sub{Id,০}EE
M ⊂ End{A}E
fM, XA ∈ Sub{f}Ef[X] ⊂ A. ∎
The trajectory of an element xE by a transformation monoid M of E, is the set it generates:

〈{x}〉M = {f(x)|fM} ⊂ E

For a monoid M, Inv M is made of unions of trajectories of tuples. Other cases come down to this as ∀LEE, Inv L = Inv 〈L{Id,০}, so that closures can be written

EndInv(n)L E = {gEE| ∀xEn, ∃f∈〈L{Id,০}, fx=gx}.
EndInv L E = {gEE| ∀n∈ℕ,∀xEn, ∃f∈〈L{Id,০}, fx=gx}.

Trajectories by commutative monoids

Let a monoid M act on a set X, and let kX. The trajectory Y of k by M is stable by M, thus defines a morphism of monoid from M to YY 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