A Lost Proof (bibtex)
by Christoph Benzmüller, Manfred Kerber
Abstract:
We re-investigate a proof example presented by George Boolos which perspicuously illustrates Gödel's argument for the potentially drastic increase of proof-lengths in formal systems when carrying through the argument at too low a level. More concretely, restricting the order of the logic in which the proof is carried through to the order of the logic in which the problem is formulated in the first place can result in unmanageable long proofs, although there are short proofs in a logic of higher order. Our motivation in this paper is of practical nature and its aim is to sketch the implications of this example to current technology in automated theorem proving, to point to related questions about the foundational character of type theory (without explicit comprehension axioms) for mathematics, and to work out some challenging aspects with regard to the automation of this proof -- which, as we belief, nicely illustrates the discrepancy between the creativity and intuition required in mathematics and the limitations of state of the art theorem provers.
Reference:
A Lost Proof (Christoph Benzmüller, Manfred Kerber), In Proceedings of the IJCAR 2001 Workshop: Future Directions in Automated Reasoning, pp. 13-24, 2001. (Url (preprint): http://christoph-benzmueller.de/papers/W13.pdf)
Bibtex Entry:
@inproceedings{W13,
  Abstract =	 {We re-investigate a proof example presented by
                  George Boolos which perspicuously illustrates
                  G\"odel's argument for the potentially drastic
                  increase of proof-lengths in formal systems when
                  carrying through the argument at too low a
                  level. More concretely, restricting the order of the
                  logic in which the proof is carried through to the
                  order of the logic in which the problem is
                  formulated in the first place can result in
                  unmanageable long proofs, although there are short
                  proofs in a logic of higher order. Our motivation in
                  this paper is of practical nature and its aim is to
                  sketch the implications of this example to current
                  technology in automated theorem proving, to point to
                  related questions about the foundational character
                  of type theory (without explicit comprehension
                  axioms) for mathematics, and to work out some
                  challenging aspects with regard to the automation of
                  this proof -- which, as we belief, nicely
                  illustrates the discrepancy between the creativity
                  and intuition required in mathematics and the
                  limitations of state of the art theorem provers.},
  Address =	 {Siena, Italy},
  Author =	 {Christoph Benzm{\"u}ller and Manfred Kerber},
  Booktitle =	 {Proceedings of the IJCAR 2001 Workshop: Future
                  Directions in Automated Reasoning},
  Pages =	 {13-24},
  Title =	 {A Lost Proof},
  Note =	 {Url (preprint):
                  \url{http://christoph-benzmueller.de/papers/W13.pdf}},
  Year =	 2001,
}
Powered by bibtexbrowser