## 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 :
• IdEM
• f,gM, gfM.
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•(yz) = (xy)•z so that either term can be written xyz
• Identity axiom : ∀x, xe = x = ex
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, ex = x ;
• A right identity of • is an element e' such that ∀x, xe' = x.
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,▪)),
• 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'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:
• 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 = 1Fx
• C E,F,G,H, x∈Mor(E,F), ∀y∈Mor(F,G),∀z∈Mor(G,H), (zy)∘x = z∘(yx) ∈ 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 = yx

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