Article
Full entry |
PDF
(0.1 MB)
Feedback
Keywords:
limit lemma; fragments of arithmetic; collection scheme
limit lemma; fragments of arithmetic; collection scheme
Summary:
The recursion theoretic limit lemma, saying that each function with a $\varSigma_{n+2}$ graph is a limit of certain function with a $\varDelta_{n+1}$ graph, is provable in $\text{\rm B}\Sigma_{n+1}$.
References:
[1] Clote P.: Partition relations in arithmetic. in C.A. DiPrisco, Ed., {Methods in Mathematical Logic}, Lecture Notes in Mathematics 1130, Springer, 1985, pp.32-68. MR 0799036 | Zbl 0567.03029
[2] Hájek P., Kučera A.: On recursion theory in $I{\Sigma_1}$. J. Symbolic Logic 54 (1989), 576-589. MR 0997890
[3] Hájek P., Pudlák P.: Metamathematics of First Order Arithmetic. Springer, 1993. MR 1219738
[4] Kučera A.: An alternative, priority-free, solution to Post's problem. in J. Gruska, B. Rovan, and J. Wiedermann, Eds., {Mathematical Foundations of Computer Science 1986} (Bratislava, Czechoslovakia, August 25-29, 1986), Lecture Notes in Computer Science 233, Springer, 1986, pp.493-500. MR 0874627 | Zbl 0615.03033
[5] Rogers H., Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967. MR 0224462 | Zbl 0256.02015
Search
Partner of