Inductive definitions and computability

Grilliot, Thomas J.

doi:10.1090/S0002-9947-1971-0304141-5

Inductive definitions and computability
HTML articles powered by AMS MathViewer

by Thomas J. Grilliot PDF

Trans. Amer. Math. Soc. 158 (1971), 309-317 Request permission

Abstract:

Sets inductively defined with respect to ${\prod _0},{\Sigma _1}$, (nonmonotonic) ${\prod _1}$ and ${\Sigma _2}$ predicates are characterized in terms of the four chief notions of abstract recursion.

References

K. J. Barwise, R. O. Gandy, and Y. N. Moschovakis, The next admissible set, J. Symbolic Logic 36 (1971), 108–120. MR 300876, DOI 10.2307/2271519

Une notion de récursivité relative

32

A comparison of abstract computability theories

34

Thomas J. Grilliot, Selection functions for recursive functionals, Notre Dame J. Formal Logic 10 (1969), 225–234. MR 265152
Daniel Lacombe, Deux généralisations de la notion de récursivité relative, C. R. Acad. Sci. Paris 258 (1964), 3410–3413 (French). MR 160719
R. Montague, Recursion theory as a branch of model theory, Logic, Methodology and Philos. Sci. III (Proc. Third Internat. Congr., Amsterdam, 1967) North-Holland, Amsterdam, 1968, pp. 63–86. MR 0272624
Yiannis N. Moschovakis, Abstract first order computability. I, II, Trans. Amer. Math. Soc. 138 (1969), 427–464. MR 244045, DOI 10.1090/S0002-9947-1969-0244045-0
Yiannis N. Moschovakis, Abstract computability and invariant definability, J. Symbolic Logic 34 (1969), 605–633. MR 270908, DOI 10.2307/2270854
Yiannis N. Moschovakis, The Suslin-Kleene theorem for countable structures, Duke Math. J. 37 (1970), 341–352. MR 272628
Wayne Richter, Recursively Mahlo ordinals and inductive definitions, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 273–288. MR 0281616
C. Spector, Inductively defined sets of natural numbers, Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959), Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw, 1961, pp. 97–102. MR 0141593