−Table of Contents
Monoids
Abbreviation: Mon
Definition
A \emph{monoid} is a structure M=⟨M,⋅,e⟩, where ⋅ is an infix binary operation, called the \emph{monoid product}, and e is a constant (nullary operation), called the \emph{identity element} , such that
⋅ is associative: (x⋅y)⋅z=x⋅(y⋅z)
e is an identity for ⋅: e⋅x=x, x⋅e=x.
Morphisms
Let M and N be monoids. A morphism from M to N is a function h:MarrowN that is a homomorphism:
h(x⋅y)=h(x)⋅h(y), h(e)=e
Examples
Example 1: ⟨XX,∘,idX⟩, the collection of functions on a sets X, with composition, and identity map.
Example 1: ⟨M(V)n,⋅,In⟩, the collection of n×n matrices over a vector space V, with matrix multiplication and identity matrix.
Example 1: ⟨Σ∗,⋅,λ⟩, the collection of strings over a set Σ, with concatenation and the empty string. This is the free monoid generated by Σ.
Basic results
Properties
Classtype | Variety |
---|---|
Equational theory | decidable in polynomial time |
Quasiequational theory | undecidable |
First-order theory | undecidable |
Locally finite | no |
Residual size | unbounded |
Congruence distributive | no |
Congruence modular | no |
Congruence n-permutable | no |
Congruence regular | no |
Congruence uniform | no |
Congruence extension property | |
Definable principal congruences | |
Equationally def. pr. cong. | no |
Amalgamation property | no |
Strong amalgamation property | no |
Epimorphisms are surjective | no |
Finite members
f(1)=1f(2)=2f(3)=7f(4)=35f(5)=228f(6)=2237f(7)=31559