×

zbMATH — the first resource for mathematics

Measure-theoretic applications of higher Demuth’s theorem. (English) Zbl 1402.03060
Summary: We investigate measure-theoretic aspects of various notions of reducibility by applying analogs of O. Demuth’s Theorem [Commentat. Math. Univ. Carol. 29, No. 2, 233–247 (1988; Zbl 0646.03039)] in the hyperarithmetic and set-theoretic settings.
MSC:
03D28 Other Turing degree structures
03D30 Other degrees and reducibilities in computability and recursion theory
03D32 Algorithmic randomness and dimension
03E15 Descriptive set theory
28A05 Classes of sets (Borel fields, \(\sigma\)-rings, etc.), measurable sets, Suslin sets, analytic sets
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] BGM Laurent Bienvenu, Noam Greenberg, and Benoit Monin, \newblock Continuous higher randomness. \newblock \em preprint. · Zbl 1420.03100
[2] Chong, C. T.; Nies, Andre; Yu, Liang, Lowness of higher randomness notions, Israel J. Math., 166, 39-60, (2008) · Zbl 1153.03020
[3] Chong, C. T.; Yu, Liang, Randomness in the higher setting, J. Symb. Log., 80, 4, 1131-1148, (2015) · Zbl 1386.03046
[4] Chong, Chi Tat; Yu, Liang, Recursion theory, De Gruyter Series in Logic and its Applications 8, xiv+306 pp., (2015), De Gruyter, Berlin · Zbl 1334.03003
[5] de Leeuw, K.; Moore, E. F.; Shannon, C. E.; Shapiro, N., Computability by probabilistic machines. Automata studies, Annals of mathematics studies, no. 34, 183-212, (1956), Princeton University Press, Princeton, N. J.
[6] Demuth, Osvald, Remarks on the structure of tt-degrees based on constructive measure theory, Comment. Math. Univ. Carolin., 29, 2, 233-247, (1988) · Zbl 0646.03039
[7] Demuth, O.; Ku\vcera, A., Remarks on \(1\)-genericity, semigenericity and related concepts, Comment. Math. Univ. Carolin., 28, 1, 85-94, (1987) · Zbl 0655.03029
[8] Downey, Rodney G.; Hirschfeldt, Denis R., Algorithmic randomness and complexity, Theory and Applications of Computability, xxviii+855 pp., (2010), Springer, New York · Zbl 1221.68005
[9] Feferman, S., Some applications of the notions of forcing and generic sets, Fund. Math., 56, 325-345, (1964/1965) · Zbl 0129.26401
[10] Hjorth, Greg; Nies, Andr\'e, Randomness via effective descriptive set theory, J. Lond. Math. Soc. (2), 75, 2, 495-508, (2007) · Zbl 1118.03034
[11] Jech, Thomas, Set theory, Springer Monographs in Mathematics, xiv+769 pp., (2003), Springer-Verlag, Berlin · Zbl 1007.03002
[12] Jockusch, Carl G., Jr.; Shore, Richard A., Pseudojump operators. I. The r.e. case, Trans. Amer. Math. Soc., 275, 2, 599-609, (1983) · Zbl 0514.03028
[13] Jockusch, Carl G., Jr.; Shore, Richard A., Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers, J. Symbolic Logic, 49, 4, 1205-1236, (1984) · Zbl 0574.03026
[14] Kautz, Steven M., Degrees of random sets, 129 pp., (1991), ProQuest LLC, Ann Arbor, MI
[15] Kechris, Alexander S., Measure and category in effective descriptive set theory, Ann. Math. Logic, 5, 337-384, (1972/73) · Zbl 0277.02019
[16] Kjos-Hanssen, Bj\o rn; Nies, Andr\'e; Stephan, Frank; Yu, Liang, Higher Kurtz randomness, Ann. Pure Appl. Logic, 161, 10, 1280-1290, (2010) · Zbl 1223.03025
[17] Kurtz, Stuart Alan, Randomness and Genericity in the Degrees of Unsolvability, 138 pp., (1981), ProQuest LLC, Ann Arbor, MI
[18] Lerman, Manuel, Degrees of unsolvability, Perspectives in Mathematical Logic, xiii+307 pp., (1983), Springer-Verlag, Berlin · Zbl 1365.03002
[19] Martin-L\"of, Per, On the notion of randomness. Intuitionism and Proof Theory, Proc. Conf., Buffalo, N.Y., 1968, 73-78, (1970), North-Holland, Amsterdam
[20] Miller, Joseph S.; Yu, Liang, On initial segment complexity and degrees of randomness, Trans. Amer. Math. Soc., 360, 6, 3193-3210, (2008) · Zbl 1140.68028
[21] Nies, Andr\'e, Computability and randomness, Oxford Logic Guides 51, xvi+433 pp., (2009), Oxford University Press, Oxford · Zbl 1237.03027
[22] Odifreddi, Piergiorgio, Classical recursion theory, Studies in Logic and the Foundations of Mathematics 125, xviii+668 pp., (1989), North-Holland Publishing Co., Amsterdam · Zbl 0661.03029
[23] Posner, David B.; Robinson, Robert W., Degrees joining to \(\textbf{0}^{′ } \), J. Symbolic Logic, 46, 4, 714-722, (1981) · Zbl 0517.03014
[24] Sacks, Gerald E., Degrees of unsolvability, ix+174 pp., (1963), Princeton University Press, Princeton, N.J.
[25] Sacks, Gerald E., Measure-theoretic uniformity in recursion theory and set theory, Trans. Amer. Math. Soc., 142, 381-420, (1969) · Zbl 0209.01603
[26] Sacks, Gerald E., Higher recursion theory, Perspectives in Mathematical Logic, xvi+344 pp., (1990), Springer-Verlag, Berlin · Zbl 0699.00011
[27] Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, xviii+437 pp., (1987), Springer-Verlag, Berlin · Zbl 0623.03042
[28] Solovay, Robert M., A model of set-theory in which every set of reals is Lebesgue measurable, Ann. of Math. (2), 92, 1-56, (1970) · Zbl 0207.00905
[29] Spector, Clifford, Measure-theoretic construction of incomparable hyperdegrees, J. Symb. Logic, 23, 280-288, (1958) · Zbl 0085.24901
[30] Wang, Wei, Relative enumerability and 1-genericity, J. Symbolic Logic, 76, 3, 897-913, (2011) · Zbl 1260.03079
[31] Yu, Liang, Lowness for genericity, Arch. Math. Logic, 45, 2, 233-238, (2006) · Zbl 1148.03033
[32] Yu, Liang, Measure theory aspects of locally countable orderings, J. Symbolic Logic, 71, 3, 958-968, (2006) · Zbl 1109.03038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.