The Program That Talks About Itself From PRA to ZFC to the Incompleteness Theorems

The Program That Talks About Itself: From PRA to ZFC to the Incompleteness Theorems
English | October 12, 2026 | ASIN: B0H2BRJ68J | 248 Pages | Epub | 1.02 MB
A quine is a program that prints its own source code. The trick that makes it work is the same one at the heart of Gödel's incompleteness theorems."There are mathematical truths that cannot be proved." "Mathematics cannot prove its own consistency." The incompleteness theorems are usually quoted in forms that drop the conditions that matter. This book skips the slogans and has you build the theorems yourself, with tools programmers use every day.What you will learnThe three layers of logic, theory (axioms), and metatheory, and why ZFC is a theory and not a logicWhy a language with only for loops (the primitive recursive functions), and PRA, the proof system built on it, are weak yet trustworthyHow formulas and proofs become integers (Gödel numbers), and how a proof checker can be written as a program that always haltsWhy Cantor's diagonal, the halting problem, and quines are one and the same techniqueHow the diagonal lemma, which matches a quine part for part, leads to the first and second incompleteness theoremsWhy "ZF cannot prove the axiom of choice" can only be proved with the condition "if ZF is consistent"A consistent theory that claims to be inconsistent, nonstandard natural numbers, and Gentzen's ε₀All the code in the book (Python and jаvascript, plus quines in Go and C in an appendix) has been run and its output checked. When the book states a theorem, it keeps hypotheses such as "if T is consistent."It is written for programmers without a background in mathematical logic who want to understand the incompleteness theorems precisely.