Lawvere-Tierney topologies for computability theorists
HTML articles powered by AMS MathViewer
- by Takayuki Kihara
- Trans. Amer. Math. Soc. Ser. B 10 (2023), 48-85
- DOI: https://doi.org/10.1090/btran/134
- Published electronically: January 23, 2023
- HTML | PDF
Abstract:
In this article, we study the lattice of Lawvere-Tierney topologies on Hyland’s effective topos. For this purpose, we introduce a new computability-theoretic reducibility notion, which is a common extension of the notions of Turing reducibility and generalized Weihrauch reducibility. Based on the work by Lee and van Oosten [Ann. Pure Appl. Logic 164 (2013), pp. 866-883], we utilize this reducibility notion for providing a concrete description of the lattice of the Lawvere-Tierney topologies on the effective topos. As an application, we solve several open problems proposed by Lee and van Oosten. For instance, we show that there exists no minimal Lawvere-Tierney topology which is strictly above the identity topology on the effective topos.References
- Paul-Elliot Anglès d’Auriac and Takayuki Kihara, A comparison of various analytic choice principles, J. Symb. Log. 86 (2021), no. 4, 1452–1485. MR 4362921, DOI 10.1017/jsl.2021.37
- Andrej Bauer, Instance reducibility and Weihrauch degrees, Log. Methods Comput. Sci. 18 (2022), no. 3, Paper No. 20, 18. MR 4467044
- Laurent Bienvenu, Noam Greenberg, and Benoit Monin, Bad oracles in higher computability and randomness, Israel J. Math. 241 (2021), no. 1, 229–276. MR 4242151, DOI 10.1007/s11856-021-2094-4
- Vasco Brattka and Guido Gherardi, Effective choice and boundedness principles in computable analysis, Bull. Symbolic Logic 17 (2011), no. 1, 73–117. MR 2760117, DOI 10.2178/bsl/1294186663
- Vasco Brattka, Guido Gherardi, and Rupert Hölzl, Probabilistic computability and choice, Inform. and Comput. 242 (2015), 249–286. MR 3350999, DOI 10.1016/j.ic.2015.03.005
- Vasco Brattka, Guido Gherardi, and Arno Pauly, Weihrauch complexity in computable analysis, Handbook of computability and complexity in analysis, Theory Appl. Comput., Springer, Cham, [2021] ©2021, pp. 367–417. MR 4300761, DOI 10.1007/978-3-030-59234-9_{1}1
- Vasco Brattka and Arno Pauly, Computation with advice, Proceedings Seventh International Conference on Computability and Complexity in Analysis, Zhenjiang, China, 21–25th June 2010 (Xizhong Zheng and Ning Zhong, eds.), Electronic Proceedings in Theoretical Computer Science, vol. 24, Open Publishing Association, 2010, pp. 41–55.
- Douglas Cenzer and Peter G. Hinman, Degrees of difficulty of generalized r.e. separating classes, Arch. Math. Logic 46 (2008), no. 7-8, 629–647. MR 2395562, DOI 10.1007/s00153-007-0058-y
- Peter Cholak and Ludovic Patey, Thin set theorems and cone avoidance, Trans. Amer. Math. Soc. 373 (2020), no. 4, 2743–2773. MR 4069232, DOI 10.1090/tran/7987
- Chi Tat Chong and Liang Yu, Recursion theory, De Gruyter Series in Logic and its Applications, vol. 8, De Gruyter, Berlin, 2015. Computational aspects of definability; With an interview with Gerald E. Sacks. MR 3381097, DOI 10.1515/9783110275643
- S. Barry Cooper, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2017461
- Hannes Diener, Constructive reverse mathematics, 2018, Habilitationsschrift, University of Siegen.
- Hannes Diener and Hajime Ishihara, Bishop-style constructive reverse mathematics, Handbook of computability and complexity in analysis, Theory Appl. Comput., Springer, Cham, [2021] ©2021, pp. 347–365. MR 4300760, DOI 10.1007/978-3-030-59234-9_{1}0
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- Damir D. Dzhafarov, Strong reductions between combinatorial principles, J. Symb. Log. 81 (2016), no. 4, 1405–1431. MR 3579116, DOI 10.1017/jsl.2016.1
- Damir D. Dzhafarov, Denis R. Hirschfeldt, and Sarah C. Reitzes, Reduction games, provability, and compactness, arXiv:2008.00907, 2020.
- Damir D. Dzhafarov and Ludovic Patey, COH, SRT$^2_2$, and multiple functionals, Computability 10 (2021), no. 2, 111–121. MR 4246717, DOI 10.3233/com-190261
- Jun Le Goh, Compositions of multivalued functions, Computability 9 (2020), no. 3-4, 231–247. MR 4133715, DOI 10.3233/com-180235
- Jun Le Goh, Arno Pauly, and Manlio Valenti, Finding descending sequences through ill-founded linear orders, J. Symb. Log. 86 (2021), no. 2, 817–854. MR 4328030, DOI 10.1017/jsl.2021.15
- Edward R. Griffor (ed.), Handbook of computability theory, Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland Publishing Co., Amsterdam, 1999. MR 1721236
- Denis R. Hirschfeldt and Carl G. Jockusch Jr., On notions of computability-theoretic reduction between $\Pi _2^1$ principles, J. Math. Log. 16 (2016), no. 1, 1650002, 59. MR 3518779, DOI 10.1142/S0219061316500021
- J. M. E. Hyland, The effective topos, The L.E.J. Brouwer Centenary Symposium (Noordwijkerhout, 1981) Stud. Logic Found. Math., vol. 110, North-Holland, Amsterdam-New York, 1982, pp. 165–216. MR 717245
- Takayuki Kihara, Degrees of incomputability, realizability and constructive reverse mathematics, arXiv:2002.10712, 2020.
- Takayuki Kihara, Rethinking the notion of oracle, arXiv:2202.00188, 2022.
- Takayuki Kihara and Arno Pauly, Dividing by zero—how bad is it, really?, 41st International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 58, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, pp. Art. No. 58, 14. MR 3578494
- Sori Lee, Subtoposes of the effective topos, Master’s thesis, Utrecht University, 2011, arXiv:1112.5325.
- Sori Lee and Jaap van Oosten, Basic subtoposes of the effective topos, Ann. Pure Appl. Logic 164 (2013), no. 9, 866–883. MR 3056301, DOI 10.1016/j.apal.2013.04.001
- Vladimir Lifschitz, $\textrm {CT}_{0}$ is stronger than $\textrm {CT}_{0}!$, Proc. Amer. Math. Soc. 73 (1979), no. 1, 101–106. MR 512067, DOI 10.1090/S0002-9939-1979-0512067-X
- Saunders Mac Lane and Ieke Moerdijk, Sheaves in geometry and logic, Universitext, Springer-Verlag, New York, 1994. A first introduction to topos theory; Corrected reprint of the 1992 edition. MR 1300636, DOI 10.1007/978-1-4612-0927-0
- Benoit Monin and Ludovic Patey, $\Pi ^0_1$-encodability and omniscient reductions, Notre Dame J. Form. Log. 60 (2019), no. 1, 1–12. MR 3911103, DOI 10.1215/00294527-2018-0020
- 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
- Yiannis N. Moschovakis, Descriptive set theory, 2nd ed., Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, RI, 2009. MR 2526093, DOI 10.1090/surv/155
- Eike Neumann and Arno Pauly, A topological view on algebraic computation models, J. Complexity 44 (2018), 1–22. MR 3724808, DOI 10.1016/j.jco.2017.08.003
- 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
- Ludovic Patey, Ramsey-like theorems and moduli of computation, J. Symb. Log. 87 (2022), no. 1, 72–108. MR 4404620, DOI 10.1017/jsl.2020.69
- Arno Pauly, Many-one reductions and the category of multivalued functions, Math. Structures Comput. Sci. 27 (2017), no. 3, 376–404. MR 3606719, DOI 10.1017/S0960129515000262
- Arno Pauly and Matthew de Brecht, Descriptive set theory in the category of represented spaces, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 438–449. MR 3538461, DOI 10.1109/LICS.2015.48
- Andrew M. Pitts, The theory of triposes, Ph.D. thesis, The University of Cambridge, 1981.
- Fred Richman, Polynomials and linear transformations, Linear Algebra Appl. 131 (1990), 131–137. MR 1057069, DOI 10.1016/0024-3795(90)90379-Q
- Hartley Rogers Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890
- Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
- Stephen G. Simpson, An extension of the recursively enumerable Turing degrees, J. Lond. Math. Soc. (2) 75 (2007), no. 2, 287–297. MR 2340228, DOI 10.1112/jlms/jdl015
- Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689, DOI 10.1017/CBO9780511581007
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- Robert M. Solovay, Hyperarithmetically encodable sets, Trans. Amer. Math. Soc. 239 (1978), 99–122. MR 491103, DOI 10.1090/S0002-9947-1978-0491103-7
- Jaap van Oosten, Realizability: an introduction to its categorical side, Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier B. V., Amsterdam, 2008. MR 2479466
- Jaap van Oosten, Realizability with a local operator of A. M. Pitts, Theoret. Comput. Sci. 546 (2014), 237–243. MR 3233456, DOI 10.1016/j.tcs.2014.03.011
- Linda Westrick, A note on the diamond operator, Computability 10 (2021), no. 2, 107–110. MR 4246716, DOI 10.3233/COM-200295
- Martin Ziegler, Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra, Ann. Pure Appl. Logic 163 (2012), no. 8, 1108–1139. MR 2915702, DOI 10.1016/j.apal.2011.12.030
Bibliographic Information
- Takayuki Kihara
- Affiliation: Graduate School of Informatics, Nagoya University, Nagoya, 464-8601 Japan
- MR Author ID: 892476
- ORCID: 0000-0002-1611-952X
- Email: kihara@i.nagoya-u.ac.jp
- Received by editor(s): July 6, 2021
- Received by editor(s) in revised form: August 19, 2022, and August 24, 2022
- Published electronically: January 23, 2023
- Additional Notes: The author was partially supported by JSPS KAKENHI Grant Numbers 19K03602, 21H03392 and 22K03401, and the JSPS-RFBR Bilateral Joint Research Project JPJSBP120204809.
- © Copyright 2023 by the author under Creative Commons Attribution 3.0 License (CC BY 3.0)
- Journal: Trans. Amer. Math. Soc. Ser. B 10 (2023), 48-85
- MSC (2020): Primary 03D30; Secondary 03D80, 18B25
- DOI: https://doi.org/10.1090/btran/134
- MathSciNet review: 4538503