Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-02T19:22:14.411Z Has data issue: false hasContentIssue false
  • English
  • Français

Validating Brouwer's continuity principle for numbers using named exceptions

Published online by Cambridge University Press:  02 November 2017

VINCENT RAHLI  and
MARK BICKFORD
VINCENT RAHLI
Affiliation:
SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg Email: [email protected]
MARK BICKFORD
Affiliation:
Cornell University, Computer Science Department, Ithaca, NY, USA Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper extends the Nuprl proof assistant (a system representative of the class of extensional type theories with dependent types) with named exceptions and handlers, as well as a nominal fresh operator. Using these new features, we prove a version of Brouwer's continuity principle for numbers. We also provide a simpler proof of a weaker version of this principle that only uses diverging terms. We prove these two principles in Nuprl's metatheory using our formalization of Nuprl in Coq and reflect these metatheoretical results in the Nuprl theory as derivation rules. We also show that these additions preserve Nuprl's key metatheoretical properties, in particular consistency and the congruence of Howe's computational equivalence relation. Using continuity and the fan theorem, we prove important results of Intuitionistic Mathematics: Brouwer's continuity theorem, bar induction on monotone bars and the negation of the law of excluded middle.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 28 , Issue 6 , June 2018 , pp. 942 - 990
Copyright
Copyright © Cambridge University Press 2017 

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

Allen, S. (2006). An abstract semantics for atoms in Nuprl, Technical report TR2006-2032, Cornell University.Google Scholar
Allen, S.F. (1987a). A non-type-theoretic definition of Martin-Löf's types. In: Proceedings of Second IEEE Symposium on Logic in Computer Science 215–221.Google Scholar
Allen, S.F. (1987b). A Non-Type-Theoretic Semantics for Type-Theoretic Language, PhD thesis, Cornell University.Google Scholar
Allen, S.F., Bickford, M., Constable, R.L., Eaton, R., Kreitz, C., Lorigo, L. and Moran, E. (2006). Innovations in computational type theory using Nuprl. Journal of Applied Logic 4 (4) 428–469, http://www.nuprl.org/.Google Scholar
Anand, A., Bickford, M., Constable, R.L. and Rahli, V. (2014). A Type Theory with Partial Equivalence Relations as Types, Presented at TYPES 2014.Google Scholar
Anand, A. and Rahli, V. (2014a). Towards a Formally Verified Proof Assistant, ITP 2014, Klein, G. and Gamboa, R. (eds.) Lecture Notes in Computer Science, vol. 8558, Springer, 27–44.Google Scholar
Anand, A. and Rahli, V. (2014b). Towards a formally verified proof assistant. Technical report, Cornell University, http://www.nuprl.org/html/Nuprl2Coq/.CrossRefGoogle Scholar
Avigad, J. (2004). Forcing in proof theory. Bulletin of Symbolic Logic 10 (3) 305–333.Google Scholar
Bauer, A. and Pretnar, M. (2015). Programming with algebraic effects and handlers. Journal of Logical and Algebraic Methods in Programming 84 (1) 108–123.Google Scholar
Beeson, M.J. (1985). Foundations of Constructive Mathematics, Springer.Google Scholar
Berardi, S., Bezem, M. and Coquand, T. (1998). On the computational content of the axiom of choice. Journal of Symbolic Logic 63 (2) 600–622.Google Scholar
Berger, U. and Oliva, P. (2006). Modified bar recursion. Mathematical Structures in Computer Science 16 (2) 163–183.Google Scholar
Bertot, Y. and Casteran, P. (2004). Interactive Theorem Proving and Program Development, Springer-Verlag, http://www.labri.fr/perso/casteran/CoqArt.CrossRefGoogle Scholar
Bickford, M. (2008). Unguessable atoms: A logical foundation for security. In: Proceedings of the 2nd International Conference on Verified Software: Theories, Tools, Experiments, Lecture Notes in Computer Science, vol. 5295, Springer, 30–53.Google Scholar
Bishop, E. and Bridges, D. (1985). Constructive Analysis, Springer.Google Scholar
Bojanczyk, M., Braud, L., Klin, B. and Lasota, , (S. 2012). Towards nominal computation. In: POPL'12, ACM, 401–412.Google Scholar
Bove, A., Dybjer, P. and Norell, U. (2009). A brief overview of Agda - a functional language with dependent types. In: TPHOLs 2009, Lecture Notes in Computer Science, vol. 5674, Springer, pp. 73–78, http://wiki.portal.chalmers.se/agda/pmwiki.php.Google Scholar
Brady, E. (2011). Idris —: systems programming meets full dependent types. In: PLPV 2011, ACM, 43–54.Google Scholar
Bridges, D. and Richman, F. (1987). Varieties of Constructive Mathematics, London Mathematical Society Lecture Notes Series, Cambridge University Press.Google Scholar
Cheney, J. (2009). A simple nominal type theory. Electronic Notes in Theoretical Computer Science 228 37–52.CrossRefGoogle Scholar
Cheney, J. (2012). A dependent nominal type theory. Logical Methods in Computer Science 8 (1) 1–29.Google Scholar
Cheney, J. and Urban, C. (2004). Alpha-prolog: A logic programming language with names, binding and a-equivalence. In: ICLP 2004, Lecture Notes in Computer Science, vol. 3132, Springer, 269–283.Google Scholar
Cheney, J. and Urban, C. (2008). Nominal logic programming. ACM Transactions on Programming Languages and Systems 30 (5) Article No. 26. doi:10.1145/1387673.1387675.Google Scholar
Cohen, P.J. (1963). The independence of the continuum hypothesis. The National Academy of Sciences of the United States of America 50 (6) 1143–1148.CrossRefGoogle ScholarPubMed
Cohen, P.J. (1964). The independence of the continuum hypothesis ii. The National Academy of Sciences of the United States of America 51 (1) 105–110.Google Scholar
Constable, R.L. (1983). Constructive mathematics as a programming logic I: Some principles of theory. Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 158, Springer, 64–77.Google Scholar
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. and Smith, S.F. (1986). Implementing Mathematics with the Nuprl Proof Development System, Prentice-Hall, Inc.Google Scholar
Constable, R. and Bickford, M. (2014). Intuitionistic completeness of first-order logic. Annals of Pure and Applied Logic 165 (1) 164–198.Google Scholar
Constable, R.L. and Hickey, J. (2000). Nuprl's class theory and its applications. Foundations of Secure Computation, NATO ASI Series, Series F: Computer & System Sciences, IOS Press, 91–116.Google Scholar
Constable, R.L. and Smith, S.F. (1993). Computational foundations of basic recursive function theory. Theoretical Computer Science 121 (1&2) 89–112.CrossRefGoogle Scholar
Coquand, T. and Jaber, G. (2010). A note on forcing and type theory. Fundamenta Informaticae 100 (1–4) 43–52.Google Scholar
Coquand, T. and Jaber, G. (2012). A computational interpretation of forcing in type theory. In: Epistemology versus Ontology, Logic, Epistemology, and the Unity of Science, Springer, 203–213.Google Scholar
Coquand, T. and Paulin, C. (1988). Inductively defined types. In: COLOG-88, International Conference on Computer Logic, Lecture Notes in Computer Science, vol. 417, Springer, 50–66.Google Scholar
Crary, K. (1998). Type-Theoretic Methodology for Practical Programming Languages, PhD thesis, Cornell University.Google Scholar
Crole, R.L. and Nebel, F. (2013). Nominal lambda calculus: An internal language for fm-cartesian closed categories. Electronic Notes in Theoretical Computer Science 298 93–117.Google Scholar
Danvy, O. and Filinski, A. (1990). Abstracting control. In: LISP and Functional Programming, 151–160.Google Scholar
David, R. and Mounier, G. (2005). An intuitionistic λ-calculus with exceptions. Journal of Functional Programming 15 (1) 33–52.Google Scholar
de Groote, P. (1995). A simple calculus of exception handling. In: TLCA '95, Lecture Notes in Computer Science, vol. 902, Springer, 201–215.Google Scholar
Dummett, M.A.E. (1977). Elements of Intuitionism, 2nd ed., Clarendon Press.Google Scholar
Escardó, M. and Oliva, P. (2015). Bar recursion and products of selection functions. Journal of Symbolic Logic 80 (1) 1–28.CrossRefGoogle Scholar
Escardó, M.H. (2007). Infinite sets that admit fast exhaustive search. In: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007) 443–452.Google Scholar
Escardó, M.H. (2008). Exhaustible sets in higher-type computation. Logical Methods in Computer Science 4 (3) 1–37.Google Scholar
Escardó, M.H. (2013). Continuity of Gödel's system T definable functionals via effectful forcing. Electronic Notes in Theoretical Computer Science 298 119–141.Google Scholar
Escardó, M.H. and Xu, C. (2015). The inconsistency of a Brouwerian continuity principle with the Curry-Howard interpretation. In: TLCA 2015, LIPIcs, vol. 38, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik., 153–164.Google Scholar
Fairweather, E., Fernández, M., Szasz, N. and Tasistro, A. (2015). Dependent types for nominal terms with atom substitutions. In: TLCA 2015, LIPIcs, vol. 38, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik., 180–195.Google Scholar
Felleisen, M. (1988). The theory and practice of first-class prompts. In: Ferrante, J. and Mager, P. (eds.) POPL 1988, ACM Press, 180–190.Google Scholar
Felleisen, M., Friedman, D.P., Kohlbecker, E.E. and Duba, B.F. (1986). Reasoning with continuations. In: LICS '86, IEEE Computer Society, 131–141.Google Scholar
Gabbay, M. and Pitts, A.M. (1999). A new approach to abstract syntax involving binders. In: Proceedings of the 14th Symposium on Logic in Computer Science (LICS 1999) 214–224.Google Scholar
Gielen, W., de Swart, H.C.M. and Veldman, W. (1981). The continuum hypothesis in intuitionism. Journal of Symbolic Logic 46 (1) 121–136.Google Scholar
Girard, J.-Y., Taylor, P. and Lafont, Y. (1989). Proofs and Types, Cambridge University Press.Google Scholar
Gordon, A.D. (1995). Bisimilarity as a theory of functional programming. Electronic Notes in Theoretical Computer Science 1 232–252.Google Scholar
Gordon, M.J.C., Milner, R. and Wadsworth, C.P. (1979). Edinburgh LCF: A Mechanised Logic of Computation, Lecture Notes in Computer Science, vol. 78, Springer-Verlag.Google Scholar
Griffin, T. (1990). A formulae-as-types notion of control. In: Allen, F.E. (ed.) POPL 1990, ACM Press, 47–58.Google Scholar
Hickey, J.J. (2001). The MetaPRL Logical Programming Environment, PhD thesis, Cornell University.Google Scholar
Hofmann, M. (1995). Extensional Concepts in Intensional Type Theory, PhD thesis, University of Edinburgh.Google Scholar
Howard, W.A. and Kreisel, G. (1966). Transfinite induction and bar induction of types zero and one, and the role of continuity in intuitionistic analysis. Journal of Symbolic Logic 31 (3) 325–358.Google Scholar
Howe, D.J. (1989). Equality in lazy computation systems. In: LICS 1989, IEEE Computer Society, 198–203.Google Scholar
Howe, D.J. (1996). Semantic foundations for embedding HOL in Nuprl. In: Wirsing, M. and Nivat, M. (eds.) Algebraic Methodology and Software Technology, Lecture Notes in Computer Science, vol. 1101, Springer-Verlag, Berlin, 85–101.Google Scholar
Jeffrey, A. and Rathke, J. (1999). Towards a theory of bisimulation for local names. In: Proceedings of the 14th Symposium on Logic in Computer Science (LICS 1999) 56–66.Google Scholar
Kameyama, Y. (2001). Dynamic control operators in type theory. In: APLAS'01, 1–11.Google Scholar
Kameyama, Y. and Yonezawa, T. (2008). Typed dynamic control operators for delimited continuations. In: Garrigue, J. and Hermenegildo, M.V. (eds.) FLOPS 2008, Lecture Notes in Computer Science, vol. 4989, Springer, 239–254.Google Scholar
Kleene, S.C. and Vesley, R.E. (1965). The Foundations of Intuitionistic Mathematics, Especially in Relation to Recursive Functions, North-Holland Publishing Company.Google Scholar
Kopylov, A. (2004). Type Theoretical Foundations for Data Structures, Classes, and Objects, PhD thesis, Cornell University.Google Scholar
Kopylov, A. and Nogin, A. (2001). Markov's principle for propositional type theory. In: CSL 2001, Lecture Notes in Computer Science, vol. 2142, Springer, 570–584.Google Scholar
Krebbers, R. and Spitters, B. (2011). Type classes for efficient exact real arithmetic in Coq. Logical Methods in Computer Science 9 (1) 1–27.Google Scholar
Kreisel, (1962). On weak completeness of intuitionistic predicate logic. The Journal of Symbolic Logic 27 (2) 139–158.Google Scholar
Krivine, J.-L. (1993). Lambda-Calculus, Types and Models, Ellis Horwood Series in Computers and their Applications, Masson.Google Scholar
Lebresne, S. (2008). A system F with call-by-name exceptions. ICALP 2008, Lecture Notes in Computer Science, vol. 5126, Springer, 323–335.Google Scholar
Lebresne, S. (2009). A type system for call-by-name exceptions. Logical Methods in Computer Science 5 (4).Google Scholar
Longley, J. (1999). When is a functional program not a functional program?. In: ICFP'99, ACM, 1–7.Google Scholar
Lösch, S. and Pitts, A.M. (2011). Relating two semantics of locally scoped names. In: CSL 2011, LIPIcs, vol. 12, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 396–411.Google Scholar
Martin-Löf, P. (1984). Intuitionistic type theory. In: Studies in Proof Theory, Lecture Notes, no. 1, Bibliopolis, Napoli.Google Scholar
Miquel, A. (2000). A model for impredicative type systems, universes, intersection types and subtyping. In: LICS 2000, IEEE Computer Society, 18–29.Google Scholar
Miquel, A. (2001a). The implicit calculus of constructions. In: TLCA, 344–359.Google Scholar
Miquel, A. (2001b). Le Calcul des Constructions Implicites: Syntaxe et Sémantique, PhD thesis, Université Paris 7.Google Scholar
Moore, G.H. (1988). The origins of forcing. In: Logic Colloquium '86, Elsevier Science Publishers B.V. (North-Holland), 143–173.Google Scholar
Murthy, C.R. (1991). An evaluation semantics for classical proofs. In: LICS '91, IEEE Computer Society, 96–107.Google Scholar
Nakano, H. (1994). A constructive logic behind the catch and throw mechanism. Annals of Pure and Applied Logic 69 (2–3) 269–301.Google Scholar
Nogin, A. (2002). Theory and Implementings of an Efficient Tactic-Based Logical Framework, PhD thesis, Cornell University.Google Scholar
Nogin, A. and Kopylov, A. (2006). Formalizing type operations using the ‘image’ type constructor. Electronic Notes in Theoretical Computer Science 165 121–132.Google Scholar
Normann, D. (2006). Computing with functionals - computability theory or computer science?. Bulletin of Symbolic Logic 12 (1) 43–59.Google Scholar
Odersky, M. (1994). A functional theory of local names. In: POPL'94, ACM Press, 48–59.CrossRefGoogle Scholar
Parigot, M. (1992). λμ-calculus: An algorithmic interpretation of classical natural deduction. In: Voronkov, A. (ed.) LPAR'92, Lecture Notes in Computer Science, vol. 624, Springer, 190–201.Google Scholar
Pitts, A.M. (2001). Nominal logic: A first order theory of names and binding. In: TACS 2001, Lecture Notes in Computer Science, vol. 2215, Springer, 219–242.Google Scholar
Pitts, A.M. (2010). Nominal system T. In: POPL'10, ACM, 159–170.Google Scholar
Pitts, A.M. (2013). Nominal Sets: Names and Symmetry in Computer Science, Cambridge University Press.Google Scholar
Pitts, A.M. and Gabbay, M. (2000). A metalanguage for programming with bound names modulo renaming. In: MPC 2000, Lecture Notes in Computer Science, vol. 1837, Springer, 230–255.Google Scholar
Pitts, A.M., Matthiesen, J. and Derikx, J. (2015). A dependent type theory with abstractable names. Mackie, I. and Ayala-Rincon, M. (eds.) Proceedings of the LSFA 2014 Workshop, Electronic Notes in Theoretical Computer Science, vol. 312, Elsevier, 19–50.Google Scholar
Pitts, A.M. and Stark, I.D.B. (1993). Observable properties of higher order functions that dynamically create local names, or what's new?. In: MFCS'93, Lecture Notes in Computer Science, vol. 711, Springer, 122–141.Google Scholar
Pottier, F. (2007). Static name control for FreshML. In: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007) 356–365.Google Scholar
Pouillard, P. and Pottier, F. (2010). A fresh look at programming with names and binders. In: ICFP 2010, ACM, 217–228.Google Scholar
Rahli, V. and Bickford, M. (2015). Coq as a metatheory for Nuprl with bar induction. Presented at CCC 2015. Available at http://www.nuprl.org/html/Nuprl2Coq/barind.pdf.Google Scholar
Rahli, V. and Bickford, M. (2016). A nominal exploration of intuitionism. In: Avigad, J. and Chlipala, A. (eds.) CPP 2016, ACM, 130–141.Google Scholar
Rahli, V., Bickford, M. and Anand, A. (2013). Formal program optimization in Nuprl using computational equivalence and partial types. In: ITP'13, Lecture Notes in Computer Science, vol. 7998, Springer, 261–278.Google Scholar
Rahli, V., Bickford, M. and Constable, R.L. (2016). A Story of Bar Induction in Nuprl. Extended version available at http://www.nuprl.org/html/Nuprl2Coq/bar-induction-long.pdf.Google Scholar
Rahli, V., Bickford, M. and Constable, R.L. (2017). Bar induction: The good, the bad, and the ugly. In: Abstract book of LICS 2017: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science. Open Access. (http://hdl.handle.net/10993/31268)Google Scholar
Rathjen, M. (2005). Constructive set theory and Brouwerian principles. Journal of UCS 11 (12) 2008–2033.Google Scholar
Rathjen, M. (2006). A note on bar induction in constructive set theory. Mathematical Logic Quarterly 52 (3) 253–258.Google Scholar
Sacchini, J.L. (2014). Exceptions in Dependent Type Theory, Presented at TYPES'14. Available at http://www.pps.univ-paris-diderot.fr/types2014/abstract-18.pdf.Google Scholar
Schöpp, U. (2006). Names and Binding in Type Theory, PhD thesis, University of Edinburgh.Google Scholar
Schöpp, U. and Stark, I. (2004). A dependent type theory with names and binding. In: CSL 2004, Lecture Notes in Computer Science, vol. 3210, Springer, 235–249.Google Scholar
Shinwell, M.R. (2006). Fresh O'Caml: Nominal abstract syntax for the masses. Electronic Notes in Theoretical Computer Science 148 (2) 53–77.Google Scholar
Shinwell, M.R., Pitts, A.M. and Gabbay, M.J. (2003). FreshML: Programming with binders made simple. SIGPLAN Notices 38 (9) 263–274.Google Scholar
Smith, S.F. (1989). Partial Objects in Type Theory, PhD thesis, Cornell University.Google Scholar
The Univalent Foundations Program (2013). Homotopy Type Theory: Univalent Foundations of Mathematics. Available at http://homotopytypetheory.org/book, Institute for Advanced Study.Google Scholar
Thielecke, H. (2000). On exceptions versus continuations in the presence of state. In: Smolka, G. (ed.) ESOP 2000, Lecture Notes in Computer Science, vol. 1782, Springer, 397–411.Google Scholar
Thielecke, H. (2001). Contrasting Exceptions and Continuations. Available at http://www.cs.bu.edu/fac/kfoury/CVS-Working-Files/CS520-Fall06/Handouts/contrasting-exceptions-and-continuations.pdf.Google Scholar
TLCA 2015 (2015). LIPIcs, vol. 38, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.Google Scholar
Troelstra, A.S. (1973). Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Springer.Google Scholar
Troelstra, A.S. (1975). Non-extensional equality. Fundamenta Mathematicae 82 (4) 307–322.Google Scholar
Troelstra, A.S. (1977a). Aspects of constructive mathematics. In: Handbook of Mathematical Logic, North-Holland Publishing Company, 973–1052.Google Scholar
Troelstra, A.S. (1977b). A note on non-extensional operations in connection with continuity and recursiveness. Indagationes Mathematicae 39 (5) 455–462.Google Scholar
Troelstra, A.S. and van Dalen, D. (1988). Constructivism in Mathematics an Introduction, Studies in Logic and the Foundations of Mathematics, vol. 121, Elsevier.Google Scholar
van Atten, M. and van Dalen, D. (2002). Arguments for the continuity principle. Bulletin of Symbolic Logic 8 (3) 329–347.Google Scholar
Veldman, W. (2001). Understanding and using Brouwer's continuity principle. In: Reuniting the Antipodes — Constructive and Nonstandard Views of the Continuum, Synthese Library, vol. 306, Springer Netherlands, 285–302 (English).Google Scholar
Veldman, W. (2006). Brouwer's real thesis on bars. Philosophia Scientiæ CS6, 21–42.Google Scholar
Veldman, W. (2014). Brouwer's fan theorem as an axiom and as a contrast to Kleene's alternative. Archive for Mathematical Logic 53 (5–6) 621–693.Google Scholar
Waaldijk, F. (2005). On the foundations of constructive mathematics – especially in relation to the theory of continuous functions. Foundations of Science 10 (3) 249–324.Google Scholar
Westbrook, E.M. (2008). Higher-order Encodings with Constructors, PhD thesis, Washington University.Google Scholar
Westbrook, E.M., Stump, A. and Austin, E. (2009). The calculus of nominal inductive constructions: An intensional approach to encoding name-bindings. In: LFMTP '09, ACM, 74–83.Google Scholar
Xu, C. (2015). A Continuous Computational Interpretation of Type Theories, PhD thesis, University of Birmingham.Google Scholar
Xu, C. and Hötzel, Escardó M. (2013). A constructive model of uniform continuity. In: TLCA 2013, Lecture Notes in Computer Science, vol. 7941, Springer, 236–249.Google Scholar