LOGIC AND SCIENTIFIC METHODS SYNTHESE LIBRARY STUDIES IN EPISTEMOLOGY, LOGIC, METHODOLOGY, AND PHILOSOPHY OF SCIENCE Managing Editor: JAAKKO HINTIKKA, Boston University Editors: DIRK V AN DALEN, University of Utrecht, The Netherlands DONALD DAVIDSON, University of California, Berkeley THEO A.F. KUIPERS, University ofGroningen, The Netherlands PATRICK SUPPES, Stanford University, California JAN WOLEr~"sKI, Jagiellonian University, Krakow, Poland VOLUME 259 LOGIC AND SCIENTIFIC METHODS Volume One o/the Tenth International Congress o/Logic, Methodology and Philosophy o/Science, Florence, August 1995 Edited by MARIA LUISA DALLA CHIARA University of Florence KEESDOETS University ofA msterdam DANIELE MUNDICI University ofM ilan and JOHAN VAN BENTHEM University ofA msterdam and Stanford University Springer-Science+Business Media, B.Y. AC.I.P.Cataloguerecord forthisbookisavailablefrom theLibrary ofCongress ISBN978-90-481-4786-1 ISBN978-94-017-0487-8(eBook) DOI10.1007/978-94-017-0487-8 Printedonacid-freepaper _AllRights Reserved © 1997SpringerScience+BusinessMediaDordrecht OriginallypublishedbyKluwerAcademicPublishersin1997. Softcoverreprintofthehardcover 1stedition1997 Nopartofthematerial protectedbythiscopyrightnoticemaybereproducedor utilized inanyformorbyanymeans,electronicormechanical, including photocopying,recordingorbyanyinformationstorageand retrieval system,withoutwritten permissionfromthecopyrightowner. TABLE OF CONTENTS Editorial vii Sections, plenary lectures, symposia ix President's address 1 Section 1 Proof theory and categorical logic 5 A. CANTINI Proof-theoretical aspects of self-referential truth 7 A. JOYAL Free lattices, communication and money games .. 29 J. KRAJicEK On methods for proving lower bounds in propo- sitional logic. . . . . . . . . . . . . . . . . 69 V.Yu. SAZONOV On bounded set theory. . . . . . . . . . 85 Section 2 Model theory, set theory and formal systems 105 PH.G. KOLAITIS Infinitary logic in finite model theory. . 107 P.D. LINCOLN, A. SCEDROV, N. SHANKAR Decision problems for second-order linear logic . . . . . . . . . . . . . . . . . . . . 127 S. TODORCEVIC Comparing the continuum with the first two uncountable cardinals ... . . . . . . . . . . . . . . . . . .. 145 Section 3 Recursion theory and constructivism 157 K.T. KELLY, O. SCHULTE Church's thesis and Hume's problem159 Y.N. MOSCHOVAKIS The logic of functional recursion ..... 179 H. SCHWICHTENBERG, K. STROETMAN From higher or~er terms to circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 R. SOARE Computability and enumerability ........... 221 G. TAMBURRINI Mechanistic theories in cognitive science: the import of Turing's thesis. . . . . . . . . . . . . . . . . . . .. 239 Section 5 Philosophical logic 259 E. CASARI Conjoining and disjoining on different levels 261 K. DOSEN Logical consequence: a turn in style . . . . . 289 S.O. HANSSON, D. MAKINSON Applying normative rules with restraint ............................... 313 v VI Section 10 Philosophy of logic, mathematics and computer science 333 CH.D. PARSONS What can we do "in principle"? 335 J. PEARL Causation, action, and counterfactuals . 355 Symposium 1 Logic and philosophy of science: current inter- faces 377 T.A.F. KUIPERS Logic and philosophy of science: current in- terfaces ............................... 379 K.T. KELLY, O. SCHULTE, V. HENDRICKS Reliable belief re- VISIon ................................ 383 V. RANTALA Explanatory translation: beyond functionalism and reductionism . . . . . . . . . . . . . . . . . . . . . . . . . . 399 P. THAGARD, C. SHELLEY Abductive reasoning: logic, visual thinking, and coherence ...................... 413 P. WEINGARTNER Can the laws of nature (physics) be complete?429 Symposium 4 Logic in Central and Eastern Europe 447 P. HAJEK Logic in Central and Eastern Europe . . . . 449 L. BUKOVSKY Logic in Czechoslovakia and Hungary . . 451 V.A. USPENSKY Mathematical logic in the former Soviet Union: brief history and current trends .................. 457 D. VAKARELOV Logic in Central and Eastern Europe: Balkan region . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 R. WOJCICKI The postwar panorama of logic in Poland . 497 Closing address 509 B.C. VAN FRAASSEN Structure and perspective: philosophical perplexity and paradox ....................... 511 Table of contents Vol. II 531 EDITORIAL These volumes continue a long tradition. They document part of the scien tific program of the 10th International Congress of Logic, Methodology and Philosophy of Science, held at Florence, August 1995. The founding fathers of the Congress, including Alfred Tarski, Evert Beth, and Abraham Robin son, left us a legacy of cooperation between logicians and philosophers of science, on an international scale which is still unique. At the time, this al liance seemed natural. Philosophers and mathematicians in the fifties still re membered the heighdays of logical positivism, and their interests were broad. Not accidentally, Tarski's best-known textbook is a joint introduction to logic and methodology of the exact sciences. In the meantime, many things have changed. Logicians have developed new contacts with computer science and linguistics, philosophers of science also look toward history and sociology. Nevertheless, our Congress is still there, like a Grand Hotel, with perhaps a somewhat faded splendour, but with a distinctive style, elegance and comfort. And it serves an important purpose. The invited lectures published here demonstrate much of what goes on in the fields of the Congress. Through an extensive selection process, General and Sectional Program Committees have chosen speakers whose excellence in research deserves recognition. How much this honour is appreciated is shown by a remarkably high acceptance rate. The sectional organisation covers the traditional subdisciplines of mathematical logic, philosophical logic, as well as their interfaces with computer science, linguistics, philosophy. Philosophy of science is broadly represented, too, including both general issues of method ology and ethics, and specific foundational issues of natural sciences, social sciences and humanities. In addition to this planned part, the Congress also serves as the meeting place for an international community from allover the world. There have been a host of interesting contributed talks, often leading to osmosis through the sectional barriers of the program. Selections of these papers will appear in a number of satellite volumes, edited by the Florence local organizers. The program of the Congress has further special features. Traditionally, the opening and closing lectures are given by eminent scholars and scientists, who give us a broad perspective on the intellectual environment that we are working in. We are pleased to include the lectures by professors Beltrametti and van Fraassen, who did just that. Also, the general Program Committee has organized a number of special Symposia, to high-light some topics of cur rent interest, and to enhance the connectivity of our field. In Florence, these Vll Vlll were "Semantics and Semiotics", "Logic and Philosophy of Science", "Logic in Eastern Europe" and "Logic in the Far East" . These symposia are represented here, too. Not included are the so-called Affiliated Meetings on "Model Theo ry" (organized jointly by the Kurt G6del Society and the Italian Association of Logic and its Applications, AILA) and "Proof Theory for Natural Lan guage" (European Association for Logic, Language and Information), whose materials will be published elsewhere by the responsible organizers. There remains the pleasant task of expressing thanks where these are due. We have been assisted very generously by Mrs. Annie Kuipers (Kluwer Aca demic Publishers). Most of the editorial logistics have been taken care of by Kees Doets at the University of Amsterdam, assisted by Jeroen Haak and Joeri van Ruth. The four editors themselves see this Volume as the visible finished product of several years of effective and pleasant collaboration in a joint Dutch-Italian team. Readers with even the slightest knowledge of con temporary Europe will know that this is indeed a winning combination ... Maria Luisa Dalla Chiara (Firenze) Kees Doets (Amsterdam) Daniele Mundici (Milano) Johan van Benthem (Amsterdam and Stanford) SECTIONS, PLENARY LECTURES AND SPECIAL SYMPOSIA LOGIC Section 1. Proof Theory and Categorical Logic Section Program Committee: G.E. MINTS, Stanford (chair) V. OREVKOV, St. Petersburg J. LAMBEK, Montreal Invited speakers: A. CANTINI, Proof-theoretic aspects of self-referential truth Universita degli Studi di Firenze A. JOYAL, Free lattices, communication and money games a Universite du Quebec Montreal J. KRAJICEK, On methods for proving lower bounds in propositional logic Mathematical Institute of Science, Prague V.Yu. SAZONOV, On bounded set theory Russian Academy of Sciences, Pereslavl-Zalessky Section 2. Model Theory, Set Theory and Formal Systems Section Program Committee: W.A. HODGES, London (chair) X. CAICEDO, Bogota C.A. DI PRISCO, Caracas Invited speakers: PH.G. KOLAITIS, Infinitary logic in finite model theory University of California, Santa Cruz A. SCEDROV, Decision problems for second-order linear logic (with P.D. LINCOLN and N. SHANKAR) University of Pennsylvania, Philadelphia and SRI International IX