Abstract. 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.

Introduction. Two important papers in mathematical logic were published in 1931, one by Jacques Herbrand in the Journal für reine und angewandte Mathematik and the other by Kurt Gödel in the Monatshefte für Mathematik und Physik. At age 25, Gödel was Herbrand's elder by just two years. Their work dramatically impacted investigations in mathematical logic, but also became central for theoretical computer science as that subject evolved in the fifties and sixties.

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:

On this Gödel commented:

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.

There are many combinatorial properties that are shared by all constructions using the trees of strategies approach, some of which are relevant only to constructions of a fixed level. We gather some of these properties together in this chapter. We have attempted to isolate many combinatorial lemmas in this chapter, so that the proofs presented in other chapters depend only on the statements of these lemmas together with some special properties of the construction.

The lemmas of the current chapter are true of all assignments of requirements and derivatives to trees that satisfy the conditions of Chapter 2. These lemmas deal, among other things, with existence of initial and principal derivatives, an analysis of the ability to take both switching and nonswitching extensions of nodes, an analysis of the link creation process, and an analysis of the situations in which we can find free derivatives of a node. We begin, in Section 8.1, with some lemmas about the path generating and outcome functions λ and out. In Section 8.2, we demonstrate the ability to take both switching and nonswitching extensions. We prove some technical lemmas about links in Section 8.3, and apply these in Section 8.4 to conclude that certain nodes will be free at various stages of the construction. More general theorems are proved in Section 8.5. The remaining sections deal with lemmas that are level-specific, i.e., depend on the specific starting tree, or are more technical in nature.

Many of the lemmas deal with relationships between successive trees Tk and Tk+1. We will state these lemmas in full generality, but frequently present only the proof for k = 0, noting that the proofs relativize.

Δ3 constructions are similar to Δ2 constructions, raised by a level. They take place on four trees, T0, T1, T2 and T3, and are characterized by the following property: If η3 ⊂ ν3 ∈ T3, ν3 corresponds to a terminal node of the basic module associated with η3, lev(η3) = 3, and η3 has Π outcome along ν3, then no requirement is assigned to ν3 or any of its successors. In this case, the falsity of the directing sentence assigned to η3 together with activated action for this node suffices to prove the theorem.

We prove one theorem falling under this classification, the Sacks Density Theorem, in Section 6.2. We discuss certain types of requirements encountered in Δ3 constructions and state lemmas delineating properties of these requirements in Section 6.1.

Δ3 Constructions

When functional axioms need to be declared and Player I controls the enumeration of one of the oracle sets, the construction becomes more complex. This is the case when we are trying to construct a degree within a given interval. The simplest such case dealing with an arbitrary interval whose endpoints are computably enumerable degrees is the density theorem, proved in the next section; this theorem asserts that there is a computably enumerable set whose degree lies strictly between the endpoints of the interval. Thus we will be given computably enumerable sets U <TV controlled by Player I, and Player II will be assigned the responsibility to construct a computably enumerable set A such that U <TA <TV. Player II can replace A by U ⊕ A, and will use backtracking combined with permitting to show that A ≥TV.

Δ2 constructions are the simplest priority constructions in which Player I controls a set W. Such constructions take place on three trees, T0, T1, and T2. In a typical situation, W is non-computable and the success of the construction requires the entry of numbers into W at a stage at which such numbers are useful to the construction. To show that this must happen, the construction will try to compute more and more of W at prescribed sets of stages, so as W is not computable, these attempts must fail; and the failure will produce numbers that enter W when they are useful.

We discuss general Δ2 constructions in Section 4.1, stating a lemma describing relationships between nodes of that level. The lemma is applied to prove an upward cone avoidance theorem in Section 4.2, the Sacks Splitting Theorem in Section 4.3, basic facts about backtracking are presented in Section 4.4 and a permitting construction is carried out in Section 4.5.

The Δ2 Level

Unlike Σ1 constructions, Δ2 constructions will have level 2 requirements. However, these requirements will be of a very special nature, making these constructions somewhat similar to those at the Σ1 level. Prior to the existence of the classification of priority arguments using the arithmetical hierarchy, a differentiation was made between finite injury and infinite injury priority constructions only, and Δ2 constructions were classified as finite injury. But even at that time, a distinction was made between the two types of finite injury constructions.

Abstract. The metamathematical tradition that developed from Hilbert's program is based on syntactic characterizations of mathematics and the use of explicit, finitary methods in the metatheory. Although Gödel's work in logic fits squarely in that tradition, one often finds him curiously at odds with the associated methodological orientation. This essay explores that tension and what lies behind it.

§1. Introduction. While I am honored to have been asked to deliver a lecture in honor of the Kurt Gödel centennial, I agreed to do so with some hesitations. For one thing, I am not a historian, so if you are expecting latebreaking revelations from the Gödel Nachlass you will be disappointed. A more pressing concern is that I am a poor representative of Gödel's views. As a proof theorist by training and disposition, I take myself to be working in the metamathematical tradition that emerged from Hilbert's program; while I will point out, in this essay, that Gödel's work in logic falls squarely in this tradition, one often senses in Gödel a dissatisfaction with that methodological orientation that makes me uneasy. This is by no means to deny Gödel's significance; von Neumann once characterized him as the most important logician since Aristotle, and I will not dispute that characterization here. But admiration does not always translate to a sense of affinity, and I sometimes have a hard time identifying with Gödel's outlook.

Gödel has emphasized the important role that his philosophical views had played in his discoveries. Thus, in a letter to Hao Wang of December 7, 1967, explaining why Skolem and others had not obtained the completeness theorem for predicate calculus, Gödel wrote:

In a similar vein, Gödel has maintained that the “realist” or “Platonist” position regarding sets and the transfinite with which he is identified was part of his belief system from his student days. This can be seen in Gödel's replies to the detailed questionnaire prepared by Burke Grandjean in 1974. Gödel prepared three tentative mutually consistent replies, but sent none of them.

§1. Introduction. It is by now well known that Gödel first advocated the philosophy of Leibniz and then, since 1959, that of Husserl. This raises three questions:

1. How is this turn to Husserl to be interpreted? Is it a dismissal of the Leibnizian philosophy, or a different way to achieve similar goals?

2. Why did Gödel turn specifically to the later Husserl's transcendental idealism?

3. Is there any detectable influence from Husserl on Gödel's writings?

Regarding the first question, Wang reports that Gödel ‘[saw] in Husserl's work a method of refining and consolidating Leibniz' monadology’. But what does this mean? In what for Gödel relevant sense is Husserl's work a refinement and consolidation of Leibniz' monadology?

The second question is particularly pressing, given that Gödel was, by his own admission, a realist in mathematics since 1925. Wouldn't the uncompromising realism of the early Husserl's Logical investigations have been a more obvious choice for a Platonist like Gödel?

The third question can only be approached when an answer to the second has been given, and we want to suggest that the answer to the first question follows from the answer to the second. We begin, therefore, with a closer look at the actual turn towards phenomenology.

Some 30 years before his serious study of Husserl began, Gödel was well aware of the existence of phenomenology. Apart from its likely appearance in the philosophy courses that Gödel took, it reached him from various directions.

This chapter is devoted to the presentation of basic definitions and notation to be used in this monograph. The definitions fall under three general headings; those related to computable partial functionals and computably enumerable sets, those related to the computably enumerable degrees, and those related to trees.

Computably Enumerable Sets

Let ℕ be the natural numbers, i.e., the set of integers {0, 1, 2, …}. We use interval notation on ℕ; thus [k, m] = {n : k ≤ n ≤ m}. Open interval notation and half-open interval notation is used in a similar fashion. The direct sum of two subsets A and B of ℕ is denoted as A ⊕ B and is defined as {2x : x ∈ A} ∪ {2x + 1 : x ∈ B}. |A| will denote the cardinality of the set A.

If A ⊂ ℕ, m ∈ ℕ, and Φ is a partial functional, then we write Φ(A; m) ↓ if m is in the domain of Φ(A), and Φ(A; m) ↑ otherwise. If Φ and Ψ are partial functionals and A and B are sets, then we write Φ(A) ≃ Ψ(B) if Φ(A) and Ψ(B) are compatible, i.e., for all x, if Φ(A; x) ↓ and Ψ(B; x) ↓, then Φ(A; x) = Ψ(B; x); and we write Φ(A) = Ψ(B) if Φ(A) and Ψ(B) are identical, i.e., Φ(A) and Ψ(B) are compatible and for all x, Φ(A) ↓ iff Ψ(B) ↓.

Abstract. As initially envisioned, Gödel's Collected Works were to include transcriptions of material from his mathematical workbooks. In the end that material, as well as some other manuscript items from Gödel's Nachlass, had to be left out. This note describes some of the unpublished items in the Nachlass that are likely to attract the notice of scholars and surveys the extent of shorthand transcription efforts undertaken hitherto. Some examples of sources outside Gödel's Nachlass that may be of interest to Gödel scholars are also indicated.

At the time the Gödel Editorial Project began in the summer of 1982 the cataloguing of Gödel's Nachlass had only just begun. Nevertheless, despite limited knowledge of the extent of that collection, enthusiasm and expectations were high: Volume I of Gödel's Collected Works, which appeared four years later, confidently declared that “Succeeding volumes are to contain Gödel's … lecture notes, as well as extracts from his scientific notebooks.”

In the end, volume III of those Works, devoted to previously unpublished essays and lectures, contained the texts of a number of individual lectures that Gödel gave on various occasions, as well as those of several manuscripts that he left in relatively finished form, including some items transcribed from his Gabelsberger shorthand. But none of the five volumes ultimately published contain any of the notes that Gödel prepared for his lecture courses at the University of Vienna or at Notre Dame, nor any extracts from the three series of notebooks he compiled on mathematics and philosophy.

§1. I propose to address not so much Gödel's own philosophy of mathematics as the philosophical implications of his work, and especially of his incompleteness theorems. Now the phrase “philosophical implications of Gödel's theorem” suggests different things to different people. To professional logicians it may summon up thoughts of the impact of the incompleteness results on Hilbert's program. To the general public, if it calls up any thoughts at all, these are likely to be of the attempt by Lucas [1961] and Penrose [1989] to prove, if not the immortality of the soul, then at least the non-mechanical nature of mind. One goal of my present remarks will be simply to point out a significant connection between these two topics.

But let me consider each separately a bit first, starting with Hilbert. As is well known, though Brouwer's intuitionism was what provoked Hilbert's program, the real target of Hilbert's program was Kronecker's finitism, which had inspired objections to the Hilbert basis theorem early in Hilbert's career. (See the account in Reid [1970].) But indeed Hilbert himself and his followers (and perhaps his opponents as well) did not initially perceive very clearly just how far Brouwer was willing go beyond anything that Kronecker would have accepted. Finitism being his target, Hilbert made it his aim to convince the finitist, for whom no mathematical statements more complex than universal generalizations whose every instance can be verified by computation are really meaningful, of the value of “meaningless” classical mathematics as an instrument for establishing such statements.