# subsets of infinite recursive sets

A recent exam question went as follows:

1. $A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset.
2. Let $C$ be an infinite recursive subset of $A$. Must $C$ have a subset that is not recursively enumerable?

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?

• It's not quite correct at the end, because each r.e. set is enumerated by infinitely many Turing machines, not just by one. You can work around this, though. May 11 '12 at 11:15
• @Carl: Ah, right, thanks -- silly mistake. But all I need is an injection into the TMs, not a bijection, right? And on the definition of Turing-computable my class worked with, each TM is associated with one and only one function. So different sets --> different recognition functions --> different TMs that compute them. May 11 '12 at 16:29
• !user1435: you are reversing things in the last sentence. Each Turing machine computes a single function, but each computable function is obtained from infinitely many Turing machines. May 11 '12 at 16:36
• But if my function f maps {recognition functions r} to {TMs} via f(r)=any one of the infinitely many TMs that compute it, I have an injection, right? Or I suppose I could just partition {TMs} by an equivalence relation ~ that identifies the infinity of TMs that compute the same function, and then map r to the appropriate equivalence class. May 11 '12 at 16:51
• Carl is right, they are not in one-to-one correspondence, each c.e. set corresponds to infinitely many TMs. Considering other sets of objects as you do in your comment doesn't change anything, they are not the set of TMs. May 12 '12 at 5:05

It is correct.

Every infinite set has an undecidable subset, you can use the cardinality argument: $\aleph_0\leq C \implies \aleph_0 < 2^C$. In fact most of its subsets are undecidable (and you can replace undecidable with any countable class of languages, e.g. c.e., arithmetical, analytical, ...).

The bad thing about this argument is that it doesn't give any information about how difficult the subset is. We usually want a subset which is as easy as possible. One way to get this is using a diagonalization similar to the cardinality argument using the fact that $C$ is decidable:

Define $D = \{ i \in C \mid i \notin W_i \}$, where $W_i$ is the $i$th c.e. set. Obviously $D \subseteq C$. Moreover $D$ can be solved with an oracle for $C$ and $K = \{ i \mid i\notin W_i\}$. So if $C$ is decidable then $D$ is a co-c.e. language.

• "Every infinite set has an undecidable subset." This is weaker than the claim I tried to prove. I tried to prove C must have a non-R.E. subset, not a non-decidable subset. Is my claim still correct? May 11 '12 at 7:17
• Yes. The term "undecidable" is a bit overloaded (Wikipedia has a good discussion). So this answer probably means what you are trying to prove. May 11 '12 at 11:59
• @user1435, yes, the same argument works for any countable class of languages, I updated the question to make it clear. May 12 '12 at 5:02
• Might not D be empty? I thought the point was to show that D is not c.e.
– Veky
Feb 4 '21 at 5:08