Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-11T10:56:30.457Z Has data issue: false hasContentIssue false
  • English
  • Français

MANY-ONE REDUCIBILITY WITH REALIZABILITY

Part of: Set theory Computability and recursion theory General logic

Published online by Cambridge University Press:  27 January 2025

TAKAYUKI KIHARA Open the ORCID record for TAKAYUKI KIHARA [Opens in a new window]
TAKAYUKI KIHARA*
Affiliation:
DEPARTMENT OF MATHEMATICAL INFORMATICS GRADUATE SCHOOL OF INFORMATICS NAGOYA UNIVERSITY NAGOYA JAPAN
*
E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article, we propose a new classification of $\Sigma ^0_2$ formulas under the realizability interpretation of many-one reducibility (i.e., Levin reducibility). For example, $\mathsf {Fin}$, the decision of being eventually zero for sequences, is many-one/Levin complete among $\Sigma ^0_2$ formulas of the form $\exists n\forall m\geq n.\varphi (m,x)$, where $\varphi $ is decidable. The decision of boundedness for sequences $\mathsf {BddSeq}$ and for width of posets $\mathsf {FinWidth}$ are many-one/Levin complete among $\Sigma ^0_2$ formulas of the form $\exists n\forall m\geq n\forall k.\varphi (m,k,x)$, where $\varphi $ is decidable. However, unlike the classical many-one reducibility, none of the above is $\Sigma ^0_2$-complete. The decision of non-density of linear orders $\mathsf {NonDense}$ is truly $\Sigma ^0_2$-complete.

Keywords

many-one reducibilityWadge reducibilityLevin reducibilityrealizabilityrepresented space

MSC classification

Primary: 03D30: Other degrees and reducibilities 03D55: Hierarchies
Secondary: 03E15: Descriptive set theory 03B40: Combinatory logic and lambda-calculus 03D45: Theory of numerations, effectively presented structures
Type
Article
Information
The Journal of Symbolic Logic , First View , pp. 1 - 39
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

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

REFERENCES

Bauer, A., The realizability approach to computable analysis and topology , Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, 2000.Google Scholar
Brattka, V., Gherardi, G., and Pauly, A., Weihrauch complexity in computable analysis, Handbook of Computability and Complexity in Analysis (V. Brattka and P. Hertling, editors), Springer International Publishing, Cham, 2021, pp. 367–417.Google Scholar
Forster, Y. and Jahn, F., Constructive and synthetic reducibility degrees: Post’s problem for many-one and truth-table reducibility in Coq , 31st EACSL Annual Conference on Computer Science Logic, LIPIcs. Leibniz International Proceedings in Informatics , 252, Schloss Dagstuhl. Leibniz-Center for Informatics, Wadern, 2023, Article no. 21.Google Scholar
Levin, L. A., Universal enumeration problems . Problemy Peredači Informacii, vol. 9 (1973), no. 3, pp. 115–116.Google Scholar
Odifreddi, P., Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, 125, North-Holland Publishing Co., Amsterdam, 1989, The theory of functions and sets of natural numbers, With a foreword by G. E. Sacks.Google Scholar
van Oosten, J., Realizability: An Introduction to its Categorical Side, Studies in Logic and the Foundations of Mathematics, 152, Elsevier B. V., Amsterdam, 2008.Google Scholar
Pequignot, Y., A Wadge hierarchy for second countable spaces . Archive of Mathematical Logic, vol. 54 (2015), nos. 5–6, pp. 659–683.CrossRefGoogle Scholar
Schlicht, P., Continuous reducibility and dimension of metric spaces . Archive of Mathematical Logic, vol. 57 (2018), nos. 3–4, pp. 329–359.CrossRefGoogle Scholar
Veldman, W., Investigations in intuitionistic hierarchy theory, Ph.D. thesis, Katholieke Universiteit, Nijmegen, 1981.Google Scholar
Veldman, W., A survey of intuitionistic descriptive set theory , Mathematical Logic, (P. P. Petkov, editor), Plenum, New York, 1990, pp. 155–174.CrossRefGoogle Scholar
Veldman, W., Two simple sets that are not positively Borel . Annals of Pure Applied Logic, vol. 135 (2005), nos. 1–3, pp. 151–209.CrossRefGoogle Scholar
Veldman, W., The fine structure of the intuitionistic Borel hierarchy . The Review of Symbolic Logic, vol. 2 (2009), no. 1, pp. 30–101.CrossRefGoogle Scholar
Veldman, W., Projective sets, intuitionistically . Journal of Logic Analysis, vol. 14 (2022), no. 5, Article no. 85.CrossRefGoogle Scholar