defect theorem

Let $A$ be an arbitrary set,let $A^{\ast }$ be the free monoid on $A$,and let $X$ be a finite subset of $A^{\ast }$ which is not a code.Then the free hull $H$ of $X$ is itself finiteand .

Observe how from the defect theoremfollows that the equation $x^m=y^n$ over $A^{\ast }$has only the trivial solutions where $x$ and $y$ are powers of the same word:in fact, $x^m=y^n$ iff $\{x,y\}$ is not a code.

Proof.It is sufficient to prove the thesis in the casewhen $X$ does not contain the empty word on $A$.

Define $f:X\to H$ such that $f(x)$ is the only $h\in H$such that $x\in h{H}^{\ast }$:$f$ is well defined because of the choice of $X$ and $H$.Since $X$ is finite, the thesis shall be establishedonce we prove that $f$ is surjective but not injective.

By hypothesis, $X$ is not a code.Then there exists an equation $x_1\mathrm{\cdots }{x}_n=x_1^{\prime }\mathrm{\cdots }{x}_m^{\prime }$ over $X$with a nontrivial solution:it is not restrictive to suppose that $x_1\ne x_1^{\prime }$.Since however the factorization over $H$ is unique,the $h$ such that $x_1\in h{H}^{\ast }$is the same as the $h^{\prime }$ such that $x_1^{\prime }\in h^{\prime }{H}^{\ast }$:then $f(x_1)=f(x_1^{\prime })$ with $x_1\ne x_1^{\prime }$,so $f$ is not injective.

Now suppose, for the sake of contradiction,that $h\in H\setminus f(X)$ exists.Let $K=(H\setminus \{h\})h^{\ast }$.Then any equation

$$k_1\mathrm{\cdots }{k}_n=k_1^{\prime }\mathrm{\cdots }{k}_m^{\prime },k_1,\mathrm{\cdots },k_n,k_1^{\prime },\mathrm{\dots },k_m^{\prime }\in K$$(1)

can be rewritten as

$$h_1{h}^{r_1}\mathrm{\cdots }{h}_n{h}^{r_n}=h_1^{\prime }{h}^{s_1}\mathrm{\cdots }{h}_m^{\prime }{h}^{s_m},h_1,\mathrm{\dots },h_n,h_1^{\prime },\mathrm{\dots },h_m^{\prime }\in H\setminus \{h\},$$

with $k_i=h_i{h}^{r_i}$, $k_i^{\prime }=h_i^{\prime }{h}^{s_i}$:this is an equation over $H$,and as such, has only the trivial solution $n=m$,$h_i=h_i^{\prime }$, $r_i=s_i$ for all $i$.This implies that (1) only has trivial solutions over $K$:by the characterization of free submonoids, $K$ is a code.However, $X\subseteq K^{\ast }$ because no element of $x$ “starts with $h$”,and $K^{\ast }$ is a proper subset of $H^{\ast }$because the former does not contain $h$ and the latter does.Then $K^{\ast }$ is a free submonoid of $A^{\ast }$which contains $X$ and is properly contained in $H^{\ast }$,against the definition of $H$ as the free hull of $X$.