Mathematical Logic
From the Introduction: "We shall base our discussion on a set-theoretical foundation like that used in developing analysis, or algebra, or topology. We may consider our task as that of giving a mathematical analysis of the basic concepts of logic and math
- PDF / 40,853,047 Bytes
- 535 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 289 Views
37 Editorial Board F. W. Gehring P. R. Halmos Managing Editor
c.
C. Moore
I.Donald Monk
Mathematical Logic
Springer- Verlag New York
Heidelberg
Berlin
1976
J. Donald Monk Department of Mathematic\ University of Colorado
Boulder. Colorado 80302
Editorial Board P. R. Halmos
F. W. Gehring
lv/aI/aging Editor
University of Michigan Department of Mathematic!'> Ann Arbor. Michigan 48104
University of California Department of Mathematics
c.
C. Moore
University of California at Berkeley Department of Mathematics
Berkeley, California 94720
Santa Barbara. California 93106
AMS Subject Classifications Primary: 02-xx Secondary: ION-xx. 06-XX. 08-XX. 26A98
Library of Congress Cataloging in Publication Data Monk. James Donald. 1930·· Mathematical logic. (Graduate texts in mathematics: 37) Bibliography Includes indexes. I. Logic. Symbolic and mathematical. I. Title. II. Series. QA9.M68 511'.3 75-42416 All rights reserved. No part of this book may be translated or reproduced in any form without written permission from Springer- Verlag.
©
1976 by Springer- Verlag Inc.
Softcover reprint of the hardcover 1st edition 1976
ISBN 978-1-4684-9454-9
ISBN 978-1-4684-9452-5 (eBook)
DOI 10.1007/978-1-4684-9452-5
to Dorothy
Preface
This book is a development of lectures given by the author numerous times at the University of Colorado, and once at the University of California, Berkeley. A large portion was written while the author worked at the Forschungsinstitut fUr Mathematik, Eidgennossische Technische Hochschule, Zurich. A detailed description of the contents of the book, notational conventions, etc., is found at the end of the introduction. The author's main professional debt is to Alfred Tarski, from whom he learned logic. Several former students have urged the author to publish such a book as this; for such encouragement I am especially indebted to Ralph McKenzie. I wish to thank James Fickett and Stephen Comer for invaluable help in finding (some of the) errors in the manuscript. Comer also suggested several of the exercises. J. Donald Monk October, 1975
vii
Contents
Introduction Interdependence of sections
I 9
Part I
Recursive Function Theory
11
I. Turing machines
14
2. Elementary recursive and primitive recursive functions
26
Recursive functions; Turing computability Markov algorithms Recursion theory Recursively enumerable sets 7. Survey of recursion theory
3. *4. 5. 6.
45
69
76 92
105
Part II
Elements of Logic *8. *9. 10. II. * 12.
Sentential logic Boolean algebra Syntactics offirst-order languages Some basic results of first-order logic Cylindric algebras
113 115 141
162 194 219
IX
Part III
Decidable and Undecidable Theories 13. 14. 15. 16. 17.
Some decidable theories Implicit definability in number theories General theory of undecidability Some undecidable theories Unprovability of consistency
231 233 244 262 279 298
Part IV
Model Theory 18. 19. *20. 21. 22. *23. 24. 25. 26. 27. 28.
Construction of models Elementary equivalence Nonstandard mathematics Complete theori
