## 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

## Additional Information

**Takayuki Kihara**- Affiliation: Department of Mathematics, University of California, Berkeley, California 94720
- Address at time of publication: Graduate School of Informatics, Nagoya University, Nagoya 464-8601, Japan
- MR Author ID: 892476
- Email: kihara@i.nagoya-u.ac.jp
**Antonio Montalbán**- Affiliation: Department of Mathematics, University of California, Berkeley, California 94720
- Email: antonio@math.berkeley.edu
- Received by editor(s): October 5, 2017
- Received by editor(s) in revised form: January 23, 2018
- Published electronically: September 18, 2018
- Additional Notes: The first-named author was partially supported by JSPS KAKENHI grants 17H06738 and 15H03634, and the JSPS Core-to-Core Program (A. Advanced Research Networks).

The second-named author was partially supported by NSF grant DMS-0901169 and the Packard Fellowship. - © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**370**(2018), 9025-9044 - MSC (2010): Primary 03D30; Secondary 03E15, 03E60
- DOI: https://doi.org/10.1090/tran/7519
- MathSciNet review: 3864404