Recursive Functions and Metamathematics Problems of Completeness and
Recursive Functions and Metamathematics deals with problems of the completeness and decidability of theories, using as its main tool the theory of recursive functions. This theory is first introduced and discussed. Then Gödel's incompleteness theorems are
- PDF / 30,446,697 Bytes
- 402 Pages / 439.37 x 666.142 pts Page_size
- 103 Downloads / 249 Views
SYNTHESE LIBRARY STUDIES IN EPISTEMOLOGY, LOGIC, METHODOLOGY, AND PHILOSOPHY OF SCIENCE
Managing Editor:
JAAKKO HINTIKKA, Boston University Editors: DIRK VAN DALEN, University of Utrecht, The Netherlands DONALD DAVIDSON, University of California, Berkeley THEO A.F. KUIPERS, University of Groningen, The Netherlands PATRICK SUPPES, Stanford University, California JAN WOLENSKI, lagiellonian University, Krakow, Poland
VOLUME 286
ROMAN MURAWSKI Adam Mickiewicz University, Poznan, Poland
RECURSIVE FUNCTIONS AND METAMATHEMATICS Problems of Completeness and Decidability, G6del's Theorems
SPRINGER-SCIENCE+BUSINESS MEDIA, B.V.
A c.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-90-481-5298-8 ISBN 978-94-017-2866-9 (eBook) DOI 10.1007/978-94-017-2866-9
Printed on acid-free paper
All Rights Reserved © 1999 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1999 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
To H ania and Zosia
One can be sure that if Cod does actually exist then Cadet is in direct contact with him.
A. Mostowski
Preface Godel's incompleteness theorems and the decidability theory constitute one of the most significant parts of mathematical logic and the foundations of mathematics. Being very important and meaningful for mathematics they also have far-reaching epistemological and methodological consequences. They arose in the atmosphere of the late twenties and early thirties of the twentieth century marked by Hilbert's program of validation and justification of (infinite) classical mathematics. This program was one of the attempts to find a way out of the difficulties revealed by the discovery of antinomies connected with the notion of the actual infini ty (on the turn of the nineteenth century). Godel's theorems and the results on undecidability of theories have shown that Hilbert's program cannot be realized in the proposed form. They also forced the revision of certain views on the nature and structure of mathematical knowledge. The indicated results are not a closed chapter of logic and the foundations of mathematics. On the contrary, new interesting theorems being generalizations and strengthenings of Godel's theorems have been obtained in the seventies. Quite recently the so-called reverse mathematics opened a new perspective showing that Hilbert's program can be partially realized. Problems of (un )decidability of theories got a new dimension and new impulses by the development of computer science and computers themselves (cf. problems of practical decidability). All those Vll
Vlll
PREFACE
issues are still a subject of interesting philosophical discussions and investigations. The aim of this book is to present Godel's incompleteness theorems and the decidability theor
