Auto formalisation of Gödel’s Second Incompleteness Theorem in Binary Recursive Arithmetic

Thierry Coquand · 2026

Read Auto formalisation of Gödel’s Second Incompleteness Theorem in Binary Recursive Arithmetic by Thierry Coquand (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01898.txt.

Introduction

Coquand reports an auto-formalization of Gödel's second incompleteness theorem. The proof is built in Agda for Basic Recursive Arithmetic. The outline follows Guard's 1963 lecture notes. The full development runs near 50,000 lines of code. It contains no postulates at all.

All Agda code was produced through talks with Claude. The author wrote no Agda code by hand. An early attempt based on Rose's paper failed. A false lemma led that attempt astray. It proved a claim that merely resembled Gödel's theorem. The flaw was a weak spec of the provability predicate. The case study shows strengths and limits of current models. Careful specification emerges as the key lesson.

Catalog record

CREATORThierry Coquand
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01898

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Auto formalisation of Gödel’s Second Incompleteness Theorem in Binary Recursive Arithmetic 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, 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 paper of Rose failed because of a wrong Lemma; the resulting formal development produced by Claude established a statement superficially resembling Gödel’s theorem but mathematically unrelated to it. 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 specification of substitution. 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 Basic Recursive Arithmetic. Introduction We report an experiment in autoformalisation in Agda [ 14 ] , using Claude, of Gödel’s second incompleteness theorem 1 1 1 From now on, we may write Gödel I for the first incompleteness theorem and Gödel II for the second incompleteness theorem for Church’s basic recursive arithmetic (BRA), following the proof outline given by R. Guard in his 1963 lecture notes [ 5 ] . This motivation comes from the work of J. Urban [ 12 ] . The goal was to see what happens on a text which, while being precise, has several typos and gaps, and required substantial reconstruction during formalisation. Another contribution of this work is to document several mathematical details that had to be reconstructed during the formalisation. To formalise Gödel’s second incompleteness theorem is a non-trivial formalisation project. To our knowledge, Paulson’s Isabelle formalisation [ 7 ] is the only published machine-checked proof of Gödel’s second incompleteness theorem that we were able to locate. This represents a version of this theorem not for arithmetic but for hereditary finite sets, and using a nominal definitional extension of HOL. Gödel himself never published Part II, announced at the end of his 1931 paper [ 6 ] , where he was supposed to give a detailed proof of the second incompleteness theorem. See J. von Plato’s book [ 13 ] for further historical analysis. The entire Agda development was produced through interaction with Claude; I did not write any Agda code myself. The development can be found at https://github.com/coquand/agda-godel-tree . The development is done from scratch (no library), without any tactics. Once this is done, we have enough infrastructure to encode other proofs of Gödel incompleteness, such as Chaitin’s proof with Kolmogorov’s complexity [ 2 ] , which can be found on github at the same address and will be documented in a following paper. 1 The original attempt We started as a purely autonomous attempt using the paper of Rose [ 8 ] . We were not aware that Theorem 15 in this paper is wrong (see for instance [ 4 ] ; this was correct later [ 9 ] ). After several days of autonomous coding, Claude was not able to prove Theorem 15, but stated that it could find an alternative path to the Gödel II. We were quite impressed, until we realized that the statement claimed by Claude had very little to do with Gödel’s result. So it is difficult to trust the system when it is claiming to have proved a statement. It is important that one can check independently the claimed statement. 2 The statement After this attempt, we decided to follow Guard’s lecture notes [ 5 ] . The formal system follows Skolem’s formulation of primitive recursive arithmetic [ 11 ] , but with only unary and binary function symbols. (The system is presented in details below.) While it is a nice system for Gödel’s theorem, it would be difficult/challenging to do the formalisation (in any proof assistant) “by hand”. We write Deriv(A) if we can derive A from these axioms and inference rules. Following Church, we first code pairing and projection. We can then code course-of-value recursion. While this is standard, it was non trivial for Claude, and suggestions from ChatGPT were useful. We code directly list using pairing and never use prime decomposition like Gödel. We write then code for axioms and inference rules, and a function thmT that enumerates the code of derived formulae of T , so thmT(O),~thmT(s(O)),\dots are exactly the code of derived formulae. 3 Proof of first incompleteness Theorem As usual, we build by diagonalisation a formula G such that G is equivalent to thmT(x)\neq code(G) Intuitively, G is equivalent to the fact that G is not provable It is then direct to show that Deriv(G) implies Deriv(O=s(O)) . This is a consistency free statement of Gödel I. 4 Comments At this point, the only thing we have used of enumeration of the thmT function is that it is complete : from any proof of Deriv(A) we can build p such that thmT(p)=code(A) . We never used that this enumeration is sound . Indeed, with the specifications written by Guard, we cannot derive soundness. Having an unsound version of thmT there is a trivial proof of Gödel II stated as Deriv(thmT(x_{0})\neq code(0=1))\rightarrow Deriv(0=1) This is the correct statement since the variable x_{0} is implicitly universally quantified, and so the premisse states that there is no internal proof of 0=1 . (Note that this is a meta-theoretic implication between derivability judgments, not a theorem of BRA.) In the first version, thmT was not supposed to be sound (since it was not stated formally in Guard’s paper) and Claude could happily use this to claim a very simple (but trivial) proof of second incompleteness! This shows that it can (surprisingly since it can be very clever otherwise) lack a global picture of what is going on. The failure was not due to a missing lemma. Claude accepted a specification of the verifier that was too weak to characterize the intended notion of provability. It consequently produced a proof of a statement formally resembling Gödel’s second theorem but mathematically unrelated to it. This illustrates that current LLMs can reason correctly from incorrect specifications and may fail to detect that a formalisation no longer captures the intended mathematical notion. 4.1 Internal Reasoning and Surprising insights The proof of Gödel II consists in internalizing this: we build a function g such that Deriv(thmT(x)=code(G)\rightarrow thmT(g(x))=code(O=s(O))) It then follows from this that Deriv(thmT(x)\neq code(0=s(0))) , which expressed that the theory proves its own consistency, implies Deriv(thmT(x)\neq code(G)) , which is equivalent to Deriv(G) by definition of G . Since by Gödel I, we have Deriv(G) implies Deriv(0=1) , we get that Deriv(thmT(x)\neq code(0=s(0))) implies Deriv(0=1) . This means that if the theory proves its own consistency, it proves 0=1 (and so is inconsistent). For this we need to reason inside a Hilbert style system. I always thought to use a logical system based on natural deduction was better than working with a Hilbert-style

Read the complete text