Arithmetical classification of the set of all provably recursive functions
Švejdar, Vítězslav
Commentationes Mathematicae Universitatis Carolinae, Tome 40 (1999), p. 631-634 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

The set of all indices of all functions provably recursive in any reasonable theory $T$ is shown to be recursively isomorphic to $U\times\overline{U}$, where $U$ is $\Pi_2$-complete set.

Publié le : 1999-01-01
Classification:  03D20,  03D55,  03F30 
@article{119119,
     author = {V\'\i t\v ezslav \v Svejdar},
     title = {Arithmetical classification of the set of all provably recursive functions},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {40},
     year = {1999},
     pages = {631-634},
     zbl = {1010.03049},
     mrnumber = {1756541},
     language = {en},
     url = {http://dml.mathdoc.fr/item/119119}
}

Švejdar, Vítězslav. Arithmetical classification of the set of all provably recursive functions. Commentationes Mathematicae Universitatis Carolinae, Tome 40 (1999) pp. 631-634. http://gdmltest.u-ga.fr/item/119119/

Buss S.R. Bounded Arithmetic, Bibliopolis, Napoli, 1986. | MR 0880863 | Zbl 1148.03038

Hájek P.; Pudlák P. Metamathematics of First Order Arithmetic, Springer, 1993. | MR 1219738

Hay L. Index sets universal for differences of arithmetic sets, Zeitschr. f. math. Logik und Grundlagen d. Math. 20 (1974), 239-254. (1974) | MR 0429518 | Zbl 0311.02052

Kaye R. Models of Peano Arithmetic, Oxford University Press, 1991. | MR 1098499 | Zbl 1020.03065

Kirby L.A.S.; Paris J.B. Accessible independence results for Peano arithmetic, Bull. London Math. Soc. 14 285-293 (1982). (1982) | MR 0663480 | Zbl 0501.03017

Lewis F.D. Classes of recursive functions and their index sets, Zeitschr. f. math. Logik und Grundlagen d. Math. 17 291-294 (1971). (1971) | MR 0294130 | Zbl 0229.02035

Odifreddi P. Classical Recursion Theory, North-Holland, Amsterdam, 1989. | MR 0982269 | Zbl 0931.03057

Paris J.B.; Harrington L. A mathematical incompleteness in Peano arithmetic, in J. Barwise, editor, Handbook of Mathematical Logic, Chapter D8., North-Holland, 1977. | MR 0457132

Rogers H., Jr. Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967. | MR 0224462 | Zbl 0256.02015