1

Is there a computably enumerable set $A$ such that every infinite subset of $A$ is noncomputable?

I think that it's a set $K = \{n\ \ |\ \ U(n,n) \text{ is defined}\}$ (which is noncomputable, $U(n,x)$ is universal computable function). But I can't understand, how to prove, that an arbitrary infinite subset of $K$ is noncomputable. What to do?

L. Antz
  • 11
  • What do you mean by "insoluble"? Also, are you familiar with the theorem that every infinite r.e. set has an infinite computable subset? – Carl Mummert May 10 '16 at 19:25
  • Uh oh, I fixed it. No, i don't. – L. Antz May 10 '16 at 19:30
  • That theorem will solve the question at hand, so try proving it first. Also, you almost certainly want to ask about infinite c.e. sets, to avoid trivialities, e.g. the c.e. set ${0}$ has no computable infinite subsets. – Carl Mummert May 10 '16 at 19:31
  • 1
    The usual argument is this: Assume $A$ is infinite and c.e. Start enumerating it, but don't print all the outputs. Say the first output is $n_0$. Print it, but then don't print any other output unless it is larger than $n_0$. The first such output you see, print it and call it $n_1$. Then don't print any other outputs until you see one that is larger than $n_1$, etc. Do you see how to formalize this algorithm, and why ${n_0,n_1,\dots}$ is computable? – Andrés E. Caicedo May 10 '16 at 19:34
  • 1
    Oh, i see now. Let $A$ be c. e. We run the enumerator $A$, delete duplicated elements and make a function $a(n)=\text{the number at n-th printed position}$. Then, we build these ${n_0, n_1, ...}$ (as you said) using $a(n)$ in increasing order. Then, it's really easy to say why this set is computable (if number n is founded in sequence, n is in set, else isn't in set). Thanks! – L. Antz May 10 '16 at 19:47

0 Answers0