Abstract
The properties of continuous functions are very well-studied in computability theory and related areas. As it happens, there are many decompositions of continuity, which take the form
for certain spaces and where the weak continuity notions are generally independent. In this paper, we investigate the properties of some of these weak continuity notions in Kleene’s computability theory based on S1–S9. Interestingly, certain weak continuity notions can be analysed fully with rather modest means (Kleene’s quantifier \(\exists ^{2}\)), while others can be analysed with powerful tools (Kleene’s quantifier \(\exists ^{3}\)), but not with weaker oracles. In particular, finding the supremum on the unit interval is possible using \(\exists ^{2}\) for certain weak continuity notions, while for others the italicised operation is computable in \(\exists ^{3}\) but not in weaker oracles.
This research was supported by the Klaus Tschira Boost Fund (grant nr. GSO/KT 43) and RUB Bochum.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Rathjen states in [25] that \(\varPi _{2}^{1}\text {-}{\textsf {CA}}_{0}\) dwarfs \(\varPi _{1}^{1}\text {-}{\textsf {CA}}_{0}\) and Martin-Löf talks of a chasm and abyss between these two systems in [18], all in the context of ordinal analysis. Since the difference between \(\exists ^{2}\) and \(\exists ^{3}\) amounts to the difference between \({\textsf {ACA}}_{0}\) and \({\textsf {{Z}}}_{2}\) (see [28] for these systems), we believe ‘abyss’ to be apt.
- 2.
Note that \(\varphi (11\dots )=1\) and \(\varphi (g)=0\) for \(g\ne _{1} 11\dots \) by the definition of \((\exists ^{2})\), i.e. \(\lambda f.\varphi (f)\) is discontinuous at \(f=11\dots \) in the usual ‘epsilon-delta’ sense.
- 3.
We use ‘s-continuity’ as the full name was used by Baire for a different notion.
- 4.
If \(\mathfrak {c}\) is the cardinality of \(\mathbb {R}\), there are \(2^{\mathfrak {c}}\) non-measurable quasi-continuous \([0,1]\rightarrow \mathbb {R}\)-functions and \(2^{\mathfrak {c}}\) measurable quasi-continuous \([0,1]\rightarrow [0,1]\)-functions (see [13]).
References
Baire, R.: Sur les fonctions de variables réelles. Ann. di Mat. 1–123 (1899)
Bishop, E.: Foundations of Constructive Analysis. McGraw-Hill, New York (1967)
Borsík, J., Doboš, J.: A note on real cliquish functions. Real Anal. Exch. 18(1), 139–145 (1992/93)
Borsík, J.: Sums of quasicontinuous functions defined on pseudometrizable spaces. Real Anal. Exch. 22(1), 328–337 (1996/97)
Das, A., Nesterenko, V.: On decomposition of continuity, B-quasicontinuity and closed graph. Topol. Appl. 263, 325–329 (2019)
Dontchev, J.: Strong \(\mathscr {B}\)- sets and another decomposition of continuity. Acta Math. Hungar. 75(3), 259–265 (1997)
Dontchev, J.: Between \(\mathscr {A}\)- and \(\mathscr {B}\)- sets. Math. Balkanica 12(3–4), 295–302 (1998)
Gibson, R.G., Natkaniec, T.: Darboux like functions. Real Anal. Exch. 22(2), 492–533 (1996/97)
Grande, Z.: Sur les fonctions A-continues. Demonstr. Math. 11(2), 519–526 (1978). (French)
Gray, R.: Georg Cantor and transcendental numbers. Amer. Math. Monthly 101(9), 819–832 (1994)
Hatir, E., Noiri, T., Yüksel, S.: A decomposition of continuity. Acta Math. Hungar. 70(1–2), 145–150 (1996)
Hilbert, D., Bernays, P.: Grundlagen der Mathematik. II, Zweite Auflage. Die Grundlehren der mathematischen Wissenschaften, Band 50. Springer (1970)
Holá, Ľ.: There are \(2^\mathfrak{c}\) quasicontinuous non Borel functions on uncountable Polish space. Results Math. 76(3), 11 (2021). Paper No. 126
Kohlenbach, U., Higher order reverse mathematics. In: Reverse Mathematics, vol. 2005. Lecture Notes in Logic 21, pp. 281–295. ASL (2001)
Levine, N.: Semi-open sets and semi-continuity in topological spaces. Amer. Math. Monthly 70, 36–41 (1963)
Longley, J., Normann, D.: Higher-Order Computability. Theory and Applications of Computability. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47992-6
Maliszewski, A.: On the sums of Darboux upper semicontinuous quasi-continuous functions. Real Anal. Exch. 20(1), 244–249 (1994/95)
Martin-Löf, P.: The Hilbert-Brouwer controversy resolved? In: One Hundred Years of Intuitionism (1907–2007), pp. 243–256 (1967)
Normann, D.: Recursion on the Countable Functionals. Lecture Notes in Mathematics, vol. 811. Springer, Heidelberg (1980). https://doi.org/10.1007/BFb0098600
Normann, D., Sanders, S.: On the uncountability of \(\mathbb{R}\). J. Symb. Log. 43 (2022). https://doi.org/10.1017/jsl.2022.27
Normann, D., Sanders, S.: Betwixt Turing and Kleene. In: Artemov, S., Nerode, A. (eds.) LFCS 2022. LNCS, vol. 13137, pp. 236–252. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-93100-1_15
Normann, D., Sanders, S.: On the computational properties of basic mathematical notions. J. Log. Comput. 18 (2022). https://doi.org/10.1093/logcom/exac075
Normann, D., Sanders, S.: The biggest five of reverse mathematics. J. Math. Log. 56 (2023). https://doi.org/10.1142/S0219061324500077
Przemski, M.: A decomposition of continuity and \(\alpha \)- continuity. Acta Math. Hungar. 61(1–2), 93–98 (1993)
Rathjen, M.: The art of ordinal analysis. In: International Congress of Mathematicians, vol. II. European Mathematical Society, Zürich (2006)
Sakálová, K.: On graph continuity of functions. Demonstr. Math. 27(1), 123–128 (1994)
Sanders, S.: The non-normal abyss in Kleene’s computability theory. In: Della Vedova, G., Dundua, B., Lempp, S., Manea, F. (eds.) CiE 2023. LNCS, vol. 13967, pp. 37–49. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-36978-0_4
Simpson, S.G.: Subsystems of Second Order Arithmetic. Perspectives in Logic, vol. 2. CUP (2009)
Smith, B.D.: An alternate characterization of continuity. Proc. Amer. Math. Soc. 39, 318–320 (1973)
Soare, R.I.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer, Heidelberg (1987)
Tong, J.C.: A decomposition of continuity. Acta Math. Hungar. 48(1–2), 11–15 (1986)
Tong, J.C.: On decomposition of continuity in topological spaces. Acta Math. Hungar. 54(1–2), 51–55 (1989)
Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)
Hatice Yalvaç, T.: Decompositions of continuity. Acta Math. Hungar. 64(3), 309–313 (1994)
Young, W.H.: A theorem in the theory of functions of a real variable. Rendiconti del Circolo Matematico di Palermo XXIV, 187–192 (1907)
Acknowledgement
We thank the anonymous referees for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Sanders, S. (2024). On the Computational Properties of Weak Continuity Notions. In: Levy Patey, L., Pimentel, E., Galeotti, L., Manea, F. (eds) Twenty Years of Theoretical and Practical Synergies. CiE 2024. Lecture Notes in Computer Science, vol 14773. Springer, Cham. https://doi.org/10.1007/978-3-031-64309-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-64309-5_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-64308-8
Online ISBN: 978-3-031-64309-5
eBook Packages: Computer ScienceComputer Science (R0)