# Decidability of a set containing first symbols of elements of a decidable set

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.

• @Raphael, sorry about poor formatting and thanks for your constructive feedback. I tried to improve my question. Let me know, if I can improve more. In fact, this question has been asked to me by a friend of mine. I couldn't help him, that's why I tried to find some help here. I hope my added thoughts might help to notice where did I stuck. Thank you. – shcolf Jul 15 '18 at 21:00

You probably have to twist your head a couple of times but $B$ is decidable and it does not depend on the decidability of $A$. Note that $B \subseteq \Sigma$, i.e. a subset of your finite alphabet. Thus, $B$ is finite and hence, it is decidable.
However, this reasoning is not constructive: It is just enumerating all functions $\Sigma \to \{0, 1\}$ (that are $2^{|\Sigma|}$, i.e. finitely many), which are all computable, and one of them is the correct function although you do not know which one.