New answers tagged

1 vote

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

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 ...
喻 良's user avatar
  • 4,111
8 votes

How exactly are realizability and the Curry-Howard correspondence related?

I am sure more than one exact correspondence can be made, but here's at least one that is technically precise. We shall employ categorical logic. Executive summary: realizability is the ...
Andrej Bauer's user avatar
  • 46.7k
2 votes

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

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 $\...
Peter Gerdes's user avatar
  • 2,531
6 votes
Accepted

Proving finiteness in Reverse Mathematics

Here's a proof that $\mathsf{ACA}_0$ suffices for the analogous statement over $2^\mathbb{N}$ instead of $\mathbb{R}$, where codes for closed sets are viewed as subtrees of $2^{<\mathbb{N}}$; it's ...
Noah Schweber's user avatar
3 votes

Complexity of the set of models of TA

The set of models of true arithmetic is indeed $\pmb \Pi^0_\omega$-complete under Wadge reducibility. That is, for any $\pmb \Pi^0_\omega$ set $X$ on a Polish space $Y$, there is a continuous function ...
Dino Rossegger's user avatar
4 votes
Accepted

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

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 ...
Farmer S's user avatar
  • 7,524

Top 50 recent answers are included