TY - GEN
T1 - On Arithmetical Numberings in Reverse Mathematics
AU - Bazhenov, Nikolay
AU - Fiori-Carones, Marta
AU - Mustafa, Manat
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - The paper analyzes the strength of some statements of the theory of numberings from the point of view of reverse mathematics and Weihrauch reducibility. For a countable family S, a numbering is a surjection acting from the set of natural numbers onto S. The following types of numberings have been extensively studied in the literature: Friedberg, positive, and minimal numberings. Fix n≥2. After formalizing the needed notions in the language of second-order arithmetic, we prove that, over RCA0, ACA0 is equivalent to the principle stating the existence of a (not necessarily Σn-computable) Friedberg numbering ν for any infinite Σn0-computable family. Over RCA0+IΣ2, ACA0 is also equivalent to a similar principle for positive numberings ν. On the other hand, RCA0+IΣ2 is sufficient to prove the existence of a minimal numbering for any infinite Σn0-computable family. The reverse mathematics thus underlines a distinction between the considered types of numberings: intuitively, ‘being Friedberg’ and ‘being positive’ are internal properties of a numbering, while ‘being minimal’ is a more global property. The paper also includes a brief study of the Weihrauch reducibility strength for the existence of Friedberg numberings.
AB - The paper analyzes the strength of some statements of the theory of numberings from the point of view of reverse mathematics and Weihrauch reducibility. For a countable family S, a numbering is a surjection acting from the set of natural numbers onto S. The following types of numberings have been extensively studied in the literature: Friedberg, positive, and minimal numberings. Fix n≥2. After formalizing the needed notions in the language of second-order arithmetic, we prove that, over RCA0, ACA0 is equivalent to the principle stating the existence of a (not necessarily Σn-computable) Friedberg numbering ν for any infinite Σn0-computable family. Over RCA0+IΣ2, ACA0 is also equivalent to a similar principle for positive numberings ν. On the other hand, RCA0+IΣ2 is sufficient to prove the existence of a minimal numbering for any infinite Σn0-computable family. The reverse mathematics thus underlines a distinction between the considered types of numberings: intuitively, ‘being Friedberg’ and ‘being positive’ are internal properties of a numbering, while ‘being minimal’ is a more global property. The paper also includes a brief study of the Weihrauch reducibility strength for the existence of Friedberg numberings.
KW - Arithmetical numbering
KW - Friedberg numbering
KW - Reverse mathematics
KW - Theory of numberings
KW - Weihrauch reducibility
UR - http://www.scopus.com/inward/record.url?scp=85200419044&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85200419044&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-64309-5_11
DO - 10.1007/978-3-031-64309-5_11
M3 - Conference contribution
AN - SCOPUS:85200419044
SN - 9783031643088
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 126
EP - 138
BT - Twenty Years of Theoretical and Practical Synergies - 20th Conference on Computability in Europe, CiE 2024, Proceedings
A2 - Levy Patey, Ludovic
A2 - Pimentel, Elaine
A2 - Galeotti, Lorenzo
A2 - Manea, Florin
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th Conference on Computability in Europe, CiE 2024, Proceedings
Y2 - 8 July 2024 through 12 July 2024
ER -