Proceedings of the American Mathematical Society

A basis theorem for $\Pi_1^0$ classes of positive measure and jump inversion for random reals

Author(s): Rod Downey; Joseph S. Miller
Journal: Proc. Amer. Math. Soc. 134 (2006), 283-288.
MSC (2000): Primary 03D28, 68Q30
Posted: August 11, 2005
Retrieve article in: PDF

Abstract: We extend the Shoenfield jump inversion theorem to the members of any $\Pi^0_1$ class $\+ 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\+ P$ such that $A'\equiv_T S$ . In particular, we get jump inversion for $\Delta^0_2$

-random reals.

1.: M. M. Arslanov, R. F. Nadyrov, and V. D. Solovev, A criterion for the completeness of recursively enumerable sets, and some generalizations of a fixed point theorem, Izv. Vyss. Ucebn. Zaved. Matematika 4 (179) (1977), 3-7. MR 0446930 (56:5247)
2.: Douglas Cenzer, $\Pi\sp 0\sb 1$ classes in computability theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 37-85. MR 1720779 (2001d:03110)
3.: R. Downey and D. Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, Berlin, to appear.
4.: Rodney G. Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bulletin of Symbolic Logic, to appear.
5.: Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symb. Logic 22 (1957), 159-160. MR 0098025 (20:4488)
6.: Péter Gács, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 2-3, 186-192. MR 0859105 (87k:03043)
7.: Carl G. Jockusch, Jr. and Robert I. Soare, $\Pi \sp{0}\sb{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33-56. MR 0316227 (47:4775)
8.: S. Kautz, Degrees of random sets, Ph.D. Dissertation, Cornell University, 1991.
9.: Antonín Kucera, Measure, $\Pi\sp 0\sb 1$ -classes and complete extensions of ${\rm PA}$ , Recursion theory week (Oberwolfach, 1984), Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245-259. MR 0820784 (87e:03102)
10.: -, 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 (91c:03037)
11.: S. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. Dissertation, University of Illinois, Urbana, 1981.
12.: M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993. MR 1238938 (94j:68121)
13.: Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602-619. MR 0223179 (36:6228)
14.: Joseph S. Miller and Liang Yu, On initial segment complexity and degrees of randomness, to appear.
15.: Gerald E. Sacks, A minimal degree less than , Bull. Amer. Math. Soc. 67 (1961), 416-419. MR 0126380 (23:A3676)
16.: 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 (25:4993)
17.: J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644-653. MR 0105355 (21:4097)
18.: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987. MR 0882921 (88m:03003)
19.: Frank Stephan, Martin-Löf random sets and PA-complete sets, to appear.

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D28, 68Q30

Rod Downey
Affiliation: School of Mathematical and Computing Sciences, Victoria University, P.O. Box 600, Wellington, New Zealand
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
Email: joseph.s.miller@gmail.com

DOI: 10.1090/S0002-9939-05-07901-3
PII: S 0002-9939(05)07901-3
Received by editor(s): April 13, 2004
Received by editor(s) in revised form: June 30, 2004
Posted: 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 of article: Copyright 2005, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS