3.5. Monoids
Transformations monoids
A transformation of a set E, is a function from E
to E. The full transformation monoid of E is the set EE
of all transformations of E, seen as an algebra
with two operations: the constant Id, and the binary
operation ⚬ of composition.
A transformation monoid of E is a {Id,⚬}-algebra M ∈
Sub{Id,⚬}EE of transformations of E :
The set End(E) of endomorphisms of any object E in a concrete category, is a
transformation monoid.
Any transformation monoid can be seen as a concrete category with only one object.
Monoids
A monoid is an algebra behaving like a transformation monoid, but without
specifying a set which its elements may transform. As both symbols Id and ⚬ lose
their natural interpretation, they are respectively renamed as e and •. So, the
concept of monoid is the theory
with only one type and
- Two operation symbols
- a constant symbol e of "identity"
- a binary operation • of "composition"
- Axioms
- Associativity : ∀x,y,z, x•(y•z)
= (x•y)•z so that either term can be
written x•y•z
- Identity axiom : ∀x, x•e = x
= e•x
Both
equalities in the identity axiom may be taken separately, forming two different concepts :
- A left identity of a binary
operation • is an element e such that ∀x,
e • x = x ;
- A right identity of • is an element e' such that ∀x,
x•e' = x.
If both a left identity e and a right identity e' exist then they are
equal : e = e•e' = e' which makes
it the identity of • (the unique identity element on either side).
The existence of a right identity thus implies the uniqueness of a left identity, but otherwise
several left identities may coexist (and similarly with sides reversed).
From any associative operation on a set E we can form a monoid by adding the
identity e as an extra element, E' = E ⊔ {e},
to which the interpretation of • is extended as determined by the identity axiom. This preserves
associativity; but any identity element from E loses its status of identity in E'.
Any {e,•}-subalgebra of a monoid is a monoid, thus called a
submonoid.
Cancellativity
An element x is left cancellative for a binary operation • if the transformation
•⃗(x) (called left composition by x) is injective: ∀y,z, x•y = x•z ⇒ y = z.
Similarly x is right cancellative if •⃖(x) is injective:
∀y,z, y•x = z•x ⇒ y = z.
A cancellative operation is an operation where all elements are cancellative on both sides.
For example the monoid of addition in {0,1, several} is not cancellative as
1+several = several+several.
Any submonoid of a cancellative monoid is cancellative.
The existence of a left cancellative element implies the uniqueness of a right identity :
a•e' = a = a•e ⇒ e' = e.
Other concepts of submonoids and morphisms
Modifying the formalization of monoid by replacing the status of e as a constant
by ∃e in the identity axiom, would weaken the concepts of submonoids
and morphism (allowing more of them) as follows.
For any monoid (M,e,•), any set X with a binary operation
▪, and any morphism of composition f ∈ Mor((M,•),(X,▪)),
- its image is a monoid (A,a,▪) where A = Im f
and a = f(e)
- f is a morphism of monoid from M
to this monoid A.
If the target forms a monoid (X,e',▪)
then (by uniqueness of the identity in A)
f ∈ Mor{e}(M,X) ⇔
a = e' ⇔
e' ∈ A ⇔ A ∈ Sub{e, ▪} X
but these equivalent formulas may still be false, unless a is cancellative on one side
(a▪a = a = a▪e' ⇒ a = e').
Anti-morphisms. The opposite of a monoid is the monoid
with the same base set but where composition is replaced by its transpose. An
anti-morphism from (M,e,•) to (X,e',▪) is a morphism
f from one
monoid to the opposite of the other (or equivalently vice-versa):
f(e) = e'
∀a,b∈M, f(a•b) =
f(b)▪f(a)
Commutants and centralizers
The commutant of any subset A⊂E for a binary operation • in E,
is defined as
C(A) = {x∈E|∀y∈A,
x•y = y•x}.
This forms a Galois connection : ∀A,B⊂E,
B⊂C(A) ⇔ A⊂C(B).
Such A,B are said to commute, as each element of A
commutes with each element of B.
If • is associative then ∀A⊂E, C(A)
∈ Sub{•}F.
Proof: ∀x,y∈C(A),
(∀z∈A, x•y•z = x•z•y =
z•x•y) ∴ x•y∈C(A).
Commutants in monoids are called centralizers. They are more precisely sub-monoids as
obviously e∈C(A).
This can be understood as an intersection of submonoids in the case of a transformation
monoid M⊂XX : ∀A⊂M,
CM(A) = M ∩ EndA X
(Compared to the (End, Inv(2)) connection, this one comes by
restricting the preservation relation to the set of graphs of functions in M).
A binary operation • in a set E, is called
commutative when • = t•,
i.e. C(E) = E.
If A⊂C(A) and 〈A〉{•} = E then • is commutative.
Proof: A⊂C(A)∈ Sub{•}F
⇒ E = C(A)
⇒ A⊂C(E) ∈ Sub{•}F ⇒
C(E) = E.∎
In the case of monoids the conditions
A ⊂ C(A) and 〈A〉{e,•} = E suffice.
Categories
The concept of monoid came as an abstraction of transformation
monoids (= concrete categories with a single object). Now, the concept of category
(or abstract category) does the same with pluralities of objects : it differs from the
concept of concrete category, by forgetting that objects are sets and that morphisms
are functions. So, a category C is made of:
- the class of its "objects" ; the category is small if this class is a set;
- to any objects E,F is given a set Mor(E,F) of
«morphisms from E to F»; these are usually regarded as pairwise disjoint;
- to any object E is given a constant symbol 1E ∈ Mor(E,E);
- to any triple of objects E,F,G is given a "composition" operation
(abusively all denoted by the same symbol)
∘ :
Mor(F,G)×Mor(E,F) → Mor(E,G)
satisfying both axioms of identity and associativity, where quantifiers ∀C
mean to range in the class of objects :
- ∀C E,F, ∀x∈Mor(E,F),
x∘1E = x = 1F∘x
- ∀C E,F,G,H, ∀x∈Mor(E,F),
∀y∈Mor(F,G),∀z∈Mor(G,H),
(z∘y)∘x = z∘(y∘x) ∈ Mor(E,H)
For display convenience, composition may also be written transposed, by the semicolon notation from
computer science : ; = t∘ :
Mor(E,F)×Mor(F,G) → Mor(E,G)
x;y = y∘x
The set End(E) = Mor(E,E) of endomorphisms of any object E,
can be seen as a monoid in both opposite ways, by restriction of either ∘ or ;.
The concept of opposite category is defined similarly to opposite monoids,
as re-reading the category with sides reversed, the Mor(E,F) of the one serving as
the Mor(F,E) of the other. For any concept relative to a given category, its
dual will mean the similar concept following the same definition with sides reversed, which
amounts to applying this concept to the opposite category; it will usually be called by appending
the prefix co- to the concept's name.
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry
Other languages:
FR :
Monoïdes et catégories