Let S be a subset of N (natural numbers), so it is infinite and countable. Let Ls={a^n | n belongs to S} a language. Is Ls recursive? Is Ls recursively enumerable? Justify your answers.
I'm pretty sure that Ls is recursive for any S, because we can write a program that decides Ls (or a Turing Machine for that matter). But how do I justify it?
We have $a^n\in L$ if and only if $n\in S$. Take the set $K=\{n\mid n\in{\rm dom}\,\phi_n\}$, where $(\phi_n)$ is the sequence of unary part. rec. functions. The set $K$ is undecidable. So if you take $K=S$, then $L$ is undecidable too. But $K$ re., not recursive since its complement is not re. Take $S=\overline K$. Then $L$ is not re.