Measure-theoretic applications of higher Demuth’s Theorem

Chong, C.; Yu, Liang

doi:10.1090/tran/6881

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