Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T12:24:26.593Z Has data issue: false hasContentIssue false

Three universal representations of recursively enumerable sets

Published online by Cambridge University Press:  12 March 2014

James P. Jones*
Affiliation:
Department of Mathematics and Statistics, University of Calgary, Calgary T2N 1N4, Canada

Extract

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 of n, whether or not F(n, n) is true or false. Moreover F(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 of n such that F(n, n) is unprovable and irrefutable. Thus Gödel's Incompleteness Theorem can be “focused” into the formula F(n, n). Thus some substitution instance of F(n, n) is undecidable in Peano arithmetic, ZF set theory, etc.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1978

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable