Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite

Question

Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:

Simulate the decider of $L$ on the input, if it accepts, go over $L \setminus S$ and check if it is there, if it is, reject. If it isn't accept. If the decider of $L$ rejects - reject.

Another point is if $S \subset L$ is finite then $S$ also must be decidable, this is immediate that every finite language is decidable.

Now we have the last case where $S$ is infinite and $L \setminus S$ is infinite. We know that there must be some subsets $S$ corresponding to this case that are undecidable. This is since there are $\aleph$ such $S$ but only $\aleph_0$ deciders. Denote $D(L) = \{ S \subset L : |S|= |L \setminus S|=\infty \wedge S \text{ is decidable} \}$

Is it true that for all infinite decidable languages $L$ we have $D(L) \neq \phi$?

If this is true then as a conclusion we will have for all infinite decidable languages $L$ a sequence of decidable languages $L_n$ such that $L_0=L$ and $L_{n+1} \subset L_n$ and $|L_n \setminus L_{n+1}| = \infty$

We will also have a limit-set $L_\infty = \{ e \in L : \forall n \in \mathbb{N} \text{ } e \in L_n \}$ and can dicuss if it is empty/finite/infinite and decicable or not.

This seems like a nice way to study decidable languages, and curious to know if this direction is indeed interesting and whether there are articles published regarding these questions

Thanks for any help

Answer 1

If $L$ has a finite alphabet, then $L$ is recursively enumerable.

Then, from such an enumeration $w_0,w_1,w_2,...$ of the words of $L$ you can take $S=\{w_0,w_2,w_4,...\}$, which will also be decidable. To check if a word $w$ is in $S$ check if it is in $L$. If it is then use the enumeration of $L$ to check if its position is even or not.