The question is exactly that in the title: Does every infinite $\Sigma^1_1$ set of natural numbers have an infinite $\Delta^1_1$ subset?

Some background: The lower-level analog of this question, Does every infinite c.e. set have an infinite computable subset?, is easily seen to be true. However, this is in some sense the wrong analog of the question I want to ask. The correct intuition in higher recursion theory tends to be that $\Delta^1_1$ corresponds to finite, as opposed to computable, and that the correct analog of "c.e." is $\Pi^1_1$ rather than $\Sigma^1_1$. This makes me guess that the answer to my question is "no," since the only reason I have for favoring "yes" is based on an incorrect analogy.

I also imagine that the answer (whether a counterexample or a proof) is fairly simple. This is why I have posted on MathSE as opposed to MathOF. I have looked at Sacks' book "Higher Recursion Theory" (which can be gotten freely at Project Euclid: http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.pl/1235422631), but I have not been able to find the answer there.

This question has no broad significance; I am just interested in understanding the analytic hierarchy better, and this seemed like a problem I ought to understand.

Thank you very much for your help!

  • $\begingroup$ Now when you say $\Sigma^1_1$ and $\Delta^1_1$ do you mean analytic and Borel (resp.)? Because every subset of a countable $T_1$ space is $F_\sigma$ (or $\Sigma^0_2$ in the Borel hierarchy). $\endgroup$ – Asaf Karagila Jul 21 '11 at 11:54
  • 1
    $\begingroup$ I'm using the lightface hierarchy - so, for example, there are only countably many $\Delta^1_1$ sets. $\endgroup$ – user13568 Jul 21 '11 at 14:48

I believe there exists an infinite $\Sigma_1^1$ set which has no infinite $\Delta_1^1$ subset.

In the $\omega$ computability case, this can be proved by constructing a simple set. Recall a simple set is a c.e. set whose complement is immune. A set is immune if it contains no infinite c.e. set. Thus the complement of a simple set is a $\Pi_1^0$ set which has no infinite computable (in fact c.e.) subset. Therefore, the idea is that the analogous of c.e. subsets (of $\omega$) in $\omega_1^{CK}$ admissible computability or metacomputability are the $\Pi_1^1$ subsets. Therefore, one should just show that the simple set construction works in this new setting.

The details are the following: By Proposition V 1.2 in Sacks, $A \subset \omega$ is metarecursively enumerable if and only if it is $A$ is $\Pi_1^1$. By exercise VII 1.12 $A$ is metarecursively enumerable if and only if $A$ is $\omega_1^{CK}$ recursively enumerable. For any $\alpha$ a admissible ordinal (for example $\omega_1^{CK}$), there exist a enumeration theorem, i.e Sacks VII 1.9. Thus there is a enumeration of all $\omega_1^{CK}$ r.e. subsets of $\omega_1^{CK}$. Since $\omega < \omega_1^{CK}$, $\omega \in L_{\omega_1^{CK}}$. Thus one can easily make an enumeration of all $\omega_1^{CK}$-c.e. subsets of $\omega$, i.e. the $\Pi_1^1$ subsets.

Now define a set to be $\Pi_1^1$-immune if it is infinite and contains no infinite $\omega_1^{CK}$ ($\Pi_1^1$) subset. A set is $\Pi_1^1$-simple if it is $\omega_1^{CK}$-c.e. and has immune complement. With an enumeration of all the $\Pi_1^1$ subsets of $\omega$, I think you can carry over the regular proof to prove there exists a $\Pi_1^1$-simple set. Its complement is then the desired $\Sigma_1^1$ set with no infinite $\Delta_1^1$ subset.

I hope this works. If you know a more elementary proof, please post it.


No. The set $\{x\mid \omega_1=\omega_1^{CK} \wedge x \not\in HYP\}$ does not contain a non empty $\Delta^1_1$ subset. But the proof is not trivial.

Hjorth and Nies has another nice example. They constructed a $\Sigma^1_1$ closed set in which every real is $\Pi^1_1$-Martin-Löf random. Then the set does not contain any nonempty $\Delta^1_1$ subset.


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.