The low basis theorem says that there are PA degrees which are low - that is, which satisfy ${\bf a'}={\bf 0'}$. Appropriately relativized, given a degree ${\bf a}$ there is a degree ${\bf b}$ "not much bigger than" ${\bf a}$ which is PA over ${\bf a}$. A natural question at this point is whether the "dual" holds: if ${\bf b}$ is PA in the first place, must ${\bf b}$ be PA over some ${\bf a}$ which is "close to" ${\bf a}$? One natural way to phrase this question would be: if ${\bf b}$ is PA, then must ${\bf b}$ be PA over some ${\bf a}$ with ${\bf a'}={\bf b'}$?

It turns out that (quite surprisingly to me) the answer is no: the degree ${\bf 0'}$ is PA but not PA over anything not low.

Say that a degree ${\bf d}$ is relatively efficiently PA if there is some ${\bf b}\le_T{\bf d}$ such that ${\bf d}$ is PA over ${\bf b}$ and ${\bf d}$ is low over ${\bf b}$ (that is, ${\bf b'}={\bf d'}$). By the observation cited above, ${\bf 0'}$ is not relatively efficiently PA. However, in a precise sense "most" Turing degrees are relatively efficiently PA: the relativized low basis theorem tells us that the set of relatively efficiently PA degrees is unbounded, and so Martin's cone theorem (+ the fact that "relatively efficiently PA" is a sufficiently simple property) tells us that the set of relatively efficiently PA degrees contains a cone.

My question is roughly when this happens - that is, what might be a reasonable base for such a cone. Specifically:

Is every degree $\ge_T{\bf 0''}$ relatively efficiently PA?


Your Answer

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

Browse other questions tagged or ask your own question.