Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T03:01:52.906Z Has data issue: false hasContentIssue false
  • English
  • Français

A COMPARISON OF VARIOUS ANALYTIC CHOICE PRINCIPLES

Part of: Computability and recursion theory General logic

Published online by Cambridge University Press:  08 June 2021

PAUL-ELLIOT ANGLÈS D’AURIAC  and
TAKAYUKI KIHARA
PAUL-ELLIOT ANGLÈS D’AURIAC
Affiliation:
L ACL, DÉPARTEMENT D’INFORMATIQUE FACULTÉ DES SCIENCES ET TECHNOLOGIE 61 AVENUE DU GÉNÉRAL DE GAULLE94010CRÉTEIL CEDEX, FRANCEE-mail: [email protected]
TAKAYUKI KIHARA
Affiliation:
DEPARTMENT OF MATHEMATICAL INFORMATICS GRADUATE SCHOOL OF INFORMATICS NAGOYA UNIVERSITY, JAPANE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate computability theoretic and descriptive set theoretic contents of various kinds of analytic choice principles by performing a detailed analysis of the Medvedev lattice of $\Sigma ^1_1$ -closed sets. Among others, we solve an open problem on the Weihrauch degree of the parallelization of the $\Sigma ^1_1$ -choice principle on the integers. Harrington’s unpublished result on a jump hierarchy along a pseudo-well-ordering plays a key role in solving this problem.

Keywords

Weihrauch reducibilityarithmetical transfinite recusionΣ¹1-choice

MSC classification

Primary: 03D30: Other degrees and reducibilities
Secondary: 03D55: Hierarchies 03B30: Foundations of classical theories (including reverse mathematics)
Type
Article
Information
The Journal of Symbolic Logic , Volume 86 , Issue 4 , December 2021 , pp. 1452 - 1485
Check for updates
Copyright
© Association for Symbolic Logic 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bienvenu, L., Greenberg, N., and Monin, B., Continuous higher randomness. Journal of Mathematical Logic, vol. 17 (2017), no. 1, p. 1750004.CrossRefGoogle Scholar
Brattka, V., Gherardi, G., Hölzl, R., Nobrega, H., and Pauly, A., Borel choice, in preparation.Google Scholar
Brattka, V., Gherardi, G., and Pauly, A., Weihrauch complexity in computable analysis, Handbook of Computability and Complexity in Analysis (Brattka, V. and Hertling, P., editors), Springer, Cham, 2021, pp. 367–417.10.1007/978-3-030-59234-9_11CrossRefGoogle Scholar
Brattka, V. and Pauly, A., On the algebraic structure of Weihrauch degrees. Logical Methods in Computer Science, vol. 14 (2018), no. 4.Google Scholar
Cenzer, D. and Hinman, P.G., Density of the Medvedev lattice of ${\varPi}_1^0$ classes. Archive for Mathematical Logic, vol. 42 (2003), no. 6, pp. 583–600.10.1007/s00153-002-0166-7CrossRefGoogle Scholar
Enderton, H. B. and Putnam, H., A note on the hyperarithmetical hierarchy, this Journal, vol. 35 (1970), no. 3, pp. 429–430.Google Scholar
Friedman, H., Subsystems of analysis , Ph.D. thesis, Massachusetts Institute of Technology, ProQuest LLC, Ann Arbor, MI, 1968.Google Scholar
Friedman, H., Uniformly defined descending sequences of degrees, this Journal, vol. 41 (1976), no. 2, pp. 363–367.Google Scholar
Goh, J. L., Some computability-theoretic reductions between principles around ATR 0, preprint, 2019, arXiv:1905.06868.Google Scholar
Goh, J. L., Measuring the relative complexity of mathematical constructions and theorems , Ph.D. thesis, Cornell University, 2019.Google Scholar
Gregoriades, V., Classes of Polish spaces under effective Borel isomorphism. Memoirs of the American Mathematical Society, vol. 240 (2016), no. 1135.CrossRefGoogle Scholar
Hinman, P. G., Recursion-Theoretic Hierarchies, Perspectives in Mathematical Logic, vol. 9, Springer, Berlin and New York, 1978.10.1007/978-3-662-12898-5CrossRefGoogle Scholar
Kechris, A., Classical Descriptive Set Theory, Springer, New York, 1995.CrossRefGoogle Scholar
Kihara, T., Marcone, A., and Pauly, A., Searching for an analogue of ATR in the Weihrauch lattice, this Journal, vol. 85 (2020), no. 3, pp. 1006–1043.Google Scholar
Kihara, T. and Pauly, A., Dividing by zero—How bad is it, really? 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (Faliszewski, P., Muscholl, A., and Niedermeier, R., editors), Leibniz International Proceedings in Informatics (LIPIcs), vol. 58, Schloss Dagstuhl, Wadern, 2016, pp. 58:1–58:14.Google Scholar
Medvedev, Y.T., Degrees of difficulty of the mass problem. Doklady Akademii Nauk SSSR, New Series, vol. 104 (1955), pp. 501–504.Google Scholar
Moschovakis, Y. N., Descriptive Set Theory, second ed., Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, 2009.10.1090/surv/155CrossRefGoogle Scholar
Sacks, G. E., Higher Recursion Theory, Perspectives in Mathematical Logic, vol. 2, Springer, Berlin, 1990.CrossRefGoogle Scholar
Simpson, S., Subsystems of Second Order Arithmetic, Perspectives in Logic, Cambridge University Press, Cambridge, 2009.10.1017/CBO9780511581007CrossRefGoogle Scholar
Steel, J., Descending sequences of degrees, this Journal, vol. 40 (1975), no. 1, pp. 59–61.Google Scholar
Steel, J.R., A note on analytic sets. Proceedings of the American Mathematical Society, vol. 80 (1980), no. 4, pp. 655–657.10.1090/S0002-9939-1980-0587948-XCrossRefGoogle Scholar
Tanaka, K., The hyperarithmetical axiom of choice HAC and its companions. Sūrikaisekikenkyūsho Kōkyūroku, vol. 1301 (2003), pp. 79–83.Google Scholar