A Π¹₁-uniformization principle for reals

Chong, C.; Yu, Liang

doi:10.1090/S0002-9947-09-04783-7

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