Essential Incompleteness of Arithmetic Verified by Coq
Russell O'Connor
Abstract
A constructive proof of the Goedel-Rosser incompleteness theorem has been completed using the Coq proof assistant. Some theory of classical first-order logic over an arbitrary language is formalized. A development of primitive recursive functions is given, and all primitive recursive functions are proved to be representable in a weak axiom system. Formulas and proofs are encoded as natural numbers, and functions operating on these codes are proved to be primitive recursive. The weak axiom system is proved to be essentially incomplete. In particular, Peano arithmetic is proved to be consistent in Coq's type theory and therefore is incomplete.
arXiv comments
This paper is part of the proceedings of the 18th International Conference on Theorem Proving in Higher Order Logics (TPHOLs 2005). For the associated Coq source files see the TeX sources, or see <http://r6.ca/Goedel20050512.tar.gz>
Journal reference
Russell O'Connor, Essential Incompleteness of Arithmetic Verified by Coq, Lecture Notes in Computer Science, Volume 3603, Aug 2005, Pages 245 - 260
I don't think working with Coq has ever or will ever be particularly pleasant :-) O'Connor gave a nice talk at TPHol's which I attended: https://arxiv.org/abs/cs/0505034 Keeping up with Coq shouldn't have been too difficult for him.
I find this argument to be an unsatisfactory against "algorithmic consciousness". There have been automated proofs of Godel's theorem for a long while [0]. I don't mean this to be evidence on the contrary, but Penrose seems to ignore the fact that a computer can realize multiple…
I don't think working with Coq has ever or will ever be particularly pleasant :-) O'Connor gave a nice talk at TPHol's which I attended: https://arxiv.org/abs/cs/0505034 Keeping up with Coq shouldn't have been too difficult for him.
auggieroseView on HNParent context