|
|
|
|
free semigroup
|
(Definition)
|
|
|
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.
- 1
- J.M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, Oxford, 1991.
|
"free semigroup" is owned by yark. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
| Also defines: |
word, empty word, free semigroup, free monoid |
|
|
Cross-references: isomorphism, universal algebra, inclusion map, monoid homomorphism, semigroup homomorphism, map, mapping, universal, monoid, semigroup, associative, easy to see, juxtaposition, infinite, alphabet, power
There are 20 references to this entry.
This is version 12 of free semigroup, born on 2006-08-24, modified 2007-06-10.
Object id is 8287, canonical name is FreeSemigroup.
Accessed 4118 times total.
Classification:
| AMS MSC: | 20M10 (Group theory and generalizations :: Semigroups :: General structure theory) | | | 20M05 (Group theory and generalizations :: Semigroups :: Free semigroups, generators and relations, word problems) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ & X \ar[r]^{\iota} \ar[d]_{\Phi} & X^+ \ar[dl]^{\overline{\Phi}} \ & S & } } \end{xy}\end{displaymath}](http://images.planetmath.org:8080/cache/objects/8287/l2h/img36.png "\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ & X \ar[r]^{\iota} \ar[d]_{\Phi} & X^+ \ar[dl]^{\overline{\Phi}} \ & S & } } \end{xy}\end{displaymath}")
![\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ & X \ar[r]^{\iota} \ar[d]_{\Phi} & X^* \ar[dl]^{\overline{\Phi}} \ & M & } } \end{xy}\end{displaymath}](http://images.planetmath.org:8080/cache/objects/8287/l2h/img37.png "\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ & X \ar[r]^{\iota} \ar[d]_{\Phi} & X^* \ar[dl]^{\overline{\Phi}} \ & M & } } \end{xy}\end{displaymath}")