3
$\begingroup$

I'm fairly certain this question has a very simple answer, and that I've learned it before; I just can't seem to remember it.

Suppose I have a nonempty lightface Borel set $X\subseteq 2^\omega$. What is something we can say about how simple some member of $X$ must be?

For example, if $X$ is lightface $\Pi^0_1$, then by the low basis theorem $X$ has a low element, and if $X$ is lightface $\Sigma^0_1$, $X$ has a computable element by obviousness.

My recollection is that every nonempty lightface Borel subset of $2^\omega$ has a hyperarithmetic member, but I can't seem to prove this myself or find this result in Moschovakis' book, so I'm beginning to suspect I'm wrong.

(I'd also like to know - if my recollection is correct - when was this proved, and by whom?)

$\endgroup$
5
  • $\begingroup$ You can find Sack's book on Project Euclid. The theorem I am referring to is III.1.1. The theorem is stated for $\omega^\omega$ not $2^\omega$, although I don't see why the proof does not hold just as well. The essence is that $X \in HYP$ is $\Sigma_1^1$. The put it into normal form $(\exists Y)(\forall n)R(X \upharpoonright n, Y \upharpoonright n)$, where $R$ is computable. Then $(\forall n)R(X \upharpoonright n, Y \upharpoonright n)$ should be the desired $\Pi_1^0$ formula in $2^\omega$. However as you mentioned this contradicts the Low Basis Theorem since every low element ... $\endgroup$
    – William
    Jan 12, 2013 at 22:04
  • $\begingroup$ ... is hyperarithmetic. Perhaps something subtle is happening such that when you restrict to $2^\omega$ the formula is no longer $\Pi_1^0$ but pushed up a few arithmetical quantifiers. (which still gives a borel class with no hyperarithmetic member) I will think about this some more. Let me know if you figure out where the distinction between $\omega^\omega$ and $2^\omega$ is used in this proof. I find this very disturbing. $\endgroup$
    – William
    Jan 12, 2013 at 22:08
  • $\begingroup$ @William: it takes work to code $\omega^\omega$ into $2^\omega$. As an easier example, consider the $\Pi^0_1$ subset of $\omega^\omega$ given by $P(f) = (\forall x)(\forall s)[T(x,x,s) \to T(x,x,f(x))]$ which says $f(x)$ bounds the running time of $\phi_x(x)$ whenever the latter halts. There is no low element of this $\Pi^0_1$ class, the low basis theorem notwithstanding. To get an analogue of $P$ for $2^\omega$ we have to treat an element $A$ of $2^\omega$ (a subset of ω) as a code for a function in $\omega^\omega$, which requires a $\Pi^0_2$ clause saying $A$ codes a total function. $\endgroup$ Jan 12, 2013 at 22:57
  • $\begingroup$ @William: the example you pointed out does answer the question. Let $P$ be a property of an element of $\omega^\omega$ which is $\Pi^0_1$ and has no hyperarithmetical member. Let $Q$ be a property of an element $A$ of $2^\omega$ which says "$A$ codes a total function $f_A\colon\omega\to\omega$ and $P(f_A)$". Then $Q$ will be arithmetical, hence lightface Borel. If there was a hyperarithmetical set $B$ in $Q$ then the function $f_B$ would also be hyperarithmetical, which is impossible. I'd rather let you edit your (deleted) answer, since you had the main point, rather than writing one myself. $\endgroup$ Jan 12, 2013 at 23:12
  • $\begingroup$ @CarlMummert Thanks. $\endgroup$
    – William
    Jan 12, 2013 at 23:16

1 Answer 1

2
$\begingroup$

Does every nonempty lightface Borel subset of $2^\omega$ have a hyperarithmetic member?

There is an arithmetical subset of $2^\omega$ with no hyperarithmetical member.

It is known that there is a $\Pi^0_1$ class $P$ in $\omega^\omega$ which has no hyperarithmetical member (Theorem III.1.1, Sacks, Higher Recursion Theory).

Let $Q$ be subclass of $2^\omega$ such that $A \in Q$ if and only if $A$ is the graph of a total function $f_A\colon\omega\to\omega$, under some canonical effective pairing operation, and $f_A \in P$. It is straightforward to check that $Q$ is arithmetical, using only the fact that $P$ is arithmetical. If there was a hyperarithmetical set $B$ in $Q$ then the function $f_B$ would also be hyperarithmetical, which is impossible.

The key point here is that $\omega^\omega$ is recursively isomorphic (and homeomorphic) to a $\Pi^0_2$ subclass of $2^\omega$. We can use either the class of graphs of total functions, as above, or the class of infinite subsets of $\omega$. Thus most descriptive set theory results for $\omega^\omega$ transfer to $2^\omega$ as soon as we are willing to accept $\Pi^0_2$ quantification, for example if we are looking at arithmetical or Borel classes. If we limit ourselves to $\Pi^0_1$ classes in $2^\omega$ we get stronger results than can be obtained for $\omega^\omega$, because nonempty $\Pi^0_1$ subsets of $2^\omega$ are compact.

$\endgroup$
5
  • $\begingroup$ Awesome! A couple quick follow-up questions. First, the following result in Sacks (and this is the thing I think I was incorrectly remembering) is that every nonempty Borel set has a member computable in the hyperjump of its Borel index; I seem to recall that closure under the hyperjump was equivalent (in the context of $\omega$-models) to $\Pi^1_1-CA$, but I can't seem to prove this without the additional assumption that the model is a $\beta$-model, i.e., only thinks actual well-orders are well-orders. Is my memory correct here? (Slides by Jesse Johnson claim this as well, but don't (cont'd) $\endgroup$ Jan 13, 2013 at 22:20
  • $\begingroup$ contain a citation or proof sketch.) My second question is: is there anything nice we can say about members of lightface Borel sets of various rank? E.g., is there a natural class of sets which form a basis for the lightface $\Sigma^0_3$ sets but not the lightface $\Sigma^0_3$ sets? There's a huge gap between "hyperarithmetic" and "recursive in Kleene's $\mathcal{O}$," but I don't know anything about this area. $\endgroup$ Jan 13, 2013 at 22:25
  • $\begingroup$ (One of those "3"s should be a "4".) $\endgroup$ Jan 13, 2013 at 22:40
  • $\begingroup$ @user28111: $\Pi^1_1\text{-}CA_0$ is proof-theoretically equivalent to $RCA_0$ plus the axiom that every set has a hyperjump. It's an exercise in section VII.1 of Simpson's book, but the main tool is there, which is that a formalized version of the Kleene basis theorem (the one you mentioned) is provable in $ACA_0$ when the necessary hyperjumps exist. On the other hand, Theorem VII.1.8 states that an $\omega$ model of $RCA_0$ is closed under hyperjump if and only if it is a $\beta$ model and satisfies $\Pi^1_1$ comprehension. $\endgroup$ Jan 14, 2013 at 1:58
  • $\begingroup$ For the second question, I don't have any idea. You may need to ask a descriptive set theorist. $\endgroup$ Jan 14, 2013 at 1:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .