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

As the concept of monoid is formally symmetric between left and right, transposing "composition" (switching positions of arguments), 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 that is not exactly a morphism of monoid but let us call it an anti-morphism, which means a morphism where one monoid is replaced by its opposite, i.e. seen with its composition transposed :

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

As e commutes with all elements, the commutant of a subset of a monoid, is a sub-monoid. In this case the word "centralizer" is used instead of "commutant".
By definitions, the centralizer of any GEE, is its monoid of endomorphisms EndG E. The concept of centralizer will be later generalized from this unary case (sets of transformations) to clones of operations with all arities.

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.

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