Comparing different relativizations in computability

174 Views Asked by At

Most, but not all, theorems in computability relativize. In principle, we should go through the original proof to check that a relativized version of a theorem holds. In practice, we often just wave our hands and say "relativized XXX theorem holds."

But sometimes there can be multiple ways of relativizing a theorem. For example, Posner-Robinson theorem reads:

For $X >_T 0$, there exists $G$ such that $G' \equiv_T X \oplus G$.

If I want to relativize this to a set $B$, I could say

(1) For $X >_T B$, there exists $G \ge_T B$ such that $G' \equiv_T X \oplus G$.

or alternatively

(2) For $X >_T B$, there exists $G \ge_T B$ such that $G' \equiv_T^B X \oplus G$.

where $C \le_T^B D$ if there's a Turing functional $\Phi_e$ such that $C = \Phi_e^{D \oplus B}$.

For Posner-Robinson theorem, the difference between the two is not a problem, since both of them are true. But you can think of two relativized versions for a different theorem, and, at least prima facie, they can have different truth values; and relativization of type (2) is more likely to be true. (I barely remember a time in a computability class when a relativization of type (2) is the "correct" way of doing it, but I don't remember what theorem we were talking about.) And even if they have the same truth value, the "mathematical content" of the two versions could sometimes be different.

So my questions here are:

  1. What is a concrete and natural example of a theorem such that relativization of type (1) fails but (2) holds?
  2. In practice, which versions of relativization should I claim? Is the possibility of relativization of type (1) failing higher than type (2) to the extent I should be careful?

(I know metamathematical results about elementary equivalence between cones in the degree structure; my question is more about the practice.)

2

There are 2 best solutions below

0
On BEST ANSWER

I would argue that the "right" relativization of a statement to (the degree of) a noncomputable set $B$ is the version where all the quantifiers range over the cone above $B$, $\{C: C\ge_T B\}$. On this cone, $\equiv_T$ and $\equiv_T^B$ coincide, so it doesn't matter which we use.


If we look at the co-lower cone, $\{C: C\not<_TB\}$, instead, things are much weirder - this isn't a good class of degrees! - and using $\equiv_T^B$ in place of $\equiv_T$ has the effect of "smooshing" everything into the cone above $B$, so - if you really want to work in the co-lower cone, for some reason - is the right equivalence to use.

1
On

From my understanding, the equivalence in $G' \equiv_T^B X \oplus G$ means that $G' \ge_T^B X \oplus G$ and $G' \le_T^B X \oplus G$, and according to your definition of a Turing functional we therefore have both $C = \Phi_e^{D \oplus B}$ and $D = \Phi_e^{C \oplus B}$. So we must have $B$ as some kind of identity, as for a set $S$, $S \oplus \{e\} = S$. We must also practically have $C=D$.

Effectively, the second type allows no more possibilities than the first type, if not less as it implies $B=I$.