A basis theorem for $\Pi _1^0$ classes of positive measure and jump inversion for random reals
HTML articles powered by AMS MathViewer
- by Rod Downey and Joseph S. Miller PDF
- Proc. Amer. Math. Soc. 134 (2006), 283-288 Request permission
Abstract:
We extend the Shoenfield jump inversion theorem to the members of any $\Pi ^0_1$ class $\mathcal {P}\subseteq 2^\omega$ with nonzero measure; i.e., for every $\Sigma ^0_2$ set $S\geq _T\emptyset ’$, there is a $\Delta ^0_2$ real $A\in \mathcal {P}$ such that $A’\equiv _T S$. In particular, we get jump inversion for $\Delta ^0_2$ $1$-random reals.References
- M. M. Arslanov, R. F. Nadyrov, and V. D. Solov′ev, A criterion for the completeness of recursively enumerable sets, and some generalizations of a fixed point theorem, Izv. Vysš. Učebn. Zaved. Matematika 4 (179) (1977), 3–7 (Russian). MR 0446930
- Douglas Cenzer, $\Pi ^0_1$ classes in computability theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 37–85. MR 1720779, DOI 10.1016/S0049-237X(99)80018-4
- R. Downey and D. Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, Berlin, to appear.
- Rodney G. Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bulletin of Symbolic Logic, to appear.
- Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI 10.2307/2964177
- Péter Gács, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 2-3, 186–192. MR 859105, DOI 10.1016/S0019-9958(86)80004-3
- Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- S. Kautz, Degrees of random sets, Ph.D. Dissertation, Cornell University, 1991.
- Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
- Antonín Kučera, On the use of diagonally nonrecursive functions, Logic Colloquium ’87 (Granada, 1987) Stud. Logic Found. Math., vol. 129, North-Holland, Amsterdam, 1989, pp. 219–239. MR 1015310, DOI 10.1016/S0049-237X(08)70130-7
- S. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. Dissertation, University of Illinois, Urbana, 1981.
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993. MR 1238938, DOI 10.1007/978-1-4757-3860-5
- Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 223179, DOI 10.1016/S0019-9958(66)80018-9
- Joseph S. Miller and Liang Yu, On initial segment complexity and degrees of randomness, to appear.
- Gerald E. Sacks, A minimal degree less than $0’$, Bull. Amer. Math. Soc. 67 (1961), 416–419. MR 126380, DOI 10.1090/S0002-9904-1961-10652-6
- Dana Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117–121. MR 0141595
- J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. MR 105355, DOI 10.2307/1970028
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- Frank Stephan, Martin-Löf random sets and PA-complete sets, to appear.
Additional Information
- Rod Downey
- Affiliation: School of Mathematical and Computing Sciences, Victoria University, P.O. Box 600, Wellington, New Zealand
- MR Author ID: 59535
- Email: Rod.Downey@mcs.vuw.ac.nz
- Joseph S. Miller
- Affiliation: Department of Mathematics, University of Connecticut, U-3009, 196 Auditorium Road, Storrs, Connecticut 06269
- MR Author ID: 735102
- Email: joseph.s.miller@gmail.com
- Received by editor(s): April 13, 2004
- Received by editor(s) in revised form: June 30, 2004
- Published electronically: August 11, 2005
- Additional Notes: Both authors were supported by the Marsden Fund of New Zealand. The first author was also partially supported by NSFC Grand International Joint Project Grant No. 60310213 “New Directions in Theory and Applications of Models of Computation” (China).
- Communicated by: Carl G. Jockusch, Jr.
- © Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 134 (2006), 283-288
- MSC (2000): Primary 03D28, 68Q30
- DOI: https://doi.org/10.1090/S0002-9939-05-07901-3
- MathSciNet review: 2170569