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} ∈ Sub{Id, ০}EE
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 operation • is called cancellative if all transformations defined by currying it on any side are injective:

x,y,z, (xy=xzy=z ) ∧ (xz=yzx=y ).

Cancellative operations cannot have several identities on one side.
Not all monoids are cancellative. For example the monoid of addition in the set of 3 elements {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.

Replacing the presence of e in the language by the existence quantifier on it in the axiom, weakens the concepts of submonoids and morphism of monoid as follows.
For any function f : MX from a monoid (M, e, •) to a set with a binary operation (X, ▪) preserving composition (∀a,bM, f(ab) = f(a) ▪ f(b)), Im f forms a monoid where the role of the identity element is played by f(e).
If the target forms a monoid (X,▪, e') then (by uniqueness of the identity in Im f)

f(e)=e'e'∈ Im f ⇔ Im f ∈ Sub{e, •} X

but these equivalent formulas may still be false.


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