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

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

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.
### 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*•(*y*•*z*)
= (*x*•*y*)•*z* so that either term can be
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 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*,
*x*•*y* = *x*•*z* ⇒ *y* = *z*.

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

If a right identity *e* is left cancellative then it is the unique right identity :
*e*•*e'* = *e* = *e*•*e* ⇒ *e'* = *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 *A*⊂*E* for a binary operation • in *E*,
is defined as
*C*(*A*) = {*x*∈*E*|∀*y*∈*A*,
*x*•*y *= *y*•*x*}.

This is another Galois connection :
∀*A*,*B*⊂*E*, *B*⊂*C*(*A*) ⇔ *A*⊂*C*(*B*).
Such *A*,*B* are said to commute as each element of *A*
commutes with each element of *B*.

If • is associative then ∀*A*⊂*E*,
*C*(*A*) ∈ Sub_{•}*F*. (Proof: ∀*x,y*∈*C*(*A*), (∀*z*∈*A*, *x*•*y*•*z*
= *x*•*z*•*y* = *z*•*x*•*y*) ∴ *x*•*y*∈*C*(*A*))

Commutants in monoids are called *centralizers*. They are more precisely sub-monoids as
obviously *e*∈*C*(*A*).

This can be understood for transformation monoids *M*⊂*X*^{X} by the fact it
is an intersection of submonoids: ∀*A*⊂*M*,
*C*_{M}(*A*) = *M* ∩ End_{A} 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*,*y*∈*E*, *x*•*y*
= *y*•*x*.

If *A*⊂*C*(*A*) and 〈*A*〉_{•}=*E* then • is
commutative

Proof: *A*⊂*C*(*A*)∈ Sub_{•}*F*
⇒ *E*=*C*(*A*)
⇒ *A*⊂*C*(*E*) ∈ Sub_{•}*F* ⇒
*C*(*E*) = *E*.∎

In the case of monoids the conditions
*A*⊂*C*(*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'* ∈ *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'*).
**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*,*b*∈*M*, *f*(*a*•*b*) =
*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. Initial and final objects

3.9. Algebraic terms

3.10. Term algebras

3.11. Integers and recursion

3.12. Presburger Arithmetic

4. Model Theory