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 ...
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 ...
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 $\...
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 ...
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 ...
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 ...
Top 50 recent answers are included
Related Tags
computability-theory × 946lo.logic × 510
set-theory × 161
computational-complexity × 102
computer-science × 90
reference-request × 85
descriptive-set-theory × 62
model-theory × 59
nt.number-theory × 43
reverse-math × 37
proof-theory × 36
ordinal-numbers × 36
decidability × 33
gr.group-theory × 32
theories-of-arithmetic × 30
co.combinatorics × 28
ct.category-theory × 21
algorithms × 16
forcing × 15
diophantine-equations × 15
constructive-mathematics × 15
graph-theory × 14
computable-analysis × 14
recursively-enumerable × 14
soft-question × 13