# 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 *E*^{E}
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, ০}}*E*^{E}, of transformations of *E*:
- Id
_{E} ∈ *G*

- ∀
*f,g*∈*G*, *g*০*f* ∈ *G*.

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 *∈ *E*^{E}| Inj *f* ∧ Im
*f*=*E*} = {*f *∈ *E*^{E}|*f*:*E*↔*E*}
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* ∧ ∀*f*∈*G*, *f*^{ -1}∈ *G*.

It will be seen as an algebra with one more operation : the inversion function *f*↦*f*^{ -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 *E*^{E}
or ⤹*E*.
### Trajectories

For any set of transformations *L* ⊂ *E*^{E}, seen
as a set of function symbols interpreted in *E*, ∀*x*∈*E*,
〈{*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*}〉_{L} ⊂ *K*
Id_{E}∈〈*L*〉_{{Id, ০}} ∴ *x*∈*K*

(∀*f*∈〈*L*〉_{{Id, ০}},∀*g*∈*L*, *g*০*f*∈〈*L*〉_{{Id, ০}} ∴
*g*(*f*(*x*))∈*K*) ∴ *K*∈Sub_{L}*E*

Proof of *K* ⊂ 〈{*x*}〉_{L}
*L* ⊂ {*f*∈*E*^{E}| 〈{*x*}〉_{L} ∈
Sub_{{f}} *E*} = End_{{〈{x}〉L}}*E*
∈ Sub_{{Id, ০}}*E*^{E} ∴ ∀*f*∈ 〈*L*〉_{{Id, ০}},
〈{*x*}〉_{L} ∈ Sub_{{f}} *E*
∴ *f*(*x*)∈〈{*x*}〉_{L}. ∎

The *trajectory* of an element *x*∈*E* 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*)|*f*∈*G*} ⊂ *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
- One type
- Two
operation symbols
- a constant symbol
*e* of "identity";
- a binary operation • of "composition"

- Axioms
- Associativity : ∀
*x*,*y,z**, x* • (*y* • *z*)
= (*x* • *y*) • *z* so that either term can be more simply
written *x* • *y* • *z*.
- Identity : ∀
*x*, *x* • *e* = *x*
= *e* • *x*

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*,
*e* • *x* = *x*
- a
**right identity** of • is an element *e*' such that ∀*x*,
*x* • *e'* = *x*

If both a left identity and a right identity exist then they are
equal : *e* = *e* • *e*' = *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*,
*x*•*y*=*x*•*z* ⇒ *y*=*z*.

Similarly it is
right cancellative if *x*•*z*=*y*•*z* ⇒ *x*=*y*.

If a right identity *e* is left cancellative then it is the unique right identity :
*e* • *e*' = *e* = *e* • *e* ⇒ *e*' = *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- 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*)
*a*=*e'* ⇔
*e'*∈ *A* ⇔ *A* ∈ Sub_{{e, ▪}} *X*

but these equivalent formulas may still be false, unless *a* is cancellative on one side
(*a*▪*a* = *a* = *a*▪*e'* ⇒ *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