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

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

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.

StackExchange Computer Science Q#121633, answer score: 8