Paul Cohen's method of forcing, together with Saul Kripke's related semantics for modal and intuitionistic logic, has had profound effects on a number of branches of mathematical logic, from set theory and model theory to constructive and categorical logic. Here, I argue that forcing also has a place in traditional Hilbert-style proof theory, where the goal is to formalize portions of ordinary mathematics in restricted axiomatic theories, and study those theories in constructive or syntactic terms. I will discuss the aspects of forcing that are useful in this respect, and some sample applications. The latter include ways of obtaining conservation results for classical and intuitionistic theories, interpreting classical theories in constructive ones, and constructivizing model-theoretic arguments.

Abstract. Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature ∣K∣ ≤ 1. Let Met(M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met(M) such as the diameter. They showed that for every Turing machine Te, e ϵ ω, there is a sequence (uniformly effective in e) of homology n-spheres which are also hypersurfaces, such that is diffeomorphic to the standard n-sphere Sn (denoted )iff Te halts on input k, and in this case the connected sum , so , and is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time ae σe(k)of Te on inputs y < k.

At their request Soare constructed a particular infinite sequence {Ai}ϵω of c.e. sets so that for all i the settling time of the associated Turing machine for Ai dominates that for Ai+1, even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a “fractal” like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as “the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization.” From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {Ai}iϵω above, not merely Gödel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T5 (see §9.5).

Frege Arithmetic (FA) is the second-order theory whose sole non-logical axiom is Hume's Principle, which says that the number of Fs is identical to the number of Gs if and only if the Fs and the Gs can be one-to-one correlated. According to Frege's Theorem, FA and some natural definitions imply all of second-order Peano Arithmetic. This paper distinguishes two dimensions of impredicativity involved in FA—one having to do with Hume's Principle, the other, with the underlying second-order logic—and investigates how much of Frege's Theorem goes through in various partially predicative fragments of FA. Theorem 1 shows that almost everything goes through, the most important exception being the axiom that every natural number has a successor. Theorem 2 shows that the Successor Axiom cannot be proved in the theories that are predicative in either dimension.

§1. Introduction. Asymptotic cones of metric spaces were first invented by Gromov. They are metric spaces which capture the ‘large-scale structure’ of the underlying metric space. Later, van den Dries and Wilkie gave a more general construction of asymptotic cones using ultrapowers. Certain facts about asymptotic cones, like the completeness of the metric space, now follow rather easily from saturation properties of ultrapowers, and in this survey, we want to present two applications of the van den Dries-Wilkie approach. Using ultrapowers we obtain an explicit description of the asymptotic cone of a semisimple Lie group. From this description, using semi-algebraic groups and non-standard methods, we can give a short proof of the Margulis Conjecture. In a second application, we use set theory to answer a question of Gromov.

§2. Definitions. The intuitive idea behind Gromov's concept of an asymptotic cone was to look at a given metric space from an ‘infinite distance’, so that large-scale patterns should become visible. In his original definition this was done by gradually scaling down the metric by factors 1/n for n ϵ ℕ. In the approach by van den Dries and Wilkie, this idea was captured by ultrapowers. Their construction is more general in the sense that the asymptotic cone exists for any metric space, whereas in Gromov's original definition, the asymptotic cone existed only for a rather restricted class of spaces.

Ernst Friedrich Ferdinand Zermelo (1871–1953) transformed the set theory of Cantor and Dedekind in the first decade of the 20th century by incorporating the Axiom of Choice and providing a simple and workable axiomatization setting out generative set-existence principles. Zermelo thereby tempered the ontological thrust of early set theory, initiated the delineation of what is to be regarded as set-theoretic, drawing out the combinatorial aspects from the logical, and established the basic conceptual framework for the development of modern set theory. Two decades later Zermelo promoted a distinctive cumulative hierarchy view of models of set theory and championed the use of infinitary logic, anticipating broad modern developments. In this paper Zermelo's published mathematical work in set theory is described and analyzed in its historical context, with the hindsight afforded by the awareness of what has endured in the subsequent development of set theory. Elaborating formulations and results are provided, and special emphasis is placed on the to and fro surrounding the Schröder-Bernstein Theorem and the correspondence and comparative approaches of Zermelo and Gödel. Much can be and has been written about philosophical and biographical issues and about the reception of the Axiom of Choice, and we will refer and defer to others, staying the course through the decidedly mathematical themes and details.

§0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46] (see also the papers [47], [48]), and that of Platek [58], at Stanford, on admissible sets.

Barwise's work on infinitary logic and admissible sets is described in his thesis [4], the book [13], and papers [5]—[16]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise's ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.

Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.

§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structureM, we mean a universe set M with an interpretation for each symbol of L.

This paper ties together much of the model theory of the last 50 years. Shelah's attempts to generalize the Morley theorem beyond first order logic led to the notion of excellence, which is a key to the structure theory of uncountable models. The notion of Abstract Elementary Class arose naturally in attempting to prove the categoricity theorem for Lω1,ω(Q). More recently, Zilber has attempted to identify canonical mathematical structures as those whose theory (in an appropriate logic) is categorical in all powers. Zilber's trichotomy conjecture for first order categorical structures was refuted by Hrushovski, by the introducion of a special kind of Abstract Elementary Class. Zilber uses a powerful and essentailly infinitary variant on these techniques to investigate complex exponentiation. This not only demonstrates the relevance of Shelah's model theoretic investigations to mainstream mathematics but produces new results and conjectures in algebraic geometry.

We show that there exist 2ℵ0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of Thomason). The constructions use the result of Erdos that there are finite graphs with arbitrarily large chromatic number and girth.

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that initiated by Turing in his “ordinal logics” (see Gandy and Yates [2001]) and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach.

§1. Introduction. After the pioneering work of Mostowski [29] and Lindström [23] it was Jon Barwise's papers [2] and [3] that brought abstract model theory and generalized quantifiers to the attention of logicians in the early seventies. These papers were greeted with enthusiasm at the prospect that model theory could be developed by introducing a multitude of extensions of first order logic, and by proving abstract results about relationships holding between properties of these logics. Examples of such properties are

κ-compactness. Any set of sentences of cardinality ≤ κ, every finite subset of which has a model, has itself a model. Löwenheim-Skolem Theorem down to κ. If a sentence of the logic has a model, it has a model of cardinality at most κ. Interpolation Property. If ϕ and ψ are sentences such that ⊨ ϕ → Ψ, then there is θ such that ⊨ ϕ → θ, ⊨ θ → Ψ and the vocabulary of θ is the intersection of the vocabularies of ϕ and Ψ.

Lindstrom's famous theorem characterized first order logic as the maximal ℵ0-compact logic with Downward Löwenheim-Skolem Theorem down to ℵ0. With his new concept of absolute logics Barwise was able to get similar characterizations of infinitary languages Lκω. But hopes were quickly frustrated by difficulties arising left and right, and other areas of model theory came into focus, mainly stability theory. No new characterizations of logics comparable to the early characterization of first order logic given by Lindström and of infinitary logic by Barwise emerged. What was first called soft model theory turned out to be as hard as hard model theory.

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive program

where rem(a, b) is the remainder in the division of a by b, the unique natural number r such that for some natural number q,

It is an algorithm from (relative to) the remainder function rem, meaning that in computing its time complexity function cε (a, b), we assume that the values rem(x, y) are provided on demand by some “oracle” in one “time unit”. It is easy to prove that

Much more is known about cε(a, b), but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's (worst case) optimality among its peers—algorithms from rem:

Conjecture. If an algorithm α computes gcd (x,y) from rem with time complexity cα (x,y), then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα (a,b) > r log2a.

For most of the 1980s, Jon Barwise focused much of his research in the area of natural language semantics. This article surveys his research publications in that area.

Most, but not all, of those publications were in the area of situation semantics, a new approach to natural language semantics Barwise developed jointly with his colleague John Perry in the first half of the 1980s. That work was both blessed, and cursed, by becoming closely identified in academic circles with the award of a $23 million gift to Stanford from the System Development Foundation for the establishment in 1983 of its Center for the Study of Language and Information (CSLI). The development of situation semantics, and in due course its underlying mathematical foundation Situation Theory, carried out for the most part within the framework of CSLI's STASS research group (Situation Theory and Situation Semantics), was actually a relatively small part of the overall research program at CSLI. But because Barwise and Perry were leading figures at CSLI, were centrally involved in securing the SDF gift, and were respectively the first and second directors of CSLI, a general impression sprung up that the two of them had been awarded millions of dollars to develop situation semantics.

A major consequence of this false impression was that from the theory's early days, a great deal of interest was shown in the project. With so many accomplished scholars pouring over the work while the ink was still wet on the manuscript pages, Barwise and Perry were able to take advantage of a broad range of helpful criticism (even if it was not always given with a view to being helpful). This meant that they were able to develop the new theory much more rapidly than would otherwise have been the case.

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.