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 |