Foundations and Applications depend ultimately for their existence on each other. The main links between them are education and the axiomatic method. Those links can be strengthened with the help of a categorical method which was concentrated forty years ago by Cartier, Grothendieck, Isbell, Kan, and Yoneda. I extended that method to extract some essential features of the category of categories in 1965, and I apply it here in section 3 to sketch a similar foundation within the smooth categories which provide the setting for the mathematics of change. The possibility that other methods may be needed to clarify a contradiction introduced by Cantor, now embedded in mathematical practice, is discussed in section 5.

We discuss the work of Paul Cohen in set theory and its influence, especially the background, discovery, development of forcing.

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

Convinced that the classically undecidable problems of mathematics possess determinate truth values, Gödel issued a programmatic call to search for new axioms for their solution. The platonism underlying his belief in the determinateness of those questions in combination with his conception of intuition as a kind of perception have struck many of his readers as highly problematic. Following Gödel's own suggestion, this article explores ideas from phenomenology to specify a meaning for his mathematical realism that allows for a defensible epistemology.

Two young logicians, whose work had a dramatic impact on the direction of logic, exchanged two letters in early 1931. Jacques Herbrand initiated the correspondence on 7 April and Kurt Gödel responded on 25 July, just two days before Herbrand died in a mountaineering accident at La Bérarde (Isère). Herbrand's letter played a significant role in the development of computability theory. Gödel asserted in his 1934 Princeton Lectures and on later occasions that it suggested to him a crucial part of the definition of a general recursive function. Understanding this role in detail is of great interest as the notion is absolutely central. The full text of the letter had not been available until recently, and its content (as reported by Gödel) was not in accord with Herbrand's contemporaneous published work. Together, the letters reflect broader intellectual currents of the time: they are intimately linked to the discussion of the incompleteness theorems and their potential impact on Hilbert's Program.

Schemata have played important roles in logic since Aristotle's Prior Analytics. The syllogistic figures and moods can be taken to be argument schemata as can the rules of the Stoic propositional logic. Sentence schemata have been used in axiomatizations of logic only since the landmark 1927 von Neumann paper [31]. Modern philosophers know the role of schemata in explications of the semantic conception of truth through Tarski's 1933 Convention T [42]. Mathematical logicians recognize the role of schemata in first-order number theory where Peano's second-order Induction Axiom is approximated by Herbrand's Induction-Axiom Schema [23]. Similarly, in first-order set theory, Zermelo's second-order Separation Axiom is approximated by Fraenkel's first-order Separation Schema [17]. In some of several closely related senses, a schema is a complex system having multiple components one of which is a template-text or scheme-template, a syntactic string composed of one or more “blanks” and also possibly significant words and/or symbols. In accordance with a side condition the template-text of a schema is used as a “template” to specify a multitude, often infinite, of linguistic expressions such as phrases, sentences, or argument-texts, called instances of the schema. The side condition is a second component. The collection of instances may but need not be regarded as a third component. The instances are almost always considered to come from a previously identified language (whether formal or natural), which is often considered to be another component. This article reviews the often-conflicting uses of the expressions ‘schema’ and ‘scheme’ in the literature of logic. It discusses the different definitions presupposed by those uses. And it examines the ontological and epistemic presuppositions circumvented or mooted by the use of schemata, as well as the ontological and epistemic presuppositions engendered by their use. In short, this paper is an introduction to the history and philosophy of schemata.

People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.

In [12], Ernst Zermelo described a succession of models for the axioms of set theory as initial segments of a cumulative hierarchy of levels UαVα. The recursive definition of the Vα's is:

Thus, a little reflection on the axioms of Zermelo-Fraenkel set theory (ZF) shows that Vω, the first transfinite level of the hierarchy, is a model of all the axioms of ZF with the exception of the axiom of infinity. And, in general, one finds that if κ is a strongly inaccessible ordinal, then Vκ is a model of all of the axioms of ZF. (For all these models, we take ∈ to be the standard element-set relation restricted to the members of the domain.) Doubtless, when cast as a first-order theory, ZF does not characterize the structures 〈Vκ,∈∩(Vκ×Vκ)〉 for κ a strongly inaccessible ordinal, by the Löwenheim-Skolem theorem. Still, one of the main achievements of [12] consisted in establishing that a characterization of these models can be attained when one ventures into second-order logic. For let second-order ZF be, as usual, the theory that results from ZF when the axiom schema of replacement is replaced by its second-order universal closure. Then, it is a remarkable result due to Zermelo that second-order ZF can only be satisfied in models of the form 〈Vκ,∈∩(Vκ×Vκ)〉 for κ a strongly inaccessible ordinal.

Model theory is concerned mainly, although not exclusively, with infinite structures. In recent years, finite structures have risen to greater prominence, both within the context of mainstream model theory, e.g., in work of Lachlan, Cherlin, Hrushovski, and others, and with the advent of finite model theory, which incorporates elements of classical model theory, combinatorics, and complexity theory. The purpose of this survey is to provide an overview of what might be called the model theory of finite structures. Some topics in finite model theory have strong connections to theoretical computer science, especially descriptive complexity theory (see [26, 46]). In fact, it has been suggested that finite model theory really is, or should be, logic for computer science. These connections with computer science will, however, not be treated here.

It is well-known that many classical results of ‘infinite model theory’ fail over the class of finite structures, including the compactness and completeness theorems, as well as many preservation and interpolation theorems (see [35, 26]). The failure of compactness in the finite, in particular, means that the standard proofs of many theorems are no longer valid in this context. At present, there is no known example of a classical theorem that remains true over finite structures, yet must be proved by substantially different methods. It is generally concluded that first-order logic is ‘badly behaved’ over finite structures.

From the perspective of expressive power, first-order logic also behaves badly: it is both too weak and too strong. Too weak because many natural properties, such as the size of a structure being even or a graph being connected, cannot be defined by a single sentence. Too strong, because every class of finite structures with a finite signature can be defined by an infinite set of sentences. Even worse, every finite structure is defined up to isomorphism by a single sentence. In fact, it is perhaps because of this last point more than anything else that model theorists have not been very interested in finite structures. Modern model theory is concerned largely with complete first-order theories, which are completely trivial here.

Ludics [1] is a novel approach to logic—especially proof-theory. The present introduction emphasises foundational issues.

For ages, not a single disturbing idea in the area of “foundations”: the discussion is sort of ossified—as if everything had been said, as if all notions had taken their definite place, in a big cemetery of ideas. One can still refresh the flowers or regild the stone, e.g., prove technicalities, sometimes non-trivial; but the real debate is still: this paper begins with an autopsy, the autopsy of the foundational project.

Up to say 1900, the realist/dualist approach to science was dominant; during the last century some domains like physics evolved so as to become completely anti-realist; but this evolution hardly concerned logic.

By the turn of the XXth century mathematics was jeopardised by paradoxes, the most famous of them being due to Russell. Hilbert's reaction was to focus on consistency. But the reduction of paradoxes—and therefore of foundations—to solely the antinomies is highly questionable: indeed, the typical paradoxical artifacts are secret sharers, objects satisfying the formal definitions but far astray from the intended meaning, typically the Peano “curve” which contradicts our perception of dimension. Fortunately, topology has been able to show that dimension m is not the same as dimension n … but just for a second, forget this and imagine consistent mathematics in which balls in any dimension are homeomorphic: what a disaster! This exclusive focus on consistency—not to speak of the strategic failure of the Programme—should explain why logic, especially foundations lost contact with other sciences during last century.

Kurt Gödel is almost as famous—one might say “notorious”—for his extreme platonist views as he is famous for his mathematical theorems. Moreover his platonism is not a myth; it is well-documented in his writings. Here are two platonist declarations about set theory, the first from his paper about Bertrand Russell and the second from the revised version of his paper on the Continuum Hypotheses.

Classes and concepts may, however, also be conceived as real objects, namely classes as “pluralities of things” or as structures consisting of a plurality of things and concepts as the properties and relations of things existing independently of our definitions and constructions.
It seems to me that the assumption of such objects is quite as legitimate as the assumption of physical bodies and there is quite as much reason to believe in their existence.
But, despite their remoteness from sense experience, we do have something like a perception also of the objects of set theory, as is seen from the fact that the axioms force themselves upon us as being true. I don't see any reason why we should have less confidence in this kind of perception, i.e., in mathematical intuition, than in sense perception.

The first statement is a platonist declaration of a fairly standard sort concerning set theory. What is unusual in it is the inclusion of concepts among the objects of mathematics. This I will explain below. The second statement expresses what looks like a rather wild thesis.

The history of modern logic is usually written as the history of mathematical or, more general, symbolic logic. As such it was created by mathematicians. Not regarding its anticipations in Scholastic logic and in the rationalistic era, its continuous development began with George Boole's The Mathematical Analysis of Logic of 1847, and it became a mathematical subdiscipline in the early 20th century. This style of presentation cuts off one eminent line of development, the philosophical development of logic, although logic is evidently one of the basic disciplines of philosophy. One needs only to recall some of the standard 19th century definitions of logic as, e.g., the art and science of reasoning (Whateley) or as giving the normative rules of correct reasoning (Herbart).

In the paper the relationship between the philosophical and the mathematical development of logic will be discussed. Answers to the following questions will be provided:

1. What were the reasons for the philosophers' lack of interest in formal logic?

2. What were the reasons for the mathematicians' interest in logic?

3. What did “logic reform” mean in the 19th century? Were the systems of mathematical logic initially regarded as contributions to a reform of logic?

4. Was mathematical logic regarded as art, as science or as both?

The last section of “Lecture at Zilsel's” [9, §4] contains an interesting but quite condensed discussion of Gentzen's first version of his consistency proof for PA [8], reformulating it as what has come to be called the no-counterexample interpretation. I will describe Gentzen's result (in game-theoretic terms), fill in the details (with some corrections) of Gödel's reformulation, and discuss the relation between the two proofs.

§1. Introduction. A linear ordering (also known as total ordering) embeds into another linear ordering if it is isomorphic to a subset of it. Two linear orderings are said to be equimorphic if they can be embedded in each other. This is an equivalence relation, and we call the equivalence classes equimorphism types. We analyze the structure of equimorphism types of linear orderings, which is partially ordered by the embeddability relation. Our analysis is mainly fromthe viewpoints of Computability Theory and Reverse Mathematics. But we also obtain results, as the definition of equimorphism invariants for linear orderings, which provide a better understanding of the shape of this structure in general.

This study of linear orderings started by analyzing the proof-theoretic strength of a theorem due to Jullien [Jul69]. As is often the case in Reverse Mathematics, to solve this problem it was necessary to develop a deeper understanding of the objects involved. This led to a variety of results on the structure of linear orderings and the embeddability relation on them. These results can be divided into three groups.

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic.

Kurt Gödel (1906–1978) with his work on the constructible universe L established the relative consistency of the Axiom of Choice (AC) and the Continuum Hypothesis (CH). More broadly, he ensured the ascendancy of first-order logic as the framework and a matter of method for set theory and secured the cumulative hierarchy view of the universe of sets. Gödel thereby transformed set theory and launched it with structured subject matter and specific methods of proof. In later years Gödel worked on a variety of set theoretic constructions and speculated about how problems might be settled with new axioms. We here chronicle this development from the point of view of the evolution of set theory as a field of mathematics. Much has been written, of course, about Gödel's work in set theory, from textbook expositions to the introductory notes to his collected papers. The present account presents an integrated view of the historical and mathematical development as supported by his recently published lectures and correspondence. Beyond the surface of things we delve deeper into the mathematics. What emerges are the roots and anticipations in work of Russell and Hilbert, and most prominently the sustained motif of truth as formalizable in the “next higher system”. We especially work at bringing out how transforming Gödel's work was for set theory. It is difficult now to see what conceptual and technical distance Gödel had to cover and how dramatic his re-orientation of set theory was.

Lyndon's Interpolation Theorem asserts that for any valid implication between two purely relational sentences of first-order logic, there is an interpolant in which each relation symbol appears positively (negatively) only if it appears positively (negatively) in both the antecedent and the succedent of the given implication. We prove a similar, more general interpolation result with the additional requirement that, for some fixed tuple of unary predicates U, all formulae under consideration have all quantifiers explicitly relativised to one of the U. Under this stipulation, existential (universal) quantification over U contributes a positive (negative) occurrence of U.

It is shown how this single new interpolation theorem, obtained by a canonical and rather elementary model theoretic proof, unifies a number of related results: the classical characterisation theorems concerning extensions (substructures) with those concerning monotonicity, as well as a many-sorted interpolation theorem focusing on positive vs. negative occurrences of predicates and on existentially vs. universally quantified sorts.

§ 1. Introduction. In this communication we present some recent results on the classification of Polish metric spaces up to isometry and on the isometry groups of Polish metric spaces. A Polish metric space is a complete separable metric space (X, d).

Our first goal is to determine the exact complexity of the classification problem of general Polish metric spaces up to isometry. This work was motivated by a paper of Vershik [1998], where he remarks (in the beginning of Section 2): “The classification of Polish spaces up to isometry is an enormous task. More precisely, this classification is not ‘smooth’ in the modern terminology.” Our Theorem 2.1 below quantifies precisely the enormity of this task.

After doing this, we turn to special classes of Polish metric spaces and investigate the classification problems associated with them. Note that these classification problems are in principle no more complicated than the general one above. However, the determination of their exact complexity is not necessarily easier.

The investigation of the classification problems naturally leads to some interesting results on the groups of isometries of Polish metric spaces. We shall also present these results below.

The rest of this section is devoted to an introduction of some basic ideas of a theory of complexity for classification problems, which will help to put our results in perspective. Detailed expositions of this general theory can be found, e.g., in Hjorth [2000], Kechris [1999], [2001].

§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).

Let me start by saying that I had the privilege of witnessing the birth of Jon Barwise's new research on heterogeneous logic and its subsequent developments. I entered the Stanford philosophy graduate program in the Fall of 1987, became Barwise and Etchemendy's first research assistant on the project of diagrammatic/heterogeneous reasoning during summer of 1989, and under their guidance completed my thesis, “Valid reasoning and visual representation,” in August, 1991. With this experience I would like to focus on the more personal and informal aspects of Jon's research on heterogeneous logic which may not be conveyed by his articles. (Accordingly, I have written this paper without footnotes or other references except to Jon's work.) The present article can only hint at the depth and the influence of Jon's work in this area.

In the first section, I single out an important feature of the project on heterogeneous logic Jon founded together with John Etchemendy about 15 years ago. I title it “resolving conflicts” since the research, I strongly believe, grew out of Jon's personal attitude toward how to resolve a tension between opposite extremes.

The second section focuses on how teaching logic itself was shaped as part of Barwise and Etchemendy's research agenda. It is worthwhile noting that their textbook Language, Proof, and Logic constitutes part of their research and, hence, the success of the book vindicates the goal of the overall project.