We develop a constructive version of nonstandard analysis, extending Bishop's constructive analysis with infinitesimal methods. A full transfer principle and a strong idealisation principle are obtained by using a sheaf-theoretic construction due to I. Moerdijk. The construction is, in a precise sense, a reduced power with variable filter structure. We avoid the nonconstructive standard part map by the use of nonstandard hulls. This leads to an infinitesimal analysis which includes nonconstructive theorems such as the Heine–Borel theorem, the Cauchy–Peano existence theorem for ordinary differential equations and the exact intermediate-value theorem, while it at the same time provides constructive results for concrete statements. A nonstandard measure theory which is considerably simpler than that of Bishop and Cheng is developed within this context.

§1. Introduction. I dedicate this essay to the two-dozen-odd people whose refutations of Cantor's diagonal argument (I mean the one proving that the set of real numbers and the set of natural numbers have different cardinalities) have come to me either as referee or as editor in the last twenty years or so. Sadly these submissions were all quite unpublishable; I sent them back with what I hope were helpful comments. A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument—what had it done to make them angry with it? So I started to keep notes of these papers, in the hope that some pattern would emerge.

These pages report the results. They might be useful for editors faced with similar problem papers, or even for the authors of the papers themselves. But the main message to reach me is that there are several points of basic elementary logic that we usually teach and explain very badly, or not at all.

In 1995 an engineer named William Dilworth, who had published a refutation of Cantor's argument in the Transactions of the Wisconsin Academy of Sciences, Arts and Letters, sued for libel a mathematician named Underwood Dudley who had called him a crank ([9] pp. 44f, 354).

§0. Alonzo Church's contributions to philosophy and to that most philosophical part of logic, intensional logic, are impressive indeed. He wrote relatively few papers actually devoted to specifically philosophical issues, as distinguished from related technical work in logic. Many of his contributions appear in reviews for The Journal of Symbolic Logic, and it can hardly be maintained that one finds there a “philosophical system”. But there occur a clearly articulated and powerful methodology, terse arguments, often of “crushing cogency”, and philosophical observations of the first importance.

Many of the less formal philosophical contributions center around questions concerning meaning, but there are important clarifications and insights into matters of the epistemology and ontology of the sciences, especially the formal sciences.

1.1. The logistic method. Church's writings on philosophical matters exhibit an unwavering commitment to what he called the “logistic method”. The term did not catch on and now one would just speak of “formalization”. The use of these ideas is now so common and familiar among logicians and logically-oriented philosophers that they are simply taken for granted. But they deserve to be celebrated and re-emphasized, for there are (still) philosophers who seriously underestimate and even consciously reject these techniques.

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.

For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k (free or bound) variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and extensions by so-called counting quantifiers.

Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time (PTIME) or polynomial space (PSPACE) can be characterized as collections of all classes of (ordered) finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth.

§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?

A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of forging connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.

I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine, M, and claims that the output of M consists of all and only the arithmetic truths that a human (like Lucas), or the totality of human mathematicians, will ever or can ever know. We assume that the output of M is consistent.

§1. Introduction. In this report we wish to describe recent work on a class of first order theories first introduced by Shelah in [32], the simple theories. Major progress was made in the first author's doctoral thesis [17]. We will give a survey of this, as well as further works by the authors and others.

The class of simple theories includes stable theories, but also many more, such as the theory of the random graph. Moreover, many of the theories of particular algebraic structures which have been studied recently (pseudofinite fields, algebraically closed fields with a generic automorphism, smoothly approximable structures) turn out to be simple. The interest is basically that a large amount of the machinery of stability theory, invented by Shelah, is valid in the broader class of simple theories. Stable theories will be defined formally in the next section. An exhaustive study of them is carried out in [33]. Without trying to read Shelah's mind, we feel comfortable in saying that the importance of stability for Shelah lay partly in the fact that an unstable theory T has 2λ many models in any cardinal λ ≥ ω1 + |T| (proved by Shelah). (Note that for λ ≥ |T| 2λ is the maximum possible number of models of cardinality λ.)

The journal of symbolic logic began publishing in 1936. From the outset, the Journal included a Reviews Section, edited by Alonzo Church. The very first issue carried three pages of reviews, written by Bernays, Church, Rosser, and Quine.

As the first issue stated, “It is intended that this section of the Journal shall serve as a complete bibliography of current literature in the field of symbolic logic, from January 1, 1936. To this end an effort will be made to include in it, at least by title, all publications in this field, both books and articles in journals, and as far as possible these will be accompanied by signed reviews.” Thus the purpose of the Reviews Section was two-fold. For one, there was its bibliographical function: to provide a complete, suitably indexed, listing of all the publications—both books and journal articles—in symbolic logic, wherever and in whatever language published. And secondly, the reviews were to provide critical, analytical commentary on these publications, whenever possible.

The Reviews Section should be viewed as a continuation and expansion of Church's A bibliography of symbolic logic. The Bibliography was a listing, with some annotations, of the publications in symbolic logic prior to 1936. It was published as volume 1, number 4 of the Journal. Church made the listing as complete as he could, of course.

§1. Introduction. The problem raised by the liar paradox has long been an intriguing challenge for all those interested in the concept of truth. Many “solutions” have been proposed to solve or avoid the paradox, either prescribing some linguistical restriction, or giving up the classical true-false bivalence or assuming some kind of contextual dependence of truth, among other possibilities. We shall not discuss these different approaches to the subject in this paper, but we shall concentrate on a kind of formal construction which was originated by Kripke's paper “Outline of a theory of truth” [11] and which, in different forms, reappears in later papers by various authors.

The main idea can be presented as follows: assume a first order language ℒ containing, among other unspecified symbols, a predicate symbol T intended to represent the truth predicate for ℒ. Assume, also, a fixed model M = 〈D, I〉 (the base model)where D contains all sentences of ℒ and I interprets all non-logical symbols of ℒ except T in the usual way. In general, D might contain many objects other than sentences of ℒ but as that would raise the problem of the meaning of sentences in which T is applied to one of these objects, we shall assume that this is not the case.

§1. The mission of axiomatic set theory. What is set theory needed for in the foundations of mathematics? Why cannot we transact whatever foundational business we have to transact in terms of our ordinary logic without resorting to set theory? There are many possible answers, but most of them are likely to be variations of the same theme. The core area of ordinary logic is by a fairly common consent the received first-order logic. Why cannot it take care of itself? What is it that it cannot do? A large part of every answer is probably that first-order logic cannot handle its own model theory and other metatheory. For instance, a first-order language does not allow the codification of the most important semantical concept, viz. the notion of truth, for that language in that language itself, as shown already in Tarski (1935). In view of such negative results it is generally thought that one of the most important missions of set theory is to provide the wherewithal for a model theory of logic. For instance Gregory H. Moore (1994, p. 635) asserts in his encyclopedia article “Logic and set theory” that

Set theory influenced logic, both through its semantics, by expanding the possible models of various theories and by the formal definition of a model; and through its syntax, by allowing for logical languages in which formulas can be infinite in length or in which the number of symbols is uncountable.

The purpose of this communication is to survey a theory of liftings, as developed in author's thesis ([8]). The first result in this area was Shelah's construction of a model of set theory in which every automorphism of P(ℕ)/ Fin, where Fin is the ideal of finite sets, is trivial, or inother words, it is induced by a function mapping integers into integers ([33]). (It is a classical result of W. Rudin [31] that under the Continuum Hypothesis there are automorphisms other than trivial ones.) Soon afterwards, Velickovic ([47]), was able to extract from Shelah's argument the fact that every automorphism of P(ℕ)/ Fin with a Baire-measurable lifting has to be trivial. This, for instance, implies that in Solovay's model ([36]) all automorphisms are trivial. Later on, an axiomatic approach was adopted and Shelah's conclusion was drawn first from the Proper Forcing Axiom (PFA) ([34]) and then from the milder Open Coloring Axiom (OCA) and Martin's Axiom (MA) ([48], see §5 for definitions). Both shifts from the quotient P(ℕ)/ Fin to quotients over more general ideals P(ℕ)/I and from automorphisms to arbitrary ho-momorphisms were made by Just in a series of papers ([14]-[17]), motivated by some problems in algebra ([7, pp. 38–39], [43, I.12.11], [45, Q48]) and topology ([46, p. 537]).

A way is found to add axioms to sequent calculi that maintains the eliminability of cut, through the representation of axioms as rules of inference of a suitable form. By this method, the structural analysis of proofs is extended from pure logic to free-variable theories, covering all classical theories, and a wide class of constructive theories. All results are proved for systems in which also the rules of weakening and contraction can be eliminated. Applications include a system of predicate logic with equality in which also cuts on the equality axioms are eliminated.

In a lecture manuscript written around 1961 (Gödel *1961/?), Gödel describes a philosophical path from the incompleteness theorems to Husserl's phenomenology. It is known that Gödel began to study Husserl's work in 1959 and that he continued to do so for many years. During the 1960s, for example, he recommended the sixth investigation of Husserl's Logical Investigations to several logicians for its treatment of categorial intuition (Wang 1997, p. 164). While Gödel may not have been satisfied with what he was able to obtain from philosophy and Husserl's phenomenology, he nonetheless continued to recommend Husserl's work to logicians as late as the 1970s. In this paper I present and discuss the kinds of arguments that led Gödel to the work of Husserl. Among other things, this should help to shed additional light on Gödel's philosophical and scientific ideas and to show to what extent these ideas can be viewed as part of a unified philosophical outlook. Some of the arguments that led Gödel to Husserl's work are only hinted at in Gödel's 1961 paper, but they are developed in much more detail in Gödel's earlier philosophical papers (see especially 1934, *193?, 1944, 1947, *1951, *1953/59). In particular, I focus on arguments concerning Hilbert's program and an early version of Carnap's program.

§1. Some ideas from phenomenology. Since Husserl's work is not generally known to mathematical logicians, it may be helpful to mention briefly a few details about his background.

We show that if there is a nonconstructible real, then every perfect set has a nonconstructible element, answering a question of K. Prikry. This is a specific instance of a more general theorem giving a sufficient condition on a pair M ⊂ N of models of set theory implying that every perfect set in N has an element in N which is not in M.