A Simple Character String Proof of the "True but Unprovable" Version of Gödel's First Incompleteness Theorem

Antti Valmari
(Tampere University of Technology)

A rather easy yet rigorous proof of a version of Gödel's first incompleteness theorem is presented. The version is ``each recursively enumerable theory of natural numbers with 0, 1, +, *, =, logical and, logical not, and the universal quantifier either proves a false sentence or fails to prove a true sentence''. The proof proceeds by first showing a similar result on theories of finite character strings, and then transporting it to natural numbers, by using them to model strings and their concatenation. Proof systems are expressed via Turing machines that halt if and only if their input string is a theorem. This approach makes it possible to present all but one parts of the proof rather briefly with simple and straightforward constructions. The details require some care, but do not require significant background knowledge. The missing part is the widely known fact that Turing machines can perform complicated computational tasks.

In Zoltán Ésik and Zoltán Fülöp: Proceedings 14th International Conference on Automata and Formal Languages (AFL 2014), Szeged, Hungary, May 27-29, 2014, Electronic Proceedings in Theoretical Computer Science 151, pp. 355–369.
Published: 21st May 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.151.25 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org