Effective randomness for continuous measures
HTML articles powered by AMS MathViewer
- by Jan Reimann and Theodore A. Slaman
- J. Amer. Math. Soc. 35 (2022), 467-512
- DOI: https://doi.org/10.1090/jams/980
- Published electronically: August 30, 2021
- HTML | PDF | Request permission
Abstract:
We investigate which infinite binary sequences (reals) are effectively random with respect to some continuous (i.e., non-atomic) probability measure. We prove that for every $n$, all but countably many reals are $n$-random for such a measure, where $n$ indicates the arithmetical complexity of the Martin-Löf tests allowed. The proof rests upon an application of Borel determinacy. Therefore, the proof presupposes the existence of infinitely many iterates of the power set of the natural numbers. In the second part of the paper we present a metamathematical analysis showing that this assumption is indeed necessary. More precisely, there exists a computable function $G$ such that, for any $n$, the statement “All but countably many reals are $G(n)$-random with respect to a continuous probability measure” cannot be proved in $\mathsf {ZFC}^-_n$. Here $\mathsf {ZFC}^-_n$ stands for Zermelo-Fraenkel set theory with the Axiom of Choice, where the Power Set Axiom is replaced by the existence of $n$-many iterates of the power set of the natural numbers. The proof of the latter fact rests on a very general obstruction to randomness, namely the presence of an internal definability structure.References
- Wilhelm Ackermann, Die Widerspruchsfreiheit der allgemeinen Mengenlehre, Math. Ann. 114 (1937), no. 1, 305–315 (German). MR 1513141, DOI 10.1007/BF01594179
- Laurent Bienvenu and Christopher Porter, Strong reductions in effective randomness, Theoret. Comput. Sci. 459 (2012), 55–68. MR 2974238, DOI 10.1016/j.tcs.2012.06.031
- George Boolos and Hilary Putnam, Degrees of unsolvability of constructible sets of integers, J. Symbolic Logic 33 (1968), 497–513. MR 239977, DOI 10.2307/2271357
- Adam R. Day and Joseph S. Miller, Randomness for non-computable measures, Trans. Amer. Math. Soc. 365 (2013), no. 7, 3575–3591. MR 3042595, DOI 10.1090/S0002-9947-2013-05682-6
- K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro, Computability by probabilistic machines, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 183–212. MR 0079550
- Osvald Demuth, Remarks on the structure of tt-degrees based on constructive measure theory, Comment. Math. Univ. Carolin. 29 (1988), no. 2, 233–247. MR 957390
- Keith J. Devlin, Constructibility, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1984. MR 750828, DOI 10.1007/978-3-662-21723-8
- Rod Downey, Andre Nies, Rebecca Weber, and Liang Yu, Lowness and $\Pi ^0_2$ nullsets, J. Symbolic Logic 71 (2006), no. 3, 1044–1052. MR 2251554, DOI 10.2178/jsl/1154698590
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- H. B. Enderton and Hilary Putnam, A note on the hyperarithmetical hierarchy, J. Symbolic Logic 35 (1970), 429–430. MR 290971, DOI 10.2307/2270699
- Harvey M. Friedman, Higher set theory and mathematical practice, Ann. Math. Logic 2 (1970/71), no. 3, 325–357. MR 284327, DOI 10.1016/0003-4843(71)90018-0
- Peter Gács, Uniform test of algorithmic randomness over a general space, Theoret. Comput. Sci. 341 (2005), no. 1-3, 91–137. MR 2159646, DOI 10.1016/j.tcs.2005.03.054
- Ian Robert Haken, Randomizing Reals and the First-Order Consequences of Randoms, ProQuest LLC, Ann Arbor, MI, 2014. Thesis (Ph.D.)–University of California, Berkeley. MR 3295326
- Harold T. Hodes, Jumping through the transfinite: the master code hierarchy of Turing degrees, J. Symbolic Logic 45 (1980), no. 2, 204–220. MR 569393, DOI 10.2307/2273183
- Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
- R. Björn Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR 309729, DOI 10.1016/0003-4843(72)90001-0
- Ronald B. Jensen and Carol Karp, Primitive recursive set functions, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1971, pp. 143–176. MR 0281602
- Carl G. Jockusch Jr. and Stephen G. Simpson, A degree-theoretic definition of the ramified analytical hierarchy, Ann. Math. Logic 10 (1976), no. 1, 1–32. MR 491098, DOI 10.1016/0003-4843(76)90023-1
- Steven M. Kautz, Degrees of random sets, ProQuest LLC, Ann Arbor, MI, 1991. Thesis (Ph.D.)–Cornell University. MR 2686787
- Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
- Kenneth Kunen, Set theory, Studies in Logic (London), vol. 34, College Publications, London, 2011. MR 2905394
- Stuart Alan Kurtz, RANDOMNESS AND GENERICITY IN THE DEGREES OF UNSOLVABILITY, ProQuest LLC, Ann Arbor, MI, 1981. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR 2631709
- L. A. Levin, Uniform tests for randomness, Dokl. Akad. Nauk SSSR 227 (1976), no. 1, 33–35 (Russian). MR 0414222
- Donald A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687–689. MR 227022, DOI 10.1090/S0002-9904-1968-11995-0
- Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
- Donald A. Martin, A purely inductive proof of Borel determinacy, Recursion theory (Ithaca, N.Y., 1982) Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp. 303–308. MR 791065, DOI 10.1090/pspum/042/791065
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
- John C. Oxtoby, Homeomorphic measures in metric spaces, Proc. Amer. Math. Soc. 24 (1970), 419–423. MR 260961, DOI 10.1090/S0002-9939-1970-0260961-1
- Jan Reimann and Theodore A. Slaman, Measures and their random reals, Trans. Amer. Math. Soc. 367 (2015), no. 7, 5081–5097. MR 3335411, DOI 10.1090/S0002-9947-2015-06184-4
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- 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, DOI 10.1007/BFb0112458
- Richard A. Shore and Theodore A. Slaman, Defining the Turing jump, Math. Res. Lett. 6 (1999), no. 5-6, 711–722. MR 1739227, DOI 10.4310/MRL.1999.v6.n6.a10
- 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, DOI 10.1142/9789812796554_{0}019
- 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
Bibliographic Information
- Jan Reimann
- Affiliation: Department of Mathematics, Pennsylvania State University, University Park, State College, PA 16802 USA
- MR Author ID: 667958
- ORCID: 0000-0003-1156-8390
- Email: reimann@math.psu.edu
- Theodore A. Slaman
- Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, CA 94720 USA
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
- Received by editor(s): September 9, 2016
- Received by editor(s) in revised form: August 17, 2018, May 26, 2020, and December 22, 2020
- Published electronically: August 30, 2021
- 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. - © Copyright 2021 American Mathematical Society
- Journal: J. Amer. Math. Soc. 35 (2022), 467-512
- MSC (2020): Primary 03E15, 03E45, 03D32; Secondary 60A10
- DOI: https://doi.org/10.1090/jams/980
- MathSciNet review: 4374955