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

a, bM, (∀xX, 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 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. The monoid of endomorphisms of any typed system E= ∐iI Ei, acts on every type Ei it contains, by the morphism of monoid from End(E) to EiEi defined by restricting to Ei 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 × MX such that
It defines a function f : MXX 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)=IdX
a,bM, f(ab) = f(b) ০ f(a)

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).
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 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 GEE, is its monoid of endomorphisms EndG 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 aM acting on the left and bN acting on the right on X is written

xX, (ax)b = a(xb)

which formally looks like an associativity law.

Remark. 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).

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.

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, 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. Categories
3.7. Algebraic terms and term algebras
3.8. Integers and recursion
3.9. Arithmetic with addition
4. Model Theory