A $\Pi ^1_1$-uniformization principle for reals
HTML articles powered by AMS MathViewer
- by C. T. Chong and Liang Yu PDF
- Trans. Amer. Math. Soc. 361 (2009), 4233-4245 Request permission
Abstract:
We introduce a $\Pi ^1_1$-uniformization principle and establish its equivalence with the set-theoretic hypothesis $(\omega _1)^L=\omega _1$. This principle is then applied to derive the equivalence, to suitable set-theoretic hypotheses, of the existence of $\Pi ^1_1$-maximal chains and thin maximal antichains in the Turing degrees. We also use the $\Pi ^1_1$-uniformization principle to study Martin’s conjectures on cones of Turing degrees, and show that under $V=L$ the conjectures fail for uniformly degree invariant $\Pi ^1_1$ functions.References
- Peter Aczel and Wayne Richter, Inductive definitions and analogues of large cardinals, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Lecture Notes in Math., Vol. 255, Springer, Berlin, 1972, pp. 1–9. MR 0363841
- Jon Barwise, Admissible sets and structures, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1975. An approach to definability theory. MR 0424560, DOI 10.1007/978-3-662-11035-5
- George Boolos and Hilary Putnam, Degrees of unsolvability of constructible sets of integers, J. Symbolic Logic 33 (1968), 497–513. MR 239977, DOI 10.2307/2271357
- Douglas Cenzer, Analytic inductive definitions, J. Symbolic Logic 39 (1974), 310–312. MR 357089, DOI 10.2307/2272644
- C. T. Chong and Liang Yu, Maximal chains in the Turing degrees, J. Symbolic Logic 72 (2007), no. 4, 1219–1227. MR 2371202, DOI 10.2178/jsl/1203350783
- C. T. Chong and Liang Yu. Thin maximal antichains in the Turing degrees. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, CiE, volume 4497 of Lecture Notes in Computer Science, pages 162–168. Springer, 2007.
- S. B. Cooper, Minimal degrees and the jump operator, J. Symbolic Logic 38 (1973), 249–271. MR 347572, DOI 10.2307/2272061
- Keith J. Devlin, Constructibility, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1984. MR 750828, DOI 10.1007/978-3-662-21723-8
- Leo Harrington, Analytic determinacy and $0^{\sharp }$, J. Symbolic Logic 43 (1978), no. 4, 685–693. MR 518675, DOI 10.2307/2273508
- R. Björn Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR 309729, DOI 10.1016/0003-4843(72)90001-0
- Richard Mansfield, Perfect subsets of definable sets of real numbers, Pacific J. Math. 35 (1970), 451–457. MR 280380, DOI 10.2140/pjm.1970.35.451
- Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
- Arnold W. Miller, Infinite combinatorics and definability, Ann. Pure Appl. Logic 41 (1989), no. 2, 179–203. MR 983001, DOI 10.1016/0168-0072(89)90013-4
- Gerald E. Sacks, Countable admissible ordinals and hyperdegrees, Advances in Math. 20 (1976), no. 2, 213–262. MR 429523, DOI 10.1016/0001-8708(76)90187-0
- Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
- Theodore A. Slaman and John R. Steel, Definable functions on degrees, Cabal Seminar 81–85, Lecture Notes in Math., vol. 1333, Springer, Berlin, 1988, pp. 37–55. MR 960895, DOI 10.1007/BFb0084969
- Robert M. Solovay, On the cardinality of $\sum _{2}^{1}$ sets of reals, Foundations of Mathematics (Symposium Commemorating Kurt Gödel, Columbus, Ohio, 1966) Springer, New York, 1969, pp. 58–73. MR 0277382
- Clifford Spector, Recursive well-orderings, J. Symbolic Logic 20 (1955), 151–163. MR 74347, DOI 10.2307/2266902
- John R. Steel, A classification of jump operators, J. Symbolic Logic 47 (1982), no. 2, 347–358. MR 654792, DOI 10.2307/2273146
Additional Information
- C. T. Chong
- Affiliation: Department of Mathematics, Faculty of Science, National University of Singapore, Lower Kent Ridge Road, Singapore 117543
- MR Author ID: 48725
- Email: chongct@math.nus.eud.sg
- Liang Yu
- Affiliation: Institute of Mathematical Sciences, Nanjing University, Nanjing, Jiangsu Province 210093, People’s Republic of China
- MR Author ID: 725077
- Email: yuliang.nju@gmail.com
- Received by editor(s): August 14, 2007
- Published electronically: February 10, 2009
- Additional Notes: The research of the first author was supported in part by NUS grant WBS 146-000-054-123
The second author was supported by NSF of China Grant No. 10701041, Research Fund for Doctoral Programs of Higher Education, No. 20070284043, and Scientific Research Foundation for Returned Overseas Chinese Scholars. - © Copyright 2009 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 361 (2009), 4233-4245
- MSC (2000): Primary 03D28, 03E35, 28A20
- DOI: https://doi.org/10.1090/S0002-9947-09-04783-7
- MathSciNet review: 2500887