Hyperarithmetical Sets

Yiannis N. Moschovakis

Abstract The hyperarithmetical sets of natural numbers were introduced (independently) in the early 1950s by Martin Davis, Andrej Mostowski and Stephen Cole Kleene and their study is surely one of the most significant developments in the theory of computability: they have a rich and interesting structure and they have found applications to many areas of mathematics, including inductive definability, higher- type recursion, descriptive set theory and even classical analysis. This article surveys the development of the subject in its formative period from 1950 to 1960, starting with a discussion of its origins and with some brief pointers to later developments. There are few proofs, chosen partly because of the importance of the results but mostly because they illustrate simple, classical methods specific to this area which are not easy to find in the literature, especially in the treatment of uniformity; and these are given in the spirit (if not the letter) of the methods which were available at the time. This is an elementary, expository article and includes an Appendix which summarizes the few basic facts about computability theory that it assumes.

Keyword Hyperarithmetical sets

By the early 1940s, ten years after Godel’s monumental [11], the foundations of a mathematical theory of computability had been well established, primarily by the work of Alonzo Church, Alan Turing, Emil Post and Stephen Kleene. Most significant was the formulation of the Church-Turing Thesis, which identifies the intuitive notion of computable function (on the natural numbers) with the precisely defined concept of (general) recursive function; this was well understood and accepted (as a law in Emil Post’s view) by all the researchers in the area, even if not yet by all logicians.[1] The Church-Turing Thesis makes it possible to give rigorous proofs of (absolute) unsolvability of mathematical problems whose solution asks for an “algorithm” or a “decision procedure”. Several fundamental metamathematical relations had been 1cf. Moschovakis [32].

shown to be undecidable, chief among them the relation of first-order provability (Hilbert’s Entscheidungsproblem, Church [3] and Turing [53]). Moreover, a general theory of computability had also started to develop, especially with Kleene [13].

The most obvious next steps were to

• • look for unsolvability results in “ordinary mathematics”, and
• • study (in general) the unsolvable.

The first of these was (apparently) first emphasized by Post, who said in his Post [42] that “(Hilbert’s 10th Problem) begs for an unsolvability proof”. Post [43] and Markov [29] proved (independently) the unsolvability of the word problem for (finitely generated and presented) semigroups, the first substantial result of this type. Martin Davis’ work is an important part of this line of research which is covered extensively in other parts of this volume.

My topic is the theory of hyperarithmetical sets, one of the most significant developments to come out of the general theory of unsolvability in which Davis also played a very important role. I will give a survey of the development of the subject in its formative period from 1950 to 1960, starting with a discussion of its origins and with a couple of brief pointers to later developments at the end. There are few proofs, chosen partly because of the importance of the results but mostly because they illustrate simple, classical methods specific to this area which are not easy to find in the literature, especially in the treatment of uniformity; and I have tried to give these proofs in the spirit (if not the letter) of the methods which were available at the time—with just one, notable exception, cf. Remark 5.3.1.

The Appendix collects the few basic facts from recursion and set theory that we need and fixes notation. We refer to them by App 1, App 2, etc.

• [1] Y.N. Moschovakis (B) Department of Mathematics, University of California, Los Angeles, USAe-mail: This email address is being protected from spam bots, you need Javascript enabled to view it © Springer International Publishing Switzerland 2016 107 E.G. Omodeo and A. Policriti (eds.), Martin Davis on Computability, Computational Logic, and Mathematical Foundations, Outstanding Contributions to Logic 10, DOI 10.1007/978-3-319-41842-1_5