free semigroup
Let be a set. We define the power of in a language-theoretical manner as
for all , and
where . Note that the set is not necessarily an alphabet, that is, it may be infinite; for example, we may choose .
We define the sets and as
and
The elements of are called words on , and is called the empty word on .
We define the juxtaposition of two words as
where and , with for each and . It is easy to see that the juxtaposition is associative, so if we equip and with it we obtain respectively a semigroup and a monoid. Moreover, is the free semigroup on and is the free monoid on , in the sense that they solve the following universal mapping problem: given a semigroup (resp. a monoid ) and a map (resp. ), a semigroup homomorphism (resp. a monoid homomorphism ) exists such that the following diagram commutes:
(resp.
), where (resp. ) is the inclusion map. It is well known from universal algebra that and are unique up to isomorphism.
References
- 1 J.M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, Oxford, 1991.
Title | free semigroup |
Canonical name | FreeSemigroup |
Date of creation | 2013-03-22 16:11:41 |
Last modified on | 2013-03-22 16:11:41 |
Owner | yark (2760) |
Last modified by | yark (2760) |
Numerical id | 15 |
Author | yark (2760) |
Entry type | Definition |
Classification | msc 20M10 |
Classification | msc 20M05 |
Related topic | Word |
Defines | word |
Defines | empty word |
Defines | free semigroup |
Defines | free monoid |