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
Bibliographic Information
- Patrick Lutz
- Affiliation: Department of Mathematics, University of California, Berkeley, 970 Evans Hall, MC 3840, Berkeley, CA 94720
- MR Author ID: 1399453
- ORCID: 0000-0001-9930-4183
- Email: pglutz@berkeley.edu
- Benjamin Siskind
- Affiliation: Institut für Diskrete Mathematik und Geometrie, TU Wien, Wiedner Hauptstraße 8-10/104, 1040 Wien, Austria
- MR Author ID: 1485971
- ORCID: 0000-0002-9256-6401
- Email: benjamin.siskind@tuwien.ac.at
- Received by editor(s): May 31, 2023
- Received by editor(s) in revised form: January 13, 2024
- Published electronically: April 2, 2024
- Additional Notes: The first author was supported by the NSF Postdoctoral Research Fellowship in Mathematics (DMS-2203072). The second author was supported by the Austrian Science Fund (FWF) [10.55776/Y1498]. For open access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission
- © Copyright 2024 American Mathematical Society
- Journal: J. Amer. Math. Soc.
- MSC (2020): Primary 03D55, 03E60, 03D28
- DOI: https://doi.org/10.1090/jams/1046