Kleene's amazing second recursion theorem

Bulletin of Symbolic Logic 16 (2):189 - 239 (2010)
  Copy   BIBTEX

Abstract

This little gem is stated unbilled and proved in the last two lines of §2 of the short note Kleene [1938]. In modern notation, with all the hypotheses stated explicitly and in a strong form, it reads as follows:Second Recursion Theorem. Fix a set V ⊆ ℕ, and suppose that for each natural number n ϵ ℕ = {0, 1, 2, …}, φn: ℕ1+n ⇀ V is a recursive partial function of arguments with values in V so that the standard assumptions and hold with. Every n-ary recursive partial function with values in V is for some e. For all m, n, there is a recursive function : Nm+1 → ℕ such that.Then, for every recursive, partial function f of arguments with values in V, there is a total recursive function of m arguments such thatProof. Fix e ϵ ℕ such that and let.We will abuse notation and write ž; rather than ž() when m = 0, so that takes the simpler formin this case ).

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On the recursion theorem in iterative operative spaces.J. Zashev - 2001 - Journal of Symbolic Logic 66 (4):1727-1748.
Recursion theory for metamathematics.Raymond Merrill Smullyan - 1993 - New York: Oxford University Press.
The formal language of recursion.Yiannis N. Moschovakis - 1989 - Journal of Symbolic Logic 54 (4):1216-1252.
Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
Naming and Diagonalization, from Cantor to Gödel to Kleene.Haim Gaifman - 2006 - Logic Journal of the IGPL 14 (5):709-728.
Alternative proof of a theorem of Kleene.Hao Wang - 1958 - Journal of Symbolic Logic 23 (3):250.
From semirings to residuated Kleene lattices.Peter Jipsen - 2004 - Studia Logica 76 (2):291 - 303.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.

Analytics

Added to PP
2011-05-29

Downloads
31 (#443,123)

6 months
4 (#315,466)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Naïve Truth and the Evidential Conditional.Iacona Andrea & Lorenzo Rossi - 2024 - Journal of Philosophical Logic 1:1-26.
Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.
Generalizations of the recursion theorem.Sebastiaan A. Terwijn - 2018 - Journal of Symbolic Logic 83 (4):1683-1690.
On the diagonal lemma of Gödel and Carnap.Saeed Salehi - 2020 - Bulletin of Symbolic Logic 26 (1):80-88.
A Computational Learning Semantics for Inductive Empirical Knowledge.Kevin T. Kelly - 2014 - In Alexandru Baltag & Sonja Smets (eds.), Johan van Benthem on Logic and Information Dynamics. Springer International Publishing. pp. 289-337.

View all 10 citations / Add more citations

References found in this work

Introduction to Metamathematics.H. Rasiowa - 1954 - Journal of Symbolic Logic 19 (3):215-216.
Computability and Logic.George S. Boolos, John P. Burgess & Richard C. Jeffrey - 2003 - Bulletin of Symbolic Logic 9 (4):520-521.
On notation for ordinal numbers.S. C. Kleene - 1938 - Journal of Symbolic Logic 3 (4):150-155.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
On the interpretation of intuitionistic number theory.S. C. Kleene - 1945 - Journal of Symbolic Logic 10 (4):109-124.

View all 13 references / Add more references