main-content

## Über dieses Buch

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.

## Inhaltsverzeichnis

### § 1. What Are the Real Numbers?

Abstract
About one hundred years ago, Dedekind was Professor of Mathematics at the ETH in Zurich, teaching differential and integral calculus. He describes how teaching this particular subject he was confronted with the questions of the foundations of analysis. Dedekind’s little book „Was sind und was sollen die Zahlen1, which still makes enjoyable reading, reflects his ingenious approach to the problem.
Erwin Engeler

### § 2. Language as Part of Mathematics

Abstract
Modern logic owes its existence to a truly grandiose dream — one already dreamed by Leibniz. Before recounting the dream, let me describe the historical context.
Erwin Engeler

### § 3. Elementary Theory of Real Numbers

Abstract
The axiomatization presented in the previous section is an attempt to axiomatize the set of theorems true in the intended structure. How well does it do this? The best for which one can hope in an axiomatization is that it can serve as the basis for an effective decision procedure, i.e. a procedure which, given any sentence S of the language, decides in finitely many steps whether or not S is true in the intended structure. The most informative decision procedures are those which proceed by quantifier elimination. This method is also the oldest. It was applied in the twenties by Langford to the theory of dense orderings, by Presburger to the (additive) theory of the integers, and finally by Tarski to the theory that we are considering. The paper by Yu. Ershov, mentioned in the references, surveys numerous subsequent applications of the method.
Erwin Engeler

### § 4. Non-Standard Analysis

Abstract
For the first hundred and fifty years of its existence, differential and integral calculus were known as the analysis of the infinitely small. Euler’s influential textbook, for example, is entitled “Introductio in Analysin Infinitorum” (Lausanne, 1748). The infinitely small magnitudes which we encountered as “atoms of straight lines” in Cavalieri’s integration continue to play an important role. The precursors of Newton and Leibniz found a new use for vanishingly small quantities in problems of determining tangents and in finding maxima and minima. Then they were introduced systematically by Leibniz in the form of differentials. Throughout he intended that differentials should be understood as legitimate elements of the range and domain of functions, but neither he nor his successors could provide them with a solid mathematical foundation. Long into the Enlightenment, analysis (through its stormy development) lived with this somewhat makeshift and precarious notion among its basic concepts. In his witty and well-informed polemics Bishop Berkeley could accuse the intellectually arrogant scientists themselves of harboring dubious assumptions. Very much to the point, he referred to differentials as “ghosts of departed quantities”.
Erwin Engeler

### § 5. Axiom of Choice and Continuum Hypothesis

Abstract
What are the real numbers? At least the question has become somewhat clearer since it was posed in Section 1: any satisfactory answer must provide a frame of reference for mathematical activity, in particular for proving theorems in analysis. There seem to be two aspects of this activity that go hand in hand: on the one hand there is what active mathematicians call “intuition” (without, if they are wise, going into its psychological details), or “thinking in concepts”, on the other the mathematical formalism which, with the help of symbolic logic, can be refined into a precision tool.
Erwin Engeler

### § 1. Space and Mathematics

Abstract
In the question of the concept of space, even more evidently than in the question of the real numbers, the problem of the relation between mathematics and the so-called real world is posed. Newton formulated his position as follows: “Geometry is founded in practical mechanics, and indeed is no more than that part of mechanics as a whole, which originates in and is confirmed by the art of measurement.” Or Gonseth: “Geometry is the physics of arbitrary space.” The sense of geometry may therefore lie in finding a solid basis for the art of measurement (one that imposes a duty): mathematical consequences of axioms about space ought to be verifiable in actual surveying (hence comes the name of this science). Like physicists always we are then disposed to buy the ideal situation and to treat discrepancies as “incidental” and not “systematic” mistakes of measurement.
Erwin Engeler

### § 2. Axiomatization by Means of Coordinates

Abstract
Since we have imposed on Euclidean Geometry the duty of using the field R of real numbers as distance system, this is easiest to understand as a twodimensional vector space ε over ℝ. With the help of the scalar product the distance function is defined to be $$\left\| {x,y} \right\| = \sqrt {\left( {x - y} \right)\left( {x - y} \right)}$$ for arbitrary x,yε.
Erwin Engeler

### § 3. Metatheoretical Questions and Methods in Elementary Geometry

Abstract
The completeness axiom V for plane Euclidean Geometry leaves us facing the problem already considered in Chapter I: In what sense are the sets M and N named in it to be understood? In other words, how to adequately express the content of Axiom V in our formal language? And once more we choose the same solution - we identify sets with extensions of predicates, in the present case with predicates in the first order language of elementary geometry built the basic concepts introduced in § 2. The resulting completeness axiom, made elementary, is called the Tarski Schema.
Erwin Engeler

### § 4. Geometric Constructions

Abstract
The traditional description of the theory of geometric constructions starts out by listing the different so-called constructional methods: ruler, compass, dividers, parallel ruler, permitted curves and the like, and aims to set down theorems on the possibility of applying these tools and their limitations. The best known are theorems of the impossible kind (trisection of the angle, doubling of the cube, etc.) and theorems about the substitutability or removability of constructional methods (construction with the compass alone). The first apply algebraic methods (Galois theory), the second, clever geometric constructions. The description of the theory of geometric constructions in algebra texts is certainly adequate from the algebraic viewpoint, but the basic concepts must be sharpened for foundational investigations. To this end the circle of ideas from programming languages — which I may here presume — can nowadays give useful service.
Erwin Engeler

### § 1. What is an Algorithm?

Abstract
At the start of the study of algorithms stands the concept of a function, more precisely, the concept of calculable functions.
Erwin Engeler

### § 2. The Existence of Combinatory Algebras: Combinatory Logic

Abstract
If the reader has tried to manufacture a useful example of a combinatory algebra for himself, at some stage he will blame me for doing away, along with type differences with a great deal of mathematical intuition. Indeed in this connection the step from the possible to the contradictory has been made by various mathematicians. From the point of view of the founders (Schönfinkel, Curry and Church) the general aim was not just the axiomatization of the concept of application for general functions, but rather a functional foundation of all logic and mathematics. In particular Curry and Church originally proposed systems, which together with reasonable appearing ingredients for combinatory algebra, also included logical rules and parts of mathematics. These expanded systems then proved to be inconsistent (Kleene & Rosser 1935). Curry considered that this lay in the nature of the subject — he compared the axioms with Frege’s system and gave the opinion that “here we are dealing with notions of such great generality, that intuition fails us. We are researching in a no-man’s land between what is certain and what is known to be contradictory”.
Erwin Engeler

### § 3. Concrete Combinatory Algebras

Abstract
First of all I must apologize for the word “concrete”; the concreteness of the model we describe is somewhat comparable with the concreteness of the field of real numbers, as constructed by Dedekind. It is thus concreteness relative to an unreflectively borrowed substratum from naive set-theory — as concrete therefore as the objects of classical mathematics.
Erwin Engeler

### § 4. Lambda Calculus

Abstract
Let us remind ourselves once again what “combinatory algebra” means: for each term t(x 1,…, x n) there exists an element T in D A , so that for arbitrary M 1,…,M nD A we have
$$T{M_1}{M_2} \ldots {M_n} = t\left( {{M_1}, \ldots {M_n}} \right);$$
the algorithmic rule becomes a concrete object. It lies in the nature of the subject, that by applications we always pass from a term t to an object T.
Erwin Engeler

### § 5. Computability and Combinators

Abstract
In the present section we want briefly to go into the connections between combinatory algebra and logic, and recursion theory. This will serve as a demonstration that concept formation in combinatory algebra has achieved its declared aim. We started out from the idea of capturing “algorithmic rules” by objects in an algebraic structure. But this is known to be also accomplished by the notion of a partially-recursive function; this is Church’s thesis. It therefore remains to show that each partially-recursive function corresponds to a combinator, which, applied to suitable numerical objects, does the same job.
Erwin Engeler
Weitere Informationen