Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-24T12:40:48.020Z Has data issue: false hasContentIssue false
  • English
  • Français

The Relative Consistency of the Axiom of Choice Mechanized Using Isabelle⁄zf

Published online by Cambridge University Press:  01 February 2010

Lawrence C. Paulson
Lawrence C. Paulson
Affiliation:
Computer Laboratory, University of Cambridge, JJ Thomson Avenue, Cambridge CB3 OFD, [email protected], http://www.cl.cam.ac.uk/users/lcp

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The proof of the relative consistency of the axiom of choice has been mechanized using Isabelle⁄ZF, building on a previous mechanization of the reflection theorem. The heavy reliance on metatheory in the original proof makes the formalization unusually long, and not entirely satisfactory: two parts of the proof do not fit together. It seems impossible to solve these problems without formalizing the metatheory. However, the present development follows a standard textbook, Kenneth Kunen's Set theory: an introduction to independence proofs, and could support the formalization of further material from that book. It also serves as an example of what to expect when deep mathematics is formalized.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 6 , 2003 , pp. 198 - 248
Copyright
Copyright © London Mathematical Society 2003

References

1Bruijn, N.G. De, ‘Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem’, Indag. Math. 34 (1972) 381–392.CrossRefGoogle Scholar
2Davey, B.A. and Priestley, H.A., Introduction to lattices and order (Cambridge University Press, 1990).Google Scholar
3Feferman, S. et al. , eds, Kurt Gödel: collected works, vol. II. (Oxford University Press, 1990).Google Scholar
4Gödel, Kurt, ‘The consistency of the axiom of choice and of the generalized continuum hypothesis’, [3] 26–27; first published in Proc. Nat. Acad. Sci. USA (1938) 556–557.Google Scholar
5Gödel, Kurt, ‘The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory’, [3] 33–101; first published by Princeton University Press, 1940.Google Scholar
6Gödel, Kurt, ‘Consistency proof for the generalized continuum hypothesis’, [3] 27–32; first published in Proc. Nat. Acad. Sci. USA (1939) 220–224.Google Scholar
7Halmos, Paul R., Naive set theory (Van Nostrand, 1960).Google Scholar
8Kammüller, Florian, Wenzel, Markus and Paulson, Lawrence C. ‘Locales: a sectioning concept for Isabelle’, Theorem proving in higher order logics: TPHOLs '99, Lecture Notes in Comput. Sci. 1690 (ed. Bertot, Yves, Dowek, Gilles, Hirschowitz, André, Paulin, Christine and Théry, Laurent, Springer, 1999) 149–165.CrossRefGoogle Scholar
9Kunen, Kenneth, Set theory: an introduction to independence proofs (North-Holland, 1980).Google Scholar
10Mendelson, E., Introduction to mathematical logic, 4th edn (Chapman and Hall, 1997).Google Scholar
11Nipkow, Tobias, Paulson, Lawrence C. and Wenzel, Markus, Isabelle⁄HOL: a proof assistant for higher-order logic, Lecture Notes in Comput. Sci. Tutorial 2283 (Springer, 2002).CrossRefGoogle Scholar
12Paulson, Lawrence C., ‘The foundation of a generic theorem prover‘, J. Automat. Reasoning 5 (1989) 363–397.CrossRefGoogle Scholar
13Paulson, Lawrence C., ‘Set theory for verification: I. From foundations to functions‘, J. Automat. Reasoning 11 (1993) 353–389.CrossRefGoogle Scholar
14Paulson, Lawrence C., Isabelle: a generic theorem prover, Lecture Notes in Comput. Sci. 828 (Springer, 1994).Google Scholar
15Paulson, Lawrence C., ‘Set theory for verification: II. Induction and recursion’ J. Automat. Reasoning 15 (1995) 167–215.CrossRefGoogle Scholar
16Paulson, Lawrence C., ‘Proving properties of security protocols by induction‘, 10th Computer Security Foundations Workshop (IEEE Computer Society Press, 1997) 70–83.CrossRefGoogle Scholar
17Paulson, Lawrence C., ‘A fixedpoint approach to (co)inductive and (co)datatype definitions’, Proof, language, and interaction: essays in honor of Robin Milner (ed. Plotkin, Gordon, Stirling, Colin, and Tofte, Mads, MIT Press, 2000) 187–211.CrossRefGoogle Scholar
18Paulson, Lawrence C., ‘The reflection theorem: a study in meta-theoretic reasoning’, [22] 377–391.CrossRefGoogle Scholar
19Paulson, Lawrence C. and Grąbczewski, Krzysztof, ‘Mechanizing set theory:cardinal arithmetic and the axiom of choice’, J. Automat. Reasoning 17 (1996) 291–323.CrossRefGoogle Scholar
20Prawitz, Dag, ‘Ideas and results in proof theory‘, Second Scandinavian Logic Symposium (ed. Fenstad, J.E., North-Holland, 1971) 235’308.Google Scholar
21Strecker, Martin, ‘Formal verification of a Java compiler in Isabelle’, [22] 63–77.CrossRefGoogle Scholar
22Voronkov, Andrei, ed. Automated deduction – CADE-18 International Conference, Lecture Notes in Artificial Intelligence 2392 (Springer, 2002).CrossRefGoogle Scholar
Supplementary material: PDF

JCM 6 Paulson Appendix A

Paulson Appendix A

Download JCM 6 Paulson Appendix A(PDF)
PDF 749.2 KB