Members of thin Π₁⁰ classes and generic degrees

Stephan, Frank; Wu, Guohua; Yuan, Bowen

doi:10.1090/proc/15325

Members of thin $\Pi _1^0$ classes and generic degrees
HTML articles powered by AMS MathViewer

by Frank Stephan, Guohua Wu and Bowen Yuan PDF

Proc. Amer. Math. Soc. 150 (2022), 3125-3131 Request permission

Abstract:

A $\Pi ^{0}_{1}$ class $P$ is thin if every $\Pi ^{0}_{1}$ subclass $Q$ of $P$ is the intersection of $P$ with some clopen set. In 1993, Cenzer, Downey, Jockusch and Shore initiated the study of Turing degrees of members of thin $\Pi ^{0}_{1}$ classes, and proved that degrees containing no members of thin $\Pi ^{0}_{1}$ classes can be recursively enumerable, and can be minimal degree below $\mathbf {0}’$. In this paper, we work on this topic in terms of genericity, and prove that all 2-generic degrees contain no members of thin $\Pi ^{0}_{1}$ classes. In contrast to this, we show that all 1-generic degrees below $\mathbf {0}’$ contain members of thin $\Pi ^{0}_{1}$ classes.

References

Douglas Cenzer, $\Pi ^0_1$ classes in computability theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 37–85. MR 1720779, DOI 10.1016/S0049-237X(99)80018-4
Douglas Cenzer, Rodney Downey, Carl Jockusch, and Richard A. Shore, Countable thin $\Pi ^0_1$ classes, Ann. Pure Appl. Logic 59 (1993), no. 2, 79–139. MR 1197208, DOI 10.1016/0168-0072(93)90001-T
C. T. Chong and R. G. Downey, Minimal degrees recursive in $1$-generic degrees, Ann. Pure Appl. Logic 48 (1990), no. 3, 215–225. MR 1073219, DOI 10.1016/0168-0072(90)90020-3
S. Barry Cooper, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2017461
R. Downey, Abstract Dependence, Recursion Theory and the Lattice of Recursively Enumerable Filters, PhD Thesis, Monash University, Clayton, Victoria, Australia, 1982.
Rodney G. Downey, Guohua Wu, and Yue Yang, Degrees containing members of thin $\Pi _1^0$ classes are dense and co-dense, J. Math. Log. 18 (2018), no. 1, 1850001, 47. MR 3809583, DOI 10.1142/S0219061318500010
Peter A. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic 24 (1983), no. 2, 113–130. MR 713296, DOI 10.1016/0168-0072(83)90028-3
Christine Ann Haught, The degrees below a $1$-generic degree $<{\bf 0}’$, J. Symbolic Logic 51 (1986), no. 3, 770–777. MR 853856, DOI 10.2307/2274030
Carl G. Jockusch Jr., Degrees of generic sets, Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979) London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge-New York, 1980, pp. 110–139. MR 598304
Carl G. Jockusch Jr. and Robert I. Soare, Degrees of members of $\Pi ^{0}_{1}$ classes, Pacific J. Math. 40 (1972), 605–616. MR 309722, DOI 10.2140/pjm.1972.40.605
Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205–209. MR 280374, DOI 10.2307/2270510
P. G. Odifreddi, Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland Publishing Co., Amsterdam, 1999. MR 1718169
Theodore A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic 52 (1991), no. 1-2, 155–179. International Symposium on Mathematical Logic and its Applications (Nagoya, 1988). MR 1104059, DOI 10.1016/0168-0072(91)90044-M
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
B. Yuan, Computability Theory and Degree Structures, PhD Thesis, Nanyang Technological University, 2020.