×

Characterising Brouwer’s continuity by bar recursion on moduli of continuity. (English) Zbl 1496.03254

The paper studies the notions of continuity that arise from inductively generated neighborhood functions and from functions \(\mathbb{N}^{\mathbb{N}}\to \mathbb{N}\) having a bar recursive modulus of continuity, in a strictly constructive context (constructive reverse mathematics).
The inductively generated neighborhood function (called Brouwer operations in the paper) are given by two constructors of an inductive set \(\mathbb{K}\), \(\mathrm{L} : \mathbb{N}\to\mathbb{K}\) and \(\mathrm{Sup} : (\mathbb{N}\to\mathbb{K})\to\mathbb{K}\), and an associated (primitive / structurally decreasing) recursor \(\mathcal{R}\) satisfying the equations \begin{align*} \mathcal{R} u f & (\mathrm{L} x) = u x\\ \mathcal{R} u f & (\mathrm{Sup} \phi) = f \phi (\lambda x. \mathcal{R} u f (\phi x)). \end{align*}
A function \(\xi\) is a bar recursor for a function \(Y : (\mathbb{N}\to\mathbb{N})\to\mathbb{N}\) (the stopping condition for Spector’s bar recursion) if \begin{align*} \xi G H s & = G s &\text{when } Y(\hat{s})<|s|\\ \xi G H s & = H s (\lambda x. \xi G H (s*\langle x\rangle)) &\text{when } Y(\hat{s})\geq |s|. \end{align*} The recursion in this case is not primitive/structurally decreasing as in the case of Brouwer operations.
While usual/general neighborhood functions can be simply be seen as continuous moduli for the functions they induce, in the strictly constructive setting, the relation between inductively generated neighborhood functions and the continuity of functions they induce is more subtle and the subject of this paper. In either classical mathematics (in presence of classical logic and dependent choice) or in intuitionistic mathematics (in presence of bar induction and strong continuity for numbers), all neighborhood functions are inductively defined. Similarly, the relation between bar induction and bar recursion has not been extensively studied in the strictly constructive setting.
A first result of the paper is that a function \(Y : (\mathbb{N}\to\mathbb{N})\to\mathbb{N}\) is induced by a Brouwer operation if and only if it has a bar recursive modulus of continuity (Theorem 4.15).
A second contribution of the paper is the introduction of the following equivalence-of-continuity principles.
\(\text{BC}\)
Every continuous function \(Y : (\mathbb{N}\to\mathbb{N})\to\mathbb{N}\) is induced by a Brouwer operation / has a bar recursive modulus.
\(\text{BC}_{\text{c}}\)
Every continuous function \(Y : (\mathbb{N}\to\mathbb{N})\to\mathbb{N}\) with a continuous modulus is induced by a Brouwer operation / has a bar recursive modulus.
It is shown in Proposition 5.1 that \(\text{BC}_{\text{c}}\) is equivalent to decidable bar induction, in the presence of the axiom of countable choice and the axiom of choice for functions \(\mathbb{N}\to\mathbb{N}\) and quantifier-free formulas. \(\text{BC}\) is equivalent to continuous bar induction, in the presence of the axiom of countable choice and the axiom of choice for functions \(\mathbb{N}\to\mathbb{N}\) and \(\Pi^0_1\) formulas.
A third contribution of the paper is the transposition of the previous results in the settings of Cantor space and uniform continuity.
Reviewer: Danko Ilik (Paris)

MSC:

03F55 Intuitionistic mathematics
03B30 Foundations of classical theories (including reverse mathematics)
03F35 Second- and higher-order arithmetic and fragments
03F50 Metamathematics of constructive systems
03F10 Functionals in proof theory
Full Text: DOI

References:

[1] Avigad, J.; Feferman, S.; Buss, S., Gödel’s functional (“Dialectica”) interpretation, Handbook of Proof Theory, 337-405 (1998), Amsterdam: Elsevier, Amsterdam · Zbl 0913.03053 · doi:10.1016/S0049-237X(98)80020-7
[2] Berger, J.; Cooper, SB; Löwe, B.; Torenvliet, L., The fan theorem and uniform continuity, New Computational Paradigms CiE 2005, 18-22 (2005), Berlin: Springer, Berlin · Zbl 1115.03088
[3] Berger, J.; Beckmann, A.; Berger, U.; Löwe, B.; Tucker, JV, The logical strength of the uniform continuity theorem, Logical Approaches to Computational Barriers. CiE 2006, 35-39 (2006), Berlin: Springer, Berlin · Zbl 1145.03339 · doi:10.1007/11780342_4
[4] Bridges, D.; Richman, F., Varieties of Constructive Mathematics (1987), Cambridge: Cambridge University Press, Cambridge · Zbl 0618.03032 · doi:10.1017/CBO9780511565663
[5] Brouwer, L.E.J.: Über Definitionsbereiche von Funktionen. Math. Ann. 97, 60-75 (1927) (English translation of sections 1-3 in van Heijenoort, J.: From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, pp. 457-463. Harvard University Press, Cambridge, MA (1967))
[6] Diener, H.; Loeb, I., Sequences of real functions on \([0,1]\) in constructive reverse mathematics, Ann. Pure Appl. Logic, 157, 1, 50-61 (2009) · Zbl 1156.03056 · doi:10.1016/j.apal.2008.09.018
[7] Escardó, M.: Continuity of Gödel’s system T definable functionals via effectful forcing. In: Proceedings of the 29th Conference on the Mathematical Foundations of Programming Semantics, MFPS XXIX. Electronic Notes in Theoretical Computer Science, vol. 298, pp. 119-141. Elsevier, Amsterdam (2013) · Zbl 1334.68126
[8] Fujiwara, M.; Kawai, T., Equivalence of bar induction and bar recursion for continuous functions with continuous moduli, Ann. Pure Appl. Logic, 170, 8, 867-890 (2019) · Zbl 1459.03091 · doi:10.1016/j.apal.2019.04.001
[9] Fujiwara, M.; Kawai, T.; Liu, F.; Ono, H.; Yu, J., A logical characterization of the continuous bar induction, Knowledge, Proof and Dynamics: The Fourth Asian Workshop on Philosophical Logic, 25-33 (2020), Singapore: Springer, Singapore · Zbl 07910441 · doi:10.1007/978-981-15-2221-5_2
[10] Howard, WA, Functional interpretation of bar induction by bar recursion, Compos. Math., 20, 107-124 (1968) · Zbl 0162.31503
[11] Ishihara, H.; Crosilla, L.; Schuster, P., Constructive reverse mathematics: compactness properties, From Sets and Types to Topology and Analysis: Towards Practicable Foundations for Constructive Mathematics, number 48 in Oxford Logic Guides, 245-267 (2005), Oxford: Oxford University Press, Oxford · Zbl 1095.03075 · doi:10.1093/acprof:oso/9780198566519.003.0016
[12] Kawai, T., Principles of bar induction and continuity on Baire space, J. Log. Anal., 11, FT3, 1-20 (2019) · Zbl 1445.03071
[13] Kohlenbach, U., Applied Proof Theory: Proof Interpretations and Their Use in Mathematics (2008), Berlin: Springer, Berlin · Zbl 1158.03002
[14] Kreisel, G.; Troelstra, AS, Formal systems for some branches of intuitionistic analysis, Ann. Math. Logic, 1, 3, 229-387 (1970) · Zbl 0211.01101 · doi:10.1016/0003-4843(70)90001-X
[15] Oliva, P.; Steila, S., A direct proof of Schwichtenberg’s bar recursion closure theorem, J. Symb. Logic, 83, 1, 70-83 (2018) · Zbl 1406.03059 · doi:10.1017/jsl.2017.33
[16] Spector, C.; Dekker, FDE, Provably recursive functionals of analysis: a consistency proof of analysis by an extension of principles formulated in current intuitionistic mathematics, Recursive Function Theory : Proceedings of Symposia in Pure Mathematics, 1-27 (1962), Providence: American Mathematical Society, Providence · Zbl 0143.25502 · doi:10.1090/pspum/005/0154801
[17] Troelstra, AS, Metamathematical Investigation of Intuitionistic Arithmetic and Analysis (1973), Berlin: Springer, Berlin · Zbl 0275.02025
[18] Troelstra, A.S., van Dalen, D.: Constructivism in Mathematics: An Introduction, Volume I. Studies in Logic and the Foundations of Mathematics, vol. 121. North Holland, Amsterdam (1988) · Zbl 0653.03040
[19] Troelstra, A.S., van Dalen, D.: Constructivism in Mathematics: An Introduction, Volume II. Studies in Logic and the Foundations of Mathematics, vol. 123. North Holland, Amsterdam (1988) · Zbl 0661.03047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.