2
$\begingroup$

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?

$\endgroup$

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.