Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-19T06:42:22.254Z Has data issue: false hasContentIssue false
  • English
  • Français

The next admissible set1

Published online by Cambridge University Press:  12 March 2014

K. J. Barwise ,
R. O. Gandy  and
Y. N. Moschovakis
K. J. Barwise
Affiliation:
University of Wisconsin, Madison
R. O. Gandy
Affiliation:
Oxford University
Y. N. Moschovakis
Affiliation:
University of California, Los Angeles
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper we describe generalizations of several approaches to the hyperarithmetic hierarchy, show how they are related to the Kripke-Platek theory of admissible ordinals and sets, and study conditions under which the various approaches remain equivalent.

To put matters in some perspective, let us first review various approaches to the theory of hyperarithmetic sets. For most purposes, it is convenient to first define the semi-hyperarithmetic (semi-HA) subsets of N. A set is then said to be hyperarithmetic (HA) if both it and its complement are semi-HA. A total number-theoretic function is HA if its graph is HA.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 36 , Issue 1 , March 1971 , pp. 108 - 120
Copyright
Copyright © Association for Symbolic Logic 1971

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

Most of the results of this paper were obtained during the spring of 1968 while Barwise and Gandy were attending the UCLA Logic Year, the first as an NSF Postdoctoral Fellow, the second as Visiting Associate Professor. They record here their gratitude to the Mathematics Department of UCLA for its gracious hospitality. The research of Barwise and Moschovakis was also supported in part by NSF Grants.

References

[1]Barwise, J., Infinitary logic and admissible sets, this Journal, vol. 34 (1969), pp. 226–252 (referred to as ILAS).Google Scholar
[2]Barwise, J., Applications of strict-Π11 predicates to infinitary logic, this Journal, vol. 34 (1969), pp. 409–423.Google Scholar
[3]Barwise, J., The Gandy-Kreisel-Tait theorem for countable sets, (in preparation).Google Scholar
[4]Gandy, R. O., Computable functionals of finite type, Sets, Models and Recursion Theory, North Holland, 1967, pp. 202–242.CrossRefGoogle Scholar
[5]Gandy, R. O., Kreisel, G. and Tait, W. W., Set existence, Bulletin de l'Académie Polonaise des Sciences, vol. 8 (1960), pp. 577–583.Google Scholar
[6]Grzegorczyk, A., Mostowski, A. and Ryll-Nardzewski, C., The classical and the ω-complete arithmetic, this Journal, vol. 23 (1958), pp. 188–206.Google Scholar
[7]Jensen, R. and Karp, C., Primitive recursive set functions, Proceedings of the Summer Institute on Axiomatic Set Theory, UCLA 1967, (to appear).Google Scholar
[8]Kleene, S. C., Hierarchies of number-theoretic predicates, Bulletin of the American Mathematical Society, vol. 61 (1955), pp. 193–213.CrossRefGoogle Scholar
[9]Kleene, S. C., Quantification of number theoretic functions, Compositio Mathematica, vol. 14 (1959), pp. 23–41.Google Scholar
[10]Kleene, S. C., Recursive functionals and quantifiers of finite types, I, Transactions of the American Mathematical Society, vol. 91 (1959), pp. 1–52.Google Scholar
[11]Kreisel, G., Set theoretic problems suggested by the notion of potential totality, Infinitistic Methods, Warsaw (1961), pp. 103–140.Google Scholar
[12]Kreisel, G., Model theoretic invariants, The Theory of Models, North Holland Publishing Co. (1965), pp. 190–205.Google Scholar
[13]Kreisel, G., A survey of proof theory, this Journal, vol. 33 (1968), pp. 321–338.Google Scholar
[14]Kreisel, G. and Sacks, G., Metarecursive sets, this Journal, vol. 30 (1965), pp. 318–338.Google Scholar
[15]Kripke, S., Transfinite recursion on admissible ordinals, I, II (abstract), this Journal, vol. 29 (1964), p. 162.Google Scholar
[16]Kunen, K., Implicit definability and infinitary languages, this Journal, vol. 33 (1968), pp. 446–451.Google Scholar
[17]Lorenzen, P. and Myhill, J., Constructive definitions of certain analytic sets of numbers, this Journal, vol. 24 (1959), pp. 37–49.Google Scholar
[18]Moschovakis, Y. N., Abstract first order computability, I, II, Transactions of the American Mathematical Society, vol. 138 (1969), pp. 427–464, 465–504 (referred to as AFOQ.Google Scholar
[19]Moschovakis, Y. N., Abstract computability and invariant definability, this Journal (to appear) (referred to as ACID).Google Scholar
[20]Moschovakis, Y. N., The Suslin–Kleene theorem for countable structures, Duke Journal of Mathematics, vol. 37 (1970), pp. 344–352.CrossRefGoogle Scholar
[21]Platek, R., Foundations of recursion theory, Ph.D. Thesis and supplement, Stanford Univ. 1966.Google Scholar
[22]Spector, C., Inductively defined sets of natural numbers, Infinitistic Methods, Warsaw, 1961, pp. 97–102.Google Scholar