Hyperarithmetically least elements in $\Pi^1_1$ sets

Question

My question is: Do we have a hyperarithmetically $\le_H$-least real in any $\Pi^1_1$ set? That is

Question. Suppose that $A$ is a non-empty $\Pi^1_1$ set. Then can we find a real $a\in A$ such that $a\le_H b$ for all $b\in A$?

The motivation of the question is whether there is a uniform way to "pick up" a real (modulo some equivalence, like Turing equivalence) from a $\Pi^1_1$ set over a weaker subsystem of second-order arithmetic. I know that we can do this with the help of $\Pi^1_1$-uniformization, but it is not satisfactory for the following reasons: The proof for $\Pi^1_1$-uniformization gives a way to construct a $\Pi^1_1$-formula $\hat{\phi}(x)$ from $\phi(x)$ satisfying the following:

1. $\forall x [\hat{\phi}(x)\to\phi(x)]$.
2. $\forall x,y [\hat{\phi}(x)\land \hat{\phi}(y)\to x=y]$.
3. $\exists x \phi(x) \to \exists x \hat{\phi}(x)$.

Requiring the third part is equivalent to $\Pi^1_1$-comprehension over $\mathsf{ATR}_0$, and even proving the second condition (uniqueness of $x$ satisfying $\hat{\phi}(x)$) seems to require $\mathsf{ATR}_0$ since the proof of $\Pi^1_1$-uniformization uses norms and scales in some way, which requires comparison between ordinals.

Answer 1

I suppose by $a\leq_Hb$, you mean that $a$ is $\Delta^1_1(\{b\})$. And I suppose in the question, $A=X$. Under this interpretation, the answer is no; in fact, there is a $\Delta^1_1$ set $X$ for which the property fails.

Let $X$ be the set of all reals which are the (first order) theory $T$ of a countable structure $M$ for the language of set theory which has wellfounded $\omega$ and satisfies "$V=L$" + KP + "There is no ordinal $\alpha$ such that $L_\alpha$ models KP". Then $X$ is $\Delta^1_1$ and non-empty, so it suffices to see that there is no $T_0\in X$ which is $\Delta^1_1$-minimal for $X$. So suppose otherwise, and fix such a $T_0$. Note that if $T\in X$ then there is a unique-up-to-isomorphism pointwise definable model $M$ of $T$. Let $M_0$ be some pointwise definable model of $T_0$, with transitive $\omega+1$.

Let $Y$ be the set of all $T\in X$ such that, letting $M$ be as above for $T$, there is also a model $N$ which models "$V=L$" + KP and there is $\alpha\in\mathrm{Ord}^N$ such that $M\cong L_\alpha^N$.

Claim: For each $T\in Y$, letting $M$ be a pointwise definable model of $T$ with transitive $\omega+1$, we have $\mathbb{R}\cap M\subseteq \mathbb{R}\cap M_0$.

Proof of Claim: Let $T\in Y$, as witnessed by $T,M,N,\alpha$. Since $Y\subseteq X$, we have $T_0\in\Delta^1_1(\{T\})$, and we have $T=\mathrm{Th}^M(\emptyset)$, so $T\in N$, and because $N$ models KP and has wellfounded $\omega$, it easily follows that $T_0\in N$. Let $M_0'\in N$ be a pointwise definable model of $T_0$ with wellfounded $\omega$; so $M_0'\cong M_0$, and $\mathbb{R}\cap M_0'=\mathbb{R}\cap M_0$. Then because $N$ models KP and there is no $\beta\in\mathrm{Ord}^N$ such that $N\models$"$\beta<\alpha$" and $L_\beta^M=L_\beta^N\models$ KP, note that $N$ has an isomorphism between $\alpha$ and either $\mathrm{Ord}^{M_0'}$ or some proper cut of $\mathrm{Ord}^{M_0'}$. It follows that $\mathbb{R}\cap M\subseteq M_0'$, proving the claim.

Let $A$ be the set of reals $x$ such that there is some $T\in Y$ and pointwise definable model $M$ of $T$ with $x\in M$. Note that $A$ is $\Sigma^1_1$ and $A\not\subseteq L_{\omega_1^{\mathrm{ck}}}$. So there is a perfect set $P\subseteq A$. But we have seen that $A\subseteq M_0$, and $M_0$ is countable, a contradiction.

Remark: If $X$ is thin and $\Pi^1_1$ and non-empty, then there is in fact a $\Delta^1_1$-minimal element of $X$, because then $X$ is a subset of all reals which are $\Delta^1_1$-equivalent to a master code of $L$ (that is, $\Delta^1_1$-equivalent to a theory $T$ of some $L_\alpha$ such that $L_\alpha$ projects to $\omega$ (where $\alpha$ is a true ordinal)). Thus, just take the least $\alpha$ such that $L_\alpha$ projects to $\omega$ and there is $x\in X$ with $x\equiv_{\Delta^1_1}T$ where $T=\mathrm{Th}^{L_\alpha}(\emptyset)$. Then $x\in\Delta^1_1(\{y\})$ for all $y\in X$.

Answer 2

I'm pretty sure the claim isn't even true for every $\Pi^0_1$ class (working in $\omega^\omega$ or $\Pi^0_2$ if working in $2^\omega$). It's well known that one can produce a recursive tree in $\omega^\omega$ that lacks any hyperarithmetic path however we need to make sure that there isn't a path with hyperdegree below all the other paths.

I believe we can take Harrington's approach to building $\alpha$-subgenerics and uniformly in $\alpha$ build $\Pi^0_1$ classes that contain two $\alpha$-subgeneric paths $X$, $Y$ which are a minimal pair. Then extend this to non-standard $\alpha$ (which produces uncountably many extra paths as well but we'll end up containing a minimal pair of hyperdegrees and no hyperarithmetic paths).

I suspect there is an even easier way.

Answer 3

It is well known that there is a nonempty $\Pi^0_1$ set $A\subseteq \omega^{\omega}$ containing no hyperarithmetic member.(Considering a $\Sigma^1_1$ set without a hyperarithmetic member, it is a projection of a $\Pi^0_1$-set). By Kreisel's basis theorem, for any nonhyperarithmetic real $x$, there is a $y\in A$ so that $x\not\leq_h y$. So there is no the least hyperarithmetic degree in $A$.

So

For any nonempty $\Pi^0_1$ set $A\subseteq \omega^{\omega}$ containing no hyperarithmetic member, there is no member which has the least hyperarithmetic degree in $A$.

But there can be a minimal one in $A$. I.e.

There is a nonemtpy $\Pi^0_1$ set $A$ without hyperarithmetic real in which there is real $x\in A$ so that for any $y\in A$, we have that $y\not<_h x$.

Proof: Let $M$ be an $\omega$-model of $KP$ but $\omega_1^{CK}$ is nonstandard. Now let $n\in \mathcal{O}^M$ be a nonstandard ordinal notation, and $H_n$ be a $\Pi^0_1$-singleton in $M$ coding the $|n|$-th Turing jump. In other words, there is a $\Pi^0_1$ set $A$ so that $M\models H_n \mbox{ is the unique member in }A$. Then $H_n$ has the minimal hyperarithmetic degree in $A$ (otherwise, any $x<_h H_n$ in $A$ is also in $M$. That contradicts the uniqueness of $H_n$ in $M\cap A$).