| Title:
|
Arithmetical classification of the set of all provably recursive functions (English) |
| Author:
|
Švejdar, Vítězslav |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
40 |
| Issue:
|
4 |
| Year:
|
1999 |
| Pages:
|
631-634 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
provable |
| Keyword:
|
recursive |
| Keyword:
|
complete |
| MSC:
|
03D20 |
| MSC:
|
03D55 |
| MSC:
|
03F30 |
| idZBL:
|
Zbl 1010.03049 |
| idMR:
|
MR1756541 |
| . |
| Date available:
|
2009-01-08T18:56:05Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119119 |
| . |
| Reference:
|
[1] Buss S.R.: Bounded Arithmetic.Bibliopolis, Napoli, 1986. Zbl 1148.03038, MR 0880863 |
| Reference:
|
[2] Hájek P., Pudlák P.: Metamathematics of First Order Arithmetic.Springer, 1993. MR 1219738 |
| Reference:
|
[3] Hay L.: Index sets universal for differences of arithmetic sets.Zeitschr. f. math. Logik und Grundlagen d. Math. 20 (1974), 239-254. Zbl 0311.02052, MR 0429518 |
| Reference:
|
[4] Kaye R.: Models of Peano Arithmetic.Oxford University Press, 1991. Zbl 1020.03065, MR 1098499 |
| Reference:
|
[5] Kirby L.A.S., Paris J.B.: Accessible independence results for Peano arithmetic.Bull. London Math. Soc. 14 285-293 (1982). Zbl 0501.03017, MR 0663480 |
| Reference:
|
[6] Lewis F.D.: Classes of recursive functions and their index sets.Zeitschr. f. math. Logik und Grundlagen d. Math. 17 291-294 (1971). Zbl 0229.02035, MR 0294130 |
| Reference:
|
[7] Odifreddi P.: Classical Recursion Theory.North-Holland, Amsterdam, 1989. Zbl 0931.03057, MR 0982269 |
| Reference:
|
[8] 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 |
| Reference:
|
[9] Rogers H., Jr.: Theory of Recursive Functions and Effective Computability.McGraw-Hill, New York, 1967. Zbl 0256.02015, MR 0224462 |
| . |
