The uniform Martin’s conjecture for many-one degrees

Kihara, Takayuki; Montalbán, Antonio

doi:10.1090/tran/7519

The uniform Martin’s conjecture for many-one degrees
HTML articles powered by AMS MathViewer

by Takayuki Kihara and Antonio Montalbán PDF

Trans. Amer. Math. Soc. 370 (2018), 9025-9044 Request permission

Abstract:

We study functions from reals to reals which are uniformly degree invariant from Turing equivalence to many-one equivalence, and we compare them “on a cone”. We prove that they are in one-to-one correspondence with the Wadge degrees, which can be viewed as a refinement of the uniform Martin’s conjecture for uniformly invariant functions from Turing equivalence to Turing equivalence.

Our proof works in the general case of many-one degrees on $\mathcal {Q}^{\omega }$ and Wadge degrees of functions ${\omega }^{\omega }\to \mathcal {Q}$ for any better-quasi-ordering $\mathcal {Q}$.

References

Howard Becker, A characterization of jump operators, J. Symbolic Logic 53 (1988), no. 3, 708–728. MR 960994, DOI 10.2307/2274567
Alexander C. Block, Operations on a Wadge-type hierarchy of ordinal-valued functions, 2014. Thesis (master’s)–Universiteit van Amsterdam.
Jörg Brendle and Benedikt Löwe, Solovay-type characterizations for forcing-algebras, J. Symbolic Logic 64 (1999), no. 3, 1307–1323. MR 1779764, DOI 10.2307/2586632
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
Rodney G. Downey and Richard A. Shore, There is no degree invariant half-jump, Proc. Amer. Math. Soc. 125 (1997), no. 10, 3033–3037. MR 1401736, DOI 10.1090/S0002-9939-97-03915-4
J. Duparc, Wadge hierarchy and Veblen hierarchy. I. Borel sets of finite rank, J. Symbolic Logic 66 (2001), no. 1, 56–86. MR 1825174, DOI 10.2307/2694911
J. Duparc, The Steel hierarchy of ordinal valued Borel mappings, J. Symbolic Logic 68 (2003), no. 1, 187–234. MR 1959317, DOI 10.2178/jsl/1045861511
P. Erdös and A. Tarski, On families of mutually exclusive sets, Ann. of Math. (2) 44 (1943), 315–329. MR 8249, DOI 10.2307/1968767
Fred Galvin and Karel Prikry, Borel sets and Ramsey’s theorem, J. Symbolic Logic 38 (1973), 193–198. MR 337630, DOI 10.2307/2272055
Leo A. Harrington and Alexander S. Kechris, On the determinacy of games on ordinals, Ann. Math. Logic 20 (1981), no. 2, 109–154. MR 622782, DOI 10.1016/0003-4843(81)90001-2
Alexander S. Kechris, Benedikt Löwe, and John R. Steel (eds.), Wadge degrees and projective ordinals. The Cabal Seminar. Volume II, Lecture Notes in Logic, vol. 37, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012. MR 2906066
Takayuki Kihara and Antonio Montalbán, On the structure of the Wadge degrees of BQO-valued Borel functions (to be published).
S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
Steffen Lempp, The computational complexity of torsion-freeness of finitely presented groups, Bull. Austral. Math. Soc. 56 (1997), no. 2, 273–277. MR 1470080, DOI 10.1017/S0004972700031014
Alain Louveau and Jean Saint-Raymond, On the quasi-ordering of Borel linear orders under embeddability, J. Symbolic Logic 55 (1990), no. 2, 537–560. MR 1056369, DOI 10.2307/2274645
Alain Louveau and Stephen G. Simpson, A separable image theorem for Ramsey mappings, Bull. Acad. Polon. Sci. Sér. Sci. Math. 30 (1982), no. 3-4, 105–108 (English, with Russian summary). MR 673430
Andrew Marks, Theodore A. Slaman, and John R. Steel, Martin’s conjecture, arithmetic equivalence, and countable Borel equivalence relations, Ordinal definability and recursion theory: The Cabal Seminar. Vol. III, Lect. Notes Log., vol. 43, Assoc. Symbol. Logic, Ithaca, NY, 2016, pp. 493–519. MR 3469180
Andrew S. Marks, Uniformity, universality, and computability theory, J. Math. Log. 17 (2017), no. 1, 1750003, 50. MR 3651212, DOI 10.1142/S0219061317500039
Donald A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687–689. MR 227022, DOI 10.1090/S0002-9904-1968-11995-0
Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
C. St. J. A. Nash-Williams, On well-quasi-ordering infinite trees, Proc. Cambridge Philos. Soc. 61 (1965), 697–720. MR 175814, DOI 10.1017/s0305004100039062
Anil Nerode and Richard A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no. 1, 61–89. MR 568916, DOI 10.1016/0003-4843(80)90004-2
Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
Victor L. Selivanov, Hierarchies of $\Delta ^0_2$-measurable $k$-partitions, MLQ Math. Log. Q. 53 (2007), no. 4-5, 446–461. MR 2351943, DOI 10.1002/malq.200710011
Stephen G. Simpson, “Bqo-theory and Fraïssé’s conjecture", in Richard Mansfield and Galen Weitkamp, Recursive Aspects of Descriptive Set Theory, Oxford Logic Guides, Vol. 11, Oxford University Press, Oxford, 1985, Chap. 9.
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
John R. Steel, A classification of jump operators, J. Symbolic Logic 47 (1982), no. 2, 347–358. MR 654792, DOI 10.2307/2273146
Fons van Engelen, Arnold W. Miller, and John Steel, Rigid Borel sets and better quasi-order theory, Logic and combinatorics (Arcata, Calif., 1985) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 199–222. MR 891249, DOI 10.1090/conm/065/891249
Robert Van Wesep, Wadge degrees and descriptive set theory, Cabal Seminar 76–77 (Proc. Caltech-UCLA Logic Sem., 1976–77) Lecture Notes in Math., vol. 689, Springer, Berlin, 1978, pp. 151–170. MR 526917
William Wilfred Wadge, Reducibility and determinateness on the Baire space, ProQuest LLC, Ann Arbor, MI, 1983. Thesis (Ph.D.)–University of California, Berkeley. MR 2633374
W. Hugh Woodin, The axiom of determinacy, forcing axioms, and the nonstationary ideal, De Gruyter Series in Logic and its Applications, vol. 1, Walter de Gruyter & Co., Berlin, 1999. MR 1713438, DOI 10.1515/9783110804737