patternMinor
Turing degree incomparable with any countable-ordinal jump of another Turing degree?
Viewed 0 times
degreejumpordinalwithanyincomparablecountableanotherturing
Problem
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
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
Solution
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
-
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
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 ge
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
-
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
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 ge
Context
StackExchange Computer Science Q#84575, answer score: 7
Revisions (0)
No revisions yet.