show that in every infinite computably enumerable set, there exists an infinite decidable set

Question

I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set.

As an attempt to solve the problem, I could only think of a proof by construction. Without loss of generality, let the alphabet be $\Sigma=\{0,1\}$. The construction goes as follows, suppose that $TM$ $M$ recognizes an infinite computably enumerable set $L$, we can form a decidable language $D \subseteq L$ as follows:

1) lexicographically enumerate all input words $w$ in $\Sigma^*$ and repeatedly perform steps $a-b:$

a) at the $k$th step, run $M$ on input words $\{w_0,w_1,...,w_k\}$ for $k$ steps, where words $\{w_0,w_1,...,w_k\}$ are lexicographically ordered

b) if $M$ accepts an input word $w \in \{w_0,w_1,...,w_k\}$ from step 2, include $w$ in a temporary language $D_{temp}$

2) partition the words in $D_{temp}$ into two, those starting with $0$ are $\in D$, while those starting with $1$ are $\not \in D$, along with all other words $\Sigma^* - D_{temp}$.

Step (1) does not loop in a word $w$ since each run of step (1) is limited for a finite number of $k$ steps. Is this construction okay ? Or did I miss something ...

Answer 1

Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$.

Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this contradicts the infinitude of $L$.

Furthermore, $D$ is decidable. Given a word $w$, run the enumerator for $L$, and halt whenever one of the following events happen:

• If $w_i = w$, output Yes.
• If $|w_i| > |w|$, output No.

Since $L$ is infinite, this algorithm will eventually stop.

Answer 2

Enumerate the c.e. set, keep only entries that appear in increasing lexocographic order. As the c.e. set is infinite, there will be new elements larger than the last kept one (thus the subset is infinite). To decide the subset, enumerate until hitting the element or a larger one.