On the computability of perfect subsets of sets with positive measure
HTML articles powered by AMS MathViewer
- by C. T. Chong, Wei Li, Wei Wang and Yue Yang PDF
- Proc. Amer. Math. Soc. 147 (2019), 4021-4028 Request permission
Abstract:
A set $X \subseteq 2^\omega$ with positive measure contains a perfect subset. We study such perfect subsets from the viewpoint of computability and prove that these sets can have weak computational strength. Then we connect the existence of perfect subsets of sets with positive measure with reverse mathematics.References
- Jeremy Avigad, Edward T. Dean, and Jason Rute, Algorithmic randomness, reverse mathematics, and the dominated convergence theorem, Ann. Pure Appl. Logic 163 (2012), no. 12, 1854–1864. MR 2964874, DOI 10.1016/j.apal.2012.05.010
- Chitat Chong, Wei Li, Wei Wang, and Yue Yang, On the strength of Ramsey’s theorem for trees. To appear.
- Jared Corduan, Marcia J. Groszek, and Joseph R. Mileti, Reverse mathematics and Ramsey’s property for trees, J. Symbolic Logic 75 (2010), no. 3, 945–954. MR 2723776, DOI 10.2178/jsl/1278682209
- 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
- Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
- Jiayi Liu, ${\mathsf {RT}}^2_2$ does not imply ${\mathsf {WKL}}_0$, J. Symbolic Logic 77 (2012), no. 2, 609–620. MR 2963024, DOI 10.2178/jsl/1333566640
- Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689, DOI 10.1017/CBO9780511581007
Additional Information
- C. T. Chong
- Affiliation: Department of Mathematics, National University of Singapore, Singapore 119076
- MR Author ID: 48725
- Email: chongct@nus.edu.sg
- Wei Li
- Affiliation: Department of Mathematics, National University of Singapore, Singapore 119076
- Email: matliw@nus.edu.sg
- Wei Wang
- Affiliation: Institute of Logic and Cognition and Department of Philosophy, Sun Yat-Sen University, Guangzhou, People’s Republic of China
- Email: wwang.cn@gmail.com
- Yue Yang
- Affiliation: Department of Mathematics, National University of Singapore, Singapore 119076
- Email: matyangy@nus.edu.sg
- Received by editor(s): August 16, 2018
- Received by editor(s) in revised form: September 30, 2018
- Published electronically: May 29, 2019
- Additional Notes: The first author’s research was partially supported by NUS grants C-146-000-042-001 and WBS: R389-000-040-101.
The third author’s research was partially supported by China NSF Grant 11471342.
The fourth author’s research was partially supported by NUS AcRF Tier 1 grant R146-000-231-114 and MOE2016-T2-1-019.
All the authors acknowledge the support of JSPS-NUS grants R-146-000-192-133 and R-146-000-192-733 during the course of the work. - Communicated by: Heike Mildenberger
- © Copyright 2019 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 147 (2019), 4021-4028
- MSC (2010): Primary 03D32, 03F35, 03F60, 03F30
- DOI: https://doi.org/10.1090/proc/14413
- MathSciNet review: 3993793