6
$\begingroup$

Definitions:

A set $X$ is of PA degree relative to a set $Y$ if every infinite $Y$-computable binary tree has an infinite $X$-computable path. A set $X$ is low if $X'$ is computable from $\emptyset'$.

Easy facts:

By the relativized Low basis theorem and using the fact that a low relative to a low is still low, $\emptyset'$ is of PA degree relative to every low set. Of course, if $\emptyset'$ is of PA degree relative to a set $X$, then $X$ is $\emptyset'$-computable.

Question:

Are there non-low set $Y$ such that $0'$ is of PA degree relative to $Y$ ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

No, by the Arslanov completeness criterion $0'$ is only DNC (Diagonally non-computable) relative to low sets. And PA implies DNC.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your quick answer. I'm ashamed not to have found it by myself. $\endgroup$
    – Ludovic Patey
    Commented Jan 10, 2014 at 16:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .