This paper discusses lower bounds for proof length, especially as measured by number of steps (inferences). We give the first publicly known proof of Gödel's claim that there is superrecursive (in fact. unbounded) proof speedup of (i + 1)st-order arithmetic over ith-order arithmetic, where arithmetic is formalized in Hilbert-style calculi with + and · as function symbols or with the language of PRA. The same results are established for any weakly schematic formalization of higher-order logic: this allows all tautologies as (...) axioms and allows all generalizations of axioms as axioms. Our first proof of Gödel's claim is based on self-referential sentences: we give a second proof that avoids the use of self-reference based loosely on a method of Statman. (shrink)

Recent years have seen the appearance of many English-language hand books of logic and numerous monographs on topical discoveries in the foundations of mathematics. These publications on the foundations of mathematics as a whole are rather difficult for the beginners or refer the reader to other handbooks and various piecemeal contribu tions and also sometimes to largely conceived "mathematical fol klore" of unpublished results. As distinct from these, the present book is as easy as possible systematic exposition of the now (...) classical results in the foundations of mathematics. Hence the book may be useful especially for those readers who want to have all the proofs carried out in full and all the concepts explained in detail. In this sense the book is self-contained. The reader's ability to guess is not assumed, and the author's ambition was to reduce the use of such words as evident and obvious in proofs to a minimum. This is why the book, it is believed, may be helpful in teaching or learning the foundation of mathematics in those situations in which the student cannot refer to a parallel lecture on the subject. This is also the reason that I do not insert in the book the last results and the most modem and fashionable approaches to the subject, which does not enrich the essential knowledge in founda tions but can discourage the beginner by their abstract form. A. G. (shrink)

This book grew out of a graduate student paper [261] in which I set down some criticisms of J. R. Lucas' attempt to refute mechanism by means of G6del's theorem. I had made several such abortive attempts myself and had become familiar with their pitfalls, and especially with the double edged nature of incompleteness arguments. My original idea was to model the refutation of mechanism on the almost universally accepted G6delian refutation of Hilbert's formalism, but I kept getting stuck on (...) questions of mathematical philosophy which I found myself having to beg. A thorough study of the foundational works of Hilbert and Bernays finally convinced me that I had all too naively and uncritically bought this refutation of formalism. I did indeed discover points of surprisingly close contact between formalism and mechanism, but also that it was possible to under mine certain strong arguments against these positions precisely by invok ing G6del's and related work. I also began to realize that the Church Turing thesis itself is the principal bastion protecting mechanism, and that G6del's work was perhaps the best thing that ever happened to both mechanism and formalism. I pushed these lines of argument in my dis sertation with the patient help of my readers, Raymond Nelson and Howard Stein. I would especially like to thank the latter for many valuable criticisms of my dissertation as well as some helpful suggestions for reor ganizing it in the direction of the present book. (shrink)

Kurt Gödel made many affirmations of robust realism but also showed serious engagement with the idealist tradition, especially with Leibniz, Kant, and Husserl. The root of this apparently paradoxical attitude is his conviction of the power of reason. The paper explores the question of how Gödel read Kant. His argument that relativity theory supports the idea of the ideality of time is discussed critically, in particular attempting to explain the assertion that science can go beyond the appearances and ‘approach the (...) things’. Leibniz and post-Kantian idealism are discussed more briefly, the latter as documented in the correspondence with Gotthard Günther. (shrink)

This volume is written jointly by Witold Marciszewski, who contributed the introductory and the three subsequent chapters, and Roman Murawski who is the author of the next ones - those concerned with the 19th century and the modern inquiries into formalization, algebraization and mechanization of reasonings. Besides the authors there are other persons, as well as institutions, to whom the book owes its coming into being. The study which resulted in this volume was carried out in the Historical Section of (...) the research project _Logical Systems and Algorithms for Automatic Testing of Reasoning,_ 1986-1990, in which participated nine Polish universities; the project was coordinated by the Department of Logic, Methodology and Philosophy of Science of the Bia??l??ystok Branch of the University of Warsaw, and supported by the Ministry of Education 1987). The major part of the project was focussed on the software for computer-aided theorem proving called Mizar MSE ) due to Dr. Andrzej Trybulec. He and other colleagues deserve a grateful mention for a hands-on experience and theoretical stimulants owed to their collaboration. (shrink)

Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens / von Dr. Gottlob Frege,...Date de l'edition originale : 1879Ce livre est la reproduction fidele d'une oeuvre publiee avant 1920 et fait partie d'une collection de livres reimprimes a la demande editee par Hachette Livre, dans le cadre d'un partenariat avec la Bibliotheque nationale de France, offrant l'opportunite d'acceder a des ouvrages anciens et souvent rares issus des fonds patrimoniaux de la BnF.Les oeuvres faisant partie de cette collection ont ete numerisees (...) par la BnF et sont presentes sur Gallica, sa bibliotheque numerique.En entreprenant de redonner vie a ces ouvrages au travers d'une collection de livres reimprimes a la demande, nous leur donnons la possibilite de rencontrer un public elargi et participons a la transmission de connaissances et de savoirs parfois difficilement accessibles.Nous avons cherche a concilier la reproduction fidele d'un livre ancien a partir de sa version numerisee avec le souci d'un confort de lecture optimal. Nous esperons que les ouvrages de cette nouvelle collection vous apporteront entiere satisfaction.Pour plus d'informations, rendez-vous sur www.hachettebnf.frhttp://gallica.bnf.fr/ark:/12148/bpt6k65658c. (shrink)