Profinite word

Let M and N be monoids, and let p and q be elements of the monoid M. Let φ be a morphism of monoids from M to N. It is said that the morphism φ separates p and q if ${\displaystyle \phi (p)\neq \phi (q)}$. For example, the morphism ${\displaystyle \phi :A^{*}\to \mathbb {Z} /2\mathbb {Z} ,w\mapsto |w|(\operatorname {mod} 2)}$ sending a word to the parity of its length separates the words ababa and abaa. Indeed ${\displaystyle \phi (ababa)=1\neq 0=\phi (abaa)}$.

It is said that N separates p and q if there exists a morphism of monoids φ from M to N that separates p and q. Using the previous example, ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ separates ababa and abaa. More generally, ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ separates any words whose size are not congruent modulo n. In general, any two distinct words can be separated, using the monoid whose elements are the factors of p plus a fresh element 0. The morphism sends prefixes of p to themselves and everything else to 0.

The distance between two distinct words p and q is defined as the inverse of the size of the smallest monoid N separating p and q. Thus, the distance of ababa and abaa is ${\displaystyle {\frac {1}{2}}}$. The distance of p to itself is defined as 0.

This distance d is an ultrametric, that is, ${\displaystyle d(x,z)\leq \max \left\{d(x,y),d(y,z)\right\}}$. Furthermore it satisfies ${\displaystyle d(uw,vw)\leq d(u,v)}$ and ${\displaystyle d(wu,wv)\leq d(u,v)}$. Since any word p can be separated from any other word using a monoid with |p|+1 elements, where |p| is the length of p, it follows that the distance between p and any other word is at least ${\displaystyle {\frac {1}{|p|}}}$. Thus the topology defined by this metric is discrete.

The profinite completion of ${\displaystyle A^{*}}$, denoted ${\displaystyle {\widehat {A^{*}}}}$, is the completion of the set of finite words under the distance defined above. The completion preserves the monoid structure.

The topology on ${\displaystyle {\widehat {A^{*}}}}$ is compact.

Any monoid morphism ${\displaystyle \phi :A^{*}\to M}$, with M finite can be extended uniquely into a monoid morphism ${\displaystyle {\widehat {\phi }}:{\widehat {A^{*}}}\to M}$, and this morphism is uniformly continuous (using any metric on ${\displaystyle M}$ compatible with the discrete topology). Furthermore, ${\displaystyle {\widehat {A^{*}}}}$ is the least topological space with this property.

A profinite word is an element of ${\displaystyle {\widehat {A^{*}}}}$. And a profinite language is a set of profinite words. Every finite word is a profinite word. A few examples of profinite words that are not finite are now given.

For m any word, let ${\displaystyle m^{\omega }}$ denote ${\displaystyle \lim _{i\to \infty }m^{i!}}$, which exists because ${\displaystyle m^{i!}}$ is a Cauchy sequence. Intuitively, to separate ${\displaystyle m^{i!}}$ and ${\displaystyle m^{i'!}}$, a monoid should count at least up to ${\displaystyle \min(i,i')}$, and hence requires at least ${\displaystyle \min(i,i')}$ elements. Since ${\displaystyle m^{i!}}$ is a Cauchy sequence, ${\displaystyle m^{\omega }}$ is indeed a profinite word.

Furthermore, the word ${\displaystyle m^{\omega }}$ is idempotent. This is due to the fact that, for any morphism ${\displaystyle \phi :A^{*}\to N}$ with N finite, ${\displaystyle \phi (m^{i!})=\phi (m)^{i!}}$. Since N is finite, for i great enough, ${\displaystyle \phi (m)^{i!}}$ is idempotent, and the sequence is constant.

Similarly, ${\displaystyle m^{\omega +1}}$ and ${\displaystyle m^{\omega -1}}$ are defined as ${\displaystyle \lim _{n\to \infty }m^{n!+1}}$ and ${\displaystyle \lim _{n\to \infty }m^{n!-1}}$ respectively.