A recent exam question went as follows:
- $A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset.
- Let $C$ be an infinite recursive subset of $A$. Must $C$ have a subset that is not recursively enumerable?
I answered 1. already. Regarding 2., I answered affirmatively and argued as follows.
Suppose that all the subsets of $C$ were recursively enumerable. Since $C$ is infinite, the power set of $C$ is uncountable, so by assumption there would be uncountably many recursively enumerable sets. But the recursively enumerable sets are in one-to-one correspondence with the Turing machines that recognize them, and Turing machines are enumerable. Contradiction. So $C$ must have a subset that is not recursively enumerable.
Is this correct?