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 E^{E} 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, ০}}E^{E}, but this concept of
transformation monoid is defined independently of the powerset, by the first-order axioms of stablility by Id and ০ :
- Id_{E} ∈ G
- ∀f,g∈G, f০g ∈ G.
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 G⊂E^{E},
the set of G-endomorphisms of E is the commutant of
G in E^{E}.
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
- all composites of any (possibly empty) list of elements of G
(in any chosen order with possible repetitions, but ignoring
parenthesis thanks to associativity).
- all functions defined by terms with language G (of
unary symbols) and the argument in E.
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:
- left identity : element e such that ∀x∈M
e • x = x
- right identity : element e' such that ∀x∈M
x • e' = x
If there exists both a left identity and a right identity then they
are equal : e = e • e' = 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:
- A binary operation • called "composition"
- A constant symbol e called "identity"
and the axioms
- The composition is associative: ∀x,y,z, x•(y•z)
= (x•y)•z
- e is an identity element for • : ∀x,
x • e = e • x = x
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, b ∈ M, f(a • b)
= 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 × X
→ X whose curried form is a morphism of monoid from
M to the transformation monoid X^{X}.
Namely it preserves both identity and composition:
- ∀x∈ X, e ⋅ x = x;
- ∀ a, b ∈ M, ∀ x ∈ X,
(a • b) ⋅ x = a ⋅ (b ⋅ x).
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, b ∈ M, (∀x∈ X,
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: G→X^{X}
is a morphism of monoid then ∀a∈G, f(a)०f(a^{-1})=
f(a•a^{-1})=f(e)=Id_{X}=
f(a^{-1}•a)=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,
x∈X, defines a function h_{x}: M → X.
We shall say that x is free if h_{x}
is injective. The existence of a free element implies that the
action is effective.
Let us call trajectory of x the set Im h_{x}
⊂ X (usually called the orbit of x when M
is a group). It is stable by the action of M (as ∀a∈M,
∀y =b⋅x∈Im h_{x}, a⋅y
= (a•b)⋅x ∈ Im h_{x}), so that
it is also an M-set.
The binary relation on X defined by (y∈Im h_{x})
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
- ∀x∈ X, x ⋅ e = x;
- ∀a,b ∈ M, ∀ x ∈ X,
(x ⋅ a) ⋅ b = x ⋅ (a
• b)
It defines a function f : M → X^{X} 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)=Id_{X} and ∀a,b ∈
M, f(a • b) = 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 ∀x∈ X, ∀g∈G, 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 X^{X},
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 a∈M and b∈N
in X^{X} is written
∀x∈X, (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 End_{L} 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 f ∈Mor(M,A^{A})
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 ⊂ End_{L} 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∈End_{L} A, ∃x∈M, g(k_{})=xk_{}
∧ ∀y∈A, ∃z∈L, k_{}z=y∧
g(y)=g(k_{}z)=g(k_{})z=xk_{}z=xy
so that g=f(x). Thus End_{L}
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) ≈ End_{L} A
The canonical bijection between End(F) and End_{L}
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