Monoids and actions

in the series of texts on Algebra.

Transformations monoids

A transformation of a set E, is a function from E to itself. The full transformation monoid of E is the set EE of all transformations of E, seen as an {Id, ০}-algebra, with two operation symbols: the constant Id, and the binary operation ০ of composition.
More generally, a transformation monoid of E is a set of transformations of E forming an {Id, ০}-algebra. It is thus a sub-algebra G∈Sub{Id, ০}EE, but this concept of transformation monoid is defined independently of the powerset, by the first-order axioms of stablility by Id and ০ : These conditions were already seen as those of morphisms of concrete categories (here for a concrete category with only one object, or for the endomorphisms in a fixed object). So, the set of endomorphisms of any relational system (and thus also any algebra), is a transformation monoid. In particular, for any set GEE, the set of G-endomorphisms of E is the commutant of G in EE.

The transformation monoid generated by G (in the above sense of "subalgebra generated by a subset" with this language of monoid made of 2 symbols), is equivalently described as made of

Monoids

Monoids are algebras with the same properties as transformation monoids (with associativity of "composition") but without reference to a specific set where it operates as a set of transformations.

After we introduced monoids and groups as sets of transformations of a given set, we are going to express their properties in themselves (ignoring the set they may transform), as axiomatic theories.

For any binary operation •, we may consider the concepts of:

If there exists both a left identity and a right identity then they are equal : e = ee' = e'. Thus the existence of a right identity implies the uniqueness of the left identity (thus an identity if it exists), otherwise several left identities may coexist (and similarly switching left and right).

The concept of (abstract) monoid is an axiomatic theory with 1 type, 2 operation symbols:
and the axioms
From any associative operation (without identity element) we can get a monoid by adding the identity as an extra element : the composition operation extends to it as determined by the identity axiom, and this preserves associativity.
This still works if an identity element was already there: it was an identity element of the initial system (which is stable by composition in the new one) but differs from the new identity element.

Submonoids and morphisms of monoids

Even though the composition in a monoid M suffices to determine the value of e, we do need to include e in the language (rather than only claim its existence by an axiom), as it affects the concepts of submonoids and morphism of monoid. Any subalgebra of a monoid for this language is a monoid (as expressed with the restriction of interpretations of both symbols • , e), thus called a sub-monoid.
For any function between monoids f : (M,•, e) → (M',▪, e') that preserves the composition,

a, bM, f(ab) = f(a) ▪ f(b)

its image will be stable by ▪, forming a monoid where the role of the identity element is played by f(e), and we have the equivalences f∈Mor(M,M') ⇔ f(e)=e'e'∈ Im f

Left action

A left action of a monoid (M,•, e) on a set X, is an operation ⋅ : M × XX whose curried form is a morphism of monoid from M to the transformation monoid XX. Namely it preserves both identity and composition: The set X endowed with this operation, is called an M-set.
A left action is said effective if this morphism is injective, i.e. ∀a, bM, (∀xX, a·x = b·x) ⇒ a=b.

We can similarly define a left action of a group G on a set X, as expressing a group morphism from G to the group of permutations of X. Actually both concepts of action coincide: if f: GXX is a morphism of monoid then ∀aG, f(a)०f(a-1)= f(aa-1)=f(e)=IdX= f(a-1a)=f(a-1)०f(a), thus f(a) is bijective and f is a morphism of groups (f(a-1) = f(a)-1).

Currying the action the other way, each element of an M-set, xX, defines a function hx: MX.
We shall say that x is free if hx is injective. The existence of a free element implies that the action is effective.

Let us call trajectory of x the set Im hxX (usually called the orbit of x when M is a group). It is stable by the action of M (as ∀aM, ∀y =bx∈Im hx, ay = (ab)⋅x ∈ Im hx), so that it is also an M-set.

The binary relation on X defined by (y∈Im hx) is a preorder, and if M is a group then it is an equivalence relation (whose equivalence classes are the orbits), as we noted in the example in 2.7.

Typical examples

In any theory with one type, the set of all terms with one variable (definitions of functions), is a monoid acting on each model of the theory. We can quotient it by the equivalence relation of provable equality between terms.
Its image as a transformation monoid in every model, the set of all definable functions, commutes with the monoid of endomorphisms of the model, i.e. each is included in the commutant of the other (i.e. each function in the one commutes with each function in the other). Indeed, commutation is what it means for an endomorphism to preserve a defined function.

Right actions

As the formal concept of monoid is symmetric between left and right (by transposition of the "composition" operation), we can equally define a concept of right action of a monoid M on a set X, that differs from the above concept of left action, by switching left and right positions of arguments in operations: it is an operation ⋅ from  X × M to X such that

It defines a function  f : M XX that is not directly a morphism of monoid but is only so in the twisted sense that positions are reversed (it becomes a morphism once transposed the composition operation in M) :
f(e)=IdX and ∀a,bM, f(ab) = f(b) ० f(a)
In the case of a group G, inversion reverses the order of composition, so that left and right actions of G on X are exchanged by inversion (one • can be defined from the other ▪ by ∀xX, ∀gG, x•g = g-1▪x ; these actions usually do not commute...).

Centralizers

The commutant of a subset of a monoid is called a centralizer. It is a sub-monoid. Indeed, the identity obviously commutes with all elements. In a transformation monoid XX, the centralizer of a set A of transformations, is the monoid of endomorphisms of the system having A as list of structures (function symbols).

When the actions of 2 monoids on the same set commute with each other, we can interestingly see them as acting on a different side. Namely let X a set with a left action of a monoid M and a right action of another monoid N. Then the commutation between the images of aM and bN in XX is written
xX, (ax)b = a(xb)
which has the typographical appearance of an associativity law.

For example, given 2 systems E,F with the same language, the composition of morphisms gives the set Mor(E,F) a left action by End(F) and a right action by End(E), that commute with each other (as composites of morphisms are morphisms and composition is associative).

Representation theorem

Let us verify that both axioms of monoid suffice to gather all properties of transformation monoids, and even all properties of monoids of endomorphisms.

Theorem. For any monoid M there exists an algebraic language L and an L-algebra A such that the monoid EndL A is isomorphic to M.

Proof:

Let L and A be 2 copies of M.
Interpret L as a list of function symbols with the right action on A copied from the composition in M.
Let ∈Mor(M,AA) given by the left action of M on A, again copied from the composition in M. Indeed it satisfies the axioms of left actions (making f a morphism) thanks to associativity, and that e is a left identity.
Im f ⊂ EndL A because both actions commute due to the associativity of the operation from which they are copied.
f is injective because the copy k of e in A is a free element for this action (copied from a right identity in M).
g∈EndL A, ∃xM, g(k)=xk ∧ ∀yA, ∃zL, kz=yg(y)=g(kz)=g(k)z=xkz=xy
so that g=f(x). Thus EndL A ⊂ Im f
When saying that L and A are copies of M, we meant that there exists a system of 2 bijections that identifies them with M letting both actions fit with the composition in M, however these bijections need not be canonical: there may be no way to define them from these actions (i.e. to distinguish the above k from other elements of A that may have the same properties).
This can be directly generalized from monoids to small categories. In this case, the copy of the list of objects in L and in its side of A is re-interpreted as a list of types.

This construction looks similar with the case of the actions of End(E) and End(F) on Mor(E,F). Indeed as L is a copy of M, they are "the same kind of monoid" but acting by different sides on A, just like End(E) and End(F) are "the same kind of monoid" acting by different sides on Mor(E,F).
Can we take this similarity seriously and understand both phenomena as identical ?
Let us boldly confuse them and see what it gives: let
L = End(E)
A = Mor(E,F)
M = End(F) ≈ EndL A
The canonical bijection between End(F) and EndL A means that both systems F and A are constructible from each other (but in a sense adapted to the use of morphisms instead of isomorphisms).
For L=End(E) and A=Mor(E,F) to be (non-canonical) copies of M =End(F), we just need to introduce E as a (non-canonical) copy of F. And give it the list L=End(E) of structures, in case they were not already definable from the structures of E (copies of those of F). In fact we can "block" E (forbid morphisms) by whatever additional structures we like, since the monoid M of morphisms does not aim to act on E or L, but only on A=Mor(E,F); and this action, by the endomorphisms of F, remains unaffected (stay morphisms) by any structures put on E.

Next : Groups and automorphisms
Back to homepage : Set theory and foundations of mathematics