A basis theorem for classes of positive measure and jump inversion for random reals
Authors:
Rod Downey and Joseph S. Miller
Journal:
Proc. Amer. Math. Soc. 134 (2006), 283288
MSC (2000):
Primary 03D28, 68Q30
Published electronically:
August 11, 2005
MathSciNet review:
2170569
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We extend the Shoenfield jump inversion theorem to the members of any class with nonzero measure; i.e., for every set , there is a real such that . In particular, we get jump inversion for random reals.
 1.
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
(56 #5247)
 2.
Douglas
Cenzer, Π⁰₁ classes in computability theory,
Handbook of computability theory, Stud. Logic Found. Math., vol. 140,
NorthHolland, Amsterdam, 1999, pp. 37–85. MR 1720779
(2001d:03110), http://dx.doi.org/10.1016/S0049237X(99)800184
 3.
R. Downey and D. Hirschfeldt, Algorithmic randomness and complexity, SpringerVerlag, 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. 23,
186–192. MR
859105 (87k:03043), http://dx.doi.org/10.1016/S00199958(86)800043
 7.
Carl
G. Jockusch Jr. and Robert
I. Soare, Π⁰₁ classes and
degrees of theories, Trans. Amer. Math.
Soc. 173 (1972),
33–56. MR
0316227 (47 #4775), http://dx.doi.org/10.1090/S00029947197203162270
 8.
S. Kautz, Degrees of random sets, Ph.D. Dissertation, Cornell University, 1991.
 9.
Antonín
Kučera, Measure, Π⁰₁classes and complete
extensions of 𝑃𝐴, Recursion theory week (Oberwolfach,
1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985,
pp. 245–259. MR 820784
(87e:03102), http://dx.doi.org/10.1007/BFb0076224
 10.
Antonín
Kučera, On the use of diagonally nonrecursive
functions, Logic Colloquium ’87 (Granada, 1987) Stud. Logic
Found. Math., vol. 129, NorthHolland, Amsterdam, 1989,
pp. 219–239. MR 1015310
(91c:03037), http://dx.doi.org/10.1016/S0049237X(08)701307
 11.
S. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. Dissertation, University of Illinois, Urbana, 1981.
 12.
Ming
Li and Paul
Vitányi, An introduction to Kolmogorov complexity and its
applications, Texts and Monographs in Computer Science,
SpringerVerlag, New York, 1993. MR 1238938
(94j:68121)
 13.
Per
MartinLö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
0’, Bull. Amer. Math. Soc. 67 (1961), 416–419. MR 0126380
(23 #A3676), http://dx.doi.org/10.1090/S000299041961106526
 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,
Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
 19.
Frank Stephan, MartinLöf random sets and PAcomplete sets, to appear.
 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), 37. MR 0446930 (56:5247)
 2.
 Douglas Cenzer, classes in computability theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, NorthHolland, Amsterdam, 1999, pp. 3785. MR 1720779 (2001d:03110)
 3.
 R. Downey and D. Hirschfeldt, Algorithmic randomness and complexity, SpringerVerlag, 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), 159160. MR 0098025 (20:4488)
 6.
 Péter Gács, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 23, 186192. MR 0859105 (87k:03043)
 7.
 Carl G. Jockusch, Jr. and Robert I. Soare, classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 3356. MR 0316227 (47:4775)
 8.
 S. Kautz, Degrees of random sets, Ph.D. Dissertation, Cornell University, 1991.
 9.
 Antonín Kucera, Measure, classes and complete extensions of , Recursion theory week (Oberwolfach, 1984), Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245259. MR 0820784 (87e:03102)
 10.
 , On the use of diagonally nonrecursive functions, Logic Colloquium '87 (Granada, 1987), Stud. Logic Found. Math., vol. 129, NorthHolland, Amsterdam, 1989, pp. 219239. 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, SpringerVerlag, New York, 1993. MR 1238938 (94j:68121)
 13.
 Per MartinLöf, The definition of random sequences, Information and Control 9 (1966), 602619. 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), 416419. 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. 117121. MR 0141595 (25:4993)
 17.
 J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644653. MR 0105355 (21:4097)
 18.
 Robert I. Soare, Recursively enumerable sets and degrees, SpringerVerlag, Berlin, 1987. MR 0882921 (88m:03003)
 19.
 Frank Stephan, MartinLöf random sets and PAcomplete sets, to appear.
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2000):
03D28,
68Q30
Retrieve articles in all journals
with MSC (2000):
03D28,
68Q30
Additional Information
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, U3009, 196 Auditorium Road, Storrs, Connecticut 06269
Email:
joseph.s.miller@gmail.com
DOI:
http://dx.doi.org/10.1090/S0002993905079013
PII:
S 00029939(05)079013
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.
Article copyright:
© Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
