Authors' Preface

Summary

After having finished this book on the metamathematics of first order arithmetic, we consider the following aspects of it important: first, we pay much attention to subsystems (fragments) of the usual axiomatic system of first order arithmetic (called Peano arithmetic), including weak subsystems, i.e. so-called bounded arithmetic and related theories. Second, before discussing proper metamathematical questions (such as incompleteness) we pay considerable attention to positive results, i.e. we try to develop naturally important parts of mathematics (notably, some parts of set theory, logic and combi-natorics) in suitable fragments. Third, we investigate two notions of relative strength of theories: interpret ability and partial conservativity. Fourth, we offer a systematic presentation of relations of bounded arithmetic to problems of computational complexity.

The need for a monograph on metamathematics of first order arithmetic has been felt for a long time; at present, besides our book, at least two books on this topic are to be published, one written by R, Kaye and one written by C. Smorynski. We have been in contacts with both authors and are happy that the overlaps are reasonably small so that the books will complement each other.

This book consists of a section of preliminaries and of three parts: A -Positive results on fragments, B - Incompleteness, C - Bounded arithmetic. Preliminaries and parts A, B were written by P. H., part C by P. P. We have tried to keep all parts completely compatible.

The reader is assumed to be familiar with fundamentals of mathematical logic, including the completeness theorem and Herbrand's theorem; we survey the things assumed to be known in the Preliminaries, in order to fix notation and terminology.

Acknowledgements. Our first thanks go to the members of the 12-group for the possibility of publishing the book in the series Perspectives in mathematical logic and especially to Professor Gert H. Miiller, who invited P. H. to write a monograph with the present title, agreed with his wish to write the book jointly with P. P. and continuously offered every possible help. We are happy to recognize that we have been deeply influenced by Professor Jeff Paris.