2
$\begingroup$

Remember a degree $\mathbb{d}$ is the $n$-lub of $\mathbb{c}_j$ in the Turing degrees if it is the least element (not merely a minimal element) set of $\mathbb{c}^{(n)}$ such that $\mathbb{c}$ computes every $\mathbb{c}_j$. It is non-trivial if it's not the $n$-th jump of a finite join of the degrees $\mathbb{c}_n$.

Enderton, Putnam and Sacks have proved $0^{\omega}$ is the (non-trivial) 2-lub of $0^n$. Are there any arithmetic degrees that are non-trivial 2-lub?

If so can they be arithmetic? What about an upper bound $\mathbb{c}$ of $\mathbb{c}_j$ with $\mathbb{c}$ of r.e. degree and $\mathbb{c}^{(2)}$ a non-trivial 2-lub of $\mathbb{c}_n$?

$\endgroup$

1 Answer 1

0
$\begingroup$

Yes, it turns out that there is such an arithmetic (indeed 3-REA) non-trivial 2-lub. In fact, $\emptyset'''$ is such a degree. Consider the construction I give here in answer to this question.

This construction builds an $\omega$-REA degree $A$ such that $A^{[\leq n]}$ is low for every $n$ but such that $A$ computes $\emptyset'''$ [1]. Let ${\bf{a}}_n$ be the degree of $A^{[\leq n]}$. We have ${\bf{a}}_n \leq_T \emptyset'$ and ${\bf{a}}''_n \equiv_T \emptyset''$. The first fact provides an upper bound ($\emptyset'$) whose double jump is $\emptyset'''$ and the second fact shows that $\emptyset'''$ is not the double jump of any finite join of the degrees ${\bf{a}}_n$. All that remains is to verify that the double jump of any other upper bound computes $\emptyset'''$.

Now suppose ${\bf d}$ computes each ${\bf{a}}_n$. I claim that ${\bf d}''$ can compute $A$. This follows because given an index for $A^{[\leq n]}$ as a ${\bf d}$ computable set we can (by uniformity of the REA construction) ${\bf d}$ computably recover an index for $A^{[\leq n +1]}$ as a ${\bf d}$-r.e. set and, since $A^{[\leq n +1]}$ is ${\bf d}$ computable we can recover an index for $A^{[\leq n +1]}$ as a ${\bf d}$ computable set computably in ${\bf d}''$. Thus, if ${\bf d}$ is an upper bound of ${\bf{a}}_n$ it follows that ${\bf d}''$ computes $\emptyset'''$.

[1] The construction of $A$ ensures that if for each $x$ $\lim_{t\to\infty} p_e(e,s,t)$ exists and $\lim_{t\to\infty} p_e(e,0,t) \neq \lim_{t\to\infty} p_e(e,1,t)$ then $A$ can determine if $\lim_{s\to\infty}\lim_{t\to\infty} p_e(e,s,t)$ exists. But, by appropriate choice of $e$ this lets us answer the membership question in $\emptyset'''$.


Note that this also answer the question of whether I can have an r.e. degree whose double jump is a 2-lub. However, I'm unsure if this extends to incomplete r.e. degrees but I'm guessing it might with a bit more care in the constructions.

$\endgroup$

You must log in to answer this question.

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