Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2025-01-03T17:15:36.572Z Has data issue: false hasContentIssue false
  • English
  • Français

Degrees of unsolvability of constructible sets of integers

Published online by Cambridge University Press:  12 March 2014

George Boolos  and
Hilary Putnam
George Boolos
Affiliation:
Columbia University Harvard University
Hilary Putnam
Affiliation:
Harvard University
Get access Rights & Permissions [Opens in a new window]

Extract

Why the Post-Kleene arithmetical hierarchy of degrees of (recursive) unsolvability was extended into the transfinite is not clear. Perhaps it was thought that if a hierarchy of sufficiently fine structure could be described that would include all sets of integers, some light might be thrown on the Continuum Hypothesis, and its truth or falsity possibly even ascertained. There is also some evidence in the 1955 papers of Kleene (cf. Kleene [2], [3], [4]) that it was once hoped that a theorem for the analytical hierarchy analogous to the result of Post and Kleene

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 33 , Issue 4 , January 1969 , pp. 497 - 513
Copyright
Copyright © Association for Symbolic Logic 1969

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.)

References

Addison, J. W. and Kleene, S. C., [1] A note on function quantification, Proceedings of the American Mathematical Society, vol. 8 (1957), pp. 1002–1006.CrossRefGoogle Scholar
Boolos, G. S., [1] The hierarchy of constructible sets of integers, Ph.D. thesis, M.I.T. Humanities Department, Cambridge, Mass., 1966.Google Scholar
Boyd, R., Hensel, G., and Putnam, H., [1] On an intrinsic characterization of the ramified analytic hierarchy (to appear).Google Scholar
Cohen, P. J., [1] A minimal model for set theory, Bulletin of the American Mathematical Society, vol. 69 (1963), pp. 537–540.CrossRefGoogle Scholar
Davis, M., [1] Computability and unsolvability, McGraw-Hill, New York, 1958.Google Scholar
Gandy, R. O., [1] Proof of Mostowski's conjecture, Bulletin de l' Académie Polonaise des Sciences, Série des Sciences, Mathematiques, Astronomiques, vol. 8 (1960), pp. 571–575.Google Scholar
Gödel, K., [1] Consistency-proof for the generalized continuum hypothesis, Proceedings of the National Academy of Sciences of the United States of America, vol. 25 (1939), pp. 220–224.CrossRefGoogle ScholarPubMed
Kleene, S. C., [1] Introduction to metamathematics, Van Nostrana, Princeton, N.J., 1952.Google Scholar
Kleene, S. C., [2] Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.CrossRefGoogle Scholar
Kleene, S. C., [3] On the forms of predicates in the theory of constructive ordinals. II, American journal of mathematics, vol. 77 (1955), pp. 405–428.CrossRefGoogle Scholar
Kleene, S. C., [4] Hierarchies of number-theoretic predicates, Bulletin of the American Mathematical Society, vol. 61 (1955), pp. 193–213.CrossRefGoogle Scholar
Kleene, S. C., [5] Quantification of number-theoretic predicates, Compositio mathematica, vol. 14 (1959), pp. 23–40.Google Scholar
Putnam, H., [1] A note on constructible sets of Integers, Notre Dame journal of formal logic, vol. 4 (1963), pp. 270–273.CrossRefGoogle Scholar
Spector, C., [1] Recursive well-orderlngs, this Journal, vol. 20 (1955), pp. 151–163.Google Scholar
Spector, C., [2] Hyperarithmetical quantifiers, Fundamenta mathematicae, vol. 48 (1960), pp. 313–319.CrossRefGoogle Scholar
Tarski, A. and Vaught, R. L., [1] Arithmetical extensions of relational systems, Compositio mathematica, vol. 18 (1959), pp. 81–102.Google Scholar
Tharp, L., [1] Constructibility in impredicative set theory, Ph.D. Thesis, M.I.T. Mathematics Department, Cambridge, Mass., 1965.Google Scholar
Wang, H., [1] A survey of mathematical logic, North Holland, Amsterdam, 1963.Google Scholar