Computable structures and the hyperarithmetical hierarchy (Q1572657)

This exceptionally well-organized book explores an important part of computable model theory. The basic structures of concern are countable models coded in such a way that the open diagram, or perhaps the diagram, exhibits some level of effectiveness; typically, the open diagram will be computable. One asks questions about effectivity related to the isomorphism type of the given structure, perhaps with some distinguished relation. For an illustrative example, a computable presentation of a linear ordering would be \(\mathbb{N}\), the natural numbers equipped with an ordering \(\preceq\) such that the relation \(x\preceq y\) is computable. The actual classical order type could be any countable ordering that happens to have a computable presentation. The types of questions examined in this book are based upon observations like the following. Take two computable presentations of the rationals, considered as a countable dense linear ordering without endpoints. Then, after Cantor, these two orderings are not just isomorphic, but computably isomorphic, in the sense that there is a computable isomorphism taking one to the other. Clearly this argument extends to demonstrate that if the two orderings have only a finite number of adjacencies, then they are computably isomorphic. On the other hand, it is easy to construct a copy of \(\omega\), the order type of the positive integers, where the relation ``\(x\) is adjacent to \(x\)'' is not computable. Hence, there are two computable copies of \(\omega\) which are not computably isomorphic. We call a structure computably categorical iff any two computable copies of the structure are computably isomorphic. Remmel and Goncharov independently showed that a computable linear ordering is computably categorical iff it has a finite number of adjacencies. On the other hand, while \(\omega\) is not computably categorical, it does have the property that it is \(\Delta^0_2\) categorical, in the sense that between any two computable copies there is a \(\Delta^0_2\) isomorphism. One might well ask how to classify the \(\Delta^0_2\) categorical (or, more generally, the \(\Delta^0_\alpha\) categorical for computable \(\alpha\)) computable linear orderings in terms of order type or in terms of effective syntactic properties of the ordering. The first type of question motivates the considerations of this book: Develop general machinery to classify \(\Delta^0_\alpha\) (or finer types, such as using the difference hierarchy) categorical models in terms of effective syntactic conditions on the models. While \(\omega\) is not computably categorical, it is what is called \(\Delta^0_2\) stable, meaning that every isomorphism between two computable copies is \(\Delta^0_2\). Of course the rationals, while computably categorical, are definitely not \(\Delta^0_\alpha\) stable for any computable ordinal \(\alpha\). The second type of question is to try to develop machinery to deal with stability questions on computable structures. The third type of question can still be motivated by the \(\omega\) example. The proof that \(\omega\) is not computably categorical takes the distinguished relation of adjacency and constructs another computable copy of \(\omega\) where this relation is no longer computable. Thus, the adjacency relation is not intrinsically computable, in the sense that it is computable in all computable copies. Naturally, the third motivating question is to develop a theory of classifying relations on models which are intrinsically \(\Delta^0_\alpha\). The forerunner here is the work of \textit{C. J. Ash} and \textit{A. Nerode} [``Intrinsically recursive relations'', in: J. Crossley (ed.), Aspects of effective algebra, Proc. Conf., Monash. Univ., Australia 1979, 26-41 (1981; Zbl 0467.03041)], who showed that a computable relation \(R\) on a computable structure \(M\) satisfying certain decidability conditions, is intrinsically computable iff for each tuple \(\overline m\in M\) and each existential formula \(\varphi(\overline m,\overline x)\), we can decide whether there is \(\overline a\not\in R\) satisfying \(\neg\varphi(\overline m,\overline a)\). Many of the basic model theoretical questions concerning computable categoricity and the like were examined by, particularly, Nurtazin and Goncharov. It was Ash who initiated a program to answer the higher level questions, such as \(\Delta^0_\omega\) categoricity. To do this he needed to develop a methodology for handling (certain types of) ``level \(\alpha\)'' priority arguments. This had earlier been done in some sense by Harrington with the ``method of workers.'' Again using linear orderings for illustrative purposes, suppose that one is trying to construct a computable linear ordering or order type \(\omega^n\tau\) (i.e. each point of \(\tau\) is replaced by a copy of \(\omega^n\)) given a \(\Delta^0_{2n+ 1}\) ordering \(\tau\). Then the idea is that one has \(2n+2\) workers \(W_0,\dots, W_{2n+1}\), where \(W_i\) has \(\emptyset^i\) as an oracle. It is \(W_0\) who has the task of constructing the final computable ordering, which is why it has no oracle. \(W_{2n+ 1}\) has complete information about \(\tau\), and hence can enumerate \(\tau\) as an ordering, indeed as a subordering of the rationals. It issues the command that around each point of \(\tau\) one should build a copy of \(\omega^n\). The next worker down \(W_{2n}\) has only \(\emptyset^{2n}\) as an oracle, and hence cannot know this but can understand the instructions of the boss worker \(W_{2n+1}\) via the limit lemma, and will only work with approximations, and so on down the line of workers with increasingly weaker approximations using iterates of the limit lemma. The trick is to make the end construction work. In particular, mistakes, caused by the finite number of mistakes in each application of the limit lemma, can be ``absorbed'' into the construction. Up to the work of Ash, all constructions using this kind of technique were handcrafted for the particular question at hand. Ash developed metatheorems (as have subsequently Knight and Lempp-Lermann) which allowed him to address the fundamental questions above, in certain circumstances, for general computable ordinals \(\alpha\). In Ash's original papers, there was a discussion about this as constructions in certain metric spaces. But the material has been reshaped by Ash and Knight and others to now be expressible as metatheorems concerning paths through certain kinds of trees of finite sequences and the existence of certain coherent alternating orderings on these trees. Where the Ash method applies, there is no doubt that it is far simpler to apply than, say, the Lempp-Lermann method. Now to the book at hand. While it never loses its focus on the motivating questions, to even get to them, the authors have realized that either they would need to assume knowledge of a lot of model theory and computability theory, or develop it themselves. Fortunately, they have chosen the latter. The book gives a thorough self-contained discussion of all of the basic computability theory needed, beginning with the basics of the models of computation, working through the recursion theorem, the hierarchies, trees, and computable ordinals and the hyperarithmetical and analytical hierarchies. In model theory, the authors begin with predicate calculus and again develop all the material needed for the book. This includes a discussion of infinitary logic with attention to things like Barwise compactness. In this reviewer's opinion, this is done with considerable style, and great efficiency. I particularly like the treatment of notations. The next section of the book is devoted to basic results of computable categoricity, stability and the like, with some material at the \(\Delta^0_3\) level, but no \(\alpha\) system arguments. This is done with numerous examples, so that we see how to derive the particular examples in the literature from general model theoretical results, and conversely motivated to general model theoretical arguments by particular examples, such as linear orderings, fields, and Boolean algebras. There is even a chapter on relativized questions such as intrinsic relative computability, and its relation to forcing. The final few chapters are devoted to \(n\) and then \(\alpha\) systems, and their applications to effective model theory. What is really nice here is that material previously presented using classical arguments, such as results for presentations of linear orderings, and even the Friedberg-Muchnik theorem, are reproved using the \(n\) and \(\alpha\) system methods. In this way we are given insight as to how the method works, and how it captures some of the classical methods. The \(\alpha\) system method is discussed for all computable \(\alpha\), and then variations such as simultaneous runs and \(\alpha\) friendly systems are looked at. Finally, the authors look at applications to Scott sets, and models of arithmetic (which, paradoxically, was where Harrington's worker method was first used). One sad note on the book is that it was originally meant to be done by Ash, who died before much was written. The project was completed by Knight based on some notes but greatly on her ideas and research. This is not a book on general computable model theory. So if you are looking for a book on computable dimension, or on computable omitting types, prime models or the like, then turn to Harizanov's forthcoming book, or to that of Ershov and Goncharov. However, there is no doubt in my mind that this book should be on the shelves of any model theorist or computability theorist, as it covers an important area of computable model theory. Moreover it does so with great elegance, style and beautiful lucidity. I will recommend the book to students even if they are only interested in the material of the first half and need a good introduction to those parts of computability and model theory. The authors are to be congratulated, particularly Knight for finishing Ash's project, and you should buy it, despite the astronomical price being asked for 346 pages of author prepared copy.