Three universal representations of recursively enumerable sets

Journal of Symbolic Logic 43 (2):335-351 (1978)
  Copy   BIBTEX

Abstract

In his celebrated paper of 1931 [7], Kurt Gödel proved the existence of sentences undecidable in the axiomatized theory of numbers. Gödel's proof is constructive and such a sentence may actually be written out. Of course, if we follow Gödel's original procedure the formula will be of enormous length.Forty-five years have passed since the appearance of Gödel's pioneering work. During this time enormous progress has been made in mathematical logic and recursive function theory. Many different mathematical problems have been proved recursively unsolvable. Theoretically each such result is capable of producing an explicit undecidable number theoretic predicate. We have only to carry out a suitable arithmetization. Until recently, however, techniques were not available for carrying out these arithmetizations with sufficient efficiency.In this article we construct an explicit undecidable arithmetical formula,F(x, n), in prenex normal form. The formula is explicit in the sense that it is written out in its entirety with no abbreviations. The formula is undecidable in the recursive sense that there exists no algorithm to decide, for given values ofn, whether or notF(n, n)is true or false. MoreoverF(n, n)is undecidable in the formal (axiomatic) sense of Gödel [7]. Given any of the usual axiomatic theories to which Gödel's Incompleteness Theorem applies, there exists a value ofnsuch thatF(n, n)is unprovable and irrefutable. Thus Gödel's Incompleteness Theorem can be “focused” into the formulaF(n, n). Thus some substitution instance ofF(n, n)is undecidable in Peano arithmetic, ZF set theory, etc.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,795

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
51 (#432,153)

6 months
15 (#215,221)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Scope of Gödel’s First Incompleteness Theorem.Bernd Buldt - 2014 - Logica Universalis 8 (3-4):499-552.

Add more citations

References found in this work

No references found.

Add more references