characterization of free submonoids
An intersection of free submonoids of is a free submonoid of .
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 .
- 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
|Title||characterization of free submonoids|
|Date of creation||2013-03-22 18:21:32|
|Last modified on||2013-03-22 18:21:32|
|Last modified by||Ziosilvio (18733)|
|Defines||intersection of free submonoids is free|