Skip to main content
added assumption of Projective Determinacy
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Let $$ A=\{x \mid x\ \equiv_T\ j(y)\quad \text{for some set } y\}, $$ where $j(y)$ is the $\Delta^1_{2n+1}$-jump of $y$, for $n\ge 1$.

Then $A$ is Borel, since $y$ is definable from $x$. SinceSince $x\ <_T\ j(x)$ for all $x$, $A$ is cofinal in the Turing degrees. Hence by Borelassuming Projective Determinacy, $A$ must contain a cone in the Turing degrees.

Kechris showed a restriction on possible jump inversion theorems in the $\Delta^1_{2n+1}$-degrees (see Kastanas, The jump inversion theorem for $Q_{2n+1}$ degrees, Proc. AMS 1984). So I am guessing that no base for a cone contained in $A$ is known. But perhapsI guess this is closer to set theory than recursion theory.

EDITEDITS: Changed the example since the $\omega$-jump or hyperjump do not work, by MacIntyre, Transfinite extensions of Friedberg's completeness theorem, J. Symbolic Logic, 19771977; and added the assumption PD.

Let $$ A=\{x \mid x\ \equiv_T\ j(y)\quad \text{for some set } y\}, $$ where $j(y)$ is the $\Delta^1_{2n+1}$-jump of $y$, for $n\ge 1$.

Then $A$ is Borel, since $y$ is definable from $x$. Since $x\ <_T\ j(x)$ for all $x$, $A$ is cofinal in the Turing degrees. Hence by Borel Determinacy, $A$ must contain a cone in the Turing degrees.

Kechris showed a restriction on possible jump inversion theorems in the $\Delta^1_{2n+1}$-degrees (see Kastanas, The jump inversion theorem for $Q_{2n+1}$ degrees, Proc. AMS 1984). So I am guessing that no base for a cone contained in $A$ is known. But perhaps this is closer to set theory than recursion theory.

EDIT: Changed the example since the $\omega$-jump or hyperjump do not work, by MacIntyre, Transfinite extensions of Friedberg's completeness theorem, J. Symbolic Logic, 1977.

Let $$ A=\{x \mid x\ \equiv_T\ j(y)\quad \text{for some set } y\}, $$ where $j(y)$ is the $\Delta^1_{2n+1}$-jump of $y$, for $n\ge 1$.

Since $x\ <_T\ j(x)$ for all $x$, $A$ is cofinal in the Turing degrees. Hence assuming Projective Determinacy, $A$ must contain a cone in the Turing degrees.

Kechris showed a restriction on possible jump inversion theorems in the $\Delta^1_{2n+1}$-degrees (see Kastanas, The jump inversion theorem for $Q_{2n+1}$ degrees, Proc. AMS 1984). So I am guessing that no base for a cone contained in $A$ is known. But I guess this is closer to set theory than recursion theory.

EDITS: Changed the example since the $\omega$-jump or hyperjump do not work, by MacIntyre, Transfinite extensions of Friedberg's completeness theorem, J. Symbolic Logic, 1977; and added the assumption PD.

changed the example
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Let $$ A=\{x \mid x\ \equiv_T\ y^{(\omega)}\quad \text{for some set } y\}, $$$$ A=\{x \mid x\ \equiv_T\ j(y)\quad \text{for some set } y\}, $$ where $y^{(\omega)}$$j(y)$ is the $\omega$$\Delta^1_{2n+1}$-jump (arithmetical jump) of $y$, for $n\ge 1$.

Then $A$ is Borel, since we may assume $y\ \le_T\ x$$y$ is definable from $x$. Since $x\ <_T\ x^{(\omega)}$$x\ <_T\ j(x)$ for all $x$, $A$ is cofinal in the Turing degrees. Hence by Borel Determinacy, $A$ must contain a cone in the Turing degrees.

BasedKechris showed a restriction on possible jump inversion theorems in the following it seems to be not known what a base of such a cone might be.

Let $\le_a$ denote arithmetical reducibility and $\equiv_a$ arithmetical equivalence; so$\Delta^1_{2n+1}$-degrees $x\ \le_a\ y$ if(see Kastanas, $x\ \le_T\ y^{(n)}$ for someThe jump inversion theorem for $n$. MacIntyre$Q_{2n+1}$ (Transfinite extensions of Friedberg's completeness criteriondegrees, JProc. of Symbolic Logic, 1977AMS 1984) showed that $$ B=\{x \mid x\ \equiv_a\ y^{(\omega)}\quad \text{for some set } y\}. $$ coincides with cone above $0^{(\omega)}$ in the arithmetical degrees. So if we start with a $z\ \ge_T\ 0^{(\omega)}$ then certainly $z\ \ge_a\ 0^{(\omega)}$, and so $z\ \equiv_a\ x$I am guessing that no base for some $x\in B$, but this does not imply $z\ \equiv_T\ x$.a cone contained in (See e$A$ is known.g But perhaps this is closer to set theory than recursion theory.

EDIT: Changed the proof of MacIntyre's result in Odifreddiexample since the $\omega$-jump or hyperjump do not work, by MacIntyre, Forcing and reducibilitiesTransfinite extensions of Friedberg's completeness theorem, J. of Symbolic Logic, 1983, Prop. 4.2.)

Actually we even have for all $x$, $y$, $$ x\ \equiv_a\ y \quad\Longrightarrow\quad x^{(\omega)}\ \equiv_T \ y^{(\omega)} $$ but this doesn't seem to help either 1977.

Let $$ A=\{x \mid x\ \equiv_T\ y^{(\omega)}\quad \text{for some set } y\}, $$ where $y^{(\omega)}$ is the $\omega$-jump (arithmetical jump) of $y$.

Then $A$ is Borel, since we may assume $y\ \le_T\ x$. Since $x\ <_T\ x^{(\omega)}$ for all $x$, $A$ is cofinal in the Turing degrees. Hence by Borel Determinacy, $A$ must contain a cone in the Turing degrees.

Based on the following it seems to be not known what a base of such a cone might be.

Let $\le_a$ denote arithmetical reducibility and $\equiv_a$ arithmetical equivalence; so $x\ \le_a\ y$ if $x\ \le_T\ y^{(n)}$ for some $n$. MacIntyre (Transfinite extensions of Friedberg's completeness criterion, J. of Symbolic Logic, 1977) showed that $$ B=\{x \mid x\ \equiv_a\ y^{(\omega)}\quad \text{for some set } y\}. $$ coincides with cone above $0^{(\omega)}$ in the arithmetical degrees. So if we start with a $z\ \ge_T\ 0^{(\omega)}$ then certainly $z\ \ge_a\ 0^{(\omega)}$, and so $z\ \equiv_a\ x$ for some $x\in B$, but this does not imply $z\ \equiv_T\ x$. (See e.g. the proof of MacIntyre's result in Odifreddi, Forcing and reducibilities, J. of Symbolic Logic, 1983, Prop. 4.2.)

Actually we even have for all $x$, $y$, $$ x\ \equiv_a\ y \quad\Longrightarrow\quad x^{(\omega)}\ \equiv_T \ y^{(\omega)} $$ but this doesn't seem to help either.

Let $$ A=\{x \mid x\ \equiv_T\ j(y)\quad \text{for some set } y\}, $$ where $j(y)$ is the $\Delta^1_{2n+1}$-jump of $y$, for $n\ge 1$.

Then $A$ is Borel, since $y$ is definable from $x$. Since $x\ <_T\ j(x)$ for all $x$, $A$ is cofinal in the Turing degrees. Hence by Borel Determinacy, $A$ must contain a cone in the Turing degrees.

Kechris showed a restriction on possible jump inversion theorems in the $\Delta^1_{2n+1}$-degrees (see Kastanas, The jump inversion theorem for $Q_{2n+1}$ degrees, Proc. AMS 1984). So I am guessing that no base for a cone contained in $A$ is known. But perhaps this is closer to set theory than recursion theory.

EDIT: Changed the example since the $\omega$-jump or hyperjump do not work, by MacIntyre, Transfinite extensions of Friedberg's completeness theorem, J. Symbolic Logic, 1977.

Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Let $$ A=\{x \mid x\ \equiv_T\ y^{(\omega)}\quad \text{for some set } y\}, $$ where $y^{(\omega)}$ is the $\omega$-jump (arithmetical jump) of $y$.

Then $A$ is Borel, since we may assume $y\ \le_T\ x$. Since $x\ <_T\ x^{(\omega)}$ for all $x$, $A$ is cofinal in the Turing degrees. Hence by Borel Determinacy, $A$ must contain a cone in the Turing degrees.

Based on the following it seems to be not known what a base of such a cone might be.

Let $\le_a$ denote arithmetical reducibility and $\equiv_a$ arithmetical equivalence; so $x\ \le_a\ y$ if $x\ \le_T\ y^{(n)}$ for some $n$. MacIntyre (Transfinite extensions of Friedberg's completeness criterion, J. of Symbolic Logic, 1977) showed that $$ B=\{x \mid x\ \equiv_a\ y^{(\omega)}\quad \text{for some set } y\}. $$ coincides with cone above $0^{(\omega)}$ in the arithmetical degrees. So if we start with a $z\ \ge_T\ 0^{(\omega)}$ then certainly $z\ \ge_a\ 0^{(\omega)}$, and so $z\ \equiv_a\ x$ for some $x\in B$, but this does not imply $z\ \equiv_T\ x$. (See e.g. the proof of MacIntyre's result in Odifreddi, Forcing and reducibilities, J. of Symbolic Logic, 1983, Prop. 4.2.)

Actually we even have for all $x$, $y$, $$ x\ \equiv_a\ y \quad\Longrightarrow\quad x^{(\omega)}\ \equiv_T \ y^{(\omega)} $$ but this doesn't seem to help either.