characterization of free submonoids
Let be an arbitrary set,
let be the free monoid on ,
and let be the identity element (empty word
) of .
Let be a submonoid of
and let be its minimal
generating set
.
We recall the universal property of free monoids:
for every mapping with a monoid,
there exists a unique morphism
such that for every .
Theorem 1
The following are equivalent.
-
1.
is a free submonoid of .
- 2.
-
3.
For every , if exist such that , then .
Corollary 1
An intersection of free submonoids of
is a free submonoid of .
As a consequence of Theorem 1, there is no Nielsen-Schreier theorem for monoids. In fact, consider and : then , but has a nontrivial solution over , namely, .
We now prove Theorem 1.
Point 2 implies point 1.
Let be a bijection.
By the universal property of free monoids,
there exists a unique morphism that extends ;
such a morphism is clearly surjective.
Moreover, any equation
translates
into an equation of the form (1),
which by hypothesis
has only trivial solutions:
therefore , for all , and is injective
.
Point 3 implies point 2.
Suppose the existence of such that
implies is actually in .
Consider an equation of the form (1)
which is a counterexample to the thesis,
and such that the length of the compared words is minimal:
we may suppose is a prefix of ,
so that for some .
Put :
then and belong to by construction.
By hypothesis, this implies :
then equals a product with —which,
by definition of ,
is only possible if .
Then and :
since we had chosen a counterexample of minimal length,
.
Then the original equation has only trivial solutions,
and is not a counterexample after all.
Point 1 implies point 3.
Let be an isomorphism of monoids.
Then clearly ;
since removing from removes from ,
the equality holds.
Let and let satisfy :
put , ,
, .
Then , so :
this is an equality over ,
and is satisfied only by , for some .
Then .
References
- 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
Title | characterization of free submonoids |
---|---|
Canonical name | CharacterizationOfFreeSubmonoids |
Date of creation | 2013-03-22 18:21:32 |
Last modified on | 2013-03-22 18:21:32 |
Owner | Ziosilvio (18733) |
Last modified by | Ziosilvio (18733) |
Numerical id | 7 |
Author | Ziosilvio (18733) |
Entry type | Theorem |
Classification | msc 20M05 |
Classification | msc 20M10 |
Defines | intersection of free submonoids is free |