×

Higher order functions and Brouwer’s thesis. (English) Zbl 1520.03016

Summary: Extending Martín Escardó’s effectful forcing technique, we give a new proof of a well-known result: Brouwer’s monotone bar theorem holds for any bar that can be realized by a functional of type \((\mathbb{N} \rightarrow \mathbb{N})\rightarrow \mathbb{N}\) in Gödel’s System T. Effectful forcing is an elementary alternative to standard sheaf-theoretic forcing arguments, using ideas from programming languages, including computational effects, monads, the algebra interpretation of call-by-name \(\lambda \)-calculus, and logical relations. Our argument proceeds by interpreting System T programs as well-founded dialogue trees whose nodes branch on a query to an oracle of type \(\mathbb{N} \rightarrow \mathbb{N} \), lifted to higher type along a call-by-name translation. To connect this interpretation to the bar theorem, we then show that Brouwer’s famous “mental constructions” of barhood constitute an invariant form of these dialogue trees in which queries to the oracle are made maximally and in order.

MSC:

03F50 Metamathematics of constructive systems
03B40 Combinatory logic and lambda calculus
03F10 Functionals in proof theory
68N18 Functional programming and lambda calculus

References:

[1] Ackermann, W. (1928) Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen99(1), 118-133. · JFM 54.0056.06
[2] Anel, M. & Joyal, A. (2019) Topo-logie. Preprint.
[3] Awodey, S., Gambino, N., Lumsdaine, P. L. & Warren, M. A. (2009) Lawvere-Tierney sheaves in algebraic set theory. J. Symb. Logic.74(Sept.), 861-890. · Zbl 1183.03068
[4] Bauer, A. (2006) Sometimes all Functions are Continuous. Blog post.
[5] Bickford, M., Cohen, L., Constable, R. L. & Rahli, V. (2018) Computability beyond church-turing via choice sequences. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. pp. 245-254. ACM. · Zbl 1452.03133
[6] Brouwer, L. E. J. (1981) Brouwer’s Cambridge Lectures on Intuitionism. Cambridge University Press. · Zbl 1214.03048
[7] Capretta, V. & Uustalu, T. (2016) A coalgebraic view of bar recursion and bar induction. In Foundations of Software Science and Computation Structures: 19th International Conference, FOSSACS 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings,Jacobs, B. & Löding, C. (eds). Springer Berlin Heidelberg, pp. 91-106. · Zbl 1474.03105
[8] Constable, R. L., Allen, S. F., Bromley, H. M., Cleaveland, W. R., Cremer, J. F., Harper, R. W., Howe, D. J., Knoblock, T. B., Mendler, N. P., Panangaden, P., Sasaki, J. T. & Smith, S. F. (1986) Implementing Mathematics with the Nuprl Proof Development System. Prentice-Hall, Inc.
[9] Constable, R. (2014) Virtual Evidence: A Constructive Semantics for Classical Logics.
[10] Constable, R. and Bickford, M. (2014) Intuitionistic completeness of first-order logic. Ann. Pure Appl. Logic165(1), 164-198. The Constructive in Logic and Applications. · Zbl 1345.03114
[11] Coquand, T., Mannaa, B. & Ruch, F. (2017) Stack semantics of type theory. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-11. · Zbl 1452.03037
[12] Coquand, T. & Jaber, G. (2012) A computational interpretation of forcing in type theory. In Epistemology versus Ontology, Dybjer, P., Lindström, S., Palmgren, E. and Sundholm, G. (eds), Logic, Epistemology, and the Unity of Science, vol. 27. Springer Netherlands, pp. 203-213. · Zbl 1312.03021
[13] Coquand, T. & Mannaa, B. (2016) The independence of Markov’s principle in type theory. In 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016), Kesner, D. and Pientka, B. (eds), Leibniz International Proceedings in Informatics (LIPIcs), vol. 52. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 17:1:-17:18. · Zbl 1434.03137
[14] Coquand, T., Sambin, G., Smith, J. & Valentini, S. (2003) Inductively generated formal topologies. Ann. Pure Appl. Logic124(1), 71-106. · Zbl 1070.03041
[15] Dummett, M. (2000) Elements of Intuitionism. 2nd edn. Oxford Logic Guides, vol. 39. The Clarendon Press Oxford University Press. · Zbl 0949.03059
[16] Escardó, M. (2007) Seemingly Impossible Functional Programs. Guest post on Andrej Bauer’s blog.
[17] Escardó, M. (2013) Continuity of Gödel’s System T definable functionals via effectful forcing. Electron. Not. Theor. Comput. Sci.298, 119-141. Agda development: http://www.cs.bham.ac.uk/mhe/dialogue/dialogue-lambda.html. · Zbl 1334.68126
[18] Fourman, M. P. (1982) Notions of choice sequence. In L.E.J. Brouwer Centenary Symposium, Van Dalen, D. and Troelstra, A. (eds). North-Holland, pp. 91-105. · Zbl 0545.03036
[19] Fourman, M. P. (1984) Continuous Truth I: Non-constructive objects. In Logic Colloquium 1982, Lolli, G., G. L. and Marcja, A. (eds), Studies in Logic and the Foundations of Mathematics, vol. 112. Elsevier, pp. 161-180. · Zbl 0575.03041
[20] Fourman, M. P. (2013) Continuous truth II: Reflections. In Logic, Language, Information, and Computation: 20th International Workshop, WoLLIC 2013, Darmstadt, Germany, August 20-23, 2013. Proceedings, Libkin, L., Kohlenbach, U. and De Queiroz, R. (eds). Springer Berlin Heidelberg, pp. 153-167. · Zbl 1394.03084
[21] Fujiwara, M. & Kawai, T. (2019) Equivalence of bar induction and bar recursion for continuous functions with continuous moduli. Ann. Pure Appl. Logic170(8), 867-890. · Zbl 1459.03091
[22] Gambino, N. & Schuster, P. (2007) Spatiality for formal topologies. Mathematical. Structures in Comp. Sci.17(1), 65-80. · Zbl 1139.03045
[23] Gödel, K. (1958) Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes. Dialectica12(3-4), 280-287. · Zbl 0090.01003
[24] Harper, R. (2012) Exceptions are Shared Secrets. Blog post.
[25] Harper, R. (2016) Practical Foundations for Programming Languages. 2nd edn. Cambridge University Press. · Zbl 1347.68001
[26] Heyting, A. (1956) Intuitionism, an Introduction. Studies in Logic and the Foundations of Mathematics. North-Holland. Revised edition, 1966. · Zbl 0070.00801
[27] Hilbert, D. (1926) Über das Unendliche. Mathematische Annalen95, 161-190. · JFM 51.0044.02
[28] Jaber, G., Tabareau, N. & Sozeau, M. (2012) Extending type theory with forcing. In 2012 27th Annual IEEE Symposium on Logic in Computer Science, pp. 395-404. · Zbl 1364.03016
[29] Jaber, G., Lewertowski, G., Pédrot, P.-M., Sozeau, M. & Tabareau, N. (2016) The Definitional Side of the Forcing. Logics in Computer Science. · Zbl 1394.68063
[30] Johnstone, P. T. (1982) Stone Spaces. Cambridge Studies in Advanced Mathematics. Cambridge University Press. · Zbl 0499.54001
[31] Johnstone, P. T. (1983) The point of pointless topology. Bull. (New Ser.) Amer. Math. Soc.8(1), 41-53. · Zbl 0499.54002
[32] Kreisel, G. & Troelstra, A. S. (1970) Formal systems for some branches of intuitionistic analysis. Ann. Math. Logic1(3), 229-387. · Zbl 0211.01101
[33] Levy, P. B. (2006) Call-by-push-value: Decomposing call-by-value and call-by-name. Higher-Order Symb. Comput.19, 377-414. · Zbl 1112.68025
[34] Longley, J. (1999) When is a functional program not a functional program? In Proceedings of the Fourth ACM SIGPLAN International Conference on Functional Programming, ICFP 1999. ACM, pp. 1-7. · Zbl 1345.68064
[35] Longley, J. & Normann, D. (2015) Higher-Order Computability. Theory and Applications of Computability. Springer. · Zbl 1471.03002
[36] Mac Lane, S. & Moerdijk, I. (1992) Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Universitext. Springer. · Zbl 0822.18001
[37] Martin-Löf, P. (1970) Notes on Constructive Mathematics. Almqvist and Wiksell.
[38] Martin-Löf, P. (1979) Constructive mathematics and computer programming. In 6th International Congress for Logic, Methodology and Philosophy of Science, pp. 153-175. Published by North Holland, Amsterdam, 1982. · Zbl 0443.68039
[39] Norell, U. (2009) Dependently typed programming in Agda. In Proceedings of the 4th International Workshop on Types in Language Design and Implementation, TLDI 2009. ACM, pp. 1-2. · Zbl 1263.68038
[40] Oliva, P. & Steila, S. (2018) A direct proof of Schwichtenberg’s bar recursion closure theorem. J. Symb. Logic83(1), 70-83. · Zbl 1406.03059
[41] Pédrot, P. & Tabareau, N. (2017) An effectful way to eliminate addiction to dependence. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE Press, pp. 1-12. · Zbl 1452.03039
[42] Pédrot, P.-M. & Tabareau, N. (2019) The fire triangle: How to mix substitution, dependent elimination, and effects. Proc. ACM Program. Lang. 4(POPL).
[43] Petrakis, I. (2010) Brouwer’s Fan Theorem. Master’s Thesis.
[44] Rahli, V. & Bickford, M. (2016) A nominal exploration of Intuitionism. In Proceedings of the 5th ACM SIGPLAN Conference on Certified Programs and Proofs, CPP 2016. ACM, pp. 130-141.
[45] Rahli, V., Bickford, M. & Constable, R. (2017) Bar induction: The good, the bad, and the ugly. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-12. · Zbl 1457.68298
[46] Sambin, G. (2012) Real and ideal in constructive mathematics. In Epistemology versus Ontology, Dybjer, P., Lindström, S., Palmgren, E. and Sundholm, G. (eds), Logic, Epistemology, and the Unity of Science, vol. 27. Springer Netherlands, pp. 69-85. · Zbl 1312.03016
[47] Schwichtenberg, H. (1979) On bar recursion of types 0 and 1. J. Symb. Logic44(3), 325-329. · Zbl 0433.03037
[48] Spector, C. (1962) Provably recursive functionals of analysis: a consistency proof of analysis by an extension of principles in current intuitionistic mathematics. In Recursive Function Theory: Proc. Symposia in Pure Mathematics, Dekker, F. D. E. (ed), vol. 5. American Mathematical Society, pp. 1-27. · Zbl 0143.25502
[49] Sterling, J. & Harper, R. (2018) Guarded Computational Type Theory. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. ACM. · Zbl 1453.03027
[50] Streicher, T. (2005) Universes in toposes. In From Sets and Types to Topology and Analysis: Towards Practical Foundations for Constructive Mathematics, Crosilla, L. & Schuster, P. (eds), Oxford Logical Guides, vol. 48. Oxford University Press, pp. 78-90. · Zbl 1092.03038
[51] Sundholm, G. & Van Atten, M. (2008) The proper explanation of intuitionistic logic: on Brouwer’s demonstration of the bar theorem. In One Hundred Years of Intuitionism (1907-2007): The Cerisy Conference, Van Atten, M., Boldini, P., Bourdeau, M. & Heinzmann, G. (eds). Birkhäuser Basel, pp. 60-77.
[52] Tait, W. W. (1967) Intensional Interpretations of Functionals of Finite Type I. J. Symb. Logic32(2), 198-212. · Zbl 0174.01202
[53] Troelstra, A. & Van Dalen, D. (1988) Constructivism in Mathematics: An Introduction. Studies in Logic and the Foundations of Mathematics, vol. 1. North-Holland. · Zbl 0661.03047
[54] Van Atten, M., Van Dalen, D. & Tieszen, R. (2002) Brouwer and weyl: The phenomenology and mathematics of the intuitive continuumt. Philos. Math.10(2), 203-226. · Zbl 1032.01025
[55] Van Atten, M. (2004) On Brouwer. Wadsworth Philosophers Series. Thompson/Wadsworth. · Zbl 1072.03005
[56] Van Dalen, D. (2013) L.E.J. Brouwer: Topologist, Intuitionist, Philosopher: How Mathematics is Rooted in Life. Springer. · Zbl 1255.01024
[57] Van Der Hoeven, G. & Moerdijk, I. (1984) Sheaf models for choice sequences. Ann. Pure Appl. Logic27(1), 63-107. · Zbl 0546.03018
[58] Van Heijenoort, J. (2002) From Frege to Gödel : A Source Book in Mathematical Logic, 1879-1931 (Source Books in the History of the Sciences). Harvard University Press. · Zbl 1001.03005
[59] Vezzosi, A., Mörtberg, A. & Abel, A. (2019) Cubical Agda: A dependently typed programming language with univalence and higher inductive types. In Proceedings of the 24th ACM SIGPLAN International Conference on Functional Programming, ICFP 2019. ACM. · Zbl 1512.68058
[60] Vickers, S. (1989) Topology via Logic. Cambridge University Press. · Zbl 0668.54001
[61] Vickers, S. (2007) Locales and Toposes as Spaces. Springer Netherlands, pp. 429-496.
[62] Xu, C. (2015) A Continuous Computational Interpretation of Type Theories. PhD thesis, University of Birmingham.
[63] Xu, C. (2020a) A Gentzen-Style Monadic Translation of Gödel’s System T. In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020), Ariola, Z. M. (ed), Leibniz International Proceedings in Informatics (LIPIcs), vol. 167. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, pp. 25:1-25:17.
[64] Xu, C. (2020b) A syntactic approach to continuity of T-definable functionals. Log. Meth. Comput. Sci. 16(Feb.). · Zbl 1528.03115
[65] Xu, C. & Escardó, M. (2016) Universes in Sheaf Models. Unpublished note.
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.