1
$\begingroup$

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.

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

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$.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.