Distilling the Requirements of Gödel's Incompleteness Theorems with a Proof Assistant

Andrei Popescu, Dmitriy Traytel


We present an abstract development of Gödel's incompleteness theorems, performed with the help of the Isabelle/HOL proof assistant. We analyze sufficient conditions for the theorems' applicability to a partially specified logic. In addition to the usual benefits of generality, our abstract perspective enables a comparison between alternative approaches from the literature. These include Rosser's variation of the first theorem, Jeroslow's variation of the second theorem, and the Świerczkowski–Paulson semantics-based approach. As part of our framework's validation, we upgrade Paulson's Isabelle proof to produce a mechanization of the second theorem that does not assume soundness in the standard model, and in fact does not rely on any notion of model or semantic interpretation.

The final publication is available at link.springer.com.

Article draft