Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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?)

share|improve this question
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 ... – William Jan 12 at 22:04
... 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. – William Jan 12 at 22:08
@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. – Carl Mummert Jan 12 at 22:57
@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. – Carl Mummert Jan 12 at 23:12
@CarlMummert Thanks. – William Jan 12 at 23:16

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
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) – user28111 Jan 13 at 22:20
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. – user28111 Jan 13 at 22:25
(One of those "3"s should be a "4".) – user28111 Jan 13 at 22:40
@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. – Carl Mummert Jan 14 at 1:58
For the second question, I don't have any idea. You may need to ask a descriptive set theorist. – Carl Mummert Jan 14 at 1:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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