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$ ?

$\endgroup$
6
$\begingroup$

No, by the Arslanov completeness criterion $0'$ is only DNC relative to low sets. And PA implies DNC.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your quick answer. I'm ashamed not to have found it by myself. $\endgroup$ – Ludovic Patey Jan 10 '14 at 16:47
  • $\begingroup$ Diagonally non-computable $\endgroup$ – Bjørn Kjos-Hanssen Jan 11 '14 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.