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

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

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.