defect theorem
Let be an arbitrary set, let be the free monoid on , and let be a finite subset of which is not a code. Then the free hull of is itself finite and .
Observe how from the defect theorem follows that the equation over has only the trivial solutions where and are powers of the same word: in fact, iff is not a code.
Proof.
It is sufficient to prove the thesis in the case
when does not contain the empty word on .
Define such that is the only
such that :
is well defined because of the choice of and .
Since is finite, the thesis shall be established
once we prove that is surjective but not injective
.
By hypothesis, is not a code.
Then there exists an equation over
with a nontrivial solution:
it is not restrictive to suppose that .
Since however the factorization over is unique,
the such that
is the same as the such that :
then with ,
so is not injective.
Now suppose, for the sake of contradiction,
that exists.
Let .
Then any equation
(1) |
can be rewritten as
with , :
this is an equation over ,
and as such, has only the trivial solution ,
, for all .
This implies that (1) only has trivial solutions over :
by the characterization of free submonoids, is a code.
However, because no element of “starts with ”,
and is a proper subset of
because the former does not contain and the latter does.
Then is a free submonoid of
which contains and is properly contained in ,
against the definition of as the free hull of .
References
- 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
Title | defect theorem |
---|---|
Canonical name | DefectTheorem |
Date of creation | 2013-03-22 18:21:43 |
Last modified on | 2013-03-22 18:21:43 |
Owner | Ziosilvio (18733) |
Last modified by | Ziosilvio (18733) |
Numerical id | 6 |
Author | Ziosilvio (18733) |
Entry type | Theorem![]() |
Classification | msc 20M10 |
Classification | msc 20M05 |
Defines | has only trivial solutions over |