11
$\begingroup$

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?

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Carl Mummert May 11 '12 at 11:15
  • $\begingroup$ @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. $\endgroup$ – user1435 May 11 '12 at 16:29
  • 1
    $\begingroup$ !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. $\endgroup$ – Carl Mummert May 11 '12 at 16:36
  • $\begingroup$ 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. $\endgroup$ – user1435 May 11 '12 at 16:51
  • $\begingroup$ 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. $\endgroup$ – Kaveh May 12 '12 at 5:05
11
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – user1435 May 11 '12 at 7:17
  • $\begingroup$ Yes. The term "undecidable" is a bit overloaded (Wikipedia has a good discussion). So this answer probably means what you are trying to prove. $\endgroup$ – David Lewis May 11 '12 at 11:59
  • $\begingroup$ @user1435, yes, the same argument works for any countable class of languages, I updated the question to make it clear. $\endgroup$ – Kaveh May 12 '12 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.