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 {Id, ০}-algebra, with two operation symbols: the constant Id, and the binary operation ০ of composition.
More generally, a transformation monoid G of E is an {Id, ০}-algebra G∈Sub{Id, ০}EE, of transformations of E: These axioms were those directly subjecting the set of endomorphisms of a fixed object in a concrete category. In particular, they are the exact axioms subjecting (defining the concept of) a concrete category with only one object E.

Permutation groups

A permutation of a set E is a bijective transformation of E.
The set ⤹E ={f EE| Inj f ∧ Im f=E} = {f EE|f:EE} of all permutations of E, is a transformation monoid of E called the symmetric group of E.
A permutation group G of a set E, is a transformation monoid of E such that

G ⊂ ⤹E ∧ ∀fG, f -1G.

It will be seen as an algebra with one more operation : the inversion function ff -1. So it is a {Id,०, -1}-subalgebra of ⤹E.
Unlike full transformation monoids and symmetric groups, the concepts of transformation monoid and permutation group make sense independently of the powerset, as sets of transformations satisfying the above first-order stability axioms, ignoring the containing sets EE or ⤹E.

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, ০}}.

Intuitively, this is because they mean the same : the set of all composites of any number of functions in L, applied to x. This will be formalized later. But here is a simple proof, denoting K={f(x)|f∈〈L{Id, ০}}:
Proof of 〈{x}〉LK
IdE∈〈L{Id, ০}xK
(f∈〈L{Id, ০},∀gL, gf∈〈L{Id, ০}g(f(x))∈K)K∈SubLE
Proof of K ⊂ 〈{x}〉L
L ⊂ {fEE| 〈{x}〉L ∈ Sub{f} E} = End{〈{x}〉L}E ∈ Sub{Id, ০}EE ∴ ∀f∈ 〈L{Id, ০}, 〈{x}〉L ∈ Sub{f} Ef(x)∈〈{x}〉L. ∎
The trajectory of an element xE by a transformation monoid G of E, is the set it generates (usually called its orbit when G is a permutation group):

〈{x}〉G = {f(x)|fG} ⊂ E

As noted in the example in 2.7, the binary relation on E defined by (y∈〈{x}〉G) is a preorder; it is an equivalence relation if G is a permutation group.

Monoids

A monoid is an algebra behaving like a transformation monoid, but without specifying a set which its elements may transform, by which both symbols Id and ০ got their interpretation. This abstractness can be formalized by renaming these symbols, respectively 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 both identity conditions). 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} (its identity property defines how composition extends to it, preserving associativity). Any identity element in E loses its status of identity in E'.

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 xz=yzx=y.
If a right identity e is left cancellative then it is the unique right identity : ee' = e = eee' = e.
The operation • is called cancellative if all its 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 sub-monoid.
From the concept of monoid, replacing the use of e as a constant by ∃e in the axiom, would weaken or generalize the concepts of submonoids and morphism as follows.
For any monoid (M, e, •) and any set with a binary operation (X, ▪), if a function preserves composition f ∈ Mor(M,X) then 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').

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. Categories
3.7. Algebraic terms and term algebras
3.8. Integers and recursion
3.9. Arithmetic with addition
4. Model Theory