Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
provable; recursive; complete
provable; recursive; complete
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.
References:
[1] Buss S.R.: Bounded Arithmetic. Bibliopolis, Napoli, 1986. MR 0880863 | Zbl 1148.03038
[2] Hájek P., Pudlák P.: Metamathematics of First Order Arithmetic. Springer, 1993. MR 1219738
[3] Hay L.: Index sets universal for differences of arithmetic sets. Zeitschr. f. math. Logik und Grundlagen d. Math. 20 (1974), 239-254. MR 0429518 | Zbl 0311.02052
[4] Kaye R.: Models of Peano Arithmetic. Oxford University Press, 1991. MR 1098499 | Zbl 1020.03065
[5] Kirby L.A.S., Paris J.B.: Accessible independence results for Peano arithmetic. Bull. London Math. Soc. 14 285-293 (1982). MR 0663480 | Zbl 0501.03017
[6] Lewis F.D.: Classes of recursive functions and their index sets. Zeitschr. f. math. Logik und Grundlagen d. Math. 17 291-294 (1971). MR 0294130 | Zbl 0229.02035
[7] Odifreddi P.: Classical Recursion Theory. North-Holland, Amsterdam, 1989. MR 0982269 | Zbl 0931.03057
[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
[9] Rogers H., Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967. MR 0224462 | Zbl 0256.02015
Search
Partner of
