The jump operator is well defined on the Turing degrees

189 Views Asked by At

This is in a way a continuation of my previous question: Basic questions on Turing degrees and the jump operator

There's this statement:

If $A\leq_T B$, then $K^A\leq_1 K^B$. It follows that the jump operator is well defined on the Turing degrees.

First, what does the statement "the jump operator is well defined on the Turing degrees" mean exactly? The jump operator was defined on sets: for a set $A$, the jump of $A$ is $A'=K^A=\{n\in\mathbb N: \phi_n^A(n)\downarrow\}$. There are no equivalence classes in this case to check if something is well defined.

There are equivalence classes in the definition of $0^{(k)}$. I would say that well definiteness of $0^{(k)} $ means the following: if $A\equiv_T B$ and $A$ lies in $0^{(k)}$, then $B$ also lies in $0^{(k)}$. Is this what is meant? But even if so, I don't see how the implication $A\leq_T B\implies K^A\leq_1 K^B$ proves this.

And second, how to prove that $A\leq_T B\implies K^A\leq_1 K^B$? I suppose it's enough to construct a partial computable function $$V:N\times N\to N$$ such that if $n\in K^A$ then $V(n,n)$ is computable in $B$ and if $n\notin K$, then $V(n,n)$ is not computable in $B$. (After that one can apply the s-m-n theorem or something like that to get a total computable $N\to N$ that $m$-reduces $K^A$ to $K^B$). But I'm not sure how to do that.

1

There are 1 best solutions below

0
On BEST ANSWER

There are no equivalence classes in this case to check if something is well defined

Ah, but there are!

The statement "The jump operator is well defined on Turing degrees" is just an example of a more general type of statement: when we have a set $X$, a function $f:X\rightarrow X$, and an equivalence relation $E$ on $X$, we say $f$ is well defined on $X/E$ if we have $$xEy\implies f(x)Ef(y)$$ for all $x,y\in X$. Here, $X=\mathcal{P}(\mathbb{N})$, $E$ is Turing equivalence so that $X/E$ is the set of Turing degrees, and $f$ is the jump function.

The point is that when $f$ is well defined on $X/E$, we get an "analogue" of $f$ given by $$f_E: X/E\rightarrow X/E: [x]_E\mapsto [f(x)]_E$$ (note that well-definedness on $X/E$ is crucial here). Often we conflate $f$ and $f_E$; so e.g. we'll freely talk about the jump of a Turing degree even though that's an abuse of terminology.


Now as to how well-definedness on degrees is proved from the claimed implication, I suspect you're just overthinking this.

We know that $A\le_T B\rightarrow A'\le_1B'$ (my "$C'$" is your text's "$K^C$"). A fortiori then, we have $A\le_T B\rightarrow A'\le_TB'$ and so in particular we get $$A\equiv_TB\rightarrow A'\equiv_TB'$$ as desired (just use the previous implication in both directions).

Note that $\le_1$ here was overkill: we really only needed $\le_T$ in the conclusion of the result. But noting $1$-reductions when they exist is generally worthwhile if it doesn't take much additional work.


Finally, we're left with the task of proving that claimed implication, $A\le_TB\rightarrow A'\le_1B'$. I suggest first trying to show $A\le_TB\rightarrow A'\le_mB'$. The padding lemma will then let you convert that $\le_m$ into an $\le_1$.

So suppose I want to tell whether $\Phi_e^A(e)\downarrow$ (that is, whether $e\in A'$) and I have access to $B'$ as well as a method for getting $A$ from $B$. Consider a machine which, with oracle $B$, first constructs $A$ from $B$ to use as an oracle going forwards ...