Models of Peano Arithmetic RICHARD KAYE Jesus College Oxford I I I . I I CLARENDON PRESS· OXFORD I ' I' . 1991 I'.• · OXFORD LOGIC GUIDES: 15 General Editors ANGUS MACINTYRE JOHN SHEPHERDSON DANA SCOTT I I ;-. OXFORD LOGIC GUIDES 1. Jane Bridge: Beginning model theory: the completeness theorem and some consequences 2. Michael Dummett: Elements of intuitionism 3. A. S. Troelstra: Choice sequences: a chapter of intuitionistic mathematics 4. J. L. Bell: Boolean-valued models and independence proofs in set theory (1st edition) 5. Krister Segerberg: Classical propositional operators: an exercise in the foundation of logic 6. G. C. Smith: The Boole-De Morgan correspondence 1842-1864 7. Alec Fisher: Formal number theory and computability: a work book 8. Anand Pillay: An introduction to stability theory 9. H. E. Rose: Subrecursion: functions and hierarchies 10. Michael Hallett: Cantorian set theory and limitation of size 11. R. Mansfield and G. Weitkamp: Recursive aspects of descriptive set theory 12. J. L. Bell: Boolean-valued models and independence proofs in set theory (2nd edition) 13. Melvin Fitting: Computability theory: semantics and logic programming 14. J. L. Bell: Toposes and local set theories: an introduction 15. R. Kaye: Models of Peano arithmetic Oxford University Press, Walton Street, Oxford OX2 6DP Oxford New York Toronto Delhi Bombay Calcutta Madras Karachi Petaling Jaya Singapore Hong Kong Tokyo Nairobi Dar es Salaam Cape Town Melbourne Auckland and associated companies in Berlin Ibadan Oxfor.d is a trade mark of Oxford University Press Published in the United States by Oxford University Press, New York © R. Kaye, }991 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior permission of Oxford University Press British Library Cataloguing in Publication Data Kaye, Richard 'Models ofp eano arithmetic' . 1. Mathematicallogic /. Title 511.3 ISBN 0-19-853213-X Library of Congress Cataloguing in Publication Data Kaye, Richard Models of Peano arithmetic/Richard Kaye. p. 292 em. - (Oxford logic guides: 15) Includes bibliographical references and index. 1. Arithmetic Foundations. 2. Model theory. /. Title. II. Series. QA248.K385 1991 90-46826 CIP 513-de20 ISBN 0-19-853213-X Set by Apek Typesetters, Naiisea, Bristol Printed in Great Britain by Bookcraft (Bath) Ltd Midsomer Norton, Avon Preface Nonstandard models of (first-order) Peano arithmetic were first con- structed by Skolem (1934), and (implicitly) by Giidel (1930,1931) using his ". incompleteness and completeness theorems. The subject can be said to have come of age with Harvey Friedman's work on initial segments of non- standard models, when he realized the importance of the standard system of a model, rediscovering and extending Scott's work (Scott 1962) on what are today called Scott sets in the process. The most celebrated advance in the subject is the Paris-Harrington theorem (Paris and Harrington 1977), arising from work by Paris and Kirby on indicators, which in turn was inspired by Friedman's work. At roughly the same.time, we have a line of research into extensions of models of Peano arithmetic and types over such models, starting with the MacDowell-Specker theorem (MacDowell and Specker 1961) and followed by the work of Gaifman (his splitting theorem (1972) and his construction of a definable type (1976)) and others. In yet another line of attack, initiated by Abraham Robinson, and continued by Krajewski, Kotlarski, Lachlan, and others, we have the notion of satisfac- tion classes over a model of Peano arithmetic, and this links the subject up with the study of recursively saturated and resplendent models of Barwise, Schlipf, and Ressayre. This book is about these developments in the model theory of Peano arithmetic, and in particular the interplay between the first-order theory, recursion-theoretic aspects of the language, and the structural properties of models. I have tried to make the presentation as straightforward as possible, with a first-year postgraduate reader in mind; however, much of the material here is at 'undergraduate level' and, on the other hand, there are also more difficult exercises (usually with hints) and-later on-more advanced material to keep other readers happy too. I have kept to standard or self-explanatory notation where possible, and have given the most elementary proofs available, even if this means repeating ideas and arguments occasionally. Sometimes shorter or slicker proofs are possible, but often these obscure the essential ideas at hand. The advantages of this 'straightforward' approach are firstly, that (I hope) the material will be more accessible for a reader new to the subject (for whom a certain amount of repetition of similar ideas in different situations will be no bad thing), and secondly, that a more advanced reader will be able to ditdnto the book at almost any point. This last advantage is especially important for the chapter on recursive saturation (Chapter 15), a subject which arises naturally out of consideration of nonstandard models vi Preface but which has applications throughout model theory. Having said this, though, a reader who takes the book in its proper sequence will find a beautiful story emerging that liuks model theory and recursion theory in many surprising ways. The prerequisites for reading this book are set out in Chapter 0, and will probably be fewer than might at first be imagined. On the model-theoretic side, a basic knowledge of completeness, compactness, and elementary chains of models for first-order languages suffices. In particular the omitting-types theorem is not assumed, although many of the proofs here will use a similar kind of argument to that in the proof of omitting types. On the recursion-theoretic side even less background is needed: a basic knowledge of the notions 'primitive recursive', 'recursive', 'r.e.', and these notions relativized to an oracle suffices. There are two main points where recursion theory comes into the dis cussion of non-standard models. The first is concerned with the language of arithmetic, ::E and initial segments of models. It turns out that the A, natural numbers N form an initial segment of each non-standard model of arithmetic, and a natural class of formulas of ::E the 1:, formulas, A, coincides with the r.e. sets on N. Moreover, the truth of 1:, formulas is 'preserved' when one passes from validity in an initial segment of a model to validity in the full model. The second point is concerned with the notion of proof in the predicate .calculus. (The reader is assumed to have encountered some such notion, although the exact defiuition will not matter for our purposes.) The important fact about such 'notions is that they are recursively 'checkable' and 'enumerable'. Thus there is a suitable coding (or 'Giidel numbering') of formulas and proofs into integers in N so that a computer program could verify that a given n E N is the code for a valid proof of a certain sentence, and a second computer program could be written that lists all such codes of valid proofs. The reader will see both . these points at work throughout this book. I learned most of the material presented below during 1984-7 whilst I was a research student in Manchester. Lecture notes from courses by Jeff Paris (on models of arithmetic) and George Wilmers (on recursive satu ration) were extremely helpful in the preparation of this text, and the debt lowe these two people will be clear from my presentation below. There have been many other papers that I have consulted for specific parts of the text below, and I thank these authors too. I would also like to thank Angus Macintyre and Alex Wilkie for their interest and encouragement, and all the people who looked through preliminary drafts of this text and sug gested improvements. The quotations at the head of each chapter are intended to amuse the reader and lighten the text. They may only have a slight relevance to the chapter concerned, but I hope you will enjoy them! Oxford, 1990 R.K. Acknowledgements The quotations at the beginning of certain chapters are reproduced by kind permission as follows. Chapter O. From Mindswap, by Robert Sheckley. By permission of Victor Gollancz Ltd., London. Chapter 3. From Birds through a ceiling of alabaster: three Abbasid poets, translated by G. B. H. Wightman and A. Y. al-Adhari (Penguin Classics, 1975). By permission of Penguin Books Ltd., London. Chapter 5. From A mathematician's apology, by G. H. Hardy. By per mission of Cambridge University Press, Cambridge. Chapter 8. From Archy and Mehitabel, by Don Marquis. By permission of Faber and Faber Ltd., London, and Doubleday, New York. Chapters 10 and 12. From The collected poems of Wallace Stevens, by Wallace Stevens. By permission of Faber and Faber Ltd., London, and Alfred A. Knopf Inc., New York. Chapter 13. From 'An attempt at jealousy', Rich, by Craig Raine. By permission of Faber and Faber Ltd., London. Chapter 14. From 'Take a pew', by Alan Bennett, Beyond the fringe. By permission of the Peters Fraser & Dunlop Group Ltd., London, and International Creative Management, Inc., New York. Chapter 15. From The two Ronnies, BBC television. By permission of Ronnie Barker. Chapter 16. From 'A moral alphabet', Cautionary verses, by Hilaire Belloc. By permission of the Peters Fraser & Dunlop Group Ltd., London. II Contents / O. Background 1 ~ 0.1 Background model theory 2 0.2 Background recursion theory 5 , 1. The standard model 10 2. Discretely ordered rings 16 2.1 The axioms of PA- 16 2.2 Initial segments and end-extensions 21 3. Glidel incompleteness 28 3.1 l:, formulas and the computable sets 28 3.2 Incompleteness 35 4. The axioms of Peano arithmetic 42 4.1 Alternative induction schemes 43 4.2 Introducing new relations and functions 47 5. Some number theory in P A 53 5.1 Euclidean division and Bezout's theorem 53 5.2 Glide!'s lemma 58 5.3 The infinitude of primes 65 6. Models of PA 69 6.1 Overspill 70 6.2 The order-type of a model of PA 73 7. Collection 78 7.1 The arithmetic hierarchy 78 7.2 Cofinal extensions 86 8. Prime models 91 8.1 Definable elements 91 8.2 End-extensions 96 ix x Contents 9. Satisfaction 104 9.1 Sequences 105 9.2 Syntax 108 9.3 Semantics 119 10. Subsystems of PA 130 10.1 ~n-definable elements 130 10.2 ~n-elementary initial segments 134 11 Saturation 141 11.1 Coded sets 141 11.2 ~n-recursive saturation 146 11.3 Tennenbaum's theorem 153 12. Initial segments 159 12.1 Friedman's theorem 160 12.2 Variations 166 I 13. The standard system 172 13.1 Scott sets 172 13.2 The arithmetized completeness theorem 186 14. Indicators 193 14.1 What are indicators? 193 14.2 Recursively axiomatized theories have indicators 198 14.3 The Paris-Harrington theorem 206 15: Recursive saturation 223 15.1 Satisfaction classes 224 15.2 Resplendency 247 16. Suggestions for further reading 266 Bibliography 276 \ Index 285