2026/07/09

A Note on Profinite Word

${}\newcommand\set[1]{\{#1\}}$

Fix a finite alphabet $\Sigma$. A free monoid on it is $\Sigma^{*}$. Call a language $L \subseteq \Sigma^{*}$ regular, if there is a finite monoid $A$, a judge function $f: A \to \set{0, 1}$, and a homomorphism $h: \Sigma^{*} \to A$ such that $w \in L \iff f(h(w))=1$.

Consider a word sequence $w_1, w_2, \dots$. We say it's convergent, if for every finite monoid $A$ and homomorphism $h: \Sigma^{*} \to A$, the sequence $h(w_1), h(w_2), \dots$ converges. Also, we can define two sequences to be equivalent if for every finite monoid $A$ and homomorphism $h: \Sigma^{*} \to A$, the sequence $h(w_1), h(w_2), \dots$ converges to the same element in $A$.

The equivalent class of such Cauchy sequence is the space of profinite words $\hat \Sigma$. And there is an evaluating function $ev : \forall A, \hat \Sigma \to \textbf{Mon}(\Sigma^{*}, A) \to A$, where $\textbf{Mon}(\Sigma^{*})$ is the set of homomorphism from $\Sigma^{*}$ to $A$.

More over, this evaluating function is consistent, which means if $h_1, h_2 \in \textbf{Mon}(\Sigma^{*}, A)$ such that $h_1 = \varphi \circ h_2$, then $\forall \hat{w} \in \hat \Sigma, ev(\hat w, h_1) = \varphi(ev(\hat w, h_2))$.

Apparently, any profinite word $\hat w$ gives an evaluating function $ev(\hat w) : \textbf{Mon}(\Sigma^{*}, A) \to A$. But we seek the converse: Giving an evaluating function $\Phi: \textbf{Mon}(\Sigma^{*}, A) \to A$, is there a profinite word $\hat w$ such that $\Phi = ev(\hat w)$? No surprisingly the answer is yes.

Note that $\textbf{Mon}(\Sigma^{*}, A)$ is countable, so let them be $\phi_1, \phi_2, \dots$ with $\phi_i \in \textbf{Mon}(\Sigma^*, M_i)$. It suffices to construct for every $n\in\mathbb Z^+$ a word $w_n$, such that $\Phi(\phi_i) = \phi_i(w_n)$.

Note that we have a product monoid $\Pi = M_1 \times \dots \times M_n$ along with a product homomorphism $\varphi = \phi_1 \times \dots \times \phi_n$. And $\varphi$ should also be consistent with $\phi_i$, which means $\Phi(\varphi) = (\Phi(\phi_1), \dots, \Phi(\phi_n))$. We want to show that $\Phi(\varphi) \in \varphi(\Sigma^*)$.

Note also that $\varphi(\Sigma^*)$ itself is a finite (sub)monoid, with inclusion morphism $j : \varphi(\Sigma^*) \to \Pi$ and limited morphism $\hat \varphi: \Sigma^* \to \varphi(\Sigma^*)$, such that $\varphi = j \circ \hat \varphi$. Therefore, by the consistency of $\Phi$, we have $\Phi(\varphi) = j(\Phi(\hat \varphi)) \in \varphi(\Sigma^*)$. QED.