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


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

xE, 〈{x}〉L = {f(x)|f∈〈L{Id,০}}.

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 x. But here is a simple proof, denoting A=〈{x}〉L, M=〈L{Id,০} and K={f(x)|fM}:
Proof of AK
(gL, ∀yK, ∃fM, y=f(x)∧gfMg(y)∈K)K∈SubLE
Proof of KA
L ⊂ {fEE| A ∈ Sub{f}E} = End{A}E ∈ Sub{Id,০}EE
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


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 •.
Namely, the concept of monoid is the theory made of

Both equalities in the last axiom may be considered separately, forming two different concepts

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 element satisfying each identity condition). The existence of a right identity implies the uniqueness of the left identity, but without right identity, several left identities may coexist (and similarly switching left and right).
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.


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 xz=yzx=y.
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.
Any submonoid of a cancellative monoid is cancellative. Not all monoids are cancellative: the monoid of addition in {0,1, several} is not cancellative as 1+several = several+several.

Submonoids and morphisms of monoids

Any {e,•}-subalgebra of a monoid is a monoid, thus called a submonoid.
Modifying of 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 function f ∈ Mor{•}(M,X), If the target forms a monoid (X,e',▪) then (by uniqueness of the identity in A)

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

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 and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory