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 Both equalities in the identity axiom may be taken separately, forming two different concepts : If both a left identity e and a right identity e' exist then they are equal : e = ee' = 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, xy = xzy = z.

Similarly x is right cancellative if •(x) is injective:

y,z, yx = zxy = 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 :

ae' = a = aee' = 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,▪)), If the target forms a monoid (X,e',▪) then (by uniqueness of the identity in A)

f ∈ Mor{e}(M,X) ⇔ a = e'e'AA ∈ Sub{e, ▪} X

but these equivalent formulas may still be false, unless a is cancellative on one side (aa = a = ae'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,bM, f(ab) = f(b)▪f(a)

Commutants and centralizers

The commutant of any subset AE for a binary operation • in E, is defined as

C(A) = {xE|∀yA, xy = yx}.

This forms a Galois connection :

A,BE, BC(A) ⇔ AC(B).

Such A,B are said to commute, as each element of A commutes with each element of B.

If • is associative then ∀AE, C(A) ∈ Sub{•}F.
Proof: ∀x,yC(A), (∀zA, xyz = xzy = zxy) ∴ xyC(A).

Commutants in monoids are called centralizers. They are more precisely sub-monoids as obviously eC(A).
This can be understood as an intersection of submonoids in the case of a transformation monoid MXX :

AM, 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 AC(A) and 〈A{•} = E then • is commutative.
Proof: AC(A)∈ Sub{•}FE = C(A) ⇒ AC(E) ∈ Sub{•}FC(E) = E.∎

In the case of monoids the conditions AC(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:

∘ : 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 : The set End(E) = Mor(E,E) of endomorphisms of any object E, is a monoid.

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.


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