Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Measures and their random reals


Authors: Jan Reimann and Theodore A. Slaman
Journal: Trans. Amer. Math. Soc. 367 (2015), 5081-5097
MSC (2010): Primary 03D32, 68Q30
DOI: https://doi.org/10.1090/S0002-9947-2015-06184-4
Published electronically: January 30, 2015
MathSciNet review: 3335411
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the randomness properties of reals with respect to arbitrary probability measures on Cantor space. We show that every non-computable real is non-trivially random with respect to some measure. The probability measures constructed in the proof may have atoms. If one rules out the existence of atoms, i.e. considers only continuous measures, it turns out that every non-hyperarithmetical real is random for a continuous measure. On the other hand, examples of reals not random for any continuous measure can be found throughout the hyperarithmetical Turing degrees.


References [Enhancements On Off] (What's this?)

  • [1] Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, and Stanley S. Wainer, Members of countable $ \Pi ^0_1$ classes: Special issue: second Southeast Asian logic conference (Bangkok, 1984), Ann. Pure Appl. Logic 31 (1986), no. 2-3, 145-163. MR 854290 (88e:03064), https://doi.org/10.1016/0168-0072(86)90067-9
  • [2] A. Day, Randomness and computability, PhD thesis, Victoria University of Wellington, 2011.
  • [3] Adam R. Day and Joseph S. Miller, Randomness for non-computable measures, Trans. Amer. Math. Soc. 365 (2013), no. 7, 3575-3591. MR 3042595, https://doi.org/10.1090/S0002-9947-2013-05682-6
  • [4] Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin's halting probability, J. Math. Log. 5 (2005), no. 2, 167-192. MR 2188515 (2007e:68031), https://doi.org/10.1142/S0219061305000468
  • [5] Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288 (2012g:03001)
  • [6] Péter Gács, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 2-3, 186-192. MR 859105 (87k:03043), https://doi.org/10.1016/S0019-9958(86)80004-3
  • [7] Peter Gács, Uniform test of algorithmic randomness over a general space, Theoret. Comput. Sci. 341 (2005), no. 1-3, 91-137. MR 2159646 (2006m:68057), https://doi.org/10.1016/j.tcs.2005.03.054
  • [8] Eli Glasner, Ergodic theory via joinings, Mathematical Surveys and Monographs, vol. 101, American Mathematical Society, Providence, RI, 2003. MR 1958753 (2004c:37011)
  • [9] Paul R. Halmos, Measure theory, D. Van Nostrand Company, Inc., New York, N. Y., 1950. MR 0033869 (11,504d)
  • [10] Mathieu Hoyrup and Cristóbal Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. and Comput. 207 (2009), no. 7, 830-847. MR 2519075 (2011b:03066), https://doi.org/10.1016/j.ic.2008.12.009
  • [11] S. M. Kautz, Degrees of random sequences, PhD thesis, Cornell University, 1991.
  • [12] Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597 (96e:03057)
  • [13] B. Kjos-Hanssen and A. Montalbán, Personal communication, March 2005.
  • [14] G. Kreisel, Analysis of the Cantor-Bendixson theorem by means of the analytic hierarchy, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys. 7 (1959), 621-626 (unbound insert) (English, with Russian summary). MR 0118673 (22 #9444)
  • [15] Antonín Kučera, Measure, $ \Pi ^0_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 820784 (87e:03102), https://doi.org/10.1007/BFb0076224
  • [16] L. A. Levin, The concept of a random sequence, Dokl. Akad. Nauk SSSR 212 (1973), 548-550 (Russian). MR 0366096 (51 #2346)
  • [17] L. A. Levin, Uniform tests for randomness, Dokl. Akad. Nauk SSSR 227 (1976), no. 1, 33-35 (Russian). MR 0414222 (54 #2325)
  • [18] Leonid A. Levin, Randomness conservation inequalities: information and independence in mathematical theories, Inform. and Control 61 (1984), no. 1, 15-37. MR 764286 (86h:68081), https://doi.org/10.1016/S0019-9958(84)80060-1
  • [19] Richard Mansfield, Perfect subsets of definable sets of real numbers, Pacific J. Math. 35 (1970), 451-457. MR 0280380 (43 #6100)
  • [20] Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602-619. MR 0223179 (36 #6228)
  • [21] Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam, 1980. MR 561709 (82e:03002)
  • [22] Andrei A. Muchnik, Alexei L. Semenov, and Vladimir A. Uspensky, Mathematical metaphysics of randomness, Theoret. Comput. Sci. 207 (1998), no. 2, 263-317. MR 1643438 (99h:68091), https://doi.org/10.1016/S0304-3975(98)00069-3
  • [23] André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883 (2011i:03003)
  • [24] David B. Posner and Robert W. Robinson, Degrees joining to $ {\bf0}^{\prime } $, J. Symbolic Logic 46 (1981), no. 4, 714-722. MR 641485 (83c:03040), https://doi.org/10.2307/2273221
  • [25] Jan Reimann, Effectively closed sets of measures and randomness, Ann. Pure Appl. Logic 156 (2008), no. 1, 170-182. MR 2474448 (2010a:03043), https://doi.org/10.1016/j.apal.2008.06.015
  • [26] J. Reimann and T. A. Slaman, Randomness for continuous measures, in preparation.
  • [27] Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554 (32 #4013)
  • [28] Claus-Peter Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin-New York, 1971. MR 0414225 (54 #2328)
  • [29] Robert I. Soare, Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. MR 882921 (88m:03003)
  • [30] Robert M. Solovay, On the cardinality of $ \sum _{2}^{1}$ sets of reals, Foundations of Mathematics (Symposium Commemorating Kurt Gödel, Columbus, Ohio, 1966), Springer, New York, 1969, pp. 58-73. MR 0277382 (43 #3115)
  • [31] Klaus Weihrauch, Computable analysis: An introduction, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. MR 1795407 (2002b:03129)
  • [32] W. Hugh Woodin, A tt version of the Posner-Robinson theorem, Computational prospects of infinity. Part II. Presented talks, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15, World Sci. Publ., Hackensack, NJ, 2008, pp. 355-392. MR 2449474 (2009j:03067), https://doi.org/10.1142/9789812796554_0019
  • [33] A. K. Zvonkin and L. A. Levin, The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms, Uspehi Mat. Nauk 25 (1970), no. 6(156), 85-127 (Russian). MR 0307889 (46 #7004)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D32, 68Q30

Retrieve articles in all journals with MSC (2010): 03D32, 68Q30


Additional Information

Jan Reimann
Affiliation: Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
Email: reimann@math.psu.edu

Theodore A. Slaman
Affiliation: Department of Mathematics, University of California at Berkeley, Berkeley, California 94720
Email: slaman@math.berkeley.edu

DOI: https://doi.org/10.1090/S0002-9947-2015-06184-4
Received by editor(s): February 19, 2008
Received by editor(s) in revised form: May 14, 2013
Published electronically: January 30, 2015
Additional Notes: The first author was partially supported by NSF grants DMS-0801270 and DMS-1201263.
The second author was partially supported by NSF grants DMS-0501167 and DMS-1001551.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society