Degrees of unsolvability. Local and global theory.

*(English)*Zbl 0542.03023
Perspectives in Mathematical Logic. Berlin etc.: Springer-Verlag. XIII, 307 p., 56 figs. DM 138.00; $ 54.80 (1983).

The purpose of this book is the study of the upper semilattice \({\mathcal D}{\mathcal U}=({\mathcal D},\cup)\) where \({\mathcal D}=(D,\leq)\), D being the set of degrees of unsolvability. In Part A (The structure of the degrees) the general framework is defined. Necessary notions of recursive function theory and computability theory are reviewed, the degrees are defined, their importance is emphasized and basic ”local” results - about bounded intervals of degrees - are presented (incomparable degrees, embeddings into degrees, the jump operator, maximal chains and antichains, high/low hierarchies, automorphism bases). The rest of the book deals with the ”global” theory. Parts B and C (Countable ideals of degrees; Initial segments of \({\mathcal D}\) and the jump operator) have as a central point various constructions of initial segments of \({\mathcal D}\) controlled by an oracle of degree \(0^{(2)}\) and respectively by an oracle of degree 0’. Necessary notions of lattice theory and mathematical logic are introduced where needed, and separately in two appendices (Appendix A - Coding into structures and theories; Appendix B - Lattice tables and representation theorems).

This is an excellent book, rigorous and in the same time intuitive. The exercises, the bibliographical and historical remarks (appearing in almost every section) enlighten the understanding. It contains very recent results. Furthermore, important open problems are described and some methods for proving specific theorems of the area (the use of Church’s thesis, the method of forcing, the use of partial recursive trees) are treated with their own right.

This is an excellent book, rigorous and in the same time intuitive. The exercises, the bibliographical and historical remarks (appearing in almost every section) enlighten the understanding. It contains very recent results. Furthermore, important open problems are described and some methods for proving specific theorems of the area (the use of Church’s thesis, the method of forcing, the use of partial recursive trees) are treated with their own right.

Reviewer: C.Masalagiu

##### MSC:

03D30 | Other degrees and reducibilities in computability and recursion theory |

03-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations |

03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |

03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |