Metamathematics of first-order arithmetic.

*(English)*Zbl 0781.03047
Perspectives in Mathematical Logic. Berlin: Springer-Verlag. xiv, 460 p. (1993).

This is the third monograph on first-order arithmetic published recently. Earlier appeared: R. Kaye, Models of Peano arithmetic (1991; Zbl 0744.03037), and C. Smoryński, Logical number theory. I: An introduction (1991; Zbl 0759.03002). The present book overlaps with them only to a small degree. The three books complement each other – so we got in this way a nice survey of results and methods in the foundations of arithmetic of natural numbers.

The book consists of three main parts. Part A contains positive results on fragments of arithmetic. It is shown that various parts of mathematics and logic can be developed in fragments of first-order arithmetic. In particular, partial truth definitions, recursion theory, and elements of logic and of combinatorics in fragments are discussed. Part B is devoted to incompleteness. The technique of self-reference and the incompleteness results of Gödel are presented. Further, reflexive theories, definable cuts and partial conservativity and interpretability are discussed. The model-theoretical considerations in this part are devoted to the study of cuts, of the method of indicators and its applications and to formalizing model theory. Part C indicates the interrelations between fragments of first-order arithmetic and complexity theory. Various results of Part A are strengthened by showing that certain constructions done in stronger fragments are possible in some systems of bounded arithmetic. The relationship between provability in fragments and complexity of computation is studied, and witnessing functions, interpretability and consistency are considered as well.

The book is supplemented by bibliographical remarks and further readings, it contains also an extensive bibliography and indexes of terms and symbols.

It is really a highly interesting book – a survey of a large amount of results presented in a systematic and clear way. It will serve as a source of information for those who want to learn meta-mathematics of first-order arithmetic as well as a reference book for people working in this field.

The book consists of three main parts. Part A contains positive results on fragments of arithmetic. It is shown that various parts of mathematics and logic can be developed in fragments of first-order arithmetic. In particular, partial truth definitions, recursion theory, and elements of logic and of combinatorics in fragments are discussed. Part B is devoted to incompleteness. The technique of self-reference and the incompleteness results of Gödel are presented. Further, reflexive theories, definable cuts and partial conservativity and interpretability are discussed. The model-theoretical considerations in this part are devoted to the study of cuts, of the method of indicators and its applications and to formalizing model theory. Part C indicates the interrelations between fragments of first-order arithmetic and complexity theory. Various results of Part A are strengthened by showing that certain constructions done in stronger fragments are possible in some systems of bounded arithmetic. The relationship between provability in fragments and complexity of computation is studied, and witnessing functions, interpretability and consistency are considered as well.

The book is supplemented by bibliographical remarks and further readings, it contains also an extensive bibliography and indexes of terms and symbols.

It is really a highly interesting book – a survey of a large amount of results presented in a systematic and clear way. It will serve as a source of information for those who want to learn meta-mathematics of first-order arithmetic as well as a reference book for people working in this field.

Reviewer: R.Murawski (Poznań)

##### MSC:

03F30 | First-order arithmetic and fragments |

03D15 | Complexity of computation (including implicit computational complexity) |

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