## 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