Auto formalisation of Goedel's Second Incompleteness Theorem in Binary Recursive Arithmetic
2026-06-01 • Logic in Computer Science
Logic in Computer Science
AI summaryⓘ
The authors used an AI called Claude to fully write a detailed computer proof of Gödel's second incompleteness theorem for a simple arithmetic system, without writing any code themselves. They followed an old proof by Guard and had to clarify and fix some tricky parts that were not fully explained before. They also found that AI can make mistakes if given unclear instructions, shown when an initial attempt led to a wrong statement due to a bad definition. This project shows both how AI can help formalize complex math and the importance of precise specifications.
Gödel's second incompleteness theoremAgdaChurch's Basic Recursive Arithmeticautoformalisationlarge language modelsformal proofinternal provability predicatenumeral encodingsubstitutionmachine-checked proof
Authors
Thierry Coquand
Abstract
We report an experiment in autoformalisation of Gödel's second incompleteness theorem in Agda using Claude. The theorem is formalised for Church's Basic Recursive Arithmetic (BRA), following the proof outline given in Guard's 1963 lecture notes. The entire Agda development, comprising approximately 50,000 lines and containing no postulates, was produced through interaction with Claude; the author did not write any Agda code. Beyond the formalisation itself, the project provides a case study of the strengths and limitations of current large language models in mathematics. An initial autonomous attempt based on a theorem of Rose failed because the theorem is false; the resulting formal development produced by Claude established a statement superficially resembling Gödel's theorem but mathematically unrelated to it. This failure was traced to an insufficient specification of the internal provability predicate, illustrating how an LLM may reason correctly from an incorrect formal specification. The final development follows Guard's proof and required the reconstruction of several implicit mathematical arguments, including the role of the internal numeral-encoding operation and the interaction between substitution and numeral closure. The resulting formalisation clarifies a number of details left implicit in the original presentation and provides a fully machine-checked proof of Gödel's second incompleteness theorem for BRA.