7
$\begingroup$

Among the Turing degrees are degrees of the form $0^n$, e.g. $0$, $0'$, $0''$, etc.


I'll just prove this quick for completeness' sake. Hopefully nobody has any qualms with this short proof:

Lemma: Any countable set of sets of natural numbers can be encoded as a single set of natural numbers, such that each original set can be decoded by a Turing machine.

Proof: Let $S$ be our set of sets, so that each $S_n \in S$ is a set of natural numbers. Define $O = \{k \cdot 2^{n+1} - 2^n | k \in S_n \}$.

Thus, $S_n = \{ k | k \cdot 2^{n+1} - 2^n \in O \}$. Clearly, for each $S_n$ there is a Turing machine that computes $S_n$ given an oracle for $O$.

Minor Theorem: Any countable set of Turing degrees has an upper bound.

Proof: Let $D$ be our countable set of degrees. Thus, each $D_n \in D$ is a countable set of sets of natural numbers. Let $E_n$ be a set of natural numbers that encodes the elements of $D_n$, and let $E$ be a set of natural numbers that encodes all $E_n$.

Any set in any degree $D_n$ can be computed by decoding $E$ twice in succession, so as Turing degrees, $D_n \leq [E]$. Therefore $[E]$ is an upper bound of $D$.


Let $0^\omega$ be the upper bound of $\{0, 0', 0'', ... \}$ as described just above. Of course, we can take the Turing jump of $0^\omega$ to obtain $(0^\omega)'$ which we will write $0^{\omega + 1}$, and so on to obtain the countable set of Turing degrees, $0^{\omega + n}$. Taking the upper bound of these, we obtain $0^{2 \omega}$, and of course, furthermore taking the upper bound of $\{ 0, 0^{\omega}, 0^{2 \omega}, ... \}$ we obtain the Turing degree $0^{\omega^\omega}$. Generally for any countable ordinal $\beta$, we can define a degree $0^\beta$.

It is known that for every nonzero Turing degree $a$, there is a Turing degree $b$ with which it is incomparable. However, for any Turing degree $a$ (and I'm particularly interested in $0'$), is there a Turing degree $b$ that is incomparable with $a^\beta$ for all countable ordinals $\beta$?

$\endgroup$
  • $\begingroup$ In your last sentence, you probably want to say "incomparable with $\alpha^\beta$ for all countable $\beta$. $\endgroup$ – Ariel Nov 28 '17 at 6:22
  • 1
    $\begingroup$ @Ariel Good point - I take it you're referring to the fact that $a$ and $\alpha$ look very similar. $\endgroup$ – jcarpenter2 Nov 28 '17 at 6:31
  • $\begingroup$ Oh, I guess you're right since I thought you were using the same character. Phones... $\endgroup$ – Ariel Nov 28 '17 at 6:33
6
$\begingroup$

The answer to your question is a resounding: IT DEPENDS! This takes us into some set theory, which - while interesting - is a bit off the beaten track perhaps for CS; to address this, I've made the first part of my answer strictly about the computability theory, and then added a separate section on the set theory side of things.


Before we can even address your question, it turns out that there is a surprising subtlety here:

For $\alpha$ an arbitrary countable ordinal, it is not always clear how to define $0^{(\alpha)}$.

This is treated variously at mathoverflow and math.stackexchange; what I've written below should be self-contained, however.

The issue is that of presentations (or, essentially identically, fundamental sequences). In general, suppose $\lambda$ is a limit ordinal, we've defined $0^{(\alpha)}$ for each $\alpha<\lambda$, and we want to define $0^{(\lambda)}$ as the set $$Z_\lambda=\{(i, \alpha):i\in\omega,\alpha<\lambda, i\in0^{(\alpha)}\}.$$ However, this set isn't a set of natural numbers. Fixing a map $f:\lambda\rightarrow\omega$, we can "interpret" $Z_\lambda$ along $f$ in a natural way: $$Z_\lambda^f=\{(i, j): i\in\omega, j\in ran(f), i\in 0^{(f^{-1}(j))}\}.$$ Here's the problem: what $f$ do we want to use? Different choices of $f$ will yield different sets, and potentially different Turing degrees. This wasn't an issue in cooking up $0^{(\omega)}$, since there was only one obvious thing to do, but when we try to go further the problem rears its head.

As a quick aside, there's an alternate approach here which seems promising at first: simply define $0^{(\lambda)}$ for $\lambda$ a limit ordinal to be the least upper bound of $\{0^{(\alpha)}:\alpha<\lambda\}$! Combined with the clause $0^{(\beta+1)}=(0^{(\beta)})'$, this would seem to give a recursive definition which works for all countable ordinals. However, it turns out that this entire attack is built on a false assumption: $0^{(\omega)}$ is not the least upper bound of $\{0^{(n)}:n<\omega\}$ in the Turing degrees, and in fact nontrivial least upper bounds never exist (this is the "exact pair theorem" of Spector). So we do necessarily have to do some work.

At this point it's a good idea to go back and try to develop a theory of iterated jumps "from scratch" as it were. This is hyperarithmetic theory due to Kleene, and is presented in detail in the beginning of Sacks' book; I'll just give a rapid (and ahistorical) gloss.

The sets $Z_\lambda^f$ defined above are intuitively what we get if we iterate the jump not along a mere ordinal but along an explicit well-ordering of a set of natural numbers (that is, a copy of the ordinal "labelled" appropriately). To make this precise, suppose $R$ is a well-ordering of some set $D$ of natural numbers (note that $R$ determines $D$). It's easy to show that there is a unique set $J_R$ of ordered pairs of natural numbers with the following properties:

  • $(x,y)\in J_R$ only if $x\in D$.

  • If $u$ is the $R$-successor of $v$, then $(u, y)\in J_R$ iff $\Phi_y^{J_R[v]}$ halts, where $J_R[v]=\{z: (v, z)\in J_R\}$.

  • If $u$ is an $R$-limit, then $J_R[u]=\{(v, y): v<_Ru, y\in J_R[v]\}.$

This is what you get, intuitively, if you iterate the jump along $R$ starting with the emptyset (the fact that we started with the emptyset was built in secretly to the last bulletpoint, since if $u$ is the $R$-least element then $J_R[u]$ is forced to be empty; we can relativize by starting with a non-empty column).

If $R$ is "nice," this is extremely well-behaved:

Suppose $R_0, R_1$ are well-orderings of sets $D_0, D_1$ of natural numbers such that each $R_i$ is computable, their respective successor operations are computable, and their respective sets of limit elements are computable. Then if $R_0$ and $R_1$ have the same ordertype we have $J_{R_0}\equiv_TJ_{R_1}$.

The conditions above are stronger than merely demanding that the orderings be computable, but in fact every computable well-ordering is (non-computably!) order-isomorphic to such a "nice" computable well-ordering. So based on this, it makes sense to define $0^{(\alpha)}$ for $\alpha$ a "computable ordinal" as the unique Turing degree of a "jump sequence" along a "nice presentation" of $\alpha$. More generally, for any Turing degree $d$ it makes sense to talk about the degree $d^{(\alpha)}$ for any ordinal $\alpha$ with an $d$-computable presentation.

The sets computable from $0^{(\alpha)}$ for some computable $\alpha$ are the hyperarithmetic sets; hyperarithmeticity has a number of equivalent characterizations and is one of the fundamental notions of modern computability theory, and is also very important in descriptive set theory. But this only gets us through countably many ordinals; most countable ordinals don't have computable presentations! The supremum of the computable ordinals is denoted "$\omega_1^{CK}$" - it's much bigger than other popular ordinals like $\epsilon_0$, $\Gamma_0$, etc., but still countable, and indeed quite small among countable ordinals from various perspectives within logic. And it's not very hard to cook up two Turing degrees, neither of which is hyperarithmetic relative to the other, since we've only reached "countably high." Can we do better?

To go further, we need to get into set theory, so I'll put a horizontal line here:


Alright, let's talk about set theory. It turns out that we can continue the jump in a natural way past $\omega_1^{CK}$. However, this gets complicated pretty quickly. The idea comes from Godel's constructible universe, the idea being that each additional step in the $L$-hierarchy is like taking $\omega$-many jumps of what you have so far (since you're looking at everything first-order definable in what you have so far). Teasing this out precisely gets us the notion of mastercodes. I won't define them precisely here, but Hodes has an excellent paper on the topic.

Now, mastercodes have many subtle and annoying features,$^*$ but they let us unproblematically(ish) iterate the jump starting with the emptyset all the way up to $\omega_1^L$, the first ordinal which the constructible universe thinks is uncountable. (More generally, given a degree $d$ we can unproblemantically "do mastercodes" up to $\omega_1^{L[d]}$, the first orderinal that the smallest inner model of ZFC containing $d$ thinks is uncountable.)

If the constructible universe happens to be all there is - that is, if V=L - then we're peachy:

Every real in $L$ is computable from some $0^{(\alpha)}$ - in the sense of mastercodes - for some $\alpha<\omega_1^L$.

More generally, "reachable via mastercodes" just gives us the notion of relative constructibility: $x\le_Ly$ iff $x\in L[y]$ iff $x$ is in every inner model containing $y$ iff $x$ is computable from some $y^{(\alpha)}$ for $\alpha<\omega_1^{L[y]}$.

However, it's quite possible - that is, consistent relative to ZFC - that $V$ is very far from $L$. For example, $\omega_1^L$ might be countable, and indeed the "real" $\omega_1$ could appear to be quite large from the perspective of $L$! Indeed, it turns out that strong set-theoretic hypotheses can prevent us from getting very far at all with this idea:

Broadly speaking, if large cardinals exist then there are no easily-definable increasing $\omega_1$-sequences of Turing degrees. (This is parameterized: ramp up the large cardinals and we get more and more necessary undefinability.)

Even assuming $\omega_1^L=\omega_1$ and ruling out anything (like large cardinals) that will bump up consistency strength, the $\le_L$-degrees could still be quite wild, via forcing. In particular, if $c_0, c_1$ are mutually Cohen generic (say) over $L$, then $c_0\not\in L[c_1]$ and $c_1\not\in L[c_0]$; we can get Cohen generics without changing $\omega_1$, so in this case neither is reachable from the other via countably many jumps, assuming we buy the "mastercode picture" (and if we don't, we need to cook up another picture!).


$^*$They really only make sense at the level of degrees, not sets of naturals, so in that sense the "presentation issue" hasn't been avoided; see the middle of page 207 of Hodes' paper. More obnoxiously, Theorem 8 (and see the bottom of page 204 for the relevant definition) shows that ... OK, there's just no nice way to say this, and I can't put it off anymore: mastercode-jumps aren't fully monotone. We can have $\alpha<\beta$ but $a^{(\beta)}=0^{(\alpha)}$ for some degree $a$. Aaargh.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.