Foundations 01 Mathematics Symposium Papers Commemorating the Sixtieth Birthday of Kurt Codel Edited by Jack J. Bulloff Thomas C. Holyoke· S.W. Hahn Springer-Verlag New York Inc. 1969 Managing Editor: JACK J. BULLOFF State University of New York at Albany· Albany, N. Y. Technical Editors: THOMAS C. HOLYOKE Antioch College' Yellow Springs, Ohio SAMUEL W. HAHN Wittenberg University' Springfield, Ohio The Photograph of Kurt GOdel is by Orren J. Turner All rights reserved. No part of this book may be translated or reproduced in any form without written permission from Springer-Verlag ISBN-13: 978-3-642-86747-7 e-ISBN-13: 978-3-642-86745-3 DOl: 10.1 007/978-3-642-86745-3 © by Springer-Verlag, Berlin' Heidelberg 1969 Library of Congress Catalog Card Number 68-28757 Softcover reprint of the hardcover 1s t edition 1969 Title No. 1518 Kurt Cadel Biographical Data KURT GODEL was born on April 28, 1906 in Brunn (Brno), Czecho slovakia (at that time part of the Austro-Hungarian Monarchy). He studied mathematics and physics at the University of Vienna and took the Ph. D. degree there in 1930. He was Dozent in mathematics at the University of Vienna 1933-1938. He has been a member of the Institute for Advanced Study from 1940-1953, and several times before 1940. He joined its faculty in 1953. He became an American citizen in 1948 and received honorary degrees from Yale and Harvard in 1951 and 1952. He is a member of the National Academy of Sciences and of the American Philosophical Society and corecipient of the 1951 Einstein Award. Preface Dr. KURT GODEL'S sixtieth birthday (April 28, 1966) and the thirty fifth anniversary of the publication of his theorems on undecidability were celebrated during the 75th Anniversary Meeting of the Ohio Ac ademy of Science at The Ohio State University, Columbus, on April 22, 1966. The celebration took the form of a Festschrift Symposium on a theme supported by the late Director of The Institute for Advanced Study at Princeton, New Jersey, Dr. J. ROBERT OPPENHEIMER: "Logic, and Its Relations to Mathematics, Natural Science, and Philosophy." The symposium also celebrated the founding of Section L (Mathematical Sciences) of the Ohio Academy of Science. Salutations to Dr. GODEL were followed by the reading of papers by S. F. BARKER, H. B. CURRY, H. RUBIN, G. E. SACKS, and G. TAKEUTI, and by the announcement of in-absentia papers contributed in honor of Dr. GODEL by A. LEVY, B. MELTZER, R. M. SOLOVAY, and E. WETTE. A short discussion of "The II Beyond Godel's I" concluded the session. This Anniversary Volume has been prepared under the sponsorship of Section L. Thanks are due to Mr. John H. MELVIN, Executive Secre tary of the Ohio Academy of Science, and to Dr. ROBERT C. STEPHENSON, Chairman of the 75th Anniversary Committee, The Ohio State University Research Foundation, for the many things they did to make the meeting possible. Dr. CARL KAYSEN, Director of the Institute for Advanced Study, provided items from his files which have made for a better and more attractive volume. Valuable suggestions were made to authors and editors by Dr. KLAUS PETERS of Springer-Verlag. Finally, it is a pleasure to acknowledge the helpful advice offered by the referees, by colleagues of Dr. GODEL, and by members of the Association for Symbolic Logic. The Editors List of Contributors STEPHEN F. BARKER, The Johns Hopkins University, Baltimore, Mary land/USA. HASKELL B. CURRY, University of Amsterdam, Amsterdam/The Nether lands. AzRIEL LEVY, Hebrew University, Jerusalem/Israel, and Stanford University, Stanford, California /USA. BERNARD MELTZER, University of Edinburgh / Scotland. HERMAN RUBIN, Purdue University, Lafayette, Indiana/USA. GERALD E. SACKS, Massachusetts Institute of Technology, Cambridge, Massachusetts jUSA. ROBERT M. SOLOVAY, The Rockefeller University, New York, New York, and University of California, Berkeley, California/USA. GAISI TAKEUTI, University of Illinois, Urbana, Illinois, and The Institute for Advanced Study, Princeton, New Jersey /USA. EDUARD WETTE, Uckerath, and Radevormwald/West Germany. Contents Greetings from Dr. J. ROBERT OPPENHEIMER VIII Greetings from Dr. GODEL . . . . . . . . . VIII Tribute to Dr. GODEL by JOHN VON NEUMANN IX Bibliography of KURT GODEL . . . . . . . . XI Realism as a Philosophy of Mathematics. By STEPHEN F. BARKER 1 The Undecidability of AK-Conversion. By HASKELL B. CURRY 10 The Definability of Cardinal Numbers. By AZRIEL LEVY . .. 15 The Use of Symbolic Logic in Proving Mathematical Theorems by Means of a Digital Computer. By BERNARD MELTZER . . .. 39 A New Approach to the Foundations of Probability. By HERMAN RUBIN. . . . . . . . . . . . . . . . . . . . 46 Measure-Theoretic Uniformity. By GERALD E. SACKS . . . . .. 51 On the Cardinality of 2~ Sets of Reals. By ROBERT M. SOLOVAY . 58 The Universe of Set Theory. By GAISI TAKEUTI . . . . . . .. 74 Definition eines (relativ vollstandigen) formalen Systems konstruk- tiver Arithmetik. By EDUARD WETTE . . . . . . . . . .. 130 Greetings Greetings to GOdel Symposium from Dr. J. Robert Oppenheimer "It is an honor and a pleasure for me to help to celebrate KURT GODEL, his anniversaries, and his great work, which has not only im measurably deepened and enriched the understanding of the logical structure of so much abstract and mathematical argument, but illumi nated the role of limitation in human understanding in general. I salute the scholars, many of high distinction, who have assembled to honor GODEL by presenting their discoveries and their views, and I hope that the contributions to this occasion will bring great pleasure to the man who has inspired it." Greetings from Dr. GOdel "I wish to convey my greetings to the symposium, and in particular to the speakers. I am sorry I cannot attend, but I am looking forward with interest and pleasure to the volume in which the lectures will be presented." Tribute to Dr. Gijdel JOHN VON NEUMANN The true significance of Dr. GODEL'S work was perhaps most clearly and succinctly summarized by the late Professor JOHN VON NEUMANN in his remarks in March 1951, on the occasion of the presentation of the ALBERT EINSTEIN Award to Dr. GODEL. The textual reproduction of those remarks follows: "KURT GODEL'S achievement in modern logic is singular and monu mental - indeed it is more than a monument, it is a landmark which will remain visible far in space and time. Whether anything comparable to it has occurred in the logic of modern times may be debated. In any case, the conceivable proxima are very, very few. The subject of logic has certainly completely changed its nature and possibilities with GODEL'S achievement. GODEL'S name is associated with many important achievements in detail, and with two absolutely decisive ones. The occasion is such that I think I should only talk about the two latter. The nature of the first one is easy to indicate, although its exact technical character and execution escape an adequate characterization without the specialized and rather intricate techniques of formal logic. GODEL was the first man to demonstrate that certain mathematical theorems can neither be proved nor disproved with the accepted, rigorous methods of mathematics. In other words, he demonstrated the existence of undecidable mathematical propositions. He proved furthermore that a very important specific proposition belonged to this class of undecidable problems: The question, as to whether mathematics is free of inner contradictions. The result is remarkable in its quasi-paradoxical 'self denial': It will never be possible to acquire with mathematical means the certainty that mathematics does not contain contradictions. It must be emphasized that the important point is, that this is not a philosophical principle or a plausible intellectual attitude, but the result of a rigorous mathematical proof of an extremely sophisticated kind. The formulation that I gave above has coarsened the result and obliterated some of the fine points of its rigorous formulation, but if one is to state the theorem without having recourse to the difficult technical language of formal logic this is, I think, the best approximation that one can achieve. x Tribute to Dr. Giidel GODEL actually proved this theorem, not with respect to mathematics only, but for all systems which permit a formalization, that is a rigorous and exhaustive description, in terms of modern logic: For no such system can its freedom from inner contradiction be demonstrated with the means of the system itself. GODEL'S second decisive result can only be stated in the terminology of formal logic and of an important but rather abstruse modern math ematical discipline: Set theory. Two surmised theorems of set theory, or rather two principles, the so-called 'Principle of Choice' and the so-called 'Continuum Hypothesis' resisted for about 50 years all attempts of de monstration. GODEL proved that neither of the two can be disproved with mathematical means. For one of them we know that it can not be proved either, for the other the same seems likely, although it does not seem likely that a lesser man than GODEL will be able to prove this. I will not attempt a detailed evaluation of these achievements, I will limit myself to repeat: In the history oflogic, they are entirely singular. No indemonstrability within mathematics proper had ever been rigorously established before GODEL. The subject of logic will never again be the same."