7
$\begingroup$

Remember that an n-REA set is a set of the form $A_0 \oplus A_1 \oplus \cdots \oplus A_n$ with $A_n$ relatively r.e. in $A_m, m<n$ (so $A_0$ is r.e.) and that a degree is PA just if it computes a path through every infinite computable tree.

By Arslanov's completeness criterion no incomplete r.e. set can be of PA degree. While pursuing another problem I'm pretty sure I constructed a low 2-REA set of PA degree but before I bother to include that writeup in some paper (it's not the most riveting proof but seems worth mentioning somewhere) or even spend a bunch of time double checking it I wanted to see if it's known.

So anyone know if this result (or refutation) is already in the literature or is trivial to derive from it (e.g., clever use of relativized jump inversion)?

Improve this question
$\endgroup$
24
  • 2
    $\begingroup$ Unless I'm missing something, I think your theorem is false. Call a set A low-for-PA if for every PA degree P, A+P is PA relative to A. It follows from Corollary 2.3 of this paper by Reimann and Day that every low r.e. set is low-for-PA (I also know of another more direct proof of this fact). Suppose A_0 is r.e., A_1 is r.e. relative to A_0, A_0+A_1 is low and A_0+A_1 is PA. Since A_0 is low-for-PA, A_0+A_1 is PA relative to A_0. But by Arslanov's completeness criterion, this means that A_0+A_1 is Turing equivalent to the jump of A_0 and hence not low. $\endgroup$
    – Patrick Lutz
    Commented May 12, 2021 at 1:13
  • 1
    $\begingroup$ @PeterGerdes The fact that a low r.e. set is low-for-PA does relativize and so you can continue the argument I gave by induction. The alternate argument I know of that low r.e. sets are low-for-PA is not the same as what Dan mentioned though (it involves reasoning in the nonstandard model of PA coded by the PA degree and actually shows that if A is r.e. and P is PA then either A + P is PA relative to A or A + P computes 0'). $\endgroup$
    – Patrick Lutz
    Commented May 12, 2021 at 2:46
  • 1
    $\begingroup$ @DanTuretsky Corollary 2.3 of that paper says that if A is r.e. and P is PA such that P computes A then either P computes 0' or P is PA relative to A. If A is low then both of these conclusions imply P is PA relative to A. $\endgroup$
    – Patrick Lutz
    Commented May 12, 2021 at 2:51
  • 2
    $\begingroup$ @PeterGerdes the elementary diagram of the true natural numbers is Turing equivalent to $0^{(\omega)}$ but every PA degree computes the elementary diagram of some model of PA. $\endgroup$
    – Patrick Lutz
    Commented May 12, 2021 at 3:07
  • 2
    $\begingroup$ The standard system of a model M of PA is the set of subsets of $\mathbb{N}$ which are equal to $x \cap \mathbb{N}$ for some $M$-finite set $x$. $\endgroup$
    – Patrick Lutz
    Commented May 12, 2021 at 3:11

1 Answer 1

Reset to default
6
$\begingroup$

Theorem 5.1 in Recursively Enumerable Sets Modulo Iterated Jumps and Extensions of Arslanov's Completeness Criterion states that Arslanov's completeness criterion holds for $n$-REA sets. The paper is from 1989 and by Jockusch, Lerman, Soare, and Solovay.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Thanks for the cute...now to figure out what I fucked up ;-) $\endgroup$
    – Peter Gerdes
    Commented May 12, 2021 at 4:00
  • $\begingroup$ Doh...I let my requirements be pushed down an infinite path on tree so never satisfied...well knowing it was wrong helped $\endgroup$
    – Peter Gerdes
    Commented May 12, 2021 at 6:15

You must log in to answer this question.

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