Semigroups

Definition

x(yz) = (xy)z

Examples

• Any monoid (including any group)
• Some semigroups that aren't monoids (contributed by Alar Leibak = aleibak@ioc.ee):
  • non-invertible n x n matrices over a commutative ring, under matrix multiplication
  • this finite example:

                        * | 1 2 3 4 5
                        -------------
                        1 | 1 2 3 4 5
                        2 | 1 2 3 4 5
                        3 | 1 2 3 4 5
                        4 | 1 2 3 4 5
                        5 | 1 2 3 4 5
                      

Structure

Representation

Any semigroup is isomorphic to a semigroup of mappings on some set, under the operation of composition.

Decision problems

Identity problem:Solvable (associativity alone is complete)

Word problem:Unsolvable [Markov]. The following presentation has unsolvable word problem [Tsaitin1957]:

          a,b,c,d,e; ac=ca, bc=cb, ad=da, bd=db, ce=eca, de=edb, cca=ccae.
        

Spectra and growth

Finite spectrum:

Free spectrum:

Growth series:

History/Importance

References

Subsystems