Measure-theoretic applications of higher Demuth’s Theorem
HTML articles powered by AMS MathViewer
- by C. T. Chong and Liang Yu PDF
- Trans. Amer. Math. Soc. 368 (2016), 8249-8265 Request permission
Abstract:
We investigate measure-theoretic aspects of various notions of reducibility by applying analogs of Demuth’s Theorem in the hyperarithmetic and set-theoretic settings.References
- Laurent Bienvenu, Noam Greenberg, and Benoit Monin, Continuous higher randomness. preprint.
- C. T. Chong, Andre Nies, and Liang Yu, Lowness of higher randomness notions, Israel J. Math. 166 (2008), 39–60. MR 2430424, DOI 10.1007/s11856-008-1019-9
- C. T. Chong and Liang Yu, Randomness in the higher setting, J. Symb. Log. 80 (2015), no. 4, 1131–1148. MR 3436362, DOI 10.1017/jsl.2015.50
- Chi Tat Chong and Liang Yu, Recursion theory, De Gruyter Series in Logic and its Applications, vol. 8, De Gruyter, Berlin, 2015. Computational aspects of definability; With an interview with Gerald E. Sacks. MR 3381097, DOI 10.1515/9783110275643
- 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
- O. Demuth and A. Kučera, Remarks on $1$-genericity, semigenericity and related concepts, Comment. Math. Univ. Carolin. 28 (1987), no. 1, 85–94. MR 889770
- 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
- S. Feferman, Some applications of the notions of forcing and generic sets, Fund. Math. 56 (1964/65), 325–345. MR 176925, DOI 10.4064/fm-56-3-325-345
- Greg Hjorth and André Nies, Randomness via effective descriptive set theory, J. Lond. Math. Soc. (2) 75 (2007), no. 2, 495–508. MR 2340241, DOI 10.1112/jlms/jdm022
- Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
- Carl G. Jockusch Jr. and Richard A. Shore, Pseudojump operators. I. The r.e. case, Trans. Amer. Math. Soc. 275 (1983), no. 2, 599–609. MR 682720, DOI 10.1090/S0002-9947-1983-0682720-1
- Carl G. Jockusch Jr. and Richard A. Shore, Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers, J. Symbolic Logic 49 (1984), no. 4, 1205–1236. MR 771789, DOI 10.2307/2274273
- Steven M. Kautz, Degrees of random sets, ProQuest LLC, Ann Arbor, MI, 1991. Thesis (Ph.D.)–Cornell University. MR 2686787
- Alexander S. Kechris, Measure and category in effective descriptive set theory, Ann. Math. Logic 5 (1972/73), 337–384. MR 369072, DOI 10.1016/0003-4843(73)90012-0
- Bjørn Kjos-Hanssen, André Nies, Frank Stephan, and Liang Yu, Higher Kurtz randomness, Ann. Pure Appl. Logic 161 (2010), no. 10, 1280–1290. MR 2652197, DOI 10.1016/j.apal.2010.04.001
- 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
- Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
- Per Martin-Löf, On the notion of randomness, Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968) North-Holland, Amsterdam, 1970, pp. 73–78. MR 0275483
- Joseph S. Miller and Liang Yu, On initial segment complexity and degrees of randomness, Trans. Amer. Math. Soc. 360 (2008), no. 6, 3193–3210. MR 2379793, DOI 10.1090/S0002-9947-08-04395-X
- 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
- Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
- David B. Posner and Robert W. Robinson, Degrees joining to ${\bf 0}^{\prime }$, J. Symbolic Logic 46 (1981), no. 4, 714–722. MR 641485, DOI 10.2307/2273221
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- Gerald E. Sacks, Measure-theoretic uniformity in recursion theory and set theory, Trans. Amer. Math. Soc. 142 (1969), 381–420. MR 253895, DOI 10.1090/S0002-9947-1969-0253895-6
- Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
- 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
- Robert M. Solovay, A model of set-theory in which every set of reals is Lebesgue measurable, Ann. of Math. (2) 92 (1970), 1–56. MR 265151, DOI 10.2307/1970696
- Clifford Spector, Measure-theoretic construction of incomparable hyperdegrees, J. Symbolic Logic 23 (1958), 280–288. MR 112830, DOI 10.2307/2964288
- Wei Wang, Relative enumerability and 1-genericity, J. Symbolic Logic 76 (2011), no. 3, 897–913. MR 2849251, DOI 10.2178/jsl/1309952526
- Liang Yu, Lowness for genericity, Arch. Math. Logic 45 (2006), no. 2, 233–238. MR 2209745, DOI 10.1007/s00153-005-0306-y
- Liang Yu, Measure theory aspects of locally countable orderings, J. Symbolic Logic 71 (2006), no. 3, 958–968. MR 2251548, DOI 10.2178/jsl/1154698584
Additional Information
- C. T. Chong
- Affiliation: Department of Mathematics, Faculty of Science, National University of Singapore, 10 Lower Kent Ridge Road, Singapore 119076, Singapore
- MR Author ID: 48725
- Email: chongct@math.nus.edu.sg
- Liang Yu
- Affiliation: Institute of Mathematics, Nanjing University, 22 Hankou Road, Nanjing 210093, People’s Republic of China
- MR Author ID: 725077
- Email: yuliang.nju@gmail.com
- Received by editor(s): August 6, 2014
- Received by editor(s) in revised form: October 21, 2015, and December 2, 2015
- Published electronically: April 15, 2016
- Additional Notes: The first author was partially supported by NUS grant WBS 146-000-025-00
The second author was partially supported by the National Natural Science Fund of China grant 11322112 and by the Humboldt Foundation. - © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 8249-8265
- MSC (2010): Primary 03D28, 03D30, 03D32, 03E15, 28A05
- DOI: https://doi.org/10.1090/tran/6881
- MathSciNet review: 3546799