4
$\begingroup$

In Nies's monograph "Computability and Randomness", there is an interesting remark about $\Pi_2^0$-singletons, where he gives an argument that such singletons can be non-arithmetic and he gives the following proof:

There is a computable $ g $ such that $ (X^{[n]})' = W^X_{g(n)}$ for each $ X$ and $ n $, so $X = \emptyset^{(\omega)} \iff X^{[n]} = \emptyset \; \& \; \forall n, X^{[n+1]} = (X^{[n]})' \iff \forall n \, \forall k, s \, \exists t \geq s \left[ k \in X \leftrightarrow k \in W^{X_t}_{g(n),t} \right]$.

After the above proof, he goes on to shade some philosophical insights on the matter in that such an argument is an illustration of local vs global view of sets. I will add the paragraph in question for clarity:

Recall the discussion of the local versus the global view of sets in Section 1.3. If $Y \in Σ^0_n$ , the description showing this embodies the local view. This is even more apparent at the lower levels $Σ^1_0$ and $Σ^0_2$ of the arithmetical hierarchy, where we still have a reasonable effective approximation of Y . On the contrary, a description of a set Z as a $Π^0_n$ singleton, such as the description of $∅^{(ω)}$ above, embodies the global view. The description only works because it involves the set as a whole.

Now I know that we can think of a $\Pi^0_2$ class as a countable intersection of $\Sigma^0_1$ classes, which might qualify I guess as a local view of such a class.

My question is what would be a natural way of thinking about a local view of such a complicated $\Pi^0_2$ class?(I know that using an argument similar to that of Nies's above we can show that they go even further into the hyperarithmetic). I guess a way to look at it is that I know the generic, I just don't know a natural forcing notion for it.

$\endgroup$
0

1 Answer 1

6
$\begingroup$

There are well-known examples of recursive subtrees $T$ of $\omega^{<\omega}$ which have infinite paths but no hyperarithmetic infinite paths. In other words, there are nonempty $\Pi^0_1$ subsets of $\omega^\omega$ (Baire space), namely $[T]$ the infinite paths in $T$, which have no hyperarithmetic elements. By relabelling $T$ if necessary, we may assume that every element of $[T]$ is an increasing function from $\omega$ to $\omega$.

At the cost of going from $\Pi^0_1$ on $\omega^\omega$ to $\Pi^0_2$ on $2^\omega$, we can transfer the above to Cantor space. Given an infinite set $x\subseteq\omega,$ let $p_x$ be the function that maps $n$ to the $n$th element of $x$, in the natural order of $\omega$. Then, consider the $\Pi^0_2$-set $$ S=\{x:p_x\in[T]\}. $$ Syntactically, $x\in S$ iff "$x$ is infinite and every initial segment of the natural enumeration of $x$ is in $T$," which is a $\Pi^0_2$-property of $x$. The only global property of $x$ mentioned here is that it has infinitely many elements.

Conversely, for any $\Pi^0_2$-property $P$ of elements of $2^\omega$, there is a recursive infinite branching tree $T$ such that the infinite paths in $T$ recursively correspond to the solutions to $P$. Namely, an infinite path in $T$ is a Skolem function for the initial segments of a subset of $\omega$ which satisfies $P$.

For binary branching trees $T,$ the compactness of $2^\omega,$ in the form of Konig's Lemma, implies that the statement "$[T]\neq\emptyset$" is a $\Pi^0_1$-property of $T$. However, the set of $\Pi^0_2$ formulas that have solutions in $2^\omega$ is $\Sigma^1_1$-complete.

For the special case in which $[T]\subseteq\omega^\omega$ is a singleton, its unique element must be hyperarithmetic and its hyperarithmetic rank is essentially the same as the supremum of the ordinal ranks in the well-founded part of $T$. By the above, the $\Pi^0_1$-singletons in Baire space correspond to $\Pi^0_2$-singletons in Cantor space. Then the set of $\Pi^0_2$ formulas that have unique solutions in $2^\omega$ should be $\Pi^1_1$-complete. (I say "should be" in place of "is," since I am not fully checking the details right now.)

It seems to me that going from Cantor to Baire gives as local a view as possible for $\Pi^0_2$-subsets of $2^\omega$.

$\endgroup$
3
  • $\begingroup$ This settles it. If you don't mind, do you have any references in mind? $\endgroup$ Commented Feb 6 at 7:55
  • 2
    $\begingroup$ You could look at Sacks's book on Higher Recursion Theory or Chong-Yu's Recursion Theory: Computational Aspects of Definability. $\endgroup$ Commented Feb 7 at 6:28
  • $\begingroup$ I see, thanks again. $\endgroup$ Commented Feb 7 at 7:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.