Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T13:34:33.147Z Has data issue: false hasContentIssue false
  • English
  • Français

Limits on jump inversion for strong reducibilities

Published online by Cambridge University Press:  12 March 2014

Barbara F. Csima ,
Rod Downey  and
Keng Meng Ng
Barbara F. Csima
Affiliation:
Department of Pure Mathematics, University of Waterloo, Waterloo, ON, N2L 3G1, Canada, E-mail: [email protected], URL: www.math.uwaterloo.ca/~csima
Rod Downey
Affiliation:
School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, PO BOX 600, Wellington, New Zealand, E-mail: [email protected]
Keng Meng Ng
Affiliation:
University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a δ20 set B >tt ∅′ such that there is no c.e. set A with A′ ≡wttB. We also show that there is a Σ20 set C >tt ∅′ such that there is no δ20 set D with D′ ≡wttC.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 4 , December 2011 , pp. 1287 - 1296
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[And08]Anderson, B., Automorhisms of the truth-table degrees are fixed on some cone, preprint, 2008.Google Scholar
[Coo04]Cooper, S. Barry, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004.Google Scholar
[Dem88]Demuth, O., Remarks on the structure of tt-degrees based on constructive measure theory, Commentationes Mathematicae Universitatis Carolinae, vol. 29 (1988), no. 2, pp. 233–247.Google Scholar
[DR89]Downey, R. and Remmel, J., Classification of degree classes associated with r.e. subspaces, Annals of Pure and Applied Logic, vol. 42 (1989), pp. 105–124.CrossRefGoogle Scholar
[Fri58]Friedberg, R., A criterion for completeness of degrees of unsolvability, this Journal, vol. 22 (1958), pp. 159–160.Google Scholar
[Moh84]Mohrherr, J., Density of a final segment of the truth-table degrees, Pacific Journal of Mathematics, vol. 115 (1984), pp. 409–419.CrossRefGoogle Scholar
[Pos44]Post, E., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[RS08a]Reimann, J. and Slaman, T., Measures and their random reals, preprint, 2008.Google Scholar
[RS08b]Reimann, J. and Slaman, T., Probability measures and effective randomness, preprint, 2008.Google Scholar
[Rob71]Robinson, R., Jump restricted interpolation in the recursively enumerable degrees, Annals of Mathematics, vol. 93 (1971), no. 2, pp. 586–596.CrossRefGoogle Scholar
[Sac63]Sacks, G., Recursive enumerability and the jump operator, 1963, vol. 108.Google Scholar
[Sho59]Shoenfield, J., On degrees of unsolvability, Annals of Mathematics, vol. 69 (1959), pp. 644–653.CrossRefGoogle Scholar
[Soa87]Soare, R., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, 1987.CrossRefGoogle Scholar