Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts 1 to create a coherent mathematical view of these foundations. The result of this collaborative work is presented here in the hope that it does justice to the individual contributor and that the reader has a chance of judging the work as a whole. E. Engeler ETH Zurich, April 1994 lCollected in Chapter III, An Algebraization of Algorithmics, in Algorithmic Properties of Structures, Selected Papers of Erwin Engeler, World Scientific PubJ. Co., Singapore, 1993, pp. 183-257. I Historical and Philosophical Background Erwin Engeler In the fall of 1928 a young American turned up at the Mathematical Institute of Gottingen, a mecca of mathematicians at the time; he was a young man with a dream and his name was H. B. Curry. He felt that he had the tools in hand with which to solve the problem of foundations of mathematics mice and for all. His was an approach that came to be called "formalist" and embodied that later became known as Combinatory Logic."

This book appeared about ten years ago in Gennan. It started as notes for a course which I gave intermittently at the ETH over a number of years. Following repeated suggestions, this English translation was commissioned by Springer; they were most fortunate in finding translators whose mathemati cal stature, grasp of the language and unselfish dedication to the essentially thankless task of rendering the text comprehensible in a second language, both impresses and shames me. Therefore, my thanks go to Dr. Roberto Minio, now Darmstadt and Professor Charles Thomas, Cambridge. The task of preparing a La'JEX-version of the text was extremely daunting, owing to the complexity and diversity of the symbolisms inherent in the various parts of the book. Here, my warm thanks go to Barbara Aquilino of the Mathematics Department of the ETH, who spent tedious but exacting hours in front of her Olivetti. The present book is not primarily intended to teach logic and axiomat ics as such, nor is it a complete survey of what was once called "elementary mathematics from a higher standpoint." Rather, its goal is to awaken a certain critical attitude in the student and to help give this attitude some solid foun dation. Our mathematics students, having been drilled for years in high-school and college, and having studied the immense edifice of analysis, regrettably come away convinced that they understand the concepts of real numbers, Euclidean space, and algorithm."

Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts 1 to create a coherent mathematical view of these foundations. The result of this collaborative work is presented here in the hope that it does justice to the individual contributor and that the reader has a chance of judging the work as a whole. E. Engeler ETH Zurich, April 1994 lCollected in Chapter III, An Algebraization of Algorithmics, in Algorithmic Properties of Structures, Selected Papers of Erwin Engeler, World Scientific PubJ. Co., Singapore, 1993, pp. 183-257. I Historical and Philosophical Background Erwin Engeler In the fall of 1928 a young American turned up at the Mathematical Institute of Gottingen, a mecca of mathematicians at the time; he was a young man with a dream and his name was H. B. Curry. He felt that he had the tools in hand with which to solve the problem of foundations of mathematics mice and for all. His was an approach that came to be called "formalist" and embodied that later became known as Combinatory Logic."

Der Inhalt dieses Buches entspricht weitgehend dem Stoff, den die beiden Autoren seit mehreren Jahren in einem zweisemestrigen Kurs fur Informatiker an der ETH Zurich vermitteln. Vieles davon ist bereits fruher in der Form von provisorischen Notizen von E. Engeler als "Kleines Repetitorium der Berechnungstheorie" an die Stu denten abgegeben worden. Bei der Niederschrift des nun vorliegenden Textes hat sich immer deutlicher gezeigt, dass sich eine weitgehend unabhangige Redaktion der beiden, jetzt auch im Inhaltsverzeichnis abgegrenzten Teile, sowohl arbeitstechnisch als auch von der Stoffbehandlung her, als durchaus naturlich aufdrangte. So hat denn P. Lauchli den ersten, E. Engeier den zweiten Teil selbstandig betreut. Wir haben uns zwar punkto Notation weitgehend abgesprochen, nehmen jedoch eine gewisse Verschiedenheit im Stil bewusst in Kauf. Fur die Lekture des Buches wird vorausgesetzt, dass der Leser uber das mathema tische Rustzeug verfugt, welches etwa in einem elementaren Kurs "Diskrete Mathema tik" in den unteren Semestern eines Hochschulstudiums, Richtung Informatik oder Elek trotechnik, angeboten wird. Dazu gehoren jedenfalls Grundbegriffe bezuglich Mengen, Funktionen, Relationen etc. Der erste Teil, im allgemeinen elementarer formuliert, entspricht ungefahr der oben erwahnten ersten Vorlesung ("Berechnungstheorie," 4. Semester), in welcher vor allem der Berechenbarkeitsbegriff herausgearbeitet und eine erste Bekanntschaft mit der Erzeu gung, bzw. Erkennung von formalen Sprachen anhand der ausfuhrlich diskutierten regularen Sprachen vermittelt wird. Die anschliessend eingefuhrte Fixpunkttheorie soll dem Studenten ein theoretisches Werkzeug in die Hand geben, welches ihm erlaubt, ver schiedene Gegenstande von einem einheitlichen Standpunkt aus zu betrachten."