# Show that every infinite recursive set has both a nonrecursive r.e. subset and a non-r.e. subset

My attempt to solve this:

If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and $\mathcal{A}$.

Halting problem is $\mathcal{K}\subseteq\mathcal{N}$ and therefore it's also $\mathcal{K}\subseteq\mathcal{A}$. And the same can be said about $\bar{\mathcal{K}}$.

Is my solution correct? Are there any "better" solutions to this problem?

• why does it follow that $K \subset A$?? Indeed, you can find a bijection, but it may not be a subset. Commented Jan 18, 2015 at 16:15
• If I order the members of $\mathcal{A}$ and enumerate them such that lowest possible member of $\mathcal{A}$ is 0, next one is 1, next one is 2, etc. I have - because the $\mathcal{A}$ is infinite - a set of natural numbers. Let the bijecting function is $f$. So if $\mathcal{K}\subseteq\mathcal{N}$ then I use the $f$ to get the number in $\mathcal{A}$. Commented Jan 18, 2015 at 16:37
• You're claiming that $\mathcal{K}\subseteq \mathcal{A}$ and also $\overline{\mathcal{K}}\subseteq \mathcal{A}$. That cannot be true unless $\mathcal{A}=\mathcal{N}$. Commented Jan 18, 2015 at 18:08
• @DavidRicherby I am claiming that $\mathcal{A}$ has as many elements as $\mathcal{N}$. Commented Jan 18, 2015 at 20:00
• @Gordon That's not what you wrote. The sentence beginning "Halting problem is" means what I said it means. Commented Jan 18, 2015 at 20:50