Let's say we have an alphabet $\Sigma = \{a,b, \dots , z\}$
Set $A$ consists of words $x_i$ containing symbols from $\Sigma$ alphabet, which have this structure
$x_i := \alpha_i \beta_i$, where $\alpha_i$ is just 1 symbol from $\Sigma$ and $\beta_i \in \Sigma^{*}$ (can also be empty)
So the set A should look like this $A = \{ \alpha_1 \beta_1, \alpha_2 \beta_2, \dots , \alpha_n \beta_n, \dots\}$
The question is:
If the set $A$ is decidable, then should also the set $B = \{ \alpha_1, \alpha_2, \dots , \alpha_n, \dots\}$ be decidable?
My thoughts..
For the set $A$, we have a total computable function $f(x_i)$ which gives an answer, whether a given input element contains in $A$ or not. Now, when we shrink $x_i$-s and only leave $\alpha_i$ parts, we cannot use $f$ anymore. The only idea which came to my mind, is using this naive algorithm.
get input $\alpha_j$
for each $x_i \in A$
if $\alpha_j$ is prefix of $x_i$
return YES
return NO
And here, I guess, the problem is in for each
statement. Here we enumerate all elements of the set $A$. For being able to do this, I guess we need to use some kind of mapping $\phi : \mathbb{N} \to \Sigma^{*}$ and then apply $f$ on the output to get all possible $x_i$-s. This algorithm may give a correct answer, but it also may give no answer (we will never reach to return NO
). So my conclusion was B is not decidable (B is semi-decidable). But there might also be a 'better' algorithm?
..end of my thoughts.
I apologize if my thoughts are 100% wrong. That's how far I could reach.
Any help is much appreciated.