<p>Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented group (even ones countably generated) is a subgroup of a finitely presented group.</p>

<p>Note that this statement <em>could</em> relativize to: "The $O$-computably presented groups (with some oracle $O$) are precisely the finitely generated subgroups of finitely presented groups," but it does not, as one can prove that for some uncomputable $O$ there are $O$-computably presented groups that are not computably presented. </p>

<p>Indeed, I think <em>any</em> non-relativizing result of computability theory must have something of this flavor, as some part of the result or its proof must somehow "nail down" true computability from computability with an oracle $O$. In this case, it is the finiteness which nails down "actual computability." Note that, as Scott Aaronson asked for, this result is invariant to any of the usual models of computation (Turing machine, RAM, etc), but does not relativize (again, because all of the usual models of "actual" computation share some common "finiteness property").</p>

<p>On the other hand, one might argue that this "doesn't count" for this question, as it is more akin to a definition of computability using groups than it is a "result of computability theory." On the other other hand, it is a definition of computability that is robust to model yet <em>that doesn't relativize</em>. (In contrast to, say, <a href="https://en.wikipedia.org/wiki/%CE%9C-recursive_function" rel="noreferrer">Kleene's characterization</a> of the computable functions which easily relativizes, by simply adding the characteristic function of your oracle to the generating set of functions. There seems to be no analogous operation for groups in the context of Higman Embedding.)</p>

CC BY-SA 3.0
2017-03-27T11:58:37.800Z
Is it finiteness (vs. infinity) that distinguishes your example, or countability (vs. uncountability)?
András Salamon
CC BY-SA 3.0
2017-03-27T15:01:34.353Z
@AndrejBauer: I believe the answer is YES (though I haven't checked all the details): given a computable presentation of a group $G$, say, in terms of Kleene's characterization of c.e. functions, Higman essentially gives a step-by-step procedure - using induction along the structure of the "Kleene program" for the presentation - to construct a finite presentation of a group $H \supseteq G$ and the embedding $G \hookrightarrow H$.
Joshua Grochow
CC BY-SA 3.0
2017-03-27T18:12:51.073Z
So nothing seems to prevent us using the same procedure in the presence of oracles. But what theorem do we get then? *That* will be the relativization of Higman's Theorem!
Andrej Bauer
CC BY-SA 3.0
2017-03-27T18:40:49.393Z
@AndrejBauer: I don't see that. Higman's proof basically goes by showing that you can simulate Kleene's basic functions and operators (see the Wikipedia page for terminology) using group constructions. If you throw in an oracle as a basic function (the natural way of relativizing Kleene's characterization) I don't see how to simulate that using a group construction.
Joshua Grochow
CC BY-SA 3.0
2017-03-27T18:48:40.933Z
Well then, perhaps there should be a Grochow's theorem :-) For example, perhaps to every oracle we can assign some sort of a ($O$-computable) group $G_O$, and then the theorem will say that every $O$-computably presented group is a subgroup of a finitely presented quotient of a finite product of copies of $G_O$. Or something like that. We should use imagination, not look for reasons to avoid looking for a theorem.
Andrej Bauer
CC BY-SA 3.0
2017-03-28T18:20:14.507Z
Supposing that this program of coming up with an $O$-group succeeds, it seems like it would give a "relativized" version of Higman's theorem much like there is a "relativized" version of the Cook-Levin theorem that says that 3-SAT is NP^A-complete when you allow for "A-literals" in the clauses. As in, yeah, sure, you can do it, but on the other hand you're destroying a lot of the structure that makes the result so nice in the first place.
Andrew Morgan
CC BY-SA 3.0
2017-03-28T18:38:51.950Z
@AndrewMorgan: I agree with the start of your argument but disagree with your conclusion. It is often quite useful that $SAT^O$ is $NP^O$-complete. I don't think of the  relativization of Cook-Levin as at all unnatural... I like Andrej's suggestion very much and we'll think about it...
Joshua Grochow
CC BY-SA 3.0
2017-03-28T18:56:40.937Z
@JoshuaGrochow Sorry, I should have been more explicit. I meant specifically 3-SAT, where the input is a 3-CNF formula--not a general circuit. Maybe that's still not convincing enough, and it would be more persuasive to use 3-colorability or some other combinatorial problem, though the oracle mechanism gets more difficult to work out. The point is that at some point the relevant oracle mechanism becomes so unnatural that including it corrupts all our intuition about the original problem, and I think that at that point it's fair to say the original result doesn't relativize.
Andrew Morgan
CC BY-SA 3.0
2017-03-28T19:47:39.897Z
@AndrewMorgan: Agreed. I would think that knot genus would be a good candidate :).
Joshua Grochow
CC BY-SA 3.0
2017-03-27T08:15:50.857Z
2017-03-27T14:59:27.243Z
2017-03-27T14:59:27.243Z
Joshua Grochow
<p>The short version of this answer is:</p>
<blockquote>
<p><strong>Degree theory</strong> (e.g. the study of the first-order theory of the partial order of Turing degrees) yields examples of non-relativizing statements, although these statements are of course highly technical. One useful tool for understanding this situation is the cone theorem ... which also limits the extent to which this behavior can happen.</p>
</blockquote>
<hr />
<p>There are indeed theorems which don't relativize, about which I'll say more below. First, though, let me observe that there is a sense in which <strong>all (reasonable) theorems <em>eventually</em> relativize</strong>:</p>
<blockquote>
<p><strong>(Martin's cone theorem)</strong> Suppose <span class="math-container">$A$</span> is a &quot;nicely definable&quot; property of Turing degrees. Then either every sufficiently large Turing degree has <span class="math-container">$A$</span> or every sufficiently large Turing degree fails <span class="math-container">$A$</span>; precisely, there is some degree <span class="math-container">${\bf d}$</span> such that for every degree <span class="math-container">${\bf c}\ge_T{\bf d}$</span> we have <span class="math-container">$A({\bf c})\leftrightarrow A({\bf d})$</span>.</p>
</blockquote>
<p>&quot;Nicely definable&quot; here is a bit technical; specifically, we want the set of elements of <span class="math-container">$A$</span> (thought of as a subset of <span class="math-container">$2^\omega$</span>) to be <a href="https://en.wikipedia.org/wiki/Determinacy" rel="nofollow noreferrer"><em>determined</em></a>, in the sense that one player or the other has a winning strategy in the associated Gale-Stewart game. I'll briefly observe that <span class="math-container">$(i)$</span> every <em>Borel</em> set is determined, and so every property of Turing-invariant property which is expressible in the infinitary logic <span class="math-container">$\mathcal{L}_{\omega_1,\omega}$</span> either holds or fails on a cone, and <span class="math-container">$(ii)$</span> additional set-theoretic assumptions can push determinacy far beyond the Borel sets. Heuristically, one will not run into a non-determined set of Turing degrees without explicitly trying to.</p>
<p>The proof of the cone theorem can be boiled down to a single sentence:</p>
<blockquote>
<p>Supposing <span class="math-container">$A\subseteq 2^\omega$</span> is Turing-invariant and determined with a winning strategy <span class="math-container">$\sigma$</span> for player <span class="math-container">$1$</span>, given any <span class="math-container">$r\ge_T\sigma$</span> consider the play of <span class="math-container">$\sigma$</span> against the &quot;silly&quot; strategy for player <span class="math-container">$2$</span> which simply plays the bits of <span class="math-container">$r$</span> regardless of what player <span class="math-container">$1$</span> does.</p>
</blockquote>
<p><em>OK, this isn't really fair: the difficult aspect of the cone theorem isn't the theorem itself but rather the determinacy results it leans on, since it's not a prior clear that determinacy is something we should expect of &quot;nice&quot; sets in the first place. The clearest proof of Borel determinacy I've seen is in <a href="https://www.math.ucla.edu/%7Eynm/lectures/dst2009/dst2009.pdf" rel="nofollow noreferrer">Moschovakis' book</a>, but it's still quite involved. <a href="https://plato.stanford.edu/entries/large-cardinals-determinacy/#DetLarCar" rel="nofollow noreferrer">Large cardinals improve things substantially</a> - the proof of analytic determinacy from a measurable cardinal is actually much simpler than Borel determinacy from ZFC - but it's never really easy after the first couple levels of the Borel hierarchy.</em></p>
<hr />
<p>Now let's talk about the <em>positive</em> role of the cone theorem in finding non-relativization phenomena.</p>
<p>First, here's an interesting application of the cone theorem to get a <em>dubious</em> example of what you're looking for. <a href="https://mathoverflow.net/questions/154184/is-0-of-pa-degree-relative-to-a-non-low-set/154190#154190">By the Arslanov Completeness Criterion, <span class="math-container">${\bf 0'}$</span> is not PA over anything over which it is low</a>; however, since the low basis theorem does relativize, by the cone theorem we know that for all sufficiently large degrees <span class="math-container">${\bf a}$</span> there <em>is</em> some <span class="math-container">${\bf b}$</span> such that <span class="math-container">${\bf a'}$</span> is low an PA over <span class="math-container">${\bf b}$</span>. This apparently contradicts the fact that the proof of ACC <em>also</em> relativizes; the saving grace is that the required <span class="math-container">${\bf b}$</span> is not in the interval <span class="math-container">$[{\bf a},{\bf a'}]$</span> <em>(and indeed we get an interesting jump inversion counterexample here)</em>.</p>
<p>Ultimately the above indicates that <strong>we've</strong> <em>(fine, I've)</em> <strong>relativized the original result incorrectly here</strong>: when relativizing a degree-theoretic fact to <span class="math-container">${\bf a}$</span>, we should restrict attention to the upper cone <span class="math-container">$\{{\bf c}: {\bf c}\ge_T{\bf a}\}$</span> (that is, look at what happens if <span class="math-container">${\bf a}$</span> were to be thought of as <span class="math-container">${\bf 0}$</span>). This suggests a natural sub-question of your question:</p>
<blockquote>
<p>Is there some sentence <span class="math-container">$\varphi$</span> in the language of partial order such that <span class="math-container">$\mathcal{D}\models\varphi$</span> but <span class="math-container">$\mathcal{D}_{\ge_T{\bf a}}\models\neg\varphi$</span> for all sufficiently large degrees <span class="math-container">${\bf a}$</span>?</p>
</blockquote>
<p>Here <span class="math-container">$\mathcal{D}$</span> (resp. <span class="math-container">$\mathcal{D}_{\ge_T{\bf a}}$</span>) is the partial order of Turing degrees (resp. Turing degrees <span class="math-container">$\ge_T{\bf a}$</span>) under <span class="math-container">$\ge_T$</span>. The language of partial order may seem quite limited at first, but it's actually <em>extremely</em> expressive; in particular, contra early expectations it is known that <a href="https://math.berkeley.edu/%7Eslaman/talks/sw.pdf" rel="nofollow noreferrer"><span class="math-container">$\mathcal{D}$</span> has a highly complicated first-order theory and at most countably many automorphisms</a> <em>(and it's conjectured that <span class="math-container">$\mathcal{D}$</span> is rigid, a <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.1511&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">proposed counterexample by Cooper</a> being generally considered to be flawed)</em>.</p>
<ul>
<li>Note that the question above treats a <em>precise notion</em> of (non-)relativization, which I think is rather neat! And per the expressivity of <span class="math-container">$\mathcal{D}$</span>, it's not too restrictive either.</li>
</ul>
<p><strong>The answer to this sub-question turns out to be yes</strong>; this is a consequence of Theorem 3.1 of <a href="https://core.ac.uk/download/pdf/82225234.pdf" rel="nofollow noreferrer">Nerode and Shore</a> <em>(although they don't quite phrase it this way - also, they include a symbol for the Turing jump, but <a href="https://math.berkeley.edu/%7Eslaman/papers/jump.pdf" rel="nofollow noreferrer">it was later shown that the jump is definable from the partial order structure alone</a>)</em>.</p>
<p>The proof gives such a <span class="math-container">$\varphi$</span>, but we can also show the existence of such a <span class="math-container">$\varphi$</span> using their theorem as a blackbox ... via the cone theorem! Suppose no such <span class="math-container">$\varphi$</span> existed; then for each <span class="math-container">$\varphi\in Th(\mathcal{D})$</span>, the set <span class="math-container">$T_\varphi=\{{\bf a}: \mathcal{D}_{\ge{\bf a}}\models\varphi\}$</span> contains a cone. But since the intersection of countably many cones in <span class="math-container">$\mathcal{D}$</span> is again a cone, we get a cone of <span class="math-container">${\bf a}$</span> in <span class="math-container">$\bigcap_{\varphi\in Sent} T_\varphi$</span> - in other words, a cone of degrees whose upper cones are elementarily equivalent to <span class="math-container">$\mathcal{D}$</span>, contradicting Nerode/Shore.</p>

CC BY-SA 4.0
2021-08-05T14:33:56.547Z
I like it! I think the notion of relativization though, rather than restrict to the cone above a, should look at the Turing$^a$ degrees. That is, allow the reductions themselves to access the oracle. Then a automatically has the same degree as 0 (achieving what you wanted), and now I think more results relativize in this sense (?).
Joshua Grochow
CC BY-SA 4.0
2020-01-04T23:59:49.370Z
2021-08-02T07:58:23.320Z
2021-08-02T07:58:23.320Z
Noah Schweber
<p>This is something I've often wondered about as well!</p>

<p>If by "results in computability theory," you mean results that are invariant with respect to the choice of machine model (Turing machines, RAM machines, etc.), then I don't know a single example of such a result, and I definitely would've remembered if I'd seen one.</p>

<p>The closest I can suggest to an answer is: I think there are many interesting questions in computability theory that might depend on the machine model.  For example: is the Busy Beaver function, with its usual definition in terms of Turing machines, infinitely often odd?  Is the value of BB(20) independent of ZFC?  Whatever the answers to these questions are, they could surely be different for relativized analogues of the BB function.</p>

CC BY-SA 4.0
2020-01-15T19:14:16.953Z
Examples of non-relativizing statements can be found coming from degree theory (per my answer); of course, whether these are natural or not is another story.
Noah Schweber
CC BY-SA 3.0
2017-03-27T03:58:12.930Z
2017-03-27T03:58:12.930Z
Scott Aaronson
<p>I was reading Andrej Bauer's paper <a href="http://dx.doi.org/10.1016/j.entcs.2005.11.049" rel="noreferrer">First Steps in Synthetic Computability Theory</a>. In the conclusion he notes that </p>

<blockquote>
  <p>Our axiomatization has its limit: it cannot prove any results in computability
  theory that fail to relativize to oracle computations. This is so because the
  theory can be interpreted in a variant of the effective topos built from partial
  recursive functions with access to an oracle.</p>
</blockquote>

<p>This made me wonder about non-relativizing results in computability. All results I know from computability theory do relativize to computation with oracles. </p>

<p>Are there results in <strong>computability theory</strong> that do not relativize? I.e. results which hold for computability but do not hold for computability relative to some oracle? </p>

<p>By result I mean a known theorem in computability theory, not some cooked up statement. If the notion of relativization doesn't make sense for the result then it is not what I am looking for. </p>

<p>It is also interesting to know if the result can be stated in the language of Synthetic Computability Theory or not.</p>

CC BY-SA 3.0
2016-01-25T17:58:43.743Z
Everyone knows about non-relativizing results in complexity theory like IP=PSPACE. I am asking about non-relativizing _computability_ theory resuts, __not__ _complexity_ theory results.
Anonymous
CC BY-SA 3.0
2016-01-25T20:29:27.657Z
@Erfan: Your comments are not relevant to the question. My question is about computability theory, you are talking about complexity theory. I am looking for non-reletivizing results, the time hierachy theorem does relativize. If you have a question about the time hierarchy theorem and relativization you can post a separate question.
Anonymous
CC BY-SA 3.0
2016-01-26T10:50:42.167Z
Relevant stuff: the Homogeneity conjecture formulated by H. Rogers has been refuted in Richard A. Shore; The homogeneity conjecture (1979): there exists a Turing degree $\mathbf{a}$ such that $\mathcal{D}(\geq \mathbf{a})$ is not isomorphic to $\mathcal{D}$ (the structure of Turing degrees with partial order $\leq_{T} $). See a [similar question on lo.logic](http://mathoverflow.net/q/55933/35419)
Marzio De Biasi
CC BY-SA 3.0
2016-01-27T04:22:06.290Z
@Marzio: Interesting. "_So this means that there is a first order sentence $\varphi$ in the language only containing $\leq_T$ which is true about the Turing degrees, but which is false if you relativize the sentence to the Turing degrees $\geq_Tx$ for some $x$ (and of course, working in the Turing degrees $\geq_Tx$ is equivalent to giving all Turing machines access to $x$ as an oracle). Hence, the proof that $\varphi$ is true can't be relativized to $x$._" But $\varphi$ is not really a result in computability theory, it is cooked up for a meta theorem.
Anonymous
CC BY-SA 3.0
2016-01-27T04:23:01.437Z
@Marzio: Andrew Marks continues: "_All that being said, just about every proof in recursion theory that I know of relativizes. I'd be very interested in a proof which doesn't relativize and doesn't factor through the coding machinery I've mentioned above._"
Anonymous
<computability><relativization>
Is there a result in computability theory that does not relativize?
Anonymous
# Is there a result in computability theory that does not relativize?

(Asked by: username_0 on 2016-01-25)

I was reading Andrej Bauer's paper [First Steps in Synthetic Computability Theory](http://dx.doi.org/10.1016/j.entcs.2005.11.049). In the conclusion he notes that

> Our axiomatization has its limit: it cannot prove any results in computability
> theory that fail to relativize to oracle computations. This is so because the
> theory can be interpreted in a variant of the effective topos built from partial
> recursive functions with access to an oracle.

This made me wonder about non-relativizing results in computability. All results I know from computability theory do relativize to computation with oracles.

Are there results in **computability theory** that do not relativize? I.e. results which hold for computability but do not hold for computability relative to some oracle?

By result I mean a known theorem in computability theory, not some cooked up statement. If the notion of relativization doesn't make sense for the result then it is not what I am looking for.

It is also interesting to know if the result can be stated in the language of Synthetic Computability Theory or not.

**Tags:** computability, relativization
> **Comments:**
> **username_0**: Everyone knows about non-relativizing results in complexity theory like IP=PSPACE. I am asking about non-relativizing _computability_ theory resuts, __not__ _complexity_ theory results.  
> **username_0**: @Erfan: Your comments are not relevant to the question. My question is about computability theory, you are talking about complexity theory. I am looking for non-reletivizing results, the time hierachy theorem does relativize. If you have a question about the time hierarchy theorem and relativization you can post a separate question.  
> **username_1**: Relevant stuff: the Homogeneity conjecture formulated by H. Rogers has been refuted in Richard A. Shore; The homogeneity conjecture (1979): there exists a Turing degree $\mathbf{a}$ such that $\mathcal{D}(\geq \mathbf{a})$ is not isomorphic to $\mathcal{D}$ (the structure of Turing degrees with partial order $\leq_{T} $). See a [similar question on lo.logic](http://mathoverflow.net/q/55933/35419)  
> **username_0**: @Marzio: Interesting. "_So this means that there is a first order sentence $\varphi$ in the language only containing $\leq_T$ which is true about the Turing degrees, but which is false if you relativize the sentence to the Turing degrees $\geq_Tx$ for some $x$ (and of course, working in the Turing degrees $\geq_Tx$ is equivalent to giving all Turing machines access to $x$ as an oracle). Hence, the proof that $\varphi$ is true can't be relativized to $x$._" But $\varphi$ is not really a result in computability theory, it is cooked up for a meta theorem.  
> **username_0**: @Marzio: Andrew Marks continues: "_All that being said, just about every proof in recursion theory that I know of relativizes. I'd be very interested in a proof which doesn't relativize and doesn't factor through the coding machinery I've mentioned above._"  

---

## 3 answers

### Answer by username_2 on 2017-03-27. Score: 14

Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented group (even ones countably generated) is a subgroup of a finitely presented group.

Note that this statement *could* relativize to: "The $O$-computably presented groups (with some oracle $O$) are precisely the finitely generated subgroups of finitely presented groups," but it does not, as one can prove that for some uncomputable $O$ there are $O$-computably presented groups that are not computably presented.

Indeed, I think *any* non-relativizing result of computability theory must have something of this flavor, as some part of the result or its proof must somehow "nail down" true computability from computability with an oracle $O$. In this case, it is the finiteness which nails down "actual computability." Note that, as Scott Aaronson asked for, this result is invariant to any of the usual models of computation (Turing machine, RAM, etc), but does not relativize (again, because all of the usual models of "actual" computation share some common "finiteness property").

On the other hand, one might argue that this "doesn't count" for this question, as it is more akin to a definition of computability using groups than it is a "result of computability theory." On the other other hand, it is a definition of computability that is robust to model yet *that doesn't relativize*. (In contrast to, say, [Kleene's characterization](https://en.wikipedia.org/wiki/%CE%9C-recursive_function) of the computable functions which easily relativizes, by simply adding the characteristic function of your oracle to the generating set of functions. There seems to be no analogous operation for groups in the context of Higman Embedding.)

> **Comments:**
> **username_3**: Is it finiteness (vs. infinity) that distinguishes your example, or countability (vs. uncountability)?  
> **username_2**: @AndrejBauer: I believe the answer is YES (though I haven't checked all the details): given a computable presentation of a group $G$, say, in terms of Kleene's characterization of c.e. functions, Higman essentially gives a step-by-step procedure - using induction along the structure of the "Kleene program" for the presentation - to construct a finite presentation of a group $H \supseteq G$ and the embedding $G \hookrightarrow H$.  
> **username_4**: So nothing seems to prevent us using the same procedure in the presence of oracles. But what theorem do we get then? *That* will be the relativization of Higman's Theorem!  
> **username_2**: @AndrejBauer: I don't see that. Higman's proof basically goes by showing that you can simulate Kleene's basic functions and operators (see the Wikipedia page for terminology) using group constructions. If you throw in an oracle as a basic function (the natural way of relativizing Kleene's characterization) I don't see how to simulate that using a group construction.  
> **username_4**: Well then, perhaps there should be a Grochow's theorem :-) For example, perhaps to every oracle we can assign some sort of a ($O$-computable) group $G_O$, and then the theorem will say that every $O$-computably presented group is a subgroup of a finitely presented quotient of a finite product of copies of $G_O$. Or something like that. We should use imagination, not look for reasons to avoid looking for a theorem.  
> **username_5**: Supposing that this program of coming up with an $O$-group succeeds, it seems like it would give a "relativized" version of Higman's theorem much like there is a "relativized" version of the Cook-Levin theorem that says that 3-SAT is NP^A-complete when you allow for "A-literals" in the clauses. As in, yeah, sure, you can do it, but on the other hand you're destroying a lot of the structure that makes the result so nice in the first place.  
> **username_2**: @AndrewMorgan: I agree with the start of your argument but disagree with your conclusion. It is often quite useful that $SAT^O$ is $NP^O$-complete. I don't think of the  relativization of Cook-Levin as at all unnatural... I like Andrej's suggestion very much and we'll think about it...  
> **username_5**: @JoshuaGrochow Sorry, I should have been more explicit. I meant specifically 3-SAT, where the input is a 3-CNF formula--not a general circuit. Maybe that's still not convincing enough, and it would be more persuasive to use 3-colorability or some other combinatorial problem, though the oracle mechanism gets more difficult to work out. The point is that at some point the relevant oracle mechanism becomes so unnatural that including it corrupts all our intuition about the original problem, and I think that at that point it's fair to say the original result doesn't relativize.  
> **username_2**: @AndrewMorgan: Agreed. I would think that knot genus would be a good candidate :).  

---

### Answer by username_6 on 2020-01-04. Score: 7

The short version of this answer is:

> **Degree theory** (e.g. the study of the first-order theory of the partial order of Turing degrees) yields examples of non-relativizing statements, although these statements are of course highly technical. One useful tool for understanding this situation is the cone theorem ... which also limits the extent to which this behavior can happen.

---

There are indeed theorems which don't relativize, about which I'll say more below. First, though, let me observe that there is a sense in which **all (reasonable) theorems *eventually* relativize**:

> **(Martin's cone theorem)** Suppose $A$ is a "nicely definable" property of Turing degrees. Then either every sufficiently large Turing degree has $A$ or every sufficiently large Turing degree fails $A$; precisely, there is some degree ${\bf d}$ such that for every degree ${\bf c}\ge\_T{\bf d}$ we have $A({\bf c})\leftrightarrow A({\bf d})$.

"Nicely definable" here is a bit technical; specifically, we want the set of elements of $A$ (thought of as a subset of $2^\omega$) to be [*determined*](https://en.wikipedia.org/wiki/Determinacy), in the sense that one player or the other has a winning strategy in the associated Gale-Stewart game. I'll briefly observe that $(i)$ every *Borel* set is determined, and so every property of Turing-invariant property which is expressible in the infinitary logic $\mathcal{L}\_{\omega\_1,\omega}$ either holds or fails on a cone, and $(ii)$ additional set-theoretic assumptions can push determinacy far beyond the Borel sets. Heuristically, one will not run into a non-determined set of Turing degrees without explicitly trying to.

The proof of the cone theorem can be boiled down to a single sentence:

> Supposing $A\subseteq 2^\omega$ is Turing-invariant and determined with a winning strategy $\sigma$ for player $1$, given any $r\ge\_T\sigma$ consider the play of $\sigma$ against the "silly" strategy for player $2$ which simply plays the bits of $r$ regardless of what player $1$ does.

*OK, this isn't really fair: the difficult aspect of the cone theorem isn't the theorem itself but rather the determinacy results it leans on, since it's not a prior clear that determinacy is something we should expect of "nice" sets in the first place. The clearest proof of Borel determinacy I've seen is in [Moschovakis' book](https://www.math.ucla.edu/%7Eynm/lectures/dst2009/dst2009.pdf), but it's still quite involved. [Large cardinals improve things substantially](https://plato.stanford.edu/entries/large-cardinals-determinacy/#DetLarCar) - the proof of analytic determinacy from a measurable cardinal is actually much simpler than Borel determinacy from ZFC - but it's never really easy after the first couple levels of the Borel hierarchy.*

---

Now let's talk about the *positive* role of the cone theorem in finding non-relativization phenomena.

First, here's an interesting application of the cone theorem to get a *dubious* example of what you're looking for. [By the Arslanov Completeness Criterion, ${\bf 0'}$ is not PA over anything over which it is low](https://mathoverflow.net/questions/154184/is-0-of-pa-degree-relative-to-a-non-low-set/154190#154190); however, since the low basis theorem does relativize, by the cone theorem we know that for all sufficiently large degrees ${\bf a}$ there *is* some ${\bf b}$ such that ${\bf a'}$ is low an PA over ${\bf b}$. This apparently contradicts the fact that the proof of ACC *also* relativizes; the saving grace is that the required ${\bf b}$ is not in the interval $[{\bf a},{\bf a'}]$ *(and indeed we get an interesting jump inversion counterexample here)*.

Ultimately the above indicates that **we've** *(fine, I've)* **relativized the original result incorrectly here**: when relativizing a degree-theoretic fact to ${\bf a}$, we should restrict attention to the upper cone $\{{\bf c}: {\bf c}\ge\_T{\bf a}\}$ (that is, look at what happens if ${\bf a}$ were to be thought of as ${\bf 0}$). This suggests a natural sub-question of your question:

> Is there some sentence $\varphi$ in the language of partial order such that $\mathcal{D}\models\varphi$ but $\mathcal{D}\_{\ge\_T{\bf a}}\models\neg\varphi$ for all sufficiently large degrees ${\bf a}$?

Here $\mathcal{D}$ (resp. $\mathcal{D}\_{\ge\_T{\bf a}}$) is the partial order of Turing degrees (resp. Turing degrees $\ge\_T{\bf a}$) under $\ge\_T$. The language of partial order may seem quite limited at first, but it's actually *extremely* expressive; in particular, contra early expectations it is known that [$\mathcal{D}$ has a highly complicated first-order theory and at most countably many automorphisms](https://math.berkeley.edu/%7Eslaman/talks/sw.pdf) *(and it's conjectured that $\mathcal{D}$ is rigid, a [proposed counterexample by Cooper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.1511&rep=rep1&type=pdf) being generally considered to be flawed)*.

* Note that the question above treats a *precise notion* of (non-)relativization, which I think is rather neat! And per the expressivity of $\mathcal{D}$, it's not too restrictive either.

**The answer to this sub-question turns out to be yes**; this is a consequence of Theorem 3.1 of [Nerode and Shore](https://core.ac.uk/download/pdf/82225234.pdf) *(although they don't quite phrase it this way - also, they include a symbol for the Turing jump, but [it was later shown that the jump is definable from the partial order structure alone](https://math.berkeley.edu/%7Eslaman/papers/jump.pdf))*.

The proof gives such a $\varphi$, but we can also show the existence of such a $\varphi$ using their theorem as a blackbox ... via the cone theorem! Suppose no such $\varphi$ existed; then for each $\varphi\in Th(\mathcal{D})$, the set $T\_\varphi=\{{\bf a}: \mathcal{D}\_{\ge{\bf a}}\models\varphi\}$ contains a cone. But since the intersection of countably many cones in $\mathcal{D}$ is again a cone, we get a cone of ${\bf a}$ in $\bigcap\_{\varphi\in Sent} T\_\varphi$ - in other words, a cone of degrees whose upper cones are elementarily equivalent to $\mathcal{D}$, contradicting Nerode/Shore.

> **Comments:**
> **username_2**: I like it! I think the notion of relativization though, rather than restrict to the cone above a, should look at the Turing$^a$ degrees. That is, allow the reductions themselves to access the oracle. Then a automatically has the same degree as 0 (achieving what you wanted), and now I think more results relativize in this sense (?).  

---

### Answer by username_7 on 2017-03-27. Score: 3

This is something I've often wondered about as well!

If by "results in computability theory," you mean results that are invariant with respect to the choice of machine model (Turing machines, RAM machines, etc.), then I don't know a single example of such a result, and I definitely would've remembered if I'd seen one.

The closest I can suggest to an answer is: I think there are many interesting questions in computability theory that might depend on the machine model. For example: is the Busy Beaver function, with its usual definition in terms of Turing machines, infinitely often odd? Is the value of BB(20) independent of ZFC? Whatever the answers to these questions are, they could surely be different for relativized analogues of the BB function.

> **Comments:**
> **username_6**: Examples of non-relativizing statements can be found coming from degree theory (per my answer); of course, whether these are natural or not is another story.  

---

