×

Local definitions in degree structures: the Turing jump, hyperdegrees and beyond. (English) Zbl 1131.03018

\(D\) is the language of the Turing degrees with \(\leq\), \(\wedge\), and \(\vee\). Its (hyper)jump ideals are downward closed subsets of \(D\) closed also under (hyper)jump and join. The results given improve and extend work of Slaman and Woodin.
Using purely degree-theoretic methods, Shore shows how jump and double jump can be defined in any jump ideal \(I\) that contains \({\mathbf 0}^{(\omega)}\). The relation \({\mathbf x}''\leq {\mathbf y}''\) is defined in \(I\) by a \(\Pi_5\) formula, \({\mathbf w}= {\mathbf x}''\) by a \(\Pi_6\) and a \(\Sigma_6\), and \({\mathbf w}= {\mathbf x}'\) by a \(\Pi_8\) formula. Then every automorphism of \(I\) leaves fixed every degree \(\geq {\mathbf 0}''\). And for relations on \(I\) that are invariant under interchange of degrees with the same double jump or the same join with \({\mathbf 0}''\), those definable over \(I\) are exactly those definable in second-order arithmetic with set quantifiers ranging over sets whose degrees are in \(I\). Analagous conclusions are drawn for the hyperdegrees and their hyperjump ideals. Among open questions are whether the base \({\mathbf 0}''\) in the fixed cone of the result above can be lowered, and whether any jump ideal of \(D\) has uncountably many automorphisms.

MSC:

03D28 Other Turing degree structures
03D30 Other degrees and reducibilities in computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI Euclid Link

References:

[1] DOI: 10.1090/S0002-9939-01-06015-4 · Zbl 0993.03054 · doi:10.1090/S0002-9939-01-06015-4
[2] DOI: 10.2307/2274273 · Zbl 0574.03026 · doi:10.2307/2274273
[3] DOI: 10.1090/S0273-0979-1981-14871-0 · Zbl 0452.03033 · doi:10.1090/S0273-0979-1981-14871-0
[4] Proceedings of the American Mathematical Society 53 pp 445– (1975)
[5] Fundamenta Mathematicae 56 pp 325– (1965)
[6] Recursion theory week pp 141– (1990)
[7] DOI: 10.1002/1521-3870(200101)47:1&lt;3::AID-MALQ3&gt;3.0.CO;2-A · Zbl 0977.03023 · doi:10.1002/1521-3870(200101)47:1<3::AID-MALQ3>3.0.CO;2-A
[8] On a conjecture of Kleene and Post (1993)
[9] DOI: 10.1090/S0273-0979-1990-15923-3 · Zbl 0709.03035 · doi:10.1090/S0273-0979-1990-15923-3
[10] Journal of the London Mathematical Society. Third Series 53 pp 193– (1986)
[11] Proceedings of the American Mathematical Society 84 pp 256– (1982)
[12] Journal of the London Mathematical Society, (3) 24 pp 1– (1981)
[13] Proceedings of the London Mathematical Society 25 pp 586– (1972)
[14] Higher recursion theory (1990) · Zbl 0716.03043
[15] DOI: 10.1090/S0002-9947-1988-0973174-0 · doi:10.1090/S0002-9947-1988-0973174-0
[16] DOI: 10.2307/1969708 · Zbl 0057.24703 · doi:10.2307/1969708
[17] DOI: 10.1007/BF03007659 · Zbl 0372.02023 · doi:10.1007/BF03007659
[18] DOI: 10.1090/S0002-9939-1970-0265154-X · doi:10.1090/S0002-9939-1970-0265154-X
[19] DOI: 10.1016/0003-4843(76)90023-1 · Zbl 0333.02039 · doi:10.1016/0003-4843(76)90023-1
[20] Journal of Mathematical Logic (2007)
[21] Illinois Journal of Mathematics 30 pp 320– (1986)
[22] Proceedings of the international congress on mathematics, Kyoto pp 303– (1991)
[23] DOI: 10.2307/1971028 · Zbl 0349.02035 · doi:10.2307/1971028
[24] DOI: 10.4310/MRL.1999.v6.n6.a10 · Zbl 0958.03029 · doi:10.4310/MRL.1999.v6.n6.a10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.