Part 1 of Martin’s Conjecture for order-preserving and measure-preserving functions

Lutz, Patrick; Siskind, Benjamin

doi:10.1090/jams/1046

Part 1 of Martin’s Conjecture for order-preserving and measure-preserving functions
HTML articles powered by AMS MathViewer

by Patrick Lutz and Benjamin Siskind

J. Amer. Math. Soc.

DOI: https://doi.org/10.1090/jams/1046

Published electronically: April 2, 2024

HTML | PDF | Request permission

Abstract:

Martin’s Conjecture is a proposed classification of the definable functions on the Turing degrees. It is usually divided into two parts, the first of which classifies functions which are not above the identity and the second of which classifies functions which are above the identity. Slaman and Steel proved the second part of the conjecture for Borel functions which are order-preserving (i.e. which preserve Turing reducibility). We prove the first part of the conjecture for all order-preserving functions. We do this by introducing a class of functions on the Turing degrees which we call “measure-preserving” and proving that part 1 of Martin’s Conjecture holds for all measure-preserving functions and also that all nontrivial order-preserving functions are measure-preserving. Our result on measure-preserving functions has several other consequences for Martin’s Conjecture, including an equivalence between part 1 of the conjecture and a statement about the structure of the Rudin-Keisler order on ultrafilters on the Turing degrees.

References

Vasco Brattka and Guido Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic 76 (2011), no. 1, 143–176. MR 2791341, DOI 10.2178/jsl/1294170993
Raphaël Carroy, A quasi-order on continuous functions, J. Symbolic Logic 78 (2013), no. 2, 633–648. MR 3145199, DOI 10.2178/jsl.7802150
W. W. Comfort and S. Negrepontis, The theory of ultrafilters, Die Grundlehren der mathematischen Wissenschaften, Band 211, Springer-Verlag, New York-Heidelberg, 1974. MR 396267, DOI 10.1007/978-3-642-65780-1
Randall Dougherty and Alexander S. Kechris, How many Turing degrees are there?, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 83–94. MR 1770736, DOI 10.1090/conm/257/04029
Marcia J. Groszek and Theodore A. Slaman, A basis theorem for perfect sets, Bull. Symbolic Logic 4 (1998), no. 2, 204–209. MR 1632148, DOI 10.2307/421023
Kojiro Higuchi and Patrick Lutz, A note on a conjecture of sacks, Preprint, arXiv:2309.01876, 2023.
Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
Alexander S. Kechris, The theory of countable borel equivalence relations, Preprint, 2021.
Takayuki Kihara, Personal communication, 2021.
Peter Koellner and W. Hugh Woodin, Large cardinals from determinacy, Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 1951–2119. MR 2768702, DOI 10.1007/978-1-4020-5764-9_{2}4
A. H. Lachlan, Uniform enumeration operations, J. Symbolic Logic 40 (1975), no. 3, 401–409. MR 379156, DOI 10.2307/2272164
Patrick Lutz, Martin’s conjecture for regressive functions on the hyperarithmetic degrees, Preprint, arXiv:2306.05746, 2023.
Andrew Marks, The universality of polynomial time Turing equivalence, Math. Structures Comput. Sci. 28 (2018), no. 3, 448–456. MR 3778211, DOI 10.1017/S0960129516000232
Andrew Marks, Personal communication, 2020.
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
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, Measurable cardinals and analytic games, Fund. Math. 66 (1969/70), 287–291. MR 258637, DOI 10.4064/fm-66-3-287-291
Donald A. Martin, A purely inductive proof of Borel determinacy, Recursion theory (Ithaca, N.Y., 1982) Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp. 303–308. MR 791065, DOI 10.1090/pspum/042/791065
Antonio Montalbán, Martin’s conjecture: a classification of the naturally occurring Turing degrees, Notices Amer. Math. Soc. 66 (2019), no. 8, 1209–1215. MR 3967172
Janusz Pawlikowski and Marcin Sabok, Decomposing Borel functions and structure at finite levels of the Baire hierarchy, Ann. Pure Appl. Logic 163 (2012), no. 12, 1748–1764. MR 2964869, DOI 10.1016/j.apal.2012.03.004
Gerald E. Sacks, On suborderings of degrees of recursive unsolvability, Z. Math. Logik Grundlagen Math. 7 (1961), 46–56. MR 131973, DOI 10.1002/malq.19610070109
Theodore A. Slaman, Aspects of the Turing jump, Logic Colloquium 2000, Lect. Notes Log., vol. 19, Assoc. Symbol. Logic, Urbana, IL, 2005, pp. 365–382. MR 2143887
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 I. Soare, Turing computability, Theory and Applications of Computability, Springer-Verlag, Berlin, 2016. Theory and applications. MR 3496974, DOI 10.1007/978-3-642-31933-4
Sławomir Solecki, Decomposing Borel sets and functions and the structure of Baire class $1$ functions, J. Amer. Math. Soc. 11 (1998), no. 3, 521–550. MR 1606843, DOI 10.1090/S0894-0347-98-00269-0
John R. Steel, A classification of jump operators, J. Symbolic Logic 47 (1982), no. 2, 347–358. MR 654792, DOI 10.2307/2273146
J. R. Steel, The derived model theorem, Logic Colloquium 2006, Lect. Notes Log., vol. 32, Assoc. Symbol. Logic, Chicago, IL, 2009, pp. 280–327. MR 2562557, DOI 10.1017/CBO9780511605321.014
Jindřich Zapletal, Descriptive set theory and definable forcing, Mem. Amer. Math. Soc. 167 (2004), no. 793, viii+141. MR 2023448, DOI 10.1090/memo/0793