Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Inductive definitions and computability


Author: Thomas J. Grilliot
Journal: Trans. Amer. Math. Soc. 158 (1971), 309-317
MSC: Primary 02E15
DOI: https://doi.org/10.1090/S0002-9947-1971-0304141-5
MathSciNet review: 0304141
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] K. J. Barwise, R. O. Gandy and Y. N. Moschovakis, The next admissible set, J. Symbolic Logic (to appear). MR 0300876 (46:36)
  • [2] R. Fraïssé, Une notion de récursivité relative, Proc. Sympos. Infinitistic Methods, Foundations of Math. (Warsaw, 1959), Pergamon Press, Oxford; PWN, Warsaw, 1961, pp. 323-328. MR 32 #3999.
  • [3] C. E. Gordon, A comparison of abstract computability theories, J. Symbolic Logic 34 (1969), 156.
  • [4] T. J. Grilliot, Selection functions for recursive functionals, Notre Dame J. Formal Logic 10 (1969), 225-234. MR 0265152 (42:65)
  • [5] D. Lacombe, Deux généralisations de la notion de récursivité relative, C. R. Acad. Sci. Paris 258 (1964), 3410-3413. MR 28 #3930. MR 0160719 (28:3930)
  • [6] R. Montague, Recursion theory as a branch of model theory, Logic, Methodology and Philosophy of Science III, North-Holland, Amsterdam, 1968, pp. 63-86. MR 0272624 (42:7505)
  • [7] Y. N. Moschovakis, Abstract first order computability. I, II, Trans. Amer. Math. Soc. 138 (1969), 427-504. MR 39 #5362. MR 0244045 (39:5362)
  • [8] -, Abstract computability and invariant definability, J. Symbolic Logic 34 (1969), 605-633. MR 0270908 (42:5791)
  • [9] -, The Suslin-Kleene theorem for countable structures, Duke Math. J. 37 (1970), 341-352. MR 0272628 (42:7509)
  • [10] Wayne Richter, Recursively Mahlo ordinals and inductive definitions (to appear). MR 0281616 (43:7331)
  • [11] C. Spector, Inductively defined sets of natural numbers, Proc. Sympos. Infinitistic Methods, Foundations of Math. (Warsaw, 1959), Pergamon Press, Oxford; PWN, Warsaw, 1961, pp. 97-102. MR 25 #4991. MR 0141593 (25:4991)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02E15

Retrieve articles in all journals with MSC: 02E15


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1971-0304141-5
Keywords: Inductively defined sets, abstract computability, hyperprojective hierarchy
Article copyright: © Copyright 1971 American Mathematical Society

American Mathematical Society