Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-03T00:49:26.393Z Has data issue: false hasContentIssue false
  • English
  • Français

Formalising foundations of mathematics†

Published online by Cambridge University Press:  01 July 2011

MIHNEA IANCU  and
FLORIAN RABE
MIHNEA IANCU
Affiliation:
Computer Science, Jacobs University Bremen, Bremen, Germany Email: [email protected]; [email protected]
FLORIAN RABE
Affiliation:
Computer Science, Jacobs University Bremen, Bremen, Germany Email: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Over recent decades there has been a trend towards formalised mathematics, and a number of sophisticated systems have been developed both to support the formalisation process and to verify the results mechanically. However, each tool is based on a specific foundation of mathematics, and formalisations in different systems are not necessarily compatible. Therefore, the integration of these foundations has received growing interest. We contribute to this goal by using LF as a foundational framework in which the mathematical foundations themselves can be formalised and therefore also the relations between them. We represent three of the most important foundations – Isabelle/HOL, Mizar and ZFC set theory – as well as relations between them. The relations are formalised in such a way that the framework permits the extraction of translation functions, which are guaranteed to be well defined and sound. Our work provides the starting point for a systematic study of formalised foundations in order to compare, relate and integrate them.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 21 , Special Issue 4: Interactive Theorem Proving and the Formalisation of Mathematics , August 2011 , pp. 883 - 911
Copyright
Copyright © Cambridge University Press 2011

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

Aczel, P. (1998) On Relating Type Theories and Set Theories. In: Altenkirch, T., Naraschewski, W. and Reus, B. (eds.) Types for Proofs and Programs 1–18.Google Scholar
Bancerek, G. (2003) On the structure of Mizar types. Electronic Notes in Theoretical Computer Science 85 69–85.CrossRefGoogle Scholar
Bourbaki, N. (1964) Univers. In: Séminaire de Géométrie Algébrique du Bois Marie – Théorie des topos et cohomologie étale des schémas, Springer-Verlag 185–217.Google Scholar
Brown, C. (2006) Combining Type Theory and Untyped Set Theory. In: Furbach, U. and Shankar, N. (eds.) International Joint Conference on Automated Reasoning. Springer-Verlag Lecture Notes in Computer Science 4130205–219.CrossRefGoogle Scholar
Church, A. (1940) A Formulation of the Simple Theory of Types. Journal of Symbolic Logic 5 (1)56–68.CrossRefGoogle Scholar
Constable, R. et al. . (1986) Implementing Mathematics with the Nuprl Development System, Prentice-Hall.Google Scholar
Coquand, T. and Huet, G. (1988) The Calculus of Constructions. Information and Computation 76 (2/3)95–120.CrossRefGoogle Scholar
de Bruijn, N. (1970) The Mathematical Language AUTOMATH. In: Laudet, M. (ed.) Proceedings of the Symposium on Automated Demonstration. Springer-Verlag Lecture Notes in Computer Science 2529–61.CrossRefGoogle Scholar
de Nivelle, H. (2010) Classical Logic with Partial Functions. In: Giesl, J. and Hähnle, R. (eds.) Automated Reasoning. Springer-Verlag Lecture Notes in Computer Science 6173203–217.CrossRefGoogle Scholar
Dumbrava, S. and Rabe, F. (2010) Structuring Theories with Partial Morphisms, Workshop on Abstract Development Techniques.Google Scholar
Farmer, W., Guttman, J. and Thayer, F. (1993) IMPS: An Interactive Mathematical Proof System. Journal of Automated Reasoning 11 (2)213–248.CrossRefGoogle Scholar
Fraenkel, A. (1922) The notion of ‘definite’ and the independence of the axiom of choice.Google Scholar
Gordon, M. (1988) HOL: A Proof Generating System for Higher-Order Logic. In: Birtwistle, G. and Subrahmanyam, P. (eds.) VLSI Specification, Verification and Synthesis, Kluwer-Academic Publishers 73–128.CrossRefGoogle Scholar
Gordon, M., Milner, R. and Wadsworth, C. (1979) Edinburgh LCF: A Mechanized Logic of Computation. Springer-Verlag Lecture Notes in Computer Science 78.Google Scholar
Gordon, M. and Pitts, A. (1993) The HOL Logic. In: Gordon, M. and Melham, T. (eds.) Introduction to HOL, Part III, Cambridge University Press 191–232.Google Scholar
Hales, T. (2003) The flyspeck project. (Available at http://code.google.com/p/flyspeck/.)Google Scholar
Harper, R., Honsell, F. and Plotkin, G. (1993) A framework for defining logics. Journal of the Association for Computing Machinery 40 (1)143–184.CrossRefGoogle Scholar
Harper, R., Sannella, D. and Tarlecki, A. (1994) Structured presentations and logic representations. Annals of Pure and Applied Logic 67 113–160.CrossRefGoogle Scholar
Harrison, J. (1996) HOL Light: A tutorial introduction. In: Srivas, M. and Camilleri, A. (eds.) Proceedings of the First International Conference on Formal Methods in Computer-Aided Design (FMCAD'96). Springer-Verlag Lecture Notes in Computer Science 1166265–269.Google Scholar
Hurd, J. (2009) OpenTheory: Package Management for Higher Order Logic Theories. In: Reis, G. D. and Théry, L. (eds.) Programming Languages for Mechanized Mathematics Systems, ACM 31–37.Google Scholar
Iancu, M. and Rabe, F. (2010) Formalizing Foundations of Mathematics, LF Encodings. (Available at https://latin.omdoc.org/wiki/FormalizingFoundations.)Google Scholar
Jaśkowski, S. (1934) On the rules of suppositions in formal logic. Studia Logica 1 5–32.Google Scholar
Keller, C. and Werner, B. (2010) Importing HOL Light into Coq. In: Kaufmann, M. and Paulson, L. (eds.) Proceedings Interactive Theorem Proving, ITP 2010. Springer-Verlag Lecture Notes in Computer Science 6172307–322.Google Scholar
Klein, G., Nipkow, T. and Paulson, L. (2004) Archive of Formal Proofs. (Available at http://afp.sourceforge.net/.)Google Scholar
Kohlhase, M., Mossakowski, T. and Rabe, F. (2009) The LATIN Project. (Available at https://trac.omdoc.org/LATIN/.)Google Scholar
Krauss, A. and Schropp, A. (2010) A Mechanized Translation from Higher-Order Logic to Set Theory. In: Kaufmann, M. and Paulson, L. (eds.) Proceedings Interactive Theorem Proving, ITP 2010. Springer-Verlag Lecture Notes in Computer Science 6172323–338.Google Scholar
Landau, E. (1930) Grundlagen der Analysis, Akademische Verlagsgesellschaft.Google Scholar
Lovas, W. and Pfenning, F. (2009) Refinement Types as Proof Irrelevance. In: Curien, P. (ed.) Typed Lambda Calculi and Applications. Springer-Verlag Lecture Notes in Computer Science 5608157–171.CrossRefGoogle Scholar
Matuszewski, R. (1990) Formalized Mathematics. (Available at http://mizar.uwb.edu.pl/fm/.)Google Scholar
McLaughlin, S. (2006) An Interpretation of Isabelle/HOL in HOL Light. In: Shankar, N. and Furbach, U. (eds.) International Joint Conference on Automated Reasoning. Springer-Verlag Lecture Notes in Computer Science 4130192–204.CrossRefGoogle Scholar
Mizar, (2009) Grammar, version 7.11.02. (Available at http://mizar.org/language/mizar-grammar.xml.)Google Scholar
Naumov, P., Stehr, M. and Meseguer, J. (2001) The HOL/NuPRL proof translator – a practical approach to formal interoperability. In: Boulton, R. and Jackson, P. (eds.) 14th International Conference on Theorem Proving in Higher Order Logics. Springer-Verlag Lecture Notes in Computer Science 2152329–345.CrossRefGoogle Scholar
Nipkow, T., Paulson, L. and Wenzel, M. (2002) Isabelle/HOL – A Proof Assistant for Higher-Order Logic. Springer-Verlag Lecture Notes in Computer Science 2283.Google Scholar
Norell, U. (2005) The Agda WiKi. (Available at http://wiki.portal.chalmers.se/agda.)Google Scholar
Obua, S. and Skalberg, S. (2006) Importing HOL into Isabelle/HOL. In: Shankar, N. and Furbach, U. (eds.) International Joint Conference on Automated Reasoning. Springer-Verlag Lecture Notes in Computer Science 4130298–302.CrossRefGoogle Scholar
Owre, S., Rushby, J. and Shankar, N. (1992) PVS: A Prototype Verification System. In: Kapur, D. (ed.) 11th International Conference on Automated Deduction (CADE). Springer-Verlag Lecture Notes in Computer Science 607748–752.Google Scholar
Paulson, L. (1994) Isabelle: A Generic Theorem Prover. Springer-Verlag Lecture Notes in Computer Science 828.Google Scholar
Paulson, L. and Coen, M. (1993) Zermelo-Fraenkel Set Theory. Isabelle distribution, ZF/ZF.thy.Google Scholar
Pfenning, F. and Schürmann, C. (1999) System description: Twelf – a meta-logical framework for deductive systems. Lecture Notes in Computer Science 1632 202–206.CrossRefGoogle Scholar
Pfenning, F., Schürmann, C., Kohlhase, M., Shankar, N. and Owre, S. (2003) The Logosphere Project. (Available at http://www.logosphere.org/.)Google Scholar
Poswolsky, A. and Schürmann, C. (2008) System Description: Delphin – A Functional Programming Language for Deductive Systems. In: Abel, A. and Urban, C. (eds.) International Workshop on Logical Frameworks and Metalanguages: Theory and Practice. Electronic Notes in Theoretical Computer Science 228 135–141.Google Scholar
Rabe, F. (2010) Representing Isabelle in LF. In: Crary, K. and Miculan, M. (eds.) Logical Frameworks and Meta-languages: Theory and Practice. EPTCS 34 85–99.CrossRefGoogle Scholar
Rabe, F. and Schürmann, C. (2009) A Practical Module System for LF. In: Cheney, J. and Felty, A. (eds.) Proceedings of the Workshop on Logical Frameworks: Meta-Theory and Practice (LFMTP), ACM Press 40–48.Google Scholar
Schürmann, C. and Stehr, M. (2004) An Executable Formalization of the HOL/Nuprl Connection in the Metalogical Framework Twelf. In: Hermann, M. and Voronkov, A. (eds.) 11th International Conference on Logic for Programming Artificial Intelligence and Reasoning. Springer-Verlag Lecture Notes in Computer Science 4246150–166.Google Scholar
Hales, T., Gonthier, G., Harrison, J. and Wiedijk, F. (2008) A Special Issue on Formal Proof. Notices of the AMS 55 (11).Google Scholar
Tarski, A. (1938) Über Unerreichbare Kardinalzahlen. Fundamenta Mathematicae 30 176–183.CrossRefGoogle Scholar
Trybulec, A. (1989) Tarski Grothendieck Set Theory. Journal of Formalized Mathematics, Axiomatics 1 (1)9–11.Google Scholar
Trybulec, A. and Blair, H. (1985) Computer Assisted Reasoning with MIZAR. In: Joshi, A. (ed.) Proceedings of the 9th International Joint Conference on Artificial Intelligence, Morgan Kaufmann Publishers 26–28.Google Scholar
Urban, J. (2003) Translating Mizar for First Order Theorem Provers. In: Asperti, A., Buchberger, B. and Davenport, J. (eds.) Mathematical Knowledge Management: Second International Conference, MKM 2003. Springer-Verlag Lecture Notes in Computer Science 2594203–215.CrossRefGoogle Scholar
van Benthem Jutting, L. (1977) Checking Landau's ‘Grundlagen’ in the AUTOMATH system, Ph.D. thesis, Eindhoven University of Technology.Google Scholar
Wenzel, M. (2009) The Isabelle/Isar Reference Manual. (Available at http://isabelle.in.tum.de/documentation.html.)Google Scholar
Whitehead, A. and Russell, B. (1913) Principia Mathematica, Cambridge University Press.Google Scholar
Wiedijk, F. (2006) Is ZF a hack? Comparing the complexity of some (formalist interpretations of) foundational systems for mathematics. Journal of Applied Logic 4 (4)622–645.CrossRefGoogle Scholar
Wiedijk, F. (2007) Mizar's Soft Type System. In: Schneider, K. and Brandt, J. (eds.) Theorem Proving in Higher Order Logics. Springer-Verlag Lecture Notes in Computer Science 4732383–399.CrossRefGoogle Scholar
Wiener, N. (1967) A Simplification of the Logic of Relations. In: van Heijenoort, J. (ed.) From Frege to Gödel, Harvard University Press 224–227.Google Scholar
Zermelo, E. (1908) Untersuchungen über die Grundlagen der Mengenlehre I. Mathematische Annalen 65 261–281. (English title: Investigations in the foundations of set theory I.)CrossRefGoogle Scholar