New answers tagged computability-theory
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 ...
- 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 ...
- 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 $\...
- 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 ...
- 19.1k
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 ...
- 455
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 ...
- 7,524
Top 50 recent answers are included