# 3.4. Monoids

### 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 algebra with two operations: the constant Id, and the binary operation ০ of composition.
A transformation monoid of E is a set M of transformations of E forming an {Id,০}-algebra, M ∈ Sub{Id,০}EE :
• IdEM
• f,gM, gfM.
The set of endomorphisms of a fixed object 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 : ∀x, xe = x = ex

Both equalities in the last axiom may be considered 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 and a right identity 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 implies the uniqueness of any left identity, but without right identity, 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 axioms (preserving associativity), but where any identity element which could exist in E loses its status of identity element in E'.
As the identity axiom ensures the surjectivity of •, every embedding between monoids is injective.
Any {e,•}-subalgebra of a monoid is a monoid, thus called a submonoid.

### Cancellativity

An element x is called left cancellative for an operation • if the left composition by x is injective: ∀y,z, xy = xzy = z.
Similarly it is right cancellative if yx = zxy = z.
If a right identity e is left cancellative then it is the unique right identity : ee' = e = eee' = e.
An operation is called cancellative if 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.

### 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 is another 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) ∈ SubF. (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 for transformation monoids MXX by the fact it is an intersection of submonoids: AM, CM(A) = M ∩ EndA X.

A binary operation • in a set E, is called commutative when C(E) = E, i.e. x,yE, xy = yx.

If AC(A) and 〈A=E then • is commutative
Proof: AC(A)∈ SubFE=C(A) ⇒ AC(E) ∈ SubFC(E) = E.∎
In the case of monoids the conditions AC(A) and 〈A{e,•}=E suffice.

### 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)

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Morphisms of relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Initial and final objects
3.9. Eggs, basis, clones and varieties
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry