3
$\begingroup$

This question is about compact (but not necessarily effectively compact) $\Pi^0_1$-classes in Baire space. If I am given an index for a $\Pi^0_1$-class, and assured that it is compact, is determining whether the class is nonempty a $\Sigma^1_1$ question of maximal difficulty?

To be more precise, let $A$ be the set of indices of compact nonempty $\Pi^0_1$-classes, and let $B$ be the set of indices of empty $\Pi^0_1$-classes. Is $(\Sigma^1_1, \Pi^1_1) \le_1 (A, B)$?

Relatedly, does every compact nonempty $\Pi^0_1$-class have a hyperarithmetic path? These questions are morally negations of each other, in that a yes answer for one gives a no answer for the other, and a no answer for one very likely gives a yes answer for the other.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

I think that every compact $\Pi^0_1$-class has a hyperarithmetic infinite path.

Proof: Given a compact $\Pi^0_1$-class $P$. So there is a recursive tree $T\subseteq \omega^{<\omega}$ so that $[T]=P$. Since $P$ is compact, there is a function $f$ dominating all of the members of $P$. We will find a hyperaritmetic one.

We use Spector-Gandy's theorem to recursively work on $L_{\omega_1^{CK}}$.

For $n=0$, there is some number $m$ and stage $\alpha<\omega_1^{CK}$ so that for every $k\geq m$, $T_k=\{k\sigma\mid k\sigma\in T\}$ is well founded witnessed at stage $\alpha$. Find the first such stage $\alpha_0$ and corresponded number $m_0$. Let $f(0)=m_0$.

Generally for any $n+1$, there is some number $m$ and stage $\alpha<\omega_1^{CK}$ so that for every $k\geq m$, $T_{f(0)\cdots > f(n)k}=\{k_0\cdots k_n k\sigma \mid k_0\cdots k_n k\sigma\in T \wedge \forall i\leq n (k_i\leq f(i))\}$ is well founded witnessed at stage $\alpha$. Find the first such stage $\alpha_{n+1}$ and corresponded number $m_{n+1}$. Let $f(n+1)=m_{n+1}$.

So $f$ is a total $\Pi^1_1$ function and so hyperarithmetic. Thus $P$ must contains a hyperarithmetic member since every member of $P$ is dominated by $f$. QED

$\endgroup$
1
  • $\begingroup$ Very nice. Thank you. $\endgroup$ Commented Nov 12, 2019 at 9:40

You must log in to answer this question.

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