Article contents
Finite injury and Σ1-induction
Published online by Cambridge University Press: 12 March 2014
Abstract
Working in the language of first-order arithmetic we consider models of the base theory P−. Suppose M is a model of P− and let M satisfy induction for Σ1-formulas. First it is shown that the Friedberg-Muchnik finite injury argument can be performed inside M, and then, using a blocking method for the requirements, we prove that the Sacks splitting construction can be done in M. So, the “amount” of induction needed to perform the known finite injury priority arguments is Σ1-induction.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1989
References
REFERENCES
[1]Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Sciences of the United States of America, vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[2]Kirby, L. A. S., Initial segments of models of arithmetic, Ph.D. thesis, University of Manchester, Manchester, 1977.Google Scholar
[3]Kreisel, G., Some reasons for generalizing recursion theory, Logic Colloquium '69 (Gandy, R. O. and Yates, C. E., editors), North-Holland, Amsterdam, 1971, pp. 139–198.CrossRefGoogle Scholar
[4]Muchnik, A. A., On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR, vol. 108 (1956), pp. 194–197. (Russian)Google Scholar
[5]Paris, J. B. and Kirby, L. A. S., Σ n-collection schemas in arithmetic, Logic Colloquium '77, North-Holland, Amsterdam, 1978, pp. 199–209.CrossRefGoogle Scholar
[6]Post, E. L., Recursively enumerable sets of integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 285–316.CrossRefGoogle Scholar
[7]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[8]Sacks, G. E., On degrees less than 0′, Annals of Mathematics, ser. 2, vol. 77 (1963), pp. 211–231.CrossRefGoogle Scholar
[9]Sacks, G. E. and Simpson, S. G., The α-finite injury method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343–368.CrossRefGoogle Scholar
[10]Shore, R. A., Splitting an α-recursively enumerable set, Transactions of the American Mathematical Society, vol. 204 (1975), pp. 65–78.Google Scholar
[11]Simpson, S. G., private correspondence, 05 24, 1984. (Contained the proof of Theorem 3.2 and a discussion of the program.)Google Scholar
- 24
- Cited by