3.5. Actions of monoids

Left actions

After monoids, introduced as sets of transformations, were deprived of this role, 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:

a, bM, (∀xX, a·x = b·x) ⇒ a=b

letting e and • be defined by (= unique for) the axioms on 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 a concrete category where M = End 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 action; the converse is implied by the last axiom of monoid beyond the copies of both axioms of action, which comes as a particular case once X is replaced by M :

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

Right actions

A right action of a monoid M on a set X, is an operation ⋅ : X × MX such that
It defines an anti-morphism from M to XX.

Commutants

The commutant of any subset AE for a binary operation # in E, is defined as

C(A) = {xE|∀yA, x#y = y#x}.

This is a Galois connection: ∀A,BE, BC(A) ⇔ AC(B). Such A,B are said to commute with each other as each element of A commutes with each element of B.
A binary operation # in a set E, is called commutative when C(E) = E, i.e. ∀x,yE, x#y = y#x.

Proposition. For any associative operation # on a set E, ∀AE,

  1. C(A) ∈ Sub#F
  2. If AC(A) and 〈A#=E then # is commutative
Proof:
  1. x,yC(A), (∀zA, x#y#z = x#z#y = z#x#y) ∴ x#yC(A)
  2. AC(A)∈ Sub#FE=C(A) ⇒ AC(E) ∈ Sub#FC(E) = E.

Centralizers

In monoids, commutants are called centralizers; they are sub-monoids, as e commutes with all elements, which can be seen in any transformation monoid MEEas

AM, CM(A) = M ∩ EndA E.

This concept will be later generalized to clones of operations with all arities.
If AC(A) and 〈A{e,•}=E then # is commutative.
When 2 monoids acting on the same set X commute with each other in XX, this commutation appears as an associativity law when seeing them as acting on a different side: aM left acting on X commutes with bN right acting on X when

xX, (ax)b = a(xb)

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 EndL X is isomorphic to M.

The proof is linked to the above formulas on acts, as will be used in the end of 3.7 for a wider result; let us write it separately.

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, XX) represent the left action of M on X also copied from the composition in M.
Im f ⊂ EndL 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.
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 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 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 and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory