At the 1993 Annual meeting of the Association for Symbolic Logic, the Council of the association voted to establish a new journal to be called The Bulletin of Symbolic Logic. The intended goal of the Council was to produce a journal that would be both accessible and of interest to as wide an audience as possible, with the stated purpose of keeping the logic community abreast of important developments in all parts of our discipline. The first issue was to appear in March of 1995 and you now have it in your hands.

In accordance with the Council resolution, we intend to publish primarily two types of papers. The first section of The Bulletin, Articles, will usually be devoted to works of an expository or survey nature. These papers will generally present topics of broad interest in a way that should be accessible to a large majority of the members of the Association. Topics will be drawn from all areas of logic including mathematical or philosophical logic, logic in computer science or linguistics, the history or philosophy of logic, logic education and applications of logic to other fields. One view of a role that this section of The Bulletin will play is as an ongoing handbook of logic.

In this paper, we sketch the development of two important themes of modern set theory, both of which can be regarded as growing out of work of Kurt Gödel. We begin with a review of some basic concepts and conventions of set theory.

§0. The ordinal numbers were Georg Cantor's deepest contribution to mathematics. After the natural numbers 0, 1, …, n, … comes the first infinite ordinal number ω, followed by ω + 1, ω + 2, …, ω + ω, … and so forth. ω is the first limit ordinal as it is neither 0 nor a successor ordinal. We follow the von Neumann convention, according to which each ordinal number α is identified with the set {ν ∣ ν α} of its predecessors. The ∈ relation on ordinals thus coincides with <. We have 0 = ∅ and α + 1 = α ∪ {α}. According to the usual set-theoretic conventions, ω is identified with the first infinite cardinal ℵ0, similarly for the first uncountable ordinal number ω1 and the first uncountable cardinal number ℵ1, etc. We thus arrive at the following picture:

The von Neumann hierarchy divides the class V of all sets into a hierarchy of sets Vα indexed by the ordinal numbers. The recursive definition reads: (where } is the power set of x);

Vλ = ∪v<λVv for limit ordinals λ. We can represent this hierarchy by the following picture.

In 1934 Alonzo Church, Kurt Gödei, S. C. Kleene, and J. B. Rosser were all to be found in Princeton, New Jersey. In 1936 Church founded The Journal of Symbolic Logic. Shortly thereafter Alan Turing arrived for a two year visit. The United States had become a world center for cutting-edge research in mathematical logic. In this brief survey1 we shall examine some of the writings of American logicians during the 1920s, a period of important beginnings and remarkable insights as well as of confused gropings.

The publication of Whitehead and Russell's monumental Principia Mathematica [18] during the years 1910-1913 provided the basis for much of the research that was to follow. It also provided the basis for confusion that remained a factor during the period we are discussing. In 1908, Henri Poincaré, a famous skeptic where mathematical logic was concerned, wrote pointedly ([13]):

It is difficult to admit that the word if acquires, when written ⊃, a virtue it did not possess when written if.

Principia provided no very convincing answer to Poincaré. Indeed the fact that the authors of Principia saw fit to place their first two “primitive propositions”

*1.1: Anything implied by a true proposition is true.

*1.2: ⊢ p ⋁ p ⊃ p

under one and the same heading suggest that they had thought of what they were doing as just such a translation as Poincare had derided.

Dedicated to Dana Scott on his sixtieth birthday.

It is common knowledge that for a short while Hermann Weyl joined Brouwer in his pursuit of a revision of mathematics according to intuitionistic principles. There is, however, little in the literature that sheds light on Weyl's role and in particular on Brouwer's reaction to Weyl's allegiance to the cause of intuitionism. This short episode certainly raises a number of questions: what made Weyl give up his own program, spelled out in “Das Kontinuum”, how did Weyl come to be so well-informed about Brouwer's new intuitionism, in what respect did Weyl's intuitionism differ from Brouwer's intuitionism, what did Brouwer think of Weyl's views,…? To some of these questions at least partial answers can be put forward on the basis of some of the available correspondence and notes. The present paper will concentrate mostly on the historical issues of the intuitionistic episode in Weyl's career.

Weyl entered the foundational controversy with a bang in 1920 with his sensational paper “On the new foundational crisis in mathematics”. He had already made a name for himself in the foundations of mathematics in 1918 with his monograph “The Continuum” [18]; this contained in addition to a technical logical-mathematical construction of the continuum, a fairly extensive discussion of the shortcomings of the traditional construction of the continuum on the basis of arbitrary—and hence also impredicative—Dedekind cuts.

It was questions about points on the real line that initiated the study of set theory. Points paved the way to point sets and these to ever more abstract sets. And there was more: Reflection on structural properties of point sets not only initiated the study of ordinary sets; it also supplied blueprints for defining extra-ordinary, “large” sets, transcending those provided by standard set theory. In return, the existence of such large sets turned out critical to settling open conjectures about point sets.

How to explain such action at a distance between the very large and the rather small? Rather than having an air of magic, could these results rest on deep structural similarities between the two superficially distant species of sets?

In this essay I dissect one group of such two-way results. Their linchpin is the notion of measure.

§1. Vitali's impossibility result. Our starting point is a problem in measure theory regarding the notion of “Lebesgue measure.” Before presenting the problem, I would like to review the notion of Lebesgue measure. Rather than listing its main properties, I would like to show how Lebesgue measure is born out of an attempt to generalize the notion of the length of an interval to arbitrary sets of reals. One tries to approximate arbitrary sets of reals by intervals, in the hope that the lengths of the intervals will induce a measure on these sets.

§1. Introduction. Among the most remarkable discoveries in set theory in the last quarter century is the rich structure of the arithmetic of singular cardinals, and its deep relationship to large cardinals. The problem of finding a complete set of rules describing the behavior of the continuum function 2ℵα for singular ℵα's, known as the Singular Cardinals Problem, has been attacked by many different techniques, involving forcing, large cardinals, inner models, and various combinatorial methods. The work on the singular cardinals problem has led to many often surprising results, culminating in a beautiful theory of Saharon Shelah called the pcf theory (“pcf” stands for “possible cofinalities”). The most striking result to date states that if 2ℵn < ℵω for every n = 0, 1, 2, …, then 2ℵω < ℵω4.

In this paper we present a brief history of the singular cardinals problem, the present knowledge, and an introduction into Shelah's pcf theory. In Sections 2, 3 and 4 we introduce the reader to cardinal arithmetic and to the singular cardinals problems. Sections 5, 6, 7 and 8 describe the main results and methods of the last 25 years and explain the role of large cardinals in the singular cardinals problem. In Section 9 we present an outline of the pcf theory.

§2. The arithmetic of cardinal numbers. Cardinal numbers were introduced by Cantor in the late 19th century and problems arising from investigations of rules of arithmetic of cardinal numbers led to the birth of set theory. The operations of addition, multiplication and exponentiation of infinite cardinal numbers are a natural generalization of such operations on integers. Addition and multiplication of infinite cardinals turns out to be simple: when at least one of the numbers κ, λ is infinite then both κ + λ and κ·λ are equal to max {κ, λ}. In contrast with + and ·, exponentiation presents fundamental problems. In the simplest nontrivial case, 2κ represents the cardinal number of the power set P(κ), the set of all subsets of κ. (Here we adopt the usual convention of set theory that the number κ is identified with a set of cardinality κ, namely the set of all ordinal numbers smaller than κ.

This is not about the symbolic manipulation of functions so popular these days. Rather it is about the more abstract, but infinitely less practical, problem of the primitive. Simply stated:

Given a derivative f: ℝ → ℝ, how can we recover its primitive?

The roots of this problem go back to the beginnings of calculus and it is even sometimes called “Newton's problem”. Historically, it has played a major role in the development of the theory of the integral. For example, it was Lebesgue's primary motivation behind his theory of measure and integration. Indeed, the Lebesgue integral solves the primitive problem for the important special case when f(x) is bounded. Yet, as Lebesgue noted with apparent regret, there are very simple derivatives (e.g., the derivative of F(0) = 0, F(x)= x2 sin(1/x2)for x ≠ 0) which cannot be inverted using his integral.

The general problem of the primitive was finally solved in 1912 by A. Denjoy. But his integration process was more complicated than that of Lebesgue. Denjoy's basic idea was to first calculate the definite integral f(x) dx over as many intervals (a,b) as possible, using Lebesgue integration. Then, he showed that by using these results, the definite integral could be found over even more intervals, either by using the standard improper integral technique of Cauchy, or an extension technique developed by Lebesgue (see appendix for details).

Two thoughts about the concept of number are incompatible: that any zero or more things have a (cardinal) number, and that any zero or more things have a number (if and) only if they are the members of some one set. It is Russell's paradox that shows the thoughts incompatible: the sets that are not members of themselves cannot be the members of any one set. The thought that any (zero or more) things have a number is Frege's; the thought that things have a number only if they are the members of a set may be Cantor's and is in any case a commonplace of the usual contemporary presentations of the set theory that originated with Cantor and has become ZFC.

In recent years a number of authors have examined Frege's accounts of arithmetic with a view to extracting an interesting subtheory from Frege's formal system, whose inconsistency, as is well known, was demonstrated by Russell. These accounts are contained in Frege's formal treatise Grundgesetze der Arithmetik and his earlier exoteric book Die Grundlagen der Arithmetik. We may describe the two central results of the recent re-evaluation of his work in the following way: Let Frege arithmetic be the result of adjoining to full axiomatic second-order logic a suitable formalization of the statement that the Fs and the Gs have the same number if and only if the F sand the Gs are equinumerous.

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic.

Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest paper in the subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers.

The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs.

The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure the information content of sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question is equivalent to: Given a computer with access to an oracle which will answer membership questions about a set A, can a program (allowing questions to the oracle) be written which will correctly compute the answers to all membership questions about a set B? If the answer is yes, then we say that B is Turing reducible to A and write B ≤TA. We say that B ≡TA if B ≤TA and A ≤TB. ≡T is an equivalence relation, and ≤T induces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called the degrees of unsolvability, and elements of this poset are called degrees.

Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer.

§1. The origins of recursion theory. In dedicating a book to Steve Kleene, I referred to him as the person who made recursion theory into a theory. Recursion theory was begun by Kleene's teacher at Princeton, Alonzo Church, who first defined the class of recursive functions; first maintained that this class was the class of computable functions (a claim which has come to be known as Church's Thesis); and first used this fact to solve negatively some classical problems on the existence of algorithms. However, it was Kleene who, in his thesis and in his subsequent attempts to convince himself of Church's Thesis, developed a general theory of the behavior of the recursive functions. He continued to develop this theory and extend it to new situations throughout his mathematical career. Indeed, all of the research which he did had a close relationship to recursive functions.

Church's Thesis arose in an accidental way. In his investigations of a system of logic which he had invented, Church became interested in a class of functions which he called the λ-definable functions. Initially, Church knew that the successor function and the addition function were λ-definable, but not much else. During 1932, Kleene gradually showed1 that this class of functions was quite extensive; and these results became an important part of his thesis 1935a (completed in June of 1933).

The best known and most widely discussed aspect of Kurt Gödel's philosophy of mathematics is undoubtedly his robust realism or platonism about mathematical objects and mathematical knowledge. This has scandalized many philosophers but probably has done so less in recent years than earlier. Bertrand Russell's report in his autobiography of one or more encounters with Gödel is well known:

Gödel turned out to be an unadulterated Platonist, and apparently believed that an eternal “not” was laid up in heaven, where virtuous logicians might hope to meet it hereafter.

On this Gödel commented:

Concerning my “unadulterated” Platonism, it is no more unadulterated than Russell's own in 1921 when in the Introduction to Mathematical Philosophy … he said, “Logic is concerned with the real world just as truly as zoology, though with its more abstract and general features.” At that time evidently Russell had met the “not” even in this world, but later on under the infuence of Wittgenstein he chose to overlook it.

One of the tasks I shall undertake here is to say something about what Gödel's platonism is and why he held it.

A feature of Gödel's view is the manner in which he connects it with a strong conception of mathematical intuition, strong in the sense that it appears to be a basic epistemological factor in knowledge of highly abstract mathematics, in particular higher set theory. Other defenders of intuition in the foundations of mathematics, such as Brouwer and the traditional intuitionists, have a much more modest conception of what mathematical intuition will accomplish.

§1. Introduction. The purpose of this paper is, in general, to report the state of the art of ordinal analysis and, in particular, the recent success in obtaining an ordinal analysis for the system of -analysis, which is the subsystem of formal second order arithmetic, Z2, with comprehension confined to -formulae. The same techniques can be used to provide ordinal analyses for theories that are reducible to iterated -comprehension, e.g., -comprehension. The details will be laid out in [28].

Ordinal-theoretic proof theory came into existence in 1936, springing forth from Gentzen's head in the course of his consistency proof of arithmetic. Gentzen fostered hopes that with sufficiently large constructive ordinals one could establish the consistency of analysis, i.e., Z2. Considerable progress has been made in proof theory since Gentzen's tragic death on August 4th, 1945, but an ordinal analysis of Z2 is still something to be sought. However, for reasons that cannot be explained here, -comprehension appears to be the main stumbling block on the road to understanding full comprehension, giving hope for an ordinal analysis of Z2 in the foreseeable future.

Roughly speaking, ordinally informative proof theory attaches ordinals in a recursive representation system to proofs in a given formal system; transformations on proofs to certain canonical forms are then partially mirrored by operations on the associated ordinals. Among other things, ordinal analysis of a formal system serves to characterize its provably recursive ordinals, functions and functionals and can yield both conservation and combinatorial independence results.

In this paper I shall present a method for proving determinacy from large cardinals which, in many cases, seems to yield optimal results. One of the main applications extends theorems of Martin, Steel and Woodin about determinacy within the projective hierarchy. The method can also be used to give a new proof of Woodin's theorem about determinacy in L(ℝ).

The reason we look for optimal determinacy proofs is not only vanity. Such proofs serve to tighten the connection between large cardinals and descriptive set theory, letting us bring our knowledge of one subject to bear on the other, and thus increasing our understanding of both. A classic example of this is the Harrington-Martin proof that -determinacy implies -determinacy. This is an example of a transfer theorem, which assumes a certain determinacy hypothesis and proves a stronger one. While the statement of the theorem makes no mention of large cardinals, its proof goes through 0#, first proving that

-determinacy ⇒ 0# exists,

and then that

0# exists ⇒ -determinacy

More recent examples of the connection between large cardinals and descriptive set theory include Steel's proof that

ADL(ℝ) ⇒ HODL(ℝ) ⊨ GCH,

see [9], and several results of Woodin about models of AD+, a strengthening of the axiom of determinacy AD which Woodin has introduced. These proofs not only use large cardinals, but also reveal a deep, structural connection between descriptive set theoretic notions and notions related to large cardinals.

In this paper we shall answer some questions in the set theory of L(ℝ), the universe of all sets constructible from the reals. In order to do so, we shall assume ADL(ℝ), the hypothesis that all 2-person games of perfect information on ω whose payoff set is in L(ℝ) are determined. This is by now standard practice. ZFC itself decides few questions in the set theory of L(ℝ), and for reasons we cannot discuss here, ZFC + ADL(ℝ) yields the most interesting “completion” of the ZFC-theory of L(ℝ).

ADL(ℝ) implies that L(ℝ) satisfies “every wellordered set of reals is countable”, so that the axiom of choice fails in L(ℝ). Nevertheless, there is a natural inner model of L(ℝ), namely HODL(ℝ), which satisfies ZFC. (HOD is the class of all hereditarily ordinal definable sets, that is, the class of all sets x such that every member of the transitive closure of x is definable over the universe from ordinal parameters (i.e., “OD”). The superscript “L(ℝ)” indicates, here and below, that the notion in question is to be interpreted in L(R).) HODL(ℝ) is reasonably close to the full L(ℝ), in ways we shall make precise in § 1. The most important of the questions we shall answer concern HODL(ℝ): what is its first order theory, and in particular, does it satisfy GCH?

These questions first drew attention in the 70's and early 80's. (See [4, p. 223]; also [12, p. 573] for variants involving finer notions of definability.)

About a month after his 83rd birthday Raphael Robinson was almost wholly incapacitated by a massive stroke, and 8 weeks later, on January 27, 1995, he died of ensuing complications. Mathematics was his life. He was always working on problems—those brought to him in journals or by colleagues, and others that he invented. Just three days before his death he received word that a paper of his, originating in a published problem, was accepted for publication. His 64 publications spanned a full 6 decades, and included significant papers on number theory, combinatorics, complex analysis, and geometry, in addition to logic and set theory.

Robinson was born on November 2, 1911, in National City, California. He came to Berkeley to study mathematics, obtaining an A.B. in 1932, an M.A. in 1933, and his Ph.D. in December, 1934. His dissertation was in complex analysis. He took 12 graduate courses in a variety of fields, but not one was close to logic or set theory—which was later the setting of about a quarter of his publications.

After completing his studies Robinson served as Instructor for two years at Brown University, then returned for good to Berkeley in 1937, reaching the rank of full Professor in 1949. He taught a great variety of courses and was known as an excellent teacher, but was most interested in problemsolving and research and in 1972, at age 61, he elected early retirement, at considerable financial sacrifice, in order to concentrate on these pursuits.