# Limit of set of finite words stable with prefix

Let $S$ be a set of finite words over a finite alphabet which contains at least two letters. Suppose that $S$ contains at least one word of length $n$ for all $n$ and that $a=a_0...a_k\in S \Rightarrow a_0...a_l\in S$ for all $0<l<k$. I think that then there is an infinite word $b=b_0b_1...$ such that for all $n$, $b_0...b_n\in S$. But I don't know how to prove this.

I appreciate any help.

• This is a consequence of König's lemma: Every infinite finitely branching tree has an infinite path. – J.-E. Pin Apr 29 '18 at 4:54
• @J.-E.Pin Effectivement! Merci! – Jiu Apr 29 '18 at 5:05

Let $S_n$ be all the words of length $n$ and define the map $$\rho_{n,m} :S_m \rightarrow S_n, ~ a_0 ... a_m \mapsto a_0 ... a_n$$ for all $n \leq m$. We note that $$S_1 \supset \rho_{1,2}(S_2) \supset \rho_{1,3}(S_3) \supset ...$$ and so as $S_1$ is finite (since our alphabet is) then there exists $k \in \mathbb{N}$ such that $\rho_{1,j}(S_j) = \rho_{1,k}(S_k)$ for all $j \geq k$. As $\rho_{1,k}(S_k) \neq \emptyset$ then we may choose $x_1 \in \rho_{1,k}(S_k)$.

We now note that $$S_2 \supset \rho_{1,2}^{-1}(\{x(1)\}) \supset \rho_{2,3} \left(\rho_{1,3}^{-1}(\{x(1)\}) \right) \supset \rho_{2,4} \left(\rho_{1,4}^{-1}(\{x(1)\}) \right) \supset ...$$ and as $x(1)$ is in the image of all $\rho_{1,j}$ then none of these sets are empty. As $|S_2|< \infty$ then none of the above sets are empty, thus we can find $x(2) \in S_2$ that lies in all of them.

We now repeat the above process with $x(2)$ to obtain $x(3) \in S_3$ ect. to define a sequence $(x(n))_{n \in \mathbb{N}}$ where $\rho_{n,m}(x(m))= x(n)$ for all $n \leq m$. We finally note that from this we may now define an infinite sequence $b_0 b_1 b_2 \ldots$ where $x(n) =b_0 b_1 \ldots b_n$.

From now on $n$ is fixed. Define $S_n$ as the set of all words of length $n$ in $S$.

Define $S_n^N$ as the set of all words $w\in S_n$ such that the largest word $W\in S$ that starts with $w$ (as a prefix) has length $l(W)=N$.

It is clear that the $S_n^N$ are disjoint. Therefore, since there are finitely many words of length $n$, there must be finitely many values of $N$ such that $S_n^N\neq \emptyset$, say $N_1, \ldots, N_k$ ($k$ depends on $n$). Now the point is that they do not cover $S_n$.

Indeed, pick any word in $S$ whose length is larger than $\max\{N_i\}$, and consider its size-$n$ prefix. This prefix lies in $S_n$ but in none of the $S_n^N$. Therefore, $$S_n^\infty=S_n\setminus \bigcup_{i=1}^k S_n^{N_i}$$ is not empty.

Finally, note that any element $w\in S_n^\infty$ can be extended into an element of $S_{n+1}^\infty$. Indeed, if the only ways to add a letter to $w$ implied to leave $S$ or land in one of the $S_{n+1}^N$, this would contradict the fact that there are infinitely many words in $S$ that have $w$ as a prefix.

Therefore there is in infinite word with the required properties (although to actually build it with this method you need God-like powers).