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.

Effectiveness and free elements

A left action is said effective if this morphism 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

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)

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 EndL 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, XX) represent the left action of M on X also copied from the composition in M.
Im f ⊂ EndL 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.
EndL X ⊂ Im f because
g∈EndLX, ∃uM, g(k) = uk ∴ (∀xX, ∃sL, ks = xg(x) = g(ks) = g(k)⋅s = uks = ux) ∴ 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 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. Algebraic terms
3.9. Term algebras
3.10. Integers and recursion
3.11. Presburger Arithmetic
4. Model Theory