Formal Proof: Reconciling Correctness and Understanding | SpringerLink
Skip to main content
Springer Nature Link
Log in

Formal Proof: Reconciling Correctness and Understanding

  • Conference paper
Intelligent Computer Mathematics (CICM 2009)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 5625))

Included in the following conference series:

Abstract

Hilbert’s concept of formal proof is an ideal of rigour for mathematics which has important applications in mathematical logic, but seems irrelevant for the practice of mathematics. The advent, in the last twenty years, of proof assistants was followed by an impressive record of deep mathematical theorems formally proved. Formal proof is practically achievable. With formal proof, correctness reaches a standard that no pen-and-paper proof can match, but an essential component of mathematics — the insight and understanding — seems to be in short supply. So, what makes a proof understandable? To answer this question we first suggest a list of symptoms of understanding. We then propose a vision of an environment in which users can write and check formal proofs as well as query them with reference to the symptoms of understanding. In this way, the environment reconciles the main features of proof: correctness and understanding.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. AFP. Archive of formal proofs (March 2009), http://afp.sourceforge.net

  2. Aspinall, D.: Proof general: A generic tool for proof development. In: Proceedings of the 6th International Conference on Tools and Algorithms for Construction and Analysis of Systems, pp. 38–42. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  3. Audebaud, P., Rideau, L.: TeXMacs as authoring tool for publication and dissemination of formal developments. In: Aspinall, D., Lueth, C. (eds.) User-Interface for Theorem Provers. Electronic Notes in Theoretical Computer Science, vol. 103, pp. 27–48 (2004)

    Google Scholar 

  4. Autexier, S., Benzmüller, C., Dietrich, D., Meier, A., Wirth, C.-P.: A generic modular data structure for proof attempts alternating on ideas and granularity. In: Borwein, J.M., Farmer, W.M. (eds.) MKM 2006. LNCS (LNAI), vol. 4108, pp. 126–142. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  5. Autexier, S., Campbell, J., Rubio, J., Sorge, V., Suzuki, M., Wiedijk, F. (eds.): AISC 2008, Calculemus 2008, and MKM 2008. LNCS (LNAI), vol. 5144. Springer, Heidelberg (2008)

    Google Scholar 

  6. Autexier, S., Fiedler, A., Neumann, T., Wagner, M.: Supporting user-defined notations when integrating scientific text-editors with proof assistance systems. In: Kauers, M., Kerber, M., Miner, R., Windsteiger, W. (eds.) MKM/CALCULEMUS 2007. LNCS (LNAI), vol. 4573, pp. 176–190. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  7. Autexier, S., Benzmüller, C., Dietrich, D., Wagner, M.: Organisation, transformation, and propagation of mathematical knowledge in Ωmega. Journal of Mathematics in Computer Science (accepted, 2009)

    Google Scholar 

  8. Avigad, J.: Understanding proofs. In: Mancosu, P. (ed.) The Philosophy of Mathematical Practice, pp. 317–353. Oxford University Press, Oxford (2008)

    Chapter  Google Scholar 

  9. Berners-Lee, T., Fielding, R., Masinter, L.: Uniform Resource Identifier (URI): Generic Syntax. RFC 3986, Internet Engineering Task Force (2005)

    Google Scholar 

  10. Bertot, Y., Castéran, P.: Interactive Theorem Proving and Program Development – Coq’Art: The Calculus of Inductive Constructions. Springer, Heidelberg (2004)

    Book  MATH  Google Scholar 

  11. Bourbaki, N.: Theory of Sets. Elements of Mathematics. Springer, Heidelberg (1968)

    MATH  Google Scholar 

  12. Bridges, D., Richman, F.: Varieties of Constructive Mathematics. Cambridge University Press, Cambridge (1987)

    Book  MATH  Google Scholar 

  13. Bundy, A.: A science of reasoning. In: Lassez, J.L., Plotkin, G. (eds.) Computational Logic – Essays in Honor of A. Robinson, pp. 178–198. MIT Press, Cambridge (1989)

    Google Scholar 

  14. Calude, C.S.: Information and Randomness: An Algorithmic Perspective, 2nd edn. Springer, Heidelberg (2002)

    Book  MATH  Google Scholar 

  15. Calude, C.S., Calude, E., Marcus, S.: Passages of proof. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 84, 167–188 (2004)

    MathSciNet  MATH  Google Scholar 

  16. Calude, C.S., Calude, E., Marcus, S.: Proving and programming. In: Calude, C. (ed.) Randomness and Complexity, From Leibniz to Chaitin, pp. 310–321. World Scientific, Singapore (2007)

    Chapter  Google Scholar 

  17. Calude, C.S., Dinneen, M.J.: Exact approximations of Omega numbers. Int. Journal of Bifurcation & Chaos 17(6), 1937–1954 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Calude, C.S., Marcus, S.: Mathematical proofs at a crossroad? In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol. 3113, pp. 15–28. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  19. Calude, C.S., Hay, N.J.: Every Computably Enumerable Random Real Is Provably Computably Enumerable Random. Research Report of CDMTCS-328 (July 2008)

    Google Scholar 

  20. Chaitin, G.J.: The Limits of Mathematics. Springer, Heidelberg (1998)

    MATH  Google Scholar 

  21. Chaitin, G.J.: Meta Math! Pantheon (2005)

    Google Scholar 

  22. Cheikhrouhou, L., Sorge, V.: PDS – a three-dimensional data structure for proof plans. In: Proceedings of the International Conference on Artificial and Computational Intelligence for Decision, Control and Automation in Engineering and Industrial Applications (ACIDCA 2000), pp. 144–149 (2000)

    Google Scholar 

  23. Cohen, P.J.: Set Theory and the Continuum Hypothesis. Addison-Wesley, Reading (1966)

    MATH  Google Scholar 

  24. Cooper, S.B.: Computability Theory. Chapman &Hall/CRC (2004)

    Google Scholar 

  25. Feferman, S., Dawson Jr., J., Kleene, S.C., Moore, G.H., Solovay, R.M., van Heijenoort, J., Velleman, D.J. (eds.): Kurt Gödel Collected Works. Oxford University Press, Oxford (1986)

    Google Scholar 

  26. Fiedler, A.: User-adaptive Proof Explanation. PhD Thesis, Universität des Saarlandes, Saarbrücken, Germany (2001)

    Google Scholar 

  27. Giceva, J.: Capturing Rhetorical Aspects in Mathematical Documents using OMDoc and SALT. Technical Report, Jacobs University, Germany (2008)

    Google Scholar 

  28. Goguen, J.A.: Realization is universal. Theory of Computing Systems 6(4), 359–374 (1973)

    MathSciNet  MATH  Google Scholar 

  29. Gonthier, G.: Formal proof – The Four-Color Theorem. Notices of the AMS (11), 1382–1393 (2008)

    Google Scholar 

  30. Gowers, T.: Mathematics. A Very Short Introduction. Oxford University Press, Oxford (2002)

    Book  MATH  Google Scholar 

  31. Granas, A., Dugundji, J.: Fixed Point Theory. Springer, Heidelberg (2003)

    Book  MATH  Google Scholar 

  32. Hales, T.C.: Formal proof. Notices of the AMS (11), 1370–1380 (2008)

    Google Scholar 

  33. Harrison, J.: Formal proof – theory and practice. Notices of the AMS (11), 1395–1406 (2008)

    Google Scholar 

  34. Hay, N.J.: Formal Proof for the Kraft-Chaitin Theorem (March 2009), http://www.cs.auckland.ac.nz/~nickjhay/KraftChaitin.thy

  35. Kohlhase, M.: OMDoc – An Open Markup Format for Mathematical Documents [version 1.2]. LNCS, vol. 4180. Springer, Heidelberg (2006)

    Book  Google Scholar 

  36. Kohlhase, M.: XSLT Stylesheet for converting OMDoc documents into XHTML (January 2008), http://kwarc.info/projects/xslt

  37. Lane, S.M.: Despite physicists, proof is essential in mathematics. Synthese 111(2), 147–154 (1997)

    Article  MathSciNet  Google Scholar 

  38. Lange, C.: SWiM – a semantic wiki for mathematical knowledge management. In: Bechhofer, S., Hauswirth, M., Hoffmann, J., Koubarakis, M. (eds.) ESWC 2008. LNCS, vol. 5021, pp. 832–837. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  39. Leedham-Green, C.: Personal communication to C. Müller, March 7 (2009)

    Google Scholar 

  40. Loomis, E.S.: The Pythagorean Proposition, 2nd edn. Oxford University Press, Oxford (1968)

    MATH  Google Scholar 

  41. Manin, Y.I.: Mathematics as Metaphor. American Mathematical Society (2007)

    Google Scholar 

  42. Manola, F., Miller, E.: RDF Primer. W3C Recommendation, World Wide Web Consortium (February 2004)

    Google Scholar 

  43. Melis, E., Whittle, J.: Analogy in inductive theorem proving. Journal of Automated Reasoning 22(2), 117–147 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  44. Mizar (March 2009), http://web.cs.ualberta.ca/~piotr/Mizar

  45. Müller, C., Kohlhase, M.: Panta rhei. In: Hinneburg (ed.) LWA Conference Proceedings, pp. 318–323. Martin-Luther-University (2007)

    Google Scholar 

  46. Nelson, E.: Syntax and Semantics (March 2009), http://www.math.princeton.edu/~nelson/papers/s.pdf

  47. Berghofer, S., Nipkow, T.: Random testing in Isabelle/HOL. In: Cuellar, J., Liu, Z. (eds.) Software Engineering and Formal Methods (SEFM 2004), pp. 230–239. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  48. Nipkow, T., Paulson, L.C., Wenzel, M.T.: Isabelle/HOL. LNCS, vol. 2283. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  49. Normann, I.: Theory Morphisms. PhD Thesis, Jacobs University, Germany (2008)

    Google Scholar 

  50. OpenMathHome (March 2007), http://www.openmath.org

  51. Pólya, G.: Mathematics and Plausible Reasoning Volume I: Induction and Analogy in Mathematics. Princeton University Press, Princeton (1969)

    Google Scholar 

  52. Prud’hommeaux, E., Seaborne, A.: SPARQL Query Language for RDF. W3C Recommendation (March 2009), http://www.w3.org/TR/2008/REC-rdf-sparql-query-20080115/

  53. Rabe, F.: Representing Logics and Logic Translations. PhD Thesis, Jacobs University, Germany (2008)

    Google Scholar 

  54. Schiller, M., Dietrich, D., Benzmüller, C.: Proof step analysis for proof tutoring – a learning approach to granularity. Teaching Mathematics and Computer Science (in press) (2009)

    Google Scholar 

  55. Scott, W.R.: Group Theory. Dover, New York (1987)

    Google Scholar 

  56. Siekmann, J., Benzmüller, C., Fiedler, A., Meier, A., Normann, I., Pollet, M.: Proof development in OMEGA: The irrationality of square root of 2. In: Kamareddine, F. (ed.) Thirty Five Years of Automating Mathematics, pp. 271–314. Kluwer, Dordrecht (2003)

    Chapter  Google Scholar 

  57. Siekmann, J., Benzmüller, C., Fiedler, A., Meier, A., Pollet, M.: Proof development with Omega: Sqrt(2) is irrational. In: Baaz, M., Voronkov, A. (eds.) LPAR 2002. LNCS (LNAI), vol. 2514, pp. 367–387. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  58. Solovay, R.M.: A model of set-theory in which every set of reals is Lebesgue measurable. Annals of Mathematics 38(3), 1–56 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  59. Gnu TeXMacs (March 2009), http://www.texM.s.org

  60. vdash: A Formal Math Wiki (March 2009), http://www.vdash.org

  61. Weber, T.: Bounded model generation for isabelle/hol. Electronic Notes in Theoretical Computer Science 125(3), 103–116 (2005)

    Article  MATH  Google Scholar 

  62. Wenzel, M.: Personal communication to C. Müller, March 7 (2009)

    Google Scholar 

  63. Wenzel, M.: Isabelle/Isar – a generic framework for human-readable proof documents. In: Matuszewski, R., Zalewska, A. (eds.) From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Studies in Logic, Grammar and Rhetoric, vol. 10(23), pp. 277–298. University of Białystok (2007)

    Google Scholar 

  64. Wenzel, M.T.: Isar – a generic interpretative approach to readable formal proof documents. In: Bertot, Y., Dowek, G., Hirschowitz, A., Paulin, C., Théry, L. (eds.) TPHOLs 1999. LNCS, vol. 1690, pp. 167–184. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  65. Whitehead, A.N., Russell, B.: Principia Mathematica, 2nd edn., vol. I. Cambridge University Press, Cambridge (1910)

    MATH  Google Scholar 

  66. Wiedijk, F.: Formal proof – getting started. AMS Notices (11), 1408–1414 (2008)

    Google Scholar 

  67. Winterstein, D., Bundy, A., Gurr, C., Jamnik, M.: An experimental comparison of diagrammatic and algebraic logics. In: Blackwell, A.F., Marriott, K., Shimojima, A. (eds.) Diagrams 2004. LNCS, vol. 2980, pp. 432–434. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  68. Young, N.: An Introduction to Hilbert Space. Cambridge University Press, Cambridge (1988)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Auckland, New Zealand

    Cristian S. Calude & Christine Müller

  2. Department of Computer Science, Jacobs University Url: kwarc.info/cmueller, Bremen, Germany

    Christine Müller

Authors
  1. Cristian S. Calude
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christine Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computing and Software, McMaster University, 1280 Main Street West, L8S 4K1, Hamilton, ON, Canada

    Jacques Carette

  2. Informatics, 2.02 Informatics Forum, University of Edinburgh, 10 Crichton street, EH8 9AB, Edinburgh, UK

    Lucas Dixon

  3. Department of Computer Science, University of Bologna, via Mura Anteo Zamboni, 7, 40127, Bologna, Italy

    Claudio Sacerdoti Coen

  4. Department of Computer Science MC 375, University of Western Ontario, N6A 5B7, London, ON, Canada

    Stephen M. Watt

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Calude, C.S., Müller, C. (2009). Formal Proof: Reconciling Correctness and Understanding. In: Carette, J., Dixon, L., Coen, C.S., Watt, S.M. (eds) Intelligent Computer Mathematics. CICM 2009. Lecture Notes in Computer Science(), vol 5625. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02614-0_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02614-0_20

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02613-3

  • Online ISBN: 978-3-642-02614-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation