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

### Trajectories

For any set of transformations LEE, seen as a set of function symbols interpreted in E,

xE, 〈{x}〉L = {f(x)|f∈〈L{Id,০}}
XE, 〈XL = ⋃f∈〈L{Id,০} f[X] = ⋃xX 〈{x}〉L

As we shall formalize later, this is because both mean the same : the set of all composites of any number of functions in L, applied to any xX. But here is a simple proof, denoting A=〈XL, M=〈L{Id,০} and K={f(x) | (f,x)∈M×X}:
Proof of AK
IdEMXK
gL, ∀yK, ∃(f,x)∈M×X, y=f(x) ∧ gfMg(y) = gf(x)∈K
K ∈ SubLE
Proof of KA
L ⊂ {fEE| A ∈ Sub{f}E} = End{A}E ∈ Sub{Id,০}EE
M ⊂ End{A}E
fM, XA ∈ Sub{f}Ef[X] ⊂ A. ∎
The trajectory of an element xE by a transformation monoid M of E, is the set it generates:

〈{x}〉M = {f(x)|fM} ⊂ E

### The Galois connection (Inv, End)

For any n∈ℕ and any set E, the preservation relation {(f,R)∈EE×RelE(n) |∀xR, fxR} (now focusing on only one object) induces a Galois connection (Inv(n),End) between the powersets of EE and RelE(n). The case n=1 was already seen as (Sub, End).

For any GEE, the n-ary relations in the set Inv(n)(G) are called invariant by G.
The closure End০Inv(n) is the transformation of ℘(EE) defined by L ↦ {gEE| ∀xEn, ∃f∈〈L{Id,০}, fx=gx}, as can be seen from how invariants are rebuilt in a concrete category.
Gathering all arities forms another Galois connection (Inv, End) with the product

Inv = ∏n∈ℕ Inv(n) : ℘(EE) → ∏n∈ℕ ℘(RelE(n)) ≅ ℘(RelE).

Its closure End০Inv is L ↦ {gEE| ∀n∈ℕ,∀xEn, ∃f∈〈L{Id,০}, fx=gx}.

### 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 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) ∈ 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.
This concept will be later generalized to clones of operations with all arities.

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. Algebraic terms
3.9. Term algebras
3.10. Integers and recursion
3.11. Presburger Arithmetic
4. Model Theory