summary of continuum hypothesis

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

8.5: The Continuum Hypothesis and The Generalized Continuum Hypothesis

• Last updated
• Save as PDF
• Page ID 19413

• Joseph Fields
• Southern Connecticut State University

The word “continuum” in the title of this section is used to indicate sets of points that have a certain continuity property. For example, in a real interval it is possible to move from one point to another, in a smooth fashion, without ever leaving the interval. In a range of rational numbers this is not possible, because there are irrational values in between every pair of rationals. There are many sets that behave as a continuum – the intervals \((a, b)\) or \([a, b]\), the entire real line \(\mathbb{R}\), the \(x\)-\(y\) plane \(\mathbb{R} × \mathbb{R}\), a volume in \(3\)-dimensional space (or for that matter the entire space \(\mathbb{R}^3\)). It turns out that all of these sets have the same size.

The cardinality of the continuum, denoted c , is the cardinality of all of the sets above.

In the previous section, we mentioned the continuum hypothesis and how angry Cantor became when someone (König) tried to prove it was false. In this section, we’ll delve a little deeper into what the continuum hypothesis says and even take a look at CH’s big brother, GCH. Before doing so, it seems like a good idea to look into the equivalences we’ve asserted about all those sets above which (if you trust us) have the cardinality c .

We’ve already seen that an interval is equivalent to the entire real line but the notion that the entire infinite Cartesian plane has no more points in it than an interval one inch long defies our intuition. Our conception of dimensionality leads us to think that things of higher dimension must be larger than those of lower dimension. This preconception is false as we can see by demonstrating that a \(1×1\) square can be put in one-to-one correspondence with the unit interval. Let \(S = \{(x, y) 0 < x < 1 ∧ 0 < y < 1\}\) and let \(I\) be the open unit interval \((0, 1)\). We can use the Cantor-Bernstein-Schroeder theorem to show that \(S\) and \(I\) are equinumerous – we just need to find injections from \(I\) to \(S\) and vice versa. Given an element \(r\) in \(I\) we can map it injectively to the point \((r, r)\) in \(S\). To go in the other direction, consider a point \((a, b)\) in \(S\) and write out the decimal expansions of \(a\) and \(b\):

\(a = 0.a_1a_2a_3a_4a_5 . . .\)

\(b = 0.b_1b_2b_3b_4b_5 . . .\)

as usual, if there are two decimal expansions for \(a\) and/or \(b\) we will make a consistent choice – say the infinite one.

From these decimal expansions, we can create the decimal expansion of a number in \(I\) by interleaving the digits of \(a\) and \(b\). Let

\(s = 0.a_1b_1a_2b_2a_3b_3 . . \).

be the image of \((a, b)\). If two different points get mapped to the same value s then both points have \(x\) and \(y\) coordinates that agree in every position of their decimal expansion (so they must really be equal). It is a little bit harder to create a bijective function from \(S\) to \(I\) (and thus to show the equivalence directly, without appealing to C-B-S). The problem is that, once again, we need to deal with the non-uniqueness of decimal representations of real numbers. If we make the choice that, whenever there is a choice to be made, we will use the non-terminating decimal expansions for our real numbers there will be elements of \(I\) not in the image of the map determined by interleaving digits (for example \(0.15401050902060503\) is the interleaving of the digits after the decimal point in \(π = 3.141592653\). . . and \(\dfrac{1}{2} = 0.5\), this is clearly an element of \(I\) but it can’t be in the image of our map since \(\dfrac{1}{2}\) should be represented by \(0.49\) according to our convention. If we try other conventions for dealing with the non-uniqueness it is possible to find other examples that show simple interleaving will not be surjective. A slightly more subtle approach is required.

Presume that all decimal expansions are non-terminating (as we can, WLOG) and use the following approach: Write out the decimal expansion of the coordinates of a point \((a, b)\) in \(S\). Form the digits into blocks with as many \(0\)’s as possible followed by a non-zero digit. Finally, interleave these blocks.

For example if

\(a = 0.124520047019902 . . .\)

\(b = 0.004015648000031 . . .\)

we would separate the digits into blocks as follows:

\(a = 0.1 \;\;\;\;2 \;\;\;\;4 \;\;\;\;5 \;\;\;\;2\;\;\;\; 004\;\;\;\; 7\;\;\;\; 01 \;\;\;\;9 \;\;\;\;9 \;\;\;\;02 . . .\)

\(b = 0.004\;\;\;\; 01\;\;\;\; 5 \;\;\;\;6\;\;\;\; 4\;\;\;\; 8 \;\;\;\;00003 \;\;\;\;1 . . .\)

and the number formed by interleaving them would be

\(s = 0.10042014556240048 . . .\)

We’ve shown that the unit square, \(S\), and the unit interval, \(I\), have the same cardinality. These arguments can be extended to show that all of R×R also has this cardinality ( c ).

So now let’s turn to the continuum hypothesis.

We mentioned earlier in this chapter that the cardinality of \(\mathbb{N}\) is denoted \(ℵ_0\). The fact that that capital letter aleph is wearing a subscript ought to make you wonder what other aleph-sub-something-or-others there are out there. What is \(ℵ_1\)? What about \(ℵ_2\)? Cantor presumed that there was a sequence of cardinal numbers (which is itself, of course, infinite) that give all of the possible infinities. The smallest infinite set that anyone seems to be able to imagine is \(\mathbb{N}\), so Cantor called that cardinality \(ℵ_0\). What ever the “next” infinite cardinal is, is called \(ℵ_1\). It’s conceivable that there actually isn’t a “next” infinite cardinal after \(ℵ_0\) — it might be the case that the collection of infinite cardinal numbers isn’t well-ordered! In any case, if there is a “next” infinite cardinal, what is it? Cantor’s theorem shows that there is a way to build some infinite cardinal bigger than \(ℵ_0\) — just apply the power set construction. The continuum hypothesis just says that this bigger cardinality that we get by applying the power set construction is that “next” cardinality we’ve been talking about.

To re-iterate, we’ve shown that the power set of \(\mathbb{N}\) is equivalent to the interval \((0, 1)\) which is one of the sets whose cardinality is \(\text{c}\) . So the continuum hypothesis, the thing that got Georg Cantor so very heated up, comes down to asserting that

\(ℵ_1 =\) c .

There really should be a big question mark over that. A really big question mark. It turns out that the continuum hypothesis lives in a really weird world. . . To this day, no one has the least notion of whether it is true or false. But wait! That’s not all! The real weirdness is that it would appear to be impossible to decide. Well, that’s not so bad – after all, we talked about undecidable sentences way back in the beginning of Chapter 2 . Okay, so here’s the ultimate weirdness. It has been proved that one can’t prove the continuum hypothesis. It has also been proved that one can’t disprove the continuum hypothesis.

Having reached this stage in a book about proving things I hope that the last two sentences in the previous paragraph caused some thought along the lines of “well, ok, with respect to what axioms?” to run through your head. So, if you did think something along those lines pat yourself on the back. And if you didn’t then recognize that you need to start thinking that way — things are proved or disproved only in a relative way, it depends what axioms you allow yourself to work with. The usual axioms for mathematics are called ZFC; the Zermelo-Frankel set theory axioms together with the axiom of choice. The “ultimate weirdness” we’ve been describing about the continuum hypothesis is a result due to a gentleman named Paul Cohen that says “CH is independent of ZFC.” More pedantically – it is impossible to either prove or disprove the continuum hypothesis within the framework of the ZFC axiom system.

It would be really nice to end this chapter by mentioning Paul Cohen, but there is one last thing we’d like to accomplish — explain what GCH means. So here goes.

The generalized continuum hypothesis says that the power set construction is basically the only way to get from one infinite cardinality to the next. In other words, GCH says that not only does \(\mathcal{P}(\mathbb{N})\) have the cardinality known as \(ℵ_1\), but every other aleph number can be realized by applying the power set construction a bunch of times. Some people would express this symbolically by writing

\[∀n ∈ \mathbb{N}, \;\;\;\;\; ℵ_{n+1} = 2^{ℵ_n} .\]

I’d really rather not bring this chapter to a close with that monstrosity so instead I think I’ll just say

Paul Cohen.

Hah! I did it! I ended the chapter by sayi. . . Hunh? Oh.

Continuum Hypothesis

Gödel showed that no contradiction would arise if the continuum hypothesis were added to conventional Zermelo-Fraenkel set theory . However, using a technique called forcing , Paul Cohen (1963, 1964) proved that no contradiction would arise if the negation of the continuum hypothesis was added to set theory . Together, Gödel's and Cohen's results established that the validity of the continuum hypothesis depends on the version of set theory being used, and is therefore undecidable (assuming the Zermelo-Fraenkel axioms together with the axiom of choice ).

Woodin (2001ab, 2002) formulated a new plausible "axiom" whose adoption (in addition to the Zermelo-Fraenkel axioms and axiom of choice ) would imply that the continuum hypothesis is false. Since set theoreticians have felt for some time that the Continuum Hypothesis should be false, if Woodin's axiom proves to be particularly elegant, useful, or intuitive, it may catch on. It is interesting to compare this to a situation with Euclid's parallel postulate more than 300 years ago, when Wallis proposed an additional axiom that would imply the parallel postulate (Greenberg 1994, pp. 152-153).

Portions of this entry contributed by Matthew Szudzik

Explore with Wolfram|Alpha

More things to try:

• continuum hypothesis
• 12! / (4! * 6! * 2!)
• CA k=3 r=2 rule 914752986721674989234787899872473589234512347899

Cite this as:

Szudzik, Matthew and Weisstein, Eric W. "Continuum Hypothesis." From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/ContinuumHypothesis.html

Subject classifications

Can the Continuum Hypothesis Be Solved?

In 1900, David Hilbert published a list of twenty-three open questions in mathematics , ten of which he presented at the International Congress of Mathematics in Paris that year. Hilbert had a good nose for asking mathematical questions as the ones on his list went on to lead very interesting mathematical lives. Many have been solved, but some have not been, and seem to be quite difficult. In both cases, some very deep mathematics has been developed along the way. The so-called Riemann hypothesis, for example, has withstood the attack of generations of mathematicians ever since 1900 (or earlier). But the effort to solve it has led to some beautiful mathematics. Hilbert’s fifth problem turned out to assert something that couldn’t be true, though with fine tuning the “right” question—that is, the question Hilbert should have asked—was both formulated and solved. There is certainly an art to asking a good question in mathematics.

The problem known as the continuum hypothesis has had perhaps the strangest fate of all. The very first problem on the list, it is simple to state: how many points on a line are there? Strangely enough, this simple question turns out to be deeply intertwined with most of the interesting open problems in set theory , a field of mathematics with a very general focus, so general that all other mathematics can be seen as part of it, a kind of foundation on which the house of mathematics rests. Most objects in mathematics are infinite, and set theory is indeed just a theory of the infinite.

How ironic then that the continuum hypothesis is unsolvable—indeed, “provably unsolvable,” as we say. This means that none of the known mathematical methods—those that mathematicians actually use and find legitimate—will suffice to settle the continuum hypothesis one way or another. It seems odd that being unsolvable is the kind of thing one can prove about a mathematical question. In fact, there are many questions of this type, particularly about sets of real numbers—or sets of points on a line, if you like—that we know cannot be settled using standard mathematical methods.

Now, mathematics is not frozen in time or method—to the contrary, it is a very dynamic enterprise, each generation expanding and building on what went before. This process of expansion has not always been easy; sometimes it takes a while before new methods are accepted. This was true of set theory in the late nineteenth century. Its inventor, Georg Cantor , met with serious opposition on the part of those who were hesitant to admit infinite objects into mathematics.

What concerns us here is not so much the prehistory of the continuum hypothesis, but the present state of it, and the remarkable fact that mathematicians are in the midst of developing new methods by which the continuum hypothesis could be solved after all.

I will explain some of these developments, along with some of the more recent history of the continuum hypothesis, from the point of view of Kurt Gödel’s role in them. Gödel , a Member of the Institute’s School of Mathematics on several occasions in the 1930s, and then continuously from 1940 until 1976, 1 was a relative newcomer to the problem. But it turns out that Gödel’s hand is visible in virtually every aspect of the problem, from the post-Cantorian period onward. Curiously enough, this is even more true now than it was at the time of Gödel’s death nearly thirty-five years ago.

What is the Continuum Hypothesis?

Mathematics is nowadays saturated with infinity . There are infinitely many positive whole numbers 0, 1, 2, 3 . . . . There are infinitely many lines, squares, circles in the plane, balls, cubes, polyhedra in the space, and so on. But there are also different degrees of infinity. Let us say that a set—a collection of mathematical objects such as numbers or lines—is countable if it has the same number of elements as the sequence of positive whole numbers 1, 2, 3 . . . . The set of positive whole numbers is thus countable, and so is the set of all rational numbers. In the early 1870s , Cantor made a momentous discovery: the set of real numbers (such as 5, 17, 5/12, √–2, π, e, . . . ) sometimes called the “continuum,” is uncountable . By uncountable, we mean that if we try to count the points on a line one by one, we will never succeed, even if we use all of the whole numbers. Now it is natural to ask the following question: are there any infinities between the two infinities of whole numbers and of real numbers?

This is the continuum hypothesis, which proposes that if you are given a line with an infinite set of points marked out on it, then just two things can happen: either the set is countable, or it has as many elements as the whole line. There is no third infinity between the two.

At first, Cantor thought he had a proof of the continuum hypothesis; then he thought he could prove it was false; and then he gave up. This was a blow to Cantor, who saw this as a defect in his work—if one cannot answer such a simple question as the continuum hypothesis, how can one possibly go forward?

Some History

The continuum hypothesis went on to become a very important problem, so much so that in 1900 Hilbert listed it as the first on his list of open problems, as previously mentioned. Hilbert eventually gave a proof of it in 1925—the proof was wrong, though it contained some important ideas.

Around the turn of the century, mathematicians were able to prove that the continuum hypothesis holds for a special class of sets called the Borel sets. 2 This is a concrete class of sets, containing, for the most part, the usual sets that mathematicians work with. Even with this early success in the special case of Borel sets though, and in spite of Hilbert’s attempted solution, mathematicians began to speculate that the continuum hypothesis was in general not solvable at all. Hilbert , for whom nothing less than “the glory of human existence” seemed to depend upon the ability to resolve all such questions, was an exception. “ Wir müssen wissen . Wir werden wissen ,” 3 he said in 1930 in Königsberg . In a great irony of history, at the very same meeting, but on the day before, the young Gödel announced his first incompleteness theorem. This theorem, together with Gödel’s second incompleteness theorem, is generally thought to have dealt a death blow to Hilbert’s idea that every mathematical question that permits an exact formulation can be solved. Hilbert was not in the room at the time.

Gödel , however, became a strong advocate of the solvability of the continuum hypothesis, taking the view that his incompleteness theorems , though they show that some provably undecidable statements do exist, have nothing to do with whether the continuum hypothesis is solvable or not. Like Hilbert , Gödel maintained that the continuum hypothesis will be solved.

What is Provable Unsolvability Anyway?

We arrive at an apparent conundrum. On the one hand, the continuum hypothesis is provably unsolvable, and on the other hand, both Gödel and Hilbert thought it was solvable. How to resolve this difficulty? What does it mean for something to be provably unsolvable anyway?

Some mathematical problems may be extremely difficult and therefore without a solution up to now, but one day someone may come up with a brilliant solution. Fermat’s last theorem, for example, went unsolved for three and a half centuries. But then Andrew Wiles was able to solve it in 1994. The continuum hypothesis is a problem of a very different kind; we actually can prove that it is impossible to solve it using current methods , which is not a completely unknown phenomenon in mathematics. For example, the age-old trisection problem asks: can we trisect a given angle by using just a ruler and compass? The Greeks of the classical period were very puzzled by how to make such a trisection, and no wonder, for in the nineteenth century it was proved that it is impossible—not just very difficult but impossible. You need a little more than a ruler and compass to trisect an arbitrary angle—for example, a compass and a ruler with two marks on it.

It is the same with the continuum hypothesis: we know that it is impossible to solve using the tools we have in set theory at the moment. And up until recently nobody knew what the analogue of a ruler with two marks on it would be in this case. Since the current tools of set theory are so incredibly powerful that they cover all of existing mathematics, it is almost a philosophical question: what would it be like to go beyond set-theoretic methods and suggest something new? Still, this is exactly what is needed to solve the continuum hypothesis.

Consistency

Gödel began to think about the continuum problem in the summer of 1930, though it wasn’t until 1937 that he proved the continuum hypothesis is at least consistent . This means that with current mathematical methods, we cannot prove that the continuum hypothesis is false .

Describing Gödel ’s solution would draw us into unneeded technicalities, but we can say a little bit about it. Gödel built a model of mathematics in which the continuum hypothesis is true. What is a model? This is something mathematicians build with the purpose of showing that something is possible, even if we admit that the model is just what it is, a kind of artificial construction. Children build model airplanes; architects draw up architectural plans; mathematicians build models of the mathematical universe. There is an important difference though, between mathematicians’ models and architectural plans or model airplanes: building a model that has the exact property the mathematician has in mind, is, in all but trivial cases, extremely difficult. It is like a very great feat of engineering.

The idea behind Gödel’s model, which we now call the universe of constructible sets , was that it should be made as small as is conceivably possible by throwing everything out that was not absolutely essential. It was a tour de force to show that what was left was enough to satisfy the requirements of mathematics, and, in addition, the continuum hypothesis. This did not show that the continuum hypothesis is really true, only that it is consistent, because Gödel’s universe of constructible sets is not the real universe, only a kind of artifact. Still, it suffices to demonstrate the consistency of the continuum hypothesis.

Unsolvability

After Gödel’s achievement, mathematicians sought a model in which the continuum hypothesis fails, just as Gödel found a model in which the continuum hypothesis holds. This would mean that the continuum hypothesis is unsolvable using current methods. If, on the one hand, one can build a picture of the mathematical universe in which it is true, and, on the other hand, if one can also build another universe in which it is false, it would essentially tell you that no information about the continuum hypothesis is lurking in the standard machinery of mathematics.

So how to build a model for the failure of the continuum hypothesis? Since Gödel’s universe was the only nontrivial universe that had been introduced, and, moreover, it was the smallest possible, mathematicians quickly realized that they had to find a way to extend Gödel’s model, by carefully adding real numbers to it. This is hair-raisingly difficult. It is like adding a new card to a huge house of cards, or, more exactly, like adding a new point to a line that already is—in a sense—a continuum. Where do you find the space to slip in a few new real numbers?

Looking back at Paul Cohen ’s solution, a logician has to slap her forehead, not once, but a few times. His idea was that the real numbers one adds should have “no properties,” as strange as this may sound; they should be “generic,” as he called them. In particular, a Cohen real , as they came to be called, should avoid “saying anything” nontrivial about the model. How to make this idea mathematically precise? That was Paul Cohen’s great invention: the forcing method, which is a way to add new reals to a model of the mathematical universe.

Even with this idea, serious obstacles now stood in the way of a full proof. For example, one has to prove an extremely delicate metamathematical theorem—as these are called—that even though forcing extends the universe to a bigger one, one can still talk about it in the first universe; in technical terms, one has to prove that forcing is definable . Moreover, to violate the continuum hypothesis, we have to add a lot of new points to the continuum, and what we believe is “a lot” may in the final stretch turn out to be not so many after all. This last problem—the technical term is preserving cardinals —was a very serious matter. Cohen later wrote of his sense of unease at that point, “given the rumors that had circulated that Gödel was unable to handle the CH.” 4 Perhaps Cohen sensed, while on the brink of his great discovery, the almost physical presence of the one mathematician who had walked the very long way up to that very door, but was unable to open it.

Two weeks later, while vacationing with his family in the Midwest, Cohen suddenly remembered a lemma from topology (due to N. A. Shanin ), and this was just what was needed to show that everything falls into place. The proof was now finished. It would have been an astounding achievement for any set theorist, but the fact that it was solved by someone from a completely different field—Paul Cohen was an analyst after all, not a set theorist—seemed beyond belief.

Writing the Paper

The story of what happened in the immediate aftermath of Cohen’s announcement of his proof is very interesting, also from the point of view of human interest, so we will permit ourselves a slight digression in order to touch upon it here.

The announcement seems to have been made at a time when the extent of what had been shown was not clear, and the proof, though it was finished in all the essentials, was not in all details completely finished. In a first letter to Gödel , dated April 24, 1963, Cohen communicated his results. But about a week later, he wrote a second, more urgent letter, in which he expressed his fear that there might be a hidden flaw in the proof, and, at the same time, his exasperation with logicians, who could not believe that he was able to prove that very delicate theorem on the definability of forcing.

Cohen confessed in the letter that the situation was wearing, also considering “the unexpected interest my work has aroused among the general (non-logical) mathematical world.”

Gödel replied with a very friendly letter, inviting Cohen to visit him, either at his home on Linden Lane or in his office at the Institute, writing, “You have just achieved the most important progress in set theory since its axiomatization . So you have every reason to be in high spirits.”

Soon after receiving the letter, Cohen visited Gödel at home, whereupon Gödel checked the proof, and pronounced it correct.

What followed over the next six months is a voluminous correspondence between the two, centered around the writing of the paper for the Proceedings of the National Academy of Sciences . The paper had to be carefully written; but Cohen was clearly impatient to go on to other work. It therefore fell to Gödel to fine tune the argument, as well as simplify it, all the while keeping Cohen in good spirits. The Gödel that emerges in these letters—sovereign, generous, and full of avuncular goodwill, will be unfamiliar to readers of the biographies—especially if one keeps in mind that by 1963 Gödel had devoted a good part of twenty-five years to solving the continuum problem himself, without success. “Your proof is the very best possible,” Gödel wrote at one point. “Reading it is like reading a really good play.”

Gödel and Cohen bequeathed to set theorists the only two model construction methods they have. Gödel’s method shows how to “shrink” the set-theoretic universe to obtain a concrete and comprehensible structure. Cohen’s method allows us to expand the set-theoretic universe in accordance with the intuition that the set of real numbers is very large. Building on this solid foundation, future generations of set theorists have been able to make spectacular advances.

There was one last episode concerning Gödel and the continuum hypothesis. In 1972, Gödel circulated a paper called “Some considerations leading to the probable conclusion that the true power of the continuum is ℵ 2 ,” which derived the failure of the continuum hypothesis from some new assumptions, the so-called scale axioms of Hausdorff . The proof was incorrect, and Gödel withdrew it, blaming his illness. In 2000, Jörg Brendle , Paul Larson, and Stevo Todorcevic 5 isolated three principles implicit in Gödel’s paper, which, taken together, put a bound on the size of the continuum. And subsequently Gödel’s ℵ 2 became a candidate of choice for many set theorists, as various important new principles from conceptually quite different areas were shown to imply that the size of the continuum is ℵ 2 .

Currently, there are two main programs in set theory. The inner model program seeks to construct models that resemble Gödel’s universe of constructible sets, but such that certain strong principles, called large cardinal axioms, would hold in them. These are very powerful new principles, which go beyond current mathematical methods (axioms). As Gödel predicted with great prescience in the 1940s , such cardinals have now become indispensable in contemporary set theory. One way to certify their existence is to build a model of the universe for them—not just any model, but one that resembles Gödel’s constructible universe, which has by now become what is called “canonical.” In fact, this may be the single most important question in set theory at the moment—whether the universe is “like” Gödel’s universe, or whether it is very far from it. If this question is answered, in particular if the inner model program succeeds, the continuum hypothesis will be solved.

The other program has to do with fixing larger and larger parts of the mathematical universe, beyond the world of the previously mentioned Borel sets. Here also, if the program succeeds, the continuum hypothesis will be solved.

We end with the work of another seminal figure, Saharon Shelah . Shelah has solved a generalized form of the continuum hypothesis, in the following sense: perhaps Hilbert was asking the wrong question! The right question, according to Shelah , is perhaps not how many points are on a line, but rather how many “small” subsets of a given set you need to cover every small subset by only a few of them. In a series of spectacular results using this idea in his so-called pcf-theory , Shelah was able to reverse a trend of fifty years of independence results in cardinal arithmetic, by obtaining provable bounds on the exponential function. The most dramatic of these is 2 ℵω ≤ 2 ℵ0 + ℵ ω4 . Strictly speaking, this does not bear on the continuum hypothesis directly, since Shelah changed the question and also because the result is about bigger sets. But it is a remarkable result in the general direction of the continuum hypothesis.

In his paper, 6 Shelah quotes Andrew Gleason, who made a major contribution to the solution of Hilbert’s fifth problem:

Of course, many mathematicians are not aware that the problem as stated by Hilbert is not the problem that has been ultimately called the Fifth Problem. It was shown very, very early that what he was asking people to consider was actually false. He asked to show that the action of a locally-euclidean group on a manifold was always analytic, and that’s false . . . you had to change things considerably before you could make the statement he was concerned with true. That’s sort of interesting, I think. It’s also part of the way a mathematical theory develops. People have ideas about what ought to be so and they propose this as a good question to work on, and then it turns out that part of it isn’t so .

So maybe the continuum problem has been solved after all, and we just haven’t realized it yet.

1 Appointed to the permanent Faculty in 1953; 2 This was extended to the so-called analytic sets by Mikhail Suslin in 1917. Borel sets are named for Emile Borel, uncle of the late mathematician (and IAS Faculty member) Armand Borel.; 3 “We must know. We will know.”; 4 P. J. Cohen, “The Discovery of Forcing”; 5 In their "Rectangular Axioms, Perfect Set Properties and Decomposition"; 6 "The Generalized Continuum Hypothesis Revisited"

Some Mathematical Details

Intuitively, the set-theoretic universe is the result of iterating basic constructions such as products ∏ i ∈ I A i , unions U i ∈ I A i , and power sets P(A) . In addition, the universe is assumed to satisfy so-called reflection : any property that it has is already possessed by some smaller universe, the domain of which is a set. The process starts from some given urelements , objects that are not sets, i.e., do not consist of elements, but it has been proven that the urelements are unnecessary and the process can be started from the empty set. Iterating this process into the transfinite , we obtain the cumulative hierarchy V of sets. Transfinite iterations are governed by ordinals , canonical representatives of well-ordered total orders, denoted by lower-case Greek letters α , β , etc. The hierarchy V is defined recursively by V α = U β < α P ( V β ). The fact that V = U α V α is the entire universe of sets is the intuitive content of the axioms of Zermelo-Frankel set theory with the Axiom of Choice, or ZFC , the basic system we have been working with all along.

Now Gödel’s model of the ZFC axioms, the constructible hierarchy L = U α L α , where L α = U β <α P L ( V β ), is built up not by means of the unrestricted power set operation P ( A ), but by the restricted operation P L ( A ), which takes from P ( A ) only those sets that are definable in ( A , ∈). Gödel showed that we can consistently assume V = L , but Cohen showed that it is consistent to assume that there are real numbers that are not in L .

The Borel sets of reals are obtained from open sets by means of iterating complements and countable unions. If we enlarge the set of Borel sets by including images of continuous functions, we obtain the analytic sets; a set is coanalytic if its complement is analytic.

Finally, the projective sets are obtained from analytic sets by iterating complements and continuous images. The field of descriptive set theory asks, among other questions, whether the classical theory of analytic and coanalytic sets can be extended to the projective sets; in particular, whether the projective sets are Lebesgue measurable, and have the perfect set property and the property of Baire . This was settled in the 1980s with the work of Shelah and Woodin , building on earlier work of Solovay , who showed that the projective sets have these three properties as a consequence of the existence of certain so-called large cardinals. This also follows from projective determinacy , a principle that was shown by Martin and Steel to follow from the existence of such large cardinals. A cardinal α is called a large cardinal if V α behaves in certain ways like V itself. For example, in that case, V α is a model of ZFC , but more is assumed. A famous large cardinal is a measurable cardinal, introduced by Stanislaw Ulam , an example of which is the smallest cardinal that admits a nontrivial countably additive two-valued measure.

What a State Mathematics Would Be In Today . . .

Before coming to the Institute where he was appointed as one of its first Professors in 1933, John von Neumann was a student of David Hilbert’s in Göttingen . Von Neu­mann worked on Hilbert’s program to find a complete and consistent set of axioms for all of mathematics. In addition to his many other contributions to mathematics and physics, von Neumann defined Hilbert space (unbounded operators on an infinite dimensional space), which he used to formulate a mathematical structure of quantum mechanics. Below, the late Herman Goldstine , a former Member in the Schools of Mathematics, Natural Sciences, and Historical Studies, recalls von Neumann’s working dreams about Kurt Gödel’s incompleteness theorem(s). ( Ex­cerp­ted from an oral history transcript available at www.prince­ton.edu/%7Emudd/finding_aids/math­oral/pmc15.htm ; more information about von Neumann and Gödel is available at www.ias.edu/people/noted-figures .)

His work habits were very methodical. He would get up in the morning, and go to the Nassau Club to have breakfast. And then from the Nassau Club he’d come to the Institute around nine, nine-thirty, work until lunch, have lunch, and then work until, say, five, and then go on home. Many evenings he would entertain. Usually a few of us, maybe my wife and me. We would just sit around, and he might not even sit in the same room. He had a little study that opened off of the living room, and he would just sit in there sometimes. He would listen, and if something interested him, he would interrupt. Otherwise he would work away.

At night he would go to bed at a reasonable hour, and he would waken, I think, almost every night, judging from the things he told me and the few times that he and I shared hotel rooms. He would waken in the night, two, three in the morning, and would have thought through what he had been working on. He would then write. He would write down the things he had worked on. . . .

He, under Hilbert’s tutelage, was trying to prove the opposite of the Gödel theorem. He worked and worked and worked at this, and one night he dreamed the proof. He got up and wrote it down, and he got very close to the end. He went and worked all day on that part, and the next night he dreamed again. He dreamed how to close the gap, and he got up and wrote, and he got within epsilon of the end, but he couldn’t make the final step. So he went to bed. The next day he worked and worked and worked at it, and he said to me, “You know, it was very lucky, Herman, that I didn’t dream the third night, or think what a state mathematics would be in today.” [Laughter.]

Juliette Kennedy is Associate Professor in the Department of Mathematics and Statistics at the University of Helsinki and a Member (2011–12) in the School of Historical Studies. In the history and foundations of mathematics, she has worked extensively on a project that attempts to put Kurt  Gödel  in full perspective, historically and foundationally. Her project at the Institute this year is centered on  Gödel’s  notion of semantic content. The mathematical aspect of the project involves the question of how many of the larger “large cardinals” can be captured with a newly discovered class of L-like inner models of set theory.

• Table of Contents
• Random Entry
• Chronological
• Editorial Information
• About the SEP
• Editorial Board
• How to Cite the SEP
• Special Characters
• Advanced Tools
• Support the SEP
• PDFs for SEP Friends
• Make a Donation
• SEPIA for Libraries
• Entry Contents

Bibliography

Academic tools.

• Friends PDF Preview
• Author and Citation Info
• Back to Top

Kurt Gödel

Kurt Friedrich Gödel (b. 1906, d. 1978) was one of the principal founders of the modern, metamathematical era in mathematical logic. He is widely known for his Incompleteness Theorems, which are among the handful of landmark theorems in twentieth century mathematics, but his work touched every field of mathematical logic, if it was not in most cases their original stimulus. In his philosophical work Gödel formulated and defended mathematical Platonism, the view that mathematics is a descriptive science, or alternatively the view that the concept of mathematical truth is objective. On the basis of that viewpoint he laid the foundation for the program of conceptual analysis within set theory (see below). He adhered to Hilbert’s “original rationalistic conception” in mathematics (as he called it); [ 1 ] and he was prophetic in anticipating and emphasizing the importance of large cardinals in set theory before their importance became clear.

1. Biographical Sketch

2.1.1 introduction, 2.1.2 proof of the completeness theorem, 2.1.3 an important consequence of the completeness theorem, 2.2.1 the first incompleteness theorem, 2.2.2 the proof of the first incompleteness theorem, 2.2.3 the second incompleteness theorem.

• Supplementary Document: Did the Incompleteness Theorems Refute Hilbert’s Program?

2.3 Speed-up Theorems

2.4.1 the consistency of the continuum hypothesis and the axiom of choice, 2.4.2 gödel’s proof of the consistency of the continuum hypothesis and the axiom of choice with the axioms of zermelo-fraenkel set theory, 2.4.3 consequences of consistency, 2.4.4 gödel’s view of the axiom of constructibility, 2.5.1 intuitionistic propositional logic is not finitely-valued, 2.5.2 classical arithmetic is interpretable in heyting arithmetic, 2.5.3 intuitionistic propositional logic is interpretable in s4, 2.5.4 heyting arithmetic is interpretable into computable functionals of finite type..

Supplement Document: Gödel’s Documents

3.1 Gödel’s Rationalism

3.2 gödel’s realism.

• Supplementary Document: Gödel’s Turn to Phenomenology
• Supplementary Document: A Philosophical Argument About the Content of Mathematics

Gödel’s Writings

The collected papers of kurt gödel, selected works of kurt gödel, secondary sources, other internet resources, related entries.

Kurt Gödel was born on April 28, 1906 in what was then the Austro-Hungarian city of Brünn, and what is now Brno in the Czech Republic.

Gödel’s father Rudolf August was a businessman, and his mother Marianne was a well-educated and cultured woman to whom Gödel remained close throughout his life, as witnessed by the long and wide-ranging correspondence between them. The family was well off, and Gödel’s childhood was an uneventful one, with one important exception; namely, from about the age of four Gödel suffered frequent episodes of poor health, and the health problems he suffered then as well as others of various kinds were to plague him his entire life.

Health problems notwithstanding, Gödel proved to be an exemplary student at primary school and later the Gymnasium, excelling especially in mathematics, languages and religion. Upon his graduation from the Gymnasium in Brno in 1924 Gödel enrolled in the University of Vienna, attending lectures on physics, his initial field of interest, lectures on philosophy given by Heinrich Gomperz, and lectures on mathematics. Gödel took a number of physics courses during his undergraduate years, as witnessed by his university transcript; this is notable in view of Gödel’s subsequent contributions to relativity in 1947. Philipp Furtwängler, cousin of the great German conductor Wilhelm Furtwängler, was one of his mathematics professors, and indeed Furtwängler’s course on class field theory almost tempted Gödel to pursue his studies in that area. Gödel learned his logic from Rudolph Carnap and from Hans Hahn, eventually graduating under Hahn with a Dr.phil. in mathematics in 1929. The main theorem of his dissertation was the completeness theorem for first order logic (Gödel 1929). [ 2 ]

Gödel’s university years also marked the beginning of his attendance at meetings of the Vienna Circle, a group around Moritz Schlick that quickly became known as “logical positivists,” a term coined by Feigl and Blumberg in their 1931 “Logical positivism: A new movement in European philosophy” (Feigl and Blumberg 1931). Though Gödel was not himself a logical positivist, those discussions were a crucial formative influence.

The 1930s were a prodigious decade for Gödel. After publishing his 1929 dissertation in 1930, he published his groundbreaking incompleteness theorems in 1931, on the basis of which he was granted his Habilitation in 1932 and a Privatdozentur at the University of Vienna in 1933.

Among his mathematical achievements at the decade’s close is the proof of the consistency of both the Axiom of Choice and Cantor’s Continuum Hypothesis with the Zermelo-Fraenkel axioms for set theory, obtained in 1935 and 1937, respectively. Gödel also published a number of significant papers on modal and intuitionistic logic and arithmetic during this period, principal among which is his “On intuitionistic arithmetic and number theory,” (Gödel 1933e), in which he showed that classical first order arithmetic is interpretable in Heyting arithmetic by a simple translation. Other publications of the 1930s include those on the decision problem for the predicate calculus, on the length of proofs, and on differential and projective geometry.

By the end of the decade both Gödel’s advisor Hans Hahn and Moritz Schlick had died (the latter was assassinated by an ex-student), two events which led to a personal crisis for Gödel. Also, his appointment at the University, that of Privatdozentur, was cancelled, being replaced by the position “Dozentur neuer Ordnung,” granted to candidates only after they had passed a racial test. [ 3 ] Gödel’s three trips the United States during that decade triggered an investigation. (See Sigmund 2006.) Finally, Gödel was found fit for military service by the Nazi government in 1939.

All of these events were decisive in influencing his decision to leave Austria in 1940, when he and his wife Adele emigrated to the United States. This long and difficult episode in their life is recounted by John Dawson in his biography of Gödel called “Logical Dilemmas,” (Dawson 1997) as well as by Solomon Feferman in “Gödel’s Life and Work,” (Feferman 1986) to both of which the reader is referred.

Upon arrival Gödel took up an appointment as an ordinary member at the Institute for Advanced Study; he would become a permanent member of the Institute in 1946 and would be granted his professorship in 1953. (Gödel and his wife were granted American citizenship in April 1948.) He would remain at the Institute until his retirement in 1976. The Gödels never returned to Europe.

Gödel’s early years at the Institute were notable for his close friendship with his daily walking partner Albert Einstein, as well as for his turn to philosophy of mathematics, a field on which Gödel began to concentrate almost exclusively from about 1943. The initial period of his subsequent lifelong involvement with philosophy was a fruitful one (in terms of publications): in 1944 he published his first philosophical paper, entitled “On Russell’s Mathematical Logic” (Gödel 1944), and in 1947 he published his second, entitled “What is Cantor’s Continuum Hypothesis?” (Gödel 1947). In 1949 he published his third, entitled “A Remark on the Relationship between Relativity Theory and Idealistic Philosophy.” (Gödel 1949a). The latter paper coincided with results on rotating universes in relativity he had obtained in 1949, which were first published in an article entitled: “An Example of a New Type of Cosmological Solutions of Einstein’s Field Equations of Gravitation.” (Gödel 1949).

Among Gödel’s other significant philosophical works of the 1940s must be counted his 1941 lecture entitled “In What Sense is Intuitionistic Logic Constructive?” (Gödel *1941) in which the notion: “computable function of finite type” is introduced. A paper based on the ideas in the lecture entitled “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes,” was published only in 1958, and the interpretation of Heyting arithmetic into the quantifier free calculus T in it became known as the “Dialectica Interpretation,” after the journal in which the article was published (Gödel 1958). (For the revision of it from 1972, see Gödel 1995.) Finally the decade saw the beginning of Gödel’s intensive study of Leibniz, which, Gödel reports, occupied the period from 1943 to 1946. [ 4 ]

The 1950s saw a deepening of Gödel’s involvement with philosophy: In 1951 Gödel delivered a philosophical lecture at Brown University, usually referred to as the Gibbs Lecture, entitled “Some Basic Theorems on the Foundations of Mathematics and Their Philosophical Implications” (Gödel *1951). From 1953 to 1959 Gödel worked on a submission to the Schilpp volume on Rudolf Carnap entitled “Is Mathematics a Syntax of Language?” (Gödel *1953/9-III, Gödel *1953/9-V). Gödel published neither of these two important manuscripts in his lifetime, although both would appear on two lists which were found in the Gödel Nachlass, entitled “Was ich publizieren könnte.” (In English: “What I could publish.” Both manuscripts eventually appeared in Gödel 1995.) By the decade’s close Gödel developed a serious interest in phenomenology. [ 5 ]

Gödel’s final years are notable for his circulation of two manuscripts: “Some considerations leading to the probable conclusion that the true power of the continuum is ℵ 2 ,” (Gödel *1970a, *1970b) his attempt to derive the value of the continuum from the so-called scale axioms of Hausdorff, and his “Ontologischer Beweis,” (Gödel *1970) which he entrusted to Dana Scott in 1970 (though it appears to have been written earlier). Taken together, the two manuscripts are the fitting last words of someone who, in a fifty year involvement with mathematics and philosophy, pursued, or more precisely, sought the grounds for pursuing those two subjects under the single heading: “strenge Wissenschaft”—a turn of mind that had been in place from Gödel’s start in 1929, when at the age of twenty-three he opened his doctoral thesis with some philosophical remarks.

Gödel died in Princeton on January 14, 1978 at the age of 71. His death certificate records the cause of death as “starvation and inanition, due to personality disorder.” His wife Adele survived him by three years.

For further biographical material, see Gödel 1987, Kleene 1987, Kreisel 1980, Taussky-Todd 1987 and Yourgrau 2005.

2. Gödel’s Mathematical Work

Below is an examination of some of Gödel’s main contributions in logic and set theory. This treatment of Gödel’s technical work is not exhaustive, omitting discussion of Gödel’s work in physics and his work on the decision problem. These will be treated in the sequel to this entry.

For a complete chronology of Gödel’s work the reader is referred to that compiled by John Dawson in volume I of Gödel’s Collected Works (Gödel 1986, p. 37).

2.1 The Completeness Theorem

The completeness question for the first order predicate calculus was stated precisely and in print for the first time in 1928 by Hilbert and Ackermann in their text Grundzüge der theoretischen Logik (Hilbert and Ackermann 1928), a text with which Gödel would have been quite familiar. [ 6 ]

The question Hilbert and Ackermann pose is whether a certain explicitly given axiom system for the first order predicate calculus “…is complete in the sense that from it all logical formulas that are correct for each domain of individuals can be derived…” (van Heijenoort 1967, p. 48).

We give an outline of Gödel’s own proof in his doctoral thesis (Gödel 1929). An essential difference with earlier efforts (discussed below and elsewhere, e.g. in Zach 1999), is that Gödel defines meticulously all the relevant basic concepts.

A “logical expression” in Gödel’s terminology is a well-formed first order formula without identity. An expression is “refutable” if its negation is provable, “valid” if it is true in every interpretation and “satisfiable” if it is true in some interpretation. The Completeness Theorem is stated as follows:

Theorem 1 . Every valid logical expression is provable. Equivalently, every logical expression is either satisfiable or refutable.

Gödel’s proof calculus is that of Hilbert and Ackermann’s text. An expression is in normal form if all the quantifiers occur at the beginning. The degree of an expression or formula is the number of alternating blocks of quantifiers at the beginning of the formula, assumed to begin with universal quantifiers. Gödel shows that if the completeness theorem holds for formulas of degree k it must hold for formulas of degree k + 1. Thus the question of completeness reduces to formulas of degree 1. That is, it is to be shown that any normal formula ( Q )φ of degree 1 is either satisfiable or refutable, where “( Q )” stands for a (non-empty) block of universal quantifiers followed by a (possibly empty) block of existential ones.

Gödel defines a book-keeping device, a well-ordering of all tuples of variables arising from a need to satisfy φ as dictated by ( Q ). For example, if ( Q )φ is ∀ x 0 ∃ x 1 ψ( x 0 , x 1 ), we list the quantifier-free formulas ψ( x n , x n +1 ). (Or more precisely, finite conjunctions of these in increasing length. See below.) Then in any domain consisting of the values of the different x n , in which each ψ( x n , x n+1 ) is true, the sentence ( Q )φ is clearly true. A crucial lemma claims the provability, for each k , of the formula ( Q )φ → ( Q k )φ k , where the quantifier free formula φ k asserts the truth of ψ for all tuples up to the kth tuple of variables arising from ( Q ), and ( Q k )φ k is the existential closure of φ k . (See the example below where the definition of the φ k ′ s is given.) This lemma is the main step missing from the various earlier attempts at the proof due to Löwenheim and Skolem, and, in the context of the completeness theorem for first order logic, renders the connection between syntax and semantics completely explicit.

Let us consider an example of how a particular formula would be found to be either satisfiable or its negation provable, following Gödel’s method: Consider φ = ∀ x 0 ∃ x 1 ψ( x 0 , x 1 ), where ψ( x 0 , x 1 ) is quantifier-free. We show that this is either refutable or satisfiable. We make the following definitions:

φ 0 is the expression ψ( x 0 , x 1 ) φ 1 is the expression ψ( x 0 , x 1 ) ∧ ψ( x 1 , x 2 ) … φ n is the expression ψ( x 0 , x 1 ) ∧ …∧ ψ( x n , x n +1 ).

The crucial lemma, referred to above, shows that from φ we can derive for each n , ∃ x 0 …∃ x n +1 φ n .

Case 1: For some n , φ n is not satisfiable. Then, Gödel argued, using the already known completeness theorem for propositional logic, [ 7 ] that ¬φ n is provable, and hence so is ∀ x 0 ,…, x n +1 ¬φ n . Thus ¬∃ x 0 …∃ x n +1 φ n is provable and therefore the ¬φ is provable, i.e., φ is refutable in the Hilbert-Ackermann system. (Some partial results about propositional logic in addition to those already mentioned include the semantic completeness of the propositional calculus due to Post (1921), as well as a more general completeness theorem for the same due to Bernays in 1918; the latter appears in Bernays’ unpublished Habilitationsschrift of 1918; see also Bernays 1926.) Case 2: Each φ n is satisfiable. There are only finitely many possible models with universe { x 0 ,…, x n+1 }. Gödel orders them as a tree by defining a model M to be below a model M ′ if M is a submodel of M ′. In this way we obtain a tree which is finitely branching but infinite. By König’s Lemma there is an infinite branch B . (In the proof, Gödel explicitly constructs the branch given by König’s Lemma rather than citing it by name.) The union of the models on B forms a model M with universe { x 0 , x 1 ,…}. Since M satisfies each φ n , the original formula φ holds in M . So φ is satisfiable and we are done.

Note that the model, in the satisfiability case of Gödel’s proof, is always countable. Thus this proof of the Completeness Theorem gives also the Löweheim-Skolem Theorem (see below). Gödel extends the result to countably many formulas and to the case of first order logic with identity. He also proves the independence of the axioms.

In 1930 Gödel published the paper based on his thesis (Gödel 1930) notable also for the inclusion of the compactness theorem, which is only implicitly stated in the thesis. The theorem as stated by Gödel in Gödel 1930 is as follows: a countably infinite set of quantificational formulas is satisfiable if and only if every finite subset of those formulas is satisfiable. Gödel uses compactness to derive a generalization of the completeness theorem.

The Compactness Theorem was extended to the case of uncountable vocabularies by Maltsev in 1936 (see Mal’cev 1971), from which the Upward Löwenheim-Skolem theorem immediately follows. The Compactness Theorem would become one of the main tools in the then fledgling subject of model theory.

A theory is said to be categorical if it has only one model up to isomorphism; it is λ-categorical if it has only one model of cardinality λ, up to isomorphism. One of the main consequences of the completeness theorem is that categoricity fails for Peano arithmetic and for Zermelo-Fraenkel set theory.

In detail, regarding the first order Peano axioms (henceforth PA ), the existence of non-standard models of them actually follows from completeness together with compactness. One constructs these models, which contain infinitely large integers, as follows: add a new constant symbol c to the language of arithmetic. Extend PA to a new theory PA * by adding to it the infinite collection of axioms: { c > 0 , c > 1 , …}, where, e.g., 3 is S(S(S(0))). PA * is finitely consistent (i.e., every finite subset of PA * is consistent) hence consistent, hence by the Completeness Theorem it has a model.

This simple fact about models of Peano arithmetic was not pointed out by Gödel in any of the publications connected with the Completeness Theorem from that time, and it seems not to have been noticed by the general logic community until much later. Skolem’s definable ultrapower construction from 1933 (see Skolem 1933) gives a direct construction of a non-standard model of True Arithmetic (which extends Peano arithmetic, being the set of arithmetic sentences true in the natural numbers). But Skolem never mentions the fact that the existence of such models follows from the completeness and compactness theorems. Gödel in his review (1934c) of Skolem’s paper also does not mention this fact, rather observing that the failure of categoricity for arithmetic follows from the incompleteness theorem.

As for set theory, the failure of categoricity was already taken note of by Skolem in 1923, because it follows from the Löwenheim-Skolem Theorem (which Skolem arrived at that year; see Skolem 1923, based on Löwenheim 1915 and Skolem 1920): any first order theory in a countable language that has a model has a countable model.

Skolem’s observation that categoricity fails for set theory because it has countable models is now known as the Skolem paradox. [ 8 ] The observation is strongly emphasized in Skolem’s paper, which is accordingly entitled ‘An Observation on the Axiomatic Foundations of Set Theory’ As he wrote in the conclusion of it, he had not pointed out the relativity in set theory already in 1915 because:

… first, I have in the meantime been occupied with other problems; second, I believed that it was so clear that axiomatization in terms of sets was not a satisfactory ultimate foundation of mathematics that mathematicians would, for the most part, not be very much concerned with it. But in recent times I have seen to my surprise that so many mathematicians think that these axioms of set theory provide the ideal foundation for mathematics; therefore it seemed to me that the time had come to publish a critique. (English translation taken from van Heijenoort 1967, p. 300.)

As an aside, in the proof of the Löwenheim-Skolem theorem, specifically that part of the theorem in which one constructs a model for a satisfiable sentence, Löwenheim and Skolem’s tree construction was more or less the same as appears in Gödel’s thesis. In a 1967 letter to Hao Wang, Gödel takes note of the fact that his completeness proof had almost been obtained by Skolem in 1923. Though van Heijenoort and Dreben (Dreben and van Heijenoort 1986) remark that “Throughout much of the 1920s it was not semantic completeness but the decision problem for quantificational validity, a problem originating from the work of Schröder and Löwenheim, that was the dominant concern in studying quantification theory” (examples of such results would include the decision procedure for the first order monadic predicate calculus due to Behmann, (Behmann 1922)), according to Gödel, the reasons that Skolem did not obtain the complete proof are different and philosophically important, having to do with the then dominant bias against semantics and against infinitary methods:

The Completeness Theorem, mathematically, is indeed an almost trivial consequence of Skolem 1923. However, the fact is that, at that time, nobody (including Skolem himself) drew this conclusion neither from Skolem 1923 nor, as I did, from similar considerations of his own …This blindness (or prejudice, or whatever you may call it) of logicians is indeed surprising. But I think the explanation is not hard to find. It lies in the widespread lack, at that time, of the required epistemological attitude toward metamathematics and toward non-finitary reasoning. (Gödel 2003b).

The matter of Skolem’s contribution to the Completeness Theorem has been extensively discussed in van Atten and Kennedy 2009, as well as in van Atten 2005.

2.2 The Incompleteness Theorems

Gödel mentioned the possibility of the unsolvability of a question about the reals already in his 1929 thesis, in arguing against the formalist principle of Hilbert’s, that consistency is a criterion for existence. In fact, giving a finitary proof of the consistency of analysis was a key desideratum of what was then known as the Hilbert program, along with proving its completeness. Accordingly it was Gödel’s turn to these questions, especially the first, which led him to the two incompleteness theorems. (For a discussion of the Hilbert Program the reader is referred to the standard references: Sieg 1990, 1988, 1999; Mancosu 1998, Zach 2003, Tait 1981 and Tait 2002.)

The First Incompleteness Theorem provides a counterexample to completeness by exhibiting an arithmetic statement which is neither provable nor refutable in Peano arithmetic, though true in the standard model. The Second Incompleteness Theorem shows that the consistency of arithmetic cannot be proved in arithmetic itself. Thus Gödel’s theorems demonstrated the infeasibility of the Hilbert program, if it is to be characterized by those particular desiderata, consistency and completeness.

As an aside, von Neumann understood the two theorems this way, even before Gödel did. In fact von Neumann went much further in taking the view that they showed the infeasibility of classical mathematics altogether. As he wrote to Carnap in June of 1931:

Thus today I am of the opinion that 1. Gödel has shown the unrealizability of Hilbert’s program. 2. There is no more reason to reject intuitionism (if one disregards the aesthetic issue, which in practice will also for me be the decisive factor). Therefore I consider the state of the foundational discussion in Königsberg to be outdated, for Gödel’s fundamental discoveries have brought the question to a completely different level. [ 9 ]

And the previous fall von Neumann had written to Gödel in even stronger terms:

Thus, I think that your result has solved negatively the foundational question: there is no rigorous justification for classical mathematics. (Gödel 2003b, p. 339)

It would take Gödel himself a few years to see that those aspects of the Hilbert Program had been decisively refuted by his results (Mancosu 2004).

In his Logical Journey (Wang 1996) Hao Wang published the full text of material Gödel had written (at Wang’s request) about his discovery of the incompleteness theorems. This material had formed the basis of Wang’s “Some Facts about Kurt Gödel,” and was read and approved by Gödel:

In the summer of 1930 I began to study the consistency problem of classical analysis. It is mysterious why Hilbert wanted to prove directly the consistency of analysis by finitary methods. I saw two distinguishable problems: to prove the consistency of number theory by finitary number theory and to prove the consistency of analysis by number theory … Since the domain of finitary number theory was not well-defined, I began by tackling the second half… I represented real numbers by predicates in number theory… and found that I had to use the concept of truth (for number theory) to verify the axioms of analysis. By an enumeration of symbols, sentences and proofs within the given system, I quickly discovered that the concept of arithmetic truth cannot be defined in arithmetic. If it were possible to define truth in the system itself, we would have something like the liar paradox, showing the system to be inconsistent… Note that this argument can be formalized to show the existence of undecidable propositions without giving any individual instances. (If there were no undecidable propositions, all (and only) true propositions would be provable within the system. But then we would have a contradiction.)… In contrast to truth, provability in a given formal system is an explicit combinatorial property of certain sentences of the system, which is formally specifiable by suitable elementary means…

We see that Gödel first tried to reduce the consistency problem for analysis to that of arithmetic. This seemed to require a truth definition for arithmetic, which in turn led to paradoxes, such as the Liar paradox (“This sentence is false”) and Berry’s paradox (“The least number not defined by an expression consisting of just fourteen English words”). Gödel then noticed that such paradoxes would not necessarily arise if truth were replaced by provability. But this means that arithmetic truth and arithmetic provability are not co-extensive — whence the First Incompleteness Theorem.

This account of Gödel’s discovery was told to Hao Wang very much after the fact; but in Gödel’s contemporary correspondence with Bernays and Zermelo, essentially the same description of his path to the theorems is given. (See Gödel 2003a and Gödel 2003b respectively.) From those accounts we see that the undefinability of truth in arithmetic, a result credited to Tarski, was likely obtained in some form by Gödel by 1931. But he neither publicized nor published the result; the biases logicians had expressed at the time concerning the notion of truth, biases which came vehemently to the fore when Tarski announced his results on the undefinability of truth in formal systems 1935, may have served as a deterrent to Gödel’s publication of that theorem.

We now describe the proof of the two theorems, formulating Gödel’s results in Peano arithmetic. Gödel himself used a system related to that defined in Principia Mathematica, but containing Peano arithmetic. In our presentation of the First and Second Incompleteness Theorems we refer to Peano arithmetic as P , following Gödel’s notation.

Before proceeding to the details of the formal proof, we define the notion of ω-consistency used by Gödel in the First Incompleteness Theorem: P is ω-consistent if P ⊢ ¬φ( n ) for all n implies P ⊬ ∃ x φ( x ). Naturally this implies consistency and follows from the assumption that the natural numbers satisfy the axioms of Peano arithmetic.

One of the main technical tools used in the proof is Gödel numbering , a mechanism which assigns natural numbers to terms and formulas of our formal theory P . There are different ways of doing this. The most common is based on the unique representation of natural numbers as products of powers of primes. Each symbol s of number theory is assigned a positive natural number #( s ) in a fixed but arbitrary way, e.g.

#(0) = 1 #(=) = 5 #(¬) = 9 #(1) = 2 #( ( ) = 6 #(∀) = 10 #(+) = 3 #( ) ) = 7 #( v i ) = 11 + i #(×) = 4 #(∧) = 8  

The natural number corresponding to a sequence w = < w 0 ,…, w k > of symbols is

⌈ w ⌉ = 2 #( w 0 ) · 3 #( w 1 ) · … · p k #( w k ) ,

where p k is the k +1st prime. It is called its Gödel number and denoted by ⌈ w ⌉ . In this way we can assign Gödel numbers to formulas, sequences of formulas (once a method for distinguishing when one formula ends and another begins has been adopted), and most notably, proofs.

An essential point here is that when a formula is construed as a natural number, then the numeral corresponding to that natural number can occur as the argument of a formula, thus enabling the syntax to “refer” to itself, so to speak (i.e., when a numeral is substituted into a formula the Gödel number of which the numeral represents). This will eventually allow Gödel to formalize the Liar paradox (with “provability” in place of “truth”) by substituting into the formula which says, ‘the formula, whose code is x , is unprovable,’ its own natural number code (or more precisely the corresponding numeral).

Another concept required to carry out the formalization is the concept of numeralwise expressibility of number theoretic predicates. A number-theoretic formula φ( n 1 , …, n k ) is numeralwise expressible in P if for each tuple of natural numbers ( n 1 , …, n k ):

N ⊨ φ( n 1 , …, n k ) ⇒ P ⊢ φ( n 1 , …, n k ) N ⊨ ¬φ( n 1 , …, n k ) ⇒ P ⊢ ¬φ( n 1 , …, n k )

where n is the formal term which denotes the natural number n . (In P , this is S ( S (… S (0)…), where n is the number of iterations of the successor function applied to the constant symbol 0.) One of the principal goals is to numeralwise express the predicate

Prf( x , y ): ‘the sequence with Gödel number x is a proof of the sentence with Gödel number y .’

Reaching this goal involves defining forty-five relations, each defined in terms of the preceding ones. These relations are all primitive recursive. [ 10 ] Relations needed are, among others, those which assert of a natural number that it codes a sequence, or a formula, or an axiom, or that it is the code, denoted by Sb( r u 1 … u n Z ( x 1 )… Z ( x n ) ), of a formula obtained from a formula with code r by substituting for its free variable u i the x i th numeral for i = 1, …, n . The forty-fifth primitive recursive relation defined is Prf( x , y ), and the forty-sixth is

Prov( y ): ‘the sentence with Gödel number y is provable in P ’

which without being primitive recursive, is however obtained from Prf( x , y ) by existentially quantifying x . (Prov( y ) satisfies only the ‘positive’ part of numeralwise expressibility, and not the negative part; but the negative part is not needed.)

In Theorem V of his paper, Gödel proves that any number theoretic predicate which is primitive recursive is numeralwise expressible in P . Thus since Prf( x , y ) and substitution are primitive recursive, these are decided by P when closed terms are substituted for the free variables x and y . This is the heart of the matter as we will see. Another key point about numeralwise expressibility is that although we informally interpret, for example, Prov(Sb( r u 1 … u n Z ( x 1 )… Z ( x n ) )), by: ‘the formula with Gödel number r is provable if the Gödel number for the x i th numeral is substituted in place of the i th variable,’ neither the formal statement within the theory P nor anything we prove about it appeals to such meanings. On the contrary Prov(Sb( r u 1 … u n Z ( x 1 )… Z ( x n ) )), is a meaningless string of logical and arithmetical symbols. As Gödel puts it in his introduction to his theorem V, ‘The fact that can be formulated vaguely by saying that every recursive relation is definable in the system P (if the usual meaning is given to the formulas of this system) is expressed in precise language, without reference to any interpretation of the formulas of P , by the following Theorem (V) (Gödel 1986, p. 171, italics Gödel’s).

Gödel in his incompleteness theorems uses a method given in what is called nowadays Gödel’s Fixed Point Theorem. Although Gödel constructs a fixed point in the course of proving the incompleteness theorem, he does not state the fixed point theorem explicitly. The fixed point theorem is as follows:

Theorem 2 (Gödel’s Fixed Point Theorem) If φ( v 0 ) is a formula of number theory, then there is a sentence ψ such that P ⊢ ψ ↔ φ( ⌈ ψ ⌉ ), where ⌈ ψ ⌉ is the formal term corresponding to the natural number code of ⌈ ψ ⌉ . Proof: Let σ( x , y , z ) be a formula that numeralwise expresses the number theoretic predicate ‘ y is the Gödel number of the formula obtained by replacing the variable v 0 in the formula whose Gödel number is x by the term z ’. Let θ( v 0 ) be the formula ∃ v 1 (φ( v 1 ) ∧ σ( v 0 , v 1 , v 0 )). Let k = ⌈ θ( v 0 ) ⌉ and ψ = θ( k ). Now directly by the construction P ⊢ ψ ↔ φ( ⌈ ψ ⌉ ).

A sentence is refutable from a theory if its negation is provable. The First Incompleteness Theorem as Gödel stated it is as follows:

Theorem 3 (Gödel’s First Incompleteness Theorem) If P is ω-consistent, then there is a sentence which is neither provable nor refutable from P . Proof: By judicious coding of syntax referred to above, write a formula Prf( x , y ) [ 11 ] of number theory, representable in P , so that n codes a proof of φ ⇒ P ⊢ Prf( n , ⌈ φ ⌉ ). and n does not code a proof of φ ⇒ P ⊢ ¬Prf( n , ⌈ φ ⌉ ). Let Prov( y ) denote the formula ∃ x Prf( x , y ) [ 12 ] . By Theorem 2 there is a sentence φ with the property P ⊢ (φ ↔ ¬Prov( ⌈ φ ⌉ )). Thus φ says ‘I am not provable.’ We now observe, if P ⊢ φ, then by (1) there is n such that P ⊢ Prf( n , ⌈ φ ⌉ ), hence P ⊢ Prov( ⌈ φ ⌉ ), hence, by (3) P ⊢ ¬φ, so P is inconsistent. Thus P ⊬ φ Furthermore, by (4) and (2), we have P ⊢ ¬Prf( n , ⌈ φ ⌉ ) for all natural numbers n . By ω-consistency P ⊬ ∃ x Prf( x , ⌈ φ ⌉ ). Thus (3) gives P ⊬ ¬φ. We have shown that if P is ω-consistent, then φ is independent of P .

On concluding the proof of the first theorem, Gödel remarks, “we can readily see that the proof just given is constructive; that is … proved in an intuitionistically unobjectionable manner…” (Gödel 1986, p. 177). This is because, as he points out, all the existential statements are based on his theorem V (giving the numeralwise expressibility of primitive recursive relations), which is intuitionistically unobjectionable.

The Second Incompleteness Theorem establishes the unprovability, in number theory, of the consistency of number theory. First we have to write down a number-theoretic formula that expresses the consistency of the axioms. This is surprisingly simple. We just let Con( P ) be the sentence ¬Prov( ⌈ 0 = 1 ⌉ ).

Theorem 4 (Gödel’s Second Incompleteness Theorem) If P is consistent, then Con( P ) is not provable from P . Proof: Let φ be as in (3). The reasoning used to infer ‘if P ⊢ φ, then P ⊢ 0 ≠ 1‘ does not go beyond elementary number theory, and can therefore, albeit with a lot of effort (see below), be formalized in P . This yields: P ⊢ (Prov( ⌈ φ ⌉ ) → ¬Con( P )), and thus by (3), P ⊢ (Con( P ) → φ). Since P ⊬ φ, we must have P ⊬ Con( P ).

The above proof (sketch) of the Second Incompleteness Theorem is deceptively simple as it avoids the formalization. A rigorous proof would have to establish the proof of ‘if P ⊢ φ, then P ⊢ 0 ≠ 1’ in P .

It is noteworthy that ω-consistency is not needed in the proof of Gödel’s Second Incompleteness Theorem. Also note that neither is ¬Con( P ) provable, by the consistency of P and the fact, now known as Löb’s theorem, that P ⊢ Prov( ⌈ φ ⌉ ) implies P ⊢ φ.

The assumption of ω-consistency in the First Incompleteness Theorem was eliminated by Rosser in 1936, and replaced by the weaker notion of consistency. Rosser’s generalization involves applying the fixed point theorem to the formula R ( x ): ‘for all z : either z is not the Gödel number of a proof of the formula with Gödel number x or there is a proof shorter than z of the negation of (the formula with Gödel number) x ’ (see Rosser 1936).

With regard to the Second Incompleteness Theorem, the argument relies in part on formalizing the proof of the First Incompleteness Theorem as we saw. This step is omitted in Gödel 1931. He planned to include the step in what would have been a second part II (see footnote 48a of Gödel 1931). But instead of writing it he turned to the continuum problem. [ 13 ] (Part II was to elaborate on other points too: the ‘true reason for incompleteness,’ and the applicability of the two theorems to other systems.) He perhaps did not feel compelled to attend to what looked like an exercise in formalization, relying instead on the informal argument to convince (in which it succeeded). However this step turned out to be somewhat non-trivial. As Kleene puts it in his introduction to Gödel 1931, of the informal presentation, “Certainly the idea of the argument for Theorem XI (consistency) was very convincing; but it turned out that the execution of the details required somewhat more work and care than had been anticipated.” (See pp. 126–141 of Gödel 1986.) Eventually a complete proof of the Second Theorem was given by Hilbert and Bernays in some seventy pages in their Hilbert and Bernays 1939. A much more compact treatment of the theorem was given by Löb in his Löb 1956, and subsequently Feferman, in his 1960 “Arithmetization of Metamathematics in a General Setting” (Feferman 1960/1961), gave a succinct and completely general treatment of both the First and Second Theorems. But see the supplementary document:

Did the Incompleteness Theorems Refute Hilbert’s Program?

For more detailed discussion, see the entry on Gödel’s incompleteness theorems .

Gödel’s 1936 ‘Speed-up’ theorem, published in an abstract “On the length of proofs”, Gödel 1936 says that while some sentences of arithmetic are true but unprovable, there are other sentences which are provable, but even the shortest proof is longer than any bound given in advance as a recursive function of the sentence. More exactly:

Theorem 5 . Given any recursive function f there are provable sentences φ of arithmetic such that the shortest proof is greater than f ( ⌈ φ ⌉ ) in length.

The proof we will outline is sensitive to the particular concept we use for the length of a proof. Another possibility, and the one that Gödel has in mind, is the number of formulas in the proof. Buss (see below) proves the theorem in either case, so both cases are resolved.

Proof: Let f be total recursive function. By Gödel’s Fixed Point theorem there is a formula φ( n ) stating ‘φ( n ) has no proof in PA shorter than f ( n )’. This is tenable if the length is measured by number of symbols, because we only need to search through finitely many proofs shorter than f ( n ). Note that φ( n ) is true for all n , for if φ( n ) were false, then there would be a short proof of φ( n ), and hence by soundness φ( n ) would be true, a contradiction: φ( n ) would both true and false. This can be formalized in PA and thus we get the result that for each n the sentence φ( n ) is provable in PA. Since φ( n ) is true for all n , it cannot have a proof in PA which is shorter than f ( n ).

The Speed-up Theorem is the result of contemplating and elaborating the proof of the incompleteness theorem. It applies the fixed-point technique to the concept of unprovability by a short proof, as opposed to the original idea of applying the fixed-point theorem to mere unprovability. The proof has very much the same flavor as the proof of the incompleteness theorem. Interestingly, it dates from the same year as the construction, due to Rosser, that eliminates the use of ω-consistency in the first Incompleteness Theorem; like the Speed-up Theorem of Gödel, Rosser’s construction exploits the issue of short and long proofs. Gödel never submitted a proof for the Speed-up Theorem. Over the years several related proofs were published, but the first full proof of Gödel’s original result was given only in 1994 by Sam Buss in his ‘On Gödel’s theorems on lengths of proofs I: Number of lines and speedups for arithmetic.’ (Buss 1994). Buss also gives a second proof of the theorem which avoids self-reference, following a technique due to Statman. Gödel measures the length of proofs by the number of formulas; but there are also other possibilities, such as the number of symbols in the proof. The case of the Speed-up Theorem where the length of proof is measured by the number of symbols was proved by Mostowski in 1952 (Mostowski 1982). For proofs of similar results see Ehrenfeucht and Mycieleski 1971, and Parikh 1971. Though both measures may be equally natural candidates for measuring the length of a proof, proving the theorem for length measured by the number of symbols avoids a technical complication introduced by the other measure: there are only finitely many proofs with a given number of symbols, whereas there are infinitely many proofs with a given number of formulas.

Gödel states the Speed-up Theorem differently from the above. Let S n be the system of logic of the n -th order, the variables of the first level being thought of as ranging over natural numbers. In this setting, variables of the second level range over sets of natural numbers and so on. Gödel’s formulation is:

Theorem 6 . Let n be a natural number > 0. If f is a computable function, then there are infinitely many formulas A , provable in S n , such that if k is the length of the shortest proof of A in S n and l is the length of the shortest proof of A in S n +1 , then k > f ( l ). Proof sketch: The idea is the following: Let φ( x ) be a formula, like above, for which φ( m ) does not have a short proof in S n for any m . Suppose we have a higher type system S n +1 in which we can prove ∀ x φ( x ). This proof is of constant length. Thus each φ( m ) is derivable from this universal statement by one application of the logical rule ∀ x φ( x ) → φ( t ). Thus φ( m ) has in that system for all m a short proof.

What kind of stronger system can we have in which ∀ x φ( x ) is provable? We may consider second order logic in which we can define a predicate N ( x ) for the set of natural numbers and furthermore can prove of a new predicate symbol Tr ( x ) that it satisfies the inductive clauses of the truth definition of first order formulas of arithmetic, relativized to N . Then the stronger system can prove that provable first order sentences of arithmetic satisfy the predicate Tr . By the above argument, we can prove in the stronger system that ∀ x φ( x ) satisfies Tr . Then by adding a few lines we can prove each φ( n ) satisfies Tr . Because of the nature of φ( n ), this implies the stronger system has a (short) proof of φ( n ). An alternative system is Peano’s axioms PA in an extended language where we have a new predicate symbol Tr and axioms stating that the predicate Tr codes the satisfaction relation for all sentences of the vocabulary not containing Tr .

2.4 Gödel’s Work in Set theory

Gödel’s proof of the consistency of the continuum hypothesis with the axioms of Zermelo-Fraenkel set theory is a tour de force and arguably the greatest achievement of his mathematical life. This is because aside from the arithmetization, virtually all of the technical machinery used in the proof had to be invented ab initio.

The Continuum Hypothesis (henceforth CH ) was formulated by Georg Cantor, and was the first problem on Hilbert’s list of twenty-three unsolved problems as given in his famous address to the International Mathematical Congress in Paris in 1900. The problem as stated by Hilbert is as follows: Let A be an infinite set of real numbers. Then A is either countable, or has cardinality 2 ℵ 0 , i.e., A is in one-to-one correspondence either with the set of natural numbers or with the set of all real numbers (otherwise known as the continuum). Another way to state the continuum hypothesis is that (the first uncountably infinite cardinal) ℵ 1 = 2 ℵ 0 .

As early as 1922 Skolem speculated that the CH was independent of the axioms for set theory given by Zermelo in 1908. Nevertheless Hilbert published a (false) proof of the CH in Hilbert 1926. In 1937 Gödel proved its consistency with the axioms of ZF set theory. (Henceforth we use the standard abbreviations for Zermelo-Fraenkel set theory, ZF , and Zermelo-Fraenkel set theory with the Axiom of Choice, ZFC .) The consistency of the negation of the CH was shown by Paul Cohen in 1961 (see Cohen 1963) and hence together with Gödel’s result one infers that the CH is independent of ZF (and ZFC ).

Cohen invented an important new technique called forcing in the course of proving his result; this technique is at present the main method used to construct models of set theory. Forcing led to a revival of formalism among set theorists, the plurality of models being an indication of the “essential variability in set theory,” (Dehornoy 2004) and away from the notion that there is an intended model of set theory—a perspective Gödel advocated since at least 1947, if not earlier. [ 14 ] Recently there have been signs that the CH may again be coming to be regarded as a problem to be solved mathematically (with the help of course of some new evident axioms extending ZF). (See for example Woodin 2001a, 2002, 2001b, and Foreman 1998.) If any of the proposed solutions gain acceptance, this would confirm Gödel’s view that the CH would eventually be decided by finding an evident extension of the ZF axioms for set theory. The program associated with this view is called “Gödel’s Large Cardinal Program.”

The continuum problem is shown to be consistent with ZF by finding an enumeration of the reals which is indexed by the countable ordinals, a strategy which had been recognized as a promising one already by Hilbert. [ 15 ] The problem, and the intuition behind the proof, is to build a “small” model, one in which the absolute minimum number of reals is allowed, while at the same time the model is large enough to be closed under all the operations the ZF axioms assert to exist.

Gödel’s is a relative consistency proof, obtained by constructing a so-called “inner model” for ZF together with the CH . An inner model is a subcollection M of the collection V of all sets (see below) which satisfies the axioms of ZF when only sets in M are considered. Gödel’s inner model is called the inner model of constructible sets (see below) and is denoted by L . Whatever is true in an inner model is consistent with ZF for the same reason that any theory with a model is consistent. An artifact of the construction is that the Axiom of Choice (henceforth AC ) is satisfied in Gödel’s inner model and hence the consistency of the AC with ZF was established by Gödel. Later on it was shown by Sierpinski that the AC is actually a consequence of the Generalized Continuum Hypothesis or the GCH, which states that for each κ, 2 κ = κ + (see Sierpinski 1947).

Gödel published two versions of these theorems, in 1939 and in 1940, entitled “Consistency Proof for the Generalized Continuum Hypothesis,” and “The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory,” respectively. Though completely definitive, the 1939 version is lacking in a great many details, most notably the arguments showing that if L is built inside L itself, the same L results; that is to say, the so-called absoluteness arguments are missing. Also missing are the details of the proofs that the ZF axioms hold in L . Unlike the case of the Second Incompleteness Theorem, however, Gödel subsequently gave a completely detailed proof of the two theorems in the 1940 monograph. (The 1940 proof differs substantially from the first version. For details about the two proofs and the difference between them the reader is referred to Solovay 1990 and Kanamori 2006.)

We now sketch the proof of the consistency of CH and of AC with ZFC , using modern terminology. Some preliminary concepts before sketching the proof: We first define the stratified set theoretic universe, denoted V . ( V is also known as the cumulative hierarchy.) It is obtained by iteration of the power set operation (℘) beginning with the null set:

V 0 = ∅, V α+1 = ℘( V α ), V γ = ∪ β<γ V β ,

where α, β are any ordinals, γ is a limit ordinal and ℘( x ) denotes the power set of x . Finally

V = ∪ α∈ Ord V α ,

where Ord denotes the class of all ordinals.

The constructible hierarchy L is likewise defined by recursion on ordinals. But whereas the full power set operation is iterated to obtain the cumulative hierarchy, the levels of the constructible hierarchy are defined strictly predicatively, that is by including at the next level only those sets which are first order definable using parameters from the previous level. More exactly, let Def ( A ) denote the set of all subsets of A definable in the structure < A , ∈ > by first order formulas with parameters in A . (For more on definability see the entry on model theory in this encyclopedia.)

With this notation the constructible hierarchy is defined by induction over the ordinals as follows:

L 0 = ∅, L α+1 = Def ( L α ), L γ = ∪ α<γ L α , L = ∪ α∈ Ord L α ,

A set x is said to be constructible if x ∈ L . The axiom which states that all sets are constructible is denoted V = L and is called the Axiom of Constructibility. Note that L is a proper class and not a set; although as we will see, each L α is a set, and the predicate “ x is constructible” is actually a definable term of the language.

Our next task is to show that L is a model of ZF . A set or a class is transitive if elements of it are also subsets. By a meticulous transfinite induction, L α can be shown to be transitive for each α; and therefore so is L itself. This fact, together with the observation that some elementary closure properties hold in L [ 16 ] is enough to show that L is a model of ZF . (Indeed, as it turns out, L is the minimal transitive model of the ZF axioms containing all the ordinals, and is therefore in this sense canonical.)

In detail, proving that the ZF axioms, apart from the comprehension axiom, are true in L , amounts to showing that, roughly speaking, any set with a property P that a ZF axiom asserts to exist, can be seen to exist in L by considering the relativization P L of the property P to L . (A property P is relativized to an inner model M by replacing every quantifier ∃ x φ by ∃ x ( x ∈ M ∧ φ) and every quantifier ∀ x φ by ∀ x ( x ∈ M → φ).) As for the comprehension axiom, verifying it requires showing that the set asserted to exist is constructed at a particular successor level L α + 1 . Proving this requires an important principle of set theory which in modern terminology is called the Levy (or ZF ) Reflection Principle. This principle says that any statement in the language of ZF which is true in V is already true on some level of any continuously increasing hierarchy such as L . (For the history of this principle, see Kanamori 2006.) The Levy Reflection Principle gives the level α at which the elements of the set are all constructed. Gödel did not actually have the Levy Reflection Principle but used the argument behind the proof of the principle.

Once it is established that L is a model of ZF , one can now prove that both the CH and the AC hold in L . To this end, one first shows that the definition of L is absolute for L , where absoluteness is defined as follows: given a class M , a predicate P ( x ) is said to be absolute for M if and only if for all x ∈ M , P ( x ) ↔ P M ( x ).

Proving that the predicate “ x is constructible” is absolute requires formalizing the notion of definability, which in turn requires formalizing the notion of satisfaction. This is because the predicate “ x is constructible” says of a set, that for some ordinal α, and for some formula φ with parameters in L α , x = { y ∈ L α | L α ⊨ φ( y )}. This part of the proof is tedious but unproblematic.

Once the absoluteness of L is established, it follows that ZF satisfies the axiom of constructibility if it is relativized to L ; that is, ZF ⊢ (V=L) L . In particular, the axiom V = L is consistent if ZF is.

We now give the idea of the proof of CH and AC in ZF + V = L . (For a detailed exposition of the proof, the reader is referred to the standard sources. See for example Devlin’s chapter on constructibility in Barwise 1977; see also Kunen 1983, and Jech 2003.)

As concerns the CH , the idea behind the proof of it in L is simply the following: Gödel showed that assuming V = L , every real number occurs on some countable level of the L -hierarchy. Since every countable level is itself countable (after all, there are only countably many possible defining formulas), and there are ω 1 countable levels, there must be only ω 1 real numbers.

The difficulty here, if not of the whole proof altogether, lies in showing that every real is constructed already on a countable level of the L -hierarchy. To show this Gödel argued as follows: Suppose A is a real number thought of as a set of natural numbers. By a combination of the Levy Reflection principle and the Löwenheim-Skolem Theorem there is a countable submodel < M , ∈ > of < L , ∈ > satisfying a sufficiently large finite part of the ZF axioms + V = L , such that A belongs to M . By a simple procedure < M , ∈ > can be converted into a transitive model < N , ∈ >. This procedure, used by Gödel already in 1937, was explicitly isolated by Mostowski (Mostowski 1949). The resulting model is referred to as the Mostowski Collapse.

Let us pause to discuss this important technique. Suppose < M , E > is a well-founded model of the axiom of extensionality. It is a consequence of the well-foundedness of the binary predicate E on M , and of the principle of transfinite recursion, that the equation π( x ) = {π( y ) |  y ∈ M ∧ yEx } defines a unique function on M . The range N of π is transitive, for if π( a ) ∈ N and y ∈ π( a ), then y = π( b ) for some b ∈ M with bEa , whence π( b ) ∈ N . The fact that π is an isomorphism between < M , E > and < N , ∈ > can be proved by transfinite induction on elements on M , based again on the well-foundedness of E . The well-foundedness of < M , E > is in practice often the consequence of < M , E > being a submodel of some < V α , ε >.

We now return to the proof of the CH in L . We used the Mostowski Collapse to construct the transitive set N . As it turns out, the real number A is still an element of < N , ∈ > . By basic properties of L , < N , ∈ > must be < L α , ∈ > for some α . Since N is countable, α is countable too. (It can be shown that | L α | = |α| + ℵ 0 .) Thus A is constructible on a countable level, which was to have been shown.

As for the AC , Gödel exhibits a definable well-ordering, that is, a formula of set theory which defines, in L , a well-ordering of all of L . The formula is tedious to write down but the idea is a simple one: A set x precedes a set y in the well-ordering if and only if either x occurs in the L -hierarchy on an earlier level L α than y , or else they occur on the same level but x is defined by a shorter formula than y , or else they are defined by the same formula but the parameters in the definition of x occur in L earlier than the parameters of y . This well-ordering of L shows that the AC holds in L .

This concludes the proof of the consistency of AC and the CH in L .

We note that Gödel proved more in his 1939 and 1940 than what was shown here, namely he proved the Generalized Continuum Hypothesis in L and hence that its consistency with ZF .

As noted above, it was suggested already in the 1920s that the CH might be independent of ZF or ZFC . After first conjecturing that the Axiom of Constructibility might be “absolutely consistent,” meaning not falsifiable by any further extension of models of ZF + V = L , [ 17 ] in his 1947 “What is Cantor’s Continuum Hypothesis?” Gödel conjectured that the CH would be shown to be independent. The main consequence of Gödel’s result, then, as far as the problem of proving the independence of the CH is concerned, was that it pointed mathematicians in the direction of adding non-constructible sets to a model of set theory in order to establish the consistency of the negation of the CH . In 1961 Dana Scott proved that the failure of the Axiom of Constructibility follows from the existence of a measurable cardinal, contrary to a conjecture Gödel had made in 1940. (See Scott 1961. A cardinal κ is said to be measurable if there is a non-principal κ-complete ultrafilter in the power-set Boolean algebra of κ.) In 1963, as noted, Paul Cohen proved the consistency of the negation of the CH by adding non-constructible sets to an inner model.

What other open questions of set theory could be solved by Gödel’s method? Gödel himself noted some consequences. They are related to so called projective sets of real numbers and finite sequences of real numbers. The simplest projective sets are the closed sets, also called Π 1 0 -sets. A set is Σ 1 n +1 if it is the projection of a Π 1 n -subset of the real plane. A set is Δ 1 n +1 if it and its complement are Σ 1 n +1 . Gödel observed that there is both a non-Lebesgue measurable Δ 1 2 -set and an uncountable Π 1 1 -set without a perfect subset in L . (A set of reals is perfect if it is closed, non-empty, and has no isolated points. Such sets have the size of the continuum.) Gödel gave a sketch of the proof in the 1951 second printing of Gödel 1940.

It has turned out subsequently that the axiom V = L gives a virtually complete extension of ZFC . This means that, apart from sentences arising from Gödel’s incompleteness theorems, essentially all set-theoretical questions can be decided by means of the axioms V = L . This is not to imply that such results are in any way trivial. Indeed, it has turned out that L is quite a complicated structure, despite its relatively simple description. As for settling open set-theoretical questions in L, the main step was the emergence of Jensen’s fine structure theory of L (Jensen 1972). Recalling that the successor step L α +1 in the definition of the constructible hierarchy adds to L all subsets of L α definable by first order formulas φ over ( L α , ∈), fine structure theory, roughly speaking, ramifies the step from L α to L α+1 into smaller steps according to the complexity of the defining formula φ. Jensen established by means of his fine structure a strengthening, denoted by ◊, of CH , that he used to construct a Souslin tree in L , and a combinatorial principle □ that he used to show that the Souslin Hypothesis is consistent with CH .

If he did not think this way from the outset, Gödel soon came to adopt the view that the Axiom of Constructibility was implausible. As he remarked at the end of his 1947 “What is Cantor’s Continuum Hypothesis?”

…it is very suspicious that, as against the numerous plausible propositions which imply the negation of the continuum hypothesis, not one plausible proposition is known which would imply the continuum hypothesis. (Gödel 1990, p. 186)

Gödel was compelled to this view of L by the Leibnizian [ 18 ] idea that, rather than the universe being “small,” that is, one with the minimum number of sets, it is more natural to think of the set theoretic universe as being as large as possible. [ 19 ] This idea would be reflected in his interest in maximality principles, i.e., principles which are meant to capture the intuitive idea that the universe of set theory is maximal in the sense that nothing can be added; and in his conviction that maximality principles would eventually settle statements like the CH . As Gödel put it in a letter to Ulam in the late 1950s, about a maximality principle of von Neumann:

The great interest which this axiom has lies in the fact that it is a maximality principle, somewhat similar to Hilbert’s axiom of completeness in geometry. For, roughly speaking, it says that any set which does not, in a certain well defined way, imply an inconsistency exists. Its being a maximum principle also explains the fact that this axiom implies the axiom of choice. I believe that the basic problems of set theory, such as Cantor’s continuum problem, will be solved satisfactorily only with the help of stronger axioms of this kind, which in a sense are opposite or complimentary to the constructivistic interpretation of mathematics. (Ulam 1958, as quoted in Gödel 1990, p. 168; original emphasis. Note that this is different from the very similar passage Gödel 2003b, p.295.)

Twenty years earlier, in 1938, Gödel had written seemingly differently about the Axiom of Constructibility:

The proposition A (i.e., V = L ) added as a new axiom seems to give a natural completion of the axioms of set theory, in so far as it determines the vague notion of an arbitrary infinite set in a definite way. (Gödel 1986, p.27)

Gödel may have meant by “natural completion” here “the correct completion,” or he may have meant to say no more than that the Axiom of Constructibility determines the notion of set in a definite way. In any case he used the term “natural” differently in a conversation with Wang on constructibility in 1972 (Wang 1996, p. 144):

Gödel talked more about the relation between axioms of infinity and the constructible universe…(he observed that) preliminary concepts such as that of constructible sets are necessary to arrive at the natural concept, such as that of set.

This is reminiscent of a remark of Hugh Woodin, that studying forcing leads to a better understanding of V — the general principle being that studying the models of a theory is not only useful to understand the theory itself, but useful to obtain a better picture of V (Woodin 1988).

For more on Gödel’s program and on Gödel’s program relative to the CH the reader is referred e.g., to Steel forthcoming and Feferman et al . 2000. For more on Gödel’s result, its history , and its significance the reader is referred to Floyd/Kanamori 2006 and Kennedy 2006.

2.5 Gödel’s Work in Intuitionistic Logic and Arithmetic

Gödel’s interest in intuitionism was deep and long-lasting. Although he himself did not subscribe to that view, he made a number of important contributions to intuitionistic logic. Perhaps the importance he placed on the concept of evidence (see below) led to his close consideration of it.

We discuss Gödel’s results on intuitionistic logic in their chronological order.

Both many-valued logic, introduced by Łukasiewicz in the twenties (Łukasiewicz 1970) and intuitionistic logic, formalized by Heyting in 1930, fail to satisfy the law of excluded middle. It was therefore natural to ask whether intuitionistic logic can be presented as a many-valued logic, and indeed a number of logicians in the 1920s had suggested just that. In his 1932 Gödel gave a simple argument which shows that intuitionistic propositional logic cannot be thought of as a finitely-valued logic. Precisely, Gödel proved two theorems:

Theorem 7 . There is no realization with finitely many elements (truth values) for which the formulas provable in H , and only those, are satisfied (that is, yield designated values for an arbitrary assignment).

( H is intuitionistic propositional logic, after Heyting.)

Theorem 8 . Infinitely many systems lie between H and the system A of the ordinary propositional calculus, that is, there is a monotonically decreasing sequence of systems all of which include H as a subset and are included in A as subsets.

In his proof he considered for each natural number n > 0 the sentence

F n = ∨ 1 ≤ i < j ≤ n p i ≡ p j .

He observed that in an n -valued logic the sentences F m , for m > n , should be derivable. However, Gödel showed, F n is not derivable from Heyting’s axioms for any n .

Subsequently Jaśkowski (Jaśkowski 1936) showed that intuitionistic propositional logic can be given a many-valued semantics in terms of infinitely many truth-values. For further discussion of many-valued logics, see for example the entry on many-valued logic in this encyclopedia as well as van Stigt’s article on intuitionistic logic in Mancosu 1998.

We now consider Gödel 1933e, in which Gödel showed, in effect, that intuitionistic or Heyting arithmetic is only apparently weaker than classical first-order arithmetic. This is because the latter can be interpreted within the former by means of a simple translation, and thus to be convinced of the consistency of classical arithmetic, it is enough to be convinced of the consistency of Heyting arithmetic. Heyting arithmetic is defined to be the same as classical arithmetic, except that the underlying predicate logic is given by intuitionistic axioms and rules of inference (see below).

This result extends the same assertion for the propositional case. Let H denote the intuitionistic propositional logic, and A denote its classical counterpart (as above). Inductively define:

A ′ ≡ ¬¬ A ( A atomic) (¬ A )′ ≡ ¬ A ′ ( A → B )′ ≡ ¬( A ′ ∧ ¬ B ′) ( A ∨ B )′ ≡ ¬(¬ A ′ ∧ ¬ B ′) ( A ∧ B )′ ≡ A ′ ∧ B ′

Theorem 9 . Let F be a propositional formula. Then H ⊢ F if and only if A ⊢ F ′,

The theorem follows easily from the result of Glivenko (1929) that ¬ F follows from H if and only if ¬ F follows from A , for any propositional formula F .

Gödel’s so-called double negation interpretation extends Theorem 9 to a reduction of classical first order logic to intuitionistic predicate logic. The translation in this case can be taken to map A ′ to A for atomic A . Moreover, we let ∀ xA ( x )′ = ∀ xA ′( x ) :

Theorem 10 . Suppose A is a first order formula. If A is provable in classical first order logic, then A ′ is provable in intuitionistic first order logic.

The above result had been obtained independently by Gentzen (with Bernays), but upon hearing of Gödel’s result Gentzen withdrew his paper from publication. It had also been anticipated by Kolmogorov in his 1925 “On the Principle of the Excluded Middle,” (English translation van Heijenoort 1967) but that paper was largely unknown to logicians who were outside of Kolmogorov’s circle.

Bernays has written (see Bernays’ entry on David Hilbert in Edwards 1967) that this result of Gödel’s drew the attention of the Hilbert school to two observations: first, that intuitionistic logic goes beyond finitism, and secondly, that finitist systems may not be the only acceptable ones from the foundational point of view.

The following theorem for the case of arithmetic follows from Theorem 10:

Theorem 11 . Suppose A is a first order formula of arithmetic. If A is provable in classical Peano arithmetic, then A ′ is provable in intuitionistic first order arithmetic.

For a list of the axioms and rules of intuitionistic first order logic see Gödel 1958, reprinted with detailed introductory note by A.S. Troelstra in Gödel 1990. See also Troelstra 1973, and Troelstra’s “Aspects of constructive mathematics” in Barwise 1977. For a detailed proof of the above theorem the reader is referred also to the latter.

This result of Gödel’s (Gödel 1933f), which marks the beginning of provability logic, makes exact the difference between the concept of “provability in a specified formal system” and that of “provability by any correct means.”

Gödel had already noted this difference in the introduction to his 1929 thesis. The context was the following: Gödel entertains there the possibility that his proof of the Completeness Theorem might be circular, since the law of excluded middle was used to prove it. This is because while the Completeness Theorem asserts ‘a kind of decidability,’ namely every quantificational formula is either provable or a counterexample to it can be given, ‘the principle of the excluded middle seems to express nothing other than the decidability of every problem’:

… what is affirmed (by the law of excluded middle) is the solvability not at all through specified means but only through all means that are in any way imaginable … [ 20 ]

Gödel considers intuitionistic propositional logic (henceforth IPL); he also considers a second system, classical propositional logic enriched by an operator “B”, where the intended meaning of “B” is “provable.” The axiom system now known as S4 (for a list of these axioms see for example the entry on modal logic in this encyclopedia) is added to the standard axioms for classical propositional logic together with a new rule of proof: from A , B A may be inferred. Let us call this second system G . Gödel’s theorem states that IPL is interpretable in G via the following translation:

¬ p ≡ ~B p p ⊃ q ≡ B p → B q p ∨ q ≡ B p ∨ B q p ∧ q ≡ B p ∧ B q

Theorem 12 . Let A be a formula of IPL , and let A ′ be its translation. Then IPL ⊢ A implies G ⊢ A ′.

Gödel conjectures that the converse implication must be true, and indeed this was shown in McKinsey and Tarski 1948.

The difference between the two notions of provability: “provable in a given formal system S ” and provability by any correct means — manifests itself as a consequence of Gödel’s Second Incompleteness Theorem, as follows. Let S contain Peano arithmetic, and let the operator B be interpreted as “provable in S ”. If the axioms of S4 were valid for this interpretations of B , then from B (0 ≠ 1) → (0 ≠ 1), the sentence ¬ B (0 ≠ 1) would be provable, contradicting the Second Incompleteness Theorem.

For further discussion of Gödel’s theorem, its antecedents and its extensions, as well as its philosophical significance, the reader is referred to A.S Troelstra’s introduction to 1933f .

Gödel’s so-called Dialectica intepretation (Gödel 1958) delivers a relative consistency proof and justification for Heyting arithmetic by means of a concrete interpretation involving a system T of computable functionals of finite type. Taken together with his 1933e, which reduces classical first order arithmetic to Heyting arithmetic, a justification in these terms is also obtained for classical first order arithmetic.

Gödel’s inductive definition of the notion “function of finite type” is as follows: (Gödel 1990, p. 245).

• The functionals of type 0 are the natural numbers.
• If t 0 ,…, t k are types and we have already defined what functionals of types t 0 ,…, t k are, then ( t 0 ,…, t k ) is a type and a functional of that type assigns to every k -tuple of functionals of respective types t 1 ,…, t k , a functional of type t 0 .

Gödel considers the quantifier free theory of these functionals of finite type, denoted by T . T has the following features: the language of T contains variables of each type, constants for distinguished types, and a ternary predicate = σ for equality for type σ. Equality between terms of the same type is decidable. The non-logical axioms and rules for T include the classical arithmetic axioms for 0 and successor, and the induction rule:

( F (0) ∧ ( F ( x 0 ) → F ( S ( x 0 )))) → F ( x 0 )

for quantifier-free formulas F ( x 0 ). As Gödel remarks (Gödel 1990, p. 247), the axioms for T are essentially those of primitive recursive arithmetic, except that the variables can be of any finite type.

Gödel’s translation associates with every formula F ( x ) of the language of Peano arithmetic a formula F ′( x ) = ∃ y ∀ z A ( y , z , x ) of the language of the theory T , where A is quantifier free and the (boldface) bound variables are finite sequences of variables thought to range over functionals of a finite type determined by the type of the variable. Intuitively, y is a concrete analogue of the abstract notion of a construction constituting the meaning of F .

Gödel’s theorem is as follows:

Theorem 13 . Suppose F ′ = ∃ y ∀ z A ( y , z , x ). If F is provable in intuitionistic first order arithmetic, then there are computable functionals Q of finite type such that A ( Q ( x ), z , x ) is provable in T .

The proof is by induction on the structure of the proof of F in intuitionistic first order arithmetic. (For a treatment of the proof in detail, the reader is referred to Troelstra 1986.)

The importance of the theorem for foundations cannot be overstated. [ 21 ] A discussion of its generalizations, of ensuing work on functional interpretations stimulated by the theorem due to Kreisel, Tait, Howard, Feferman and others; its foundational and philosophical significance; and finally its relation particularly to the earlier, informal, proof interpretation, so-called, given by Heyting-Kolmogorov, will not be attempted here. Accordingly the reader is referred to the large literature on the subject, e.g., the abovementioned Troelstra 1986, Tait 1967, Feferman 1993 and Avigad & Feferman 1998. For interesting recent developments, e.g., in the area of relating Gödel’s Dialectica interpretation and Kreisel’s modified realizability, see Oliva 2006. See also van Oosten 2008.

A remark concerning the philosophical context in which Gödel presented his translation, namely finitism. The question addressed in the introduction to the paper is what abstract notions must be added to finitary mathematics in order to obtain a consistency proof for arithmetic. Equivalently: what does the finitary view presuppose, which must be given up in the light of the Second Incompleteness Theorem, if the consistency proof is to be obtained:

In any case Bernays’ remark teaches us to distinguish two components of the finitary attitude; namely, first, the constructive element, which consists in our being allowed to speak of mathematical objects only insofar as we can exhibit them or actually produce them by means of a construction; second, the specifically finitistic element, which makes the further demand that the objects about which we make statements, with which the constructions are carried out and which we obtain by means of these constructions, are ‘intuitive’, that is, are in the last analysis spatiotemporal arrangements of elements whose characteristics other than their identity or nonidentity are irrelevant.… It is the second requirement that must be dropped. This fact has hitherto been taken into account by our adjoining to finitary mathematics parts of intuitionistic logic and the theory of ordinals. In what follows we shall show that, for the consistency proof of number theory, we can use, instead, the notion of computable function of finite type on the natural numbers and certain rather elementary principles of construction for such functions. (Gödel 1990, p.245).

Aside from its technical contribution, then, Gödel’s 1958/72 is one of Gödel’s most important philosophical works; notable for its analysis of the nature of finitary mathematics, as well as its analysis of the notions of “intuitive,” as in “intuitive knowledge,” and that of abstract versus concrete evidence.

In the next section, we turn to Gödel’s philosophical views. But interested readers may wish to read a brief discussion about Gödel’s Nachlass, important source of philosophical material by Gödel:

3. Gödel’s Philosophical Views

Gödel’s philosophical views can be broadly characterized by two points of focus, or, in modern parlance, commitments. These are: realism, namely the belief that mathematics is a descriptive science in the way that the empirical sciences are. The second commitment is to a form of Leibnizian rationalism in philosophy; and in fact Gödel’s principal philosophical influences, in this regard particularly but also many others, were Leibniz, Kant and Husserl. (For further discussion of how these philosophers influenced Gödel, see van Atten and Kennedy 2003.)

The terms “Gödel’s realism” and “Gödel’s rationalism” must be prefaced with a disclaimer: there is no single view one could associate with each of these terms. Gödel’s realism underwent a complex development over time, in both the nature of its ontological claims as well as in Gödel’s level of commitment to those claims. Similarly Gödel’s rationalism underwent a complex development over time, from a tentative version of it at the beginning, to what was adjudged to be a fairly strong version of it in the 1950s. Around 1959 and for some time afterward Gödel fused his rationalistic program of developing exact philosophy with the phenomenological method as developed by Husserl.

We examine these two strains of Gödel’s thinking below:

Gödel’s rationalism has its roots in the Leibnizian thought that the world, not that which we immanently experience but that which itself gives rise to immanent experience, is perfect and beautiful, and therefore rational and ordered. Gödel’s justification of this belief rests partly on an inductive generalization from the perfection and beauty of mathematics:

Rationalism is connected with Platonism because it is directed to the conceptual aspect rather than toward the (real) world. One uses inductive evidence…Mathematics has a form of perfection…We may expect that the conceptual world is perfect, and, furthermore, that objective reality is beautiful, good, and perfect. (Wang 1996, 9.4.18) Our total reality and total experience are beautiful and meaningful—this is also a Leibnizian thought. We should judge reality by the little which we truly know of it. Since that part which conceptually we know fully turns out to be so beautiful, the real world of which we know so little should also be beautiful. (9.4.20)

Although the roots of Gödel’s belief in rationalism are metaphysical in nature, his long-standing aspirations in that domain had always been practical ones. Namely, to develop exact methods in philosophy; to transform it into an exact science, or strenge Wissenschaft , to use Husserl’s term.

What this means in practice is taking the strictest view possible of what constitutes the dialectical grounds for the acceptance of an assertion; put another way, a level of rigor is aspired to in philosophical arguments approaching that which is found in mathematical proofs. A formulation of the view—one which is somewhat phenomenologically colored (see below)—can be found in a document in the Gödel Nachlass. This is a fourteen item list Gödel drew up in about 1960, entitled “My Philosophical Viewpoint.” Two items on the list are relevant here:

• There are systematic methods for the solution of all problems (also art, etc.).
• There is a scientific (exact) philosophy and theology, which deals with concepts of the highest abstractness; and this is also most highly fruitful for science.

(The list was transcribed by Cheryl Dawson and was published in Wang 1996 , p. 316.)

Gödel’s earlier conception of rationalism refers to mathematical rigor and includes the concept of having a genuine proof, and is therefore in some sense a more radical one than that to which he would later subscribe. One can see it at work at the end of the Gibbs lecture, after a sequence of arguments in favor of realism are given:

Of course I do not claim that the foregoing considerations amount to a real proof of this view about the nature of mathematics. The most I could assert would be to have disproved the nominalistic view, which considers mathematics to consist solely in syntactical conventions and their consequences. Moreover, I have adduced some strong arguments against the more general view that mathematics is our own creation. There are, however, other alternatives to Platonism, in particular psychologism and Aristotelian realism. In order to establish Platonic realism, these theories would have to be disproved one after the other, and then it would have to be shown that they exhaust all possibilities. I am not in a position to do this now; however I would like to give some indications along these lines. (Gödel 1995, p. 321–2).

(For a penetrating analysis of this passage see Tait 2001.) Such an analysis must be based on conceptual analysis:

I am under the impression that after sufficient clarification of the concepts in question it will be possible to conduct these discussions with mathematical rigour and that the result will then be…that the Platonistic view is the only one tenable. (Gödel 1995, p. 322).

Along with the methodological component, as can be seen from the items on Gödel’s list, there was also an “optimistic” component to Gödel’s rationalism: once the appropriate methods have been developed, philosophical problems such as, for example, those in ethics (e.g., item 9 on the list is: “Formal rights comprise a real science.”) can be decisively solved. As for mathematical assertions, such as the Continuum Hypothesis in set theory, once conceptual analysis has been carried out in the right way, that is, once the basic concepts, such as that of “set,” have been completely clarified, the Continuum Hypothesis should be able to be decided.

Although at the time of the Gibbs lecture the analogy in Gödel’s mind between philosophical and mathematical reasoning may have been a very close one, Gödel’s view at other periods was that the envisaged methods will not be mathematical in nature. What was wanted was a general, informal science of conceptual analysis.

Philosophy is more general than science. Already the theory of concepts is more general than mathematics…True philosophy is precise but not specialized. Perhaps the reason why no progress is made in mathematics (and there are so many unsolved problems), is that one confines oneself to the ext[ensional]—thence also the feeling of disappointment in the case of many theories, e.g., propositional logic and formalisation altogether. (Wang 1996, 9.3.20, 9.3.21) [ 22 ]

(See notebook Max IV, p. 198 (Gödel Nachlaß, Firestone Library, Princeton, item 030090). Transcription Cheryl Dawson; translation from the German ours; amendment ours. Gödel’s dating of Max IV indicates that it is from May 1941 to April 1942. See also Gödel’s letter to Bernays, Gödel 2003a, p. 283.)

An important source for understanding Gödel’s advance toward a general theory of concepts are Gödel’s remarks on conceptual analysis published by Hao Wang in Logical Journey . In remark 8.6.10 for example, Gödel expresses the belief that extensionality fails for concepts, contrary to what he said in his 1944 “Russell’s Mathematical Logic,” a remark which he now wishes to retract:

I do not (no longer) believe that generally sameness of range is sufficient to exclude the distinctness of two concepts.

In some of Gödel’s later discussions another component of conceptual analysis emerges, namely the project of finding the so-called primitive terms or concepts, and their relations. These are roughly terms or concepts which comprise a theoretical “starting point,” on the basis of their meaning being completely definite and clear. For example, the concept of “the application of a concept to another concept” is a primitive term, along with “force”. (Wang 1996, 9.1.29).

He spoke to Wang about the general project in 1972:

Phenomenology is not the only approach. Another approach is to find a list of the main categories (e.g., causation, substance, action) and their interrelations, which, however, are to be arrived at phenomenologically. The task must be done in the right manner. (Wang 1996, 5.3.7).

Gödel spoke with Sue Toledo between 1972 and 1975 about the project of finding primitive terms, as well as other aspects of phenomenology. See Toledo 2011. We discuss Gödel’s involvement with phenomenology further in the supplementary document Gödel’s Turn to Phenomenology .

The judgement levied upon Gödel’s rationalism by contemporary philosophers was a harsh one. (See for example Gödel 1995, pp. 303–4). Nevertheless Gödel himself remained optimistic. As he commented to Wang:

It is not appropriate to say that philosophy as rigorous science is not realizable in the foreseeable future. Time is not the main factor; it can happen anytime when the right idea appears. (Wang 1996, 4.3.14).

Gödel concluded his 1944 on a similarly optimistic note.

Gödel’s realist views were formulated mostly in the context of the foundations of mathematics and set theory.

We referred above the list “What I believe,” thought to have been written in 1960 or thereabouts. Out of 14 items, only two refer to realism, remarks 10 and 12:

• Materialism is false.
• Concepts have an objective existence.

Gödel published his views on realism for the first time in his 1944. The following is one of his most quoted passages on the subject:

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. They are in the same sense necessary to obtain a satisfactory system of mathematics as physical bodies are necessary for a satisfactory theory of our sense perceptions and in both cases it is impossible to interpret the propositions one wants to assert about these entities as propositions about the “data,” i.e., in the latter case the actually occurring sense perceptions.

Gödel’s reference to the impossibility of interpreting empirical laws, or more precisely, instantiations of them—the statements “one wants to assert,”—as statements about sense perceptions, is likely an endorsement of the (then) contemporary critique of phenomenalism. The critique was based on the observation that sense data are so inextricably bound up with the conditions under which they are experienced, that no correspondence between statements about those and the statements “we want to assert” can be given (see Chisholm 1948 for example). More generally Gödel was against verificationism, namely the idea that the meaning of a statement is its mode of verification.

The analogical point in the first part of the passage was amplified by Gödel in the draft manuscript “Is Mathematics a Syntax of Language?”:

It is arbitrary to consider “This is red” an immediate datum, but not so to consider the proposition expressing modus ponens or complete induction (or perhaps some simpler propositions from which the latter follows). (Gödel 1995, p. 359)

Some writers have interpreted Gödel in this and similar passages pragmatically, attributing to him the view that because empirical statements are paradigmatic of successful reference, reference in the case of abstract concepts should be modelled causally. (See Maddy 1990.) Interpreting reference to abstract objects this way, it is argued, addresses the main difficulty associated with realism, the problem how we can come to have knowledge of abstract objects. Others have argued that Gödel had no paradigm case in mind; that for him both the empirical and the abstract case are either equally problematic, or equally unproblematic. (See Tait 1986.) The latter view is referred to as epistemological parity in van Atten and Kennedy 2003. (See also Kennedy and van Atten 2004.)

In his 1947 “What is Cantor’s Continuum Problem?”, Gödel expounds the view that in the case of meaningful propositions of mathematics, there is always a fact of the matter to be decided in a yes or no fashion. This is a direct consequence of realism, for if there exists a domain of mathematical objects or concepts, then any meaningful proposition concerning them must be either true or false. [ 23 ] The Continuum Hypothesis is Gödel’s example of a meaningful question. The concept “how many” leads “unambiguously” to a definite meaning of the hypothesis, and therefore it should be decidable—at least in principle. Most strikingly Gödel does not leave the matter there but goes on to offer a practical strategy for determining the value of the continuum, as well as the truth value of other axioms extending ZFC . Specifically, he offers two criteria for their decidability: the first involves conceptual analysis and is associated with Gödel’s rationalistic program. (See the above section on Gödel’s rationalism.) Secondly one must keep an eye on the so-called success of the axiom, as a check or indicator of which direction to look to for the solution of its truth. For example, Gödel notes in the paper that none of the consequences of the Axiom of Constructibility are very plausible. It is, then, likely false. See Maddy 2011 and Koellner 2014 for discussion of intrinsic vs extrinsic justifications for new axioms of set theory.

For further discussion of Gödel’s philosophical views see the supplementary documents:

Gödel’s Turn to Phenomenology

A Philosophical Argument About the Content of Mathematics

Primary Sources

The Gödel Nachlass is located at Firestone Library of Princeton University with the exception of Gödel’s preprint collection, which is housed at the library of the Institute for Advanced Study. The Nachlass itself is the property of the Institute but a microfilm copy of it may be purchased from Brill. All of Gödel’s published work, together with a large number of the unpublished material from the Nachlass, together with a selection of Gödel’s correspondence is published in Kurt Gödel, Collected Works, Volumes I-V .

• 1986, Collected Works. I: Publications 1929–1936 . S. Feferman, S. Kleene, G. Moore, R. Solovay, and J. van Heijenoort (eds.), Oxford: Oxford University Press.
• 1990, Collected Works. II: Publications 1938–1974 . S. Feferman, J. Dawson, S. Kleene, G. Moore, R. Solovay, and J. van Heijenoort (eds.), Oxford: Oxford University Press.
• 1995, Collected Works. III: Unpublished essays and lectures . S. Feferman, J. Dawson, S. Kleene, G. Moore, R. Solovay, and J. van Heijenoort (eds.), Oxford: Oxford University Press.
• 2003a, Collected Works. IV: Correspondence A-G . S. Feferman, J. Dawson, S. Kleene, G. Moore, R. Solovay, and J. van Heijenoort (eds.), Oxford: Oxford University Press.
• 2003b, Collected Works. V: Correspondence H-Z . S. Feferman, J. Dawson, S. Kleene, G. Moore, R. Solovay, and J. van Heijenoort (eds.), Oxford: Oxford University Press.
• Avigad, J. and S. Feferman, 1998, “Gödel’s Functional (‘Dialectica’) Interpretation”, in Handbook of Proof Theory (Studies in Logic and the Foundations of Mathematics, Volume 137), Samuel Buss (ed.), Amsterdam: North-Holland, pp. 337-405.
• Awodey, S. and A. W. Carus, 2010, “Gödel and Carnap”, in Kurt Gödel: Essays for his Centennial , Solomon Feferman, Charles Parsons & Stephen G. Simpson (eds.), Cambridge: Cambridge University Press.
• Baaz, M., and C. Papadimitriou, D.Scott, H. Putnam, and C. Harper (eds.), 2011, Kurt Gödel and the Foundations of Mathematics: Horizons of Truth , Cambridge: Cambridge University Press.
• Badesa, C., and P. Mancosu, and R. Zach, 2009, “The Development of Mathematical Logic from Russell to Tarski, 1900–1935”, in Leila Haaparanta (ed.), The History of Modern Logic . New York and Oxford: Oxford University Press:318–470..
• Barwise, Jon (ed.), 1977, Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics, Volume 90), Amsterdam: North-Holland Publishing Co.
• Behmann, Heinrich, 1922, “Beiträge, Algebra, Logik, insbesodere zum Entscheidungsproblem”, Mathematische Annalen , 86: 419–432.
• Benacerraf, P. and H. Putnam (eds.), 1983, Philosophy of Mathematics: Selected Readings , Cambridge: Cambridge University Press, 2nd edition.
• Bernays, Paul, 1926, “Axiomatische Untersuchung des Aussagen-Kalkuls der ‘Principia Mathematica’”, Mathematisches Zeitschrift , 25(1): 305–320.
• Bezboruah, A., and J.C. Sheperdson, 1976, “Gödel’s second incompleteness theorem for \(Q\)”, Journal of Symbolic Logic , 41 (2): 503–512.
• Bolzano, Bernard, 1969, Wissenschaftslehre , Sections 349–391, in Bernard Bolzano — Gesamtausgabe , Reihe I/Band 13, edited and with an introduction by Jan Berg, Stuttgart-Bad Cannstatt: Frommann Holzboog.
• Burgess, John, 2009, “”Intuitions of Three Kinds in Gödel’s Views on the Continuum“”, in Interpreting Gödel Kennedy, J. (ed.) Cambridge: Cambridge University Press, 2014.
• Buss, Samuel R., 1994, “On Gödel’s Theorems on Lengths of Proofs. I. Number of Lines and Speedup for Arithmetics”, Journal of Symbolic Logic , 59(3): 737–756.
• Chisholm, R., 1948, “The Problem of Empiricism”, The Journal of Philosophy , 45: 512–7.
• Cohen, Paul, 1963, “The Independence of the Continuum Hypothesis”, Proceedings of the National Academy of Sciences of the U.S.A. , 50: 1143–1148.
• Crocco, G., 2003, “Gödel, Carnap and the Fregean Heritage”, History and Philosophy of Logic , 27: 171–191.
• –––, 2006, “Gödel on Concepts”, Synthese , 137(1,2): 21–41.
• Dawson, Jr., John W., 1997, Logical dilemmas: The Life and Work of Kurt Gödel , Wellesley, MA: A. K. Peters, Ltd.
• Dehornoy, Patrick, 2004, “Progrès récents sur l’hypothèse du continu (d’après Woodin)”, Astérisque , 294: viii, 147–172.
• Detlefsen, Michael, 1986, Hilbert’s Program: An essay on mathematical instrumentalism , Dordrecht: D. Reidel.
• –––, 2001, “What Does Gödel’s Second theorem Say?”, Philosophia Mathemathica , 9(1): 37–71.
• –––, 2014, “Completeness and the Ends of Axiomatization”, in Interpreting Gödel , Kennedy, J. (ed.) Cambridge: Cambridge University Press, 2014.
• Dreben, B. and J. van Heijenoort, 1986, “Introductory Note to 1929, 1930 and 1930a”, in Gödel 1986, pp. 44–59.
• Edwards, Paul (ed.), 1967, The Encyclopedia of Philosophy , New York: MacMillan.
• Ehrenfeucht, A. and J. Mycielski, 1971, “Abbreviating Proofs by Adding New Axioms”, Bulletin of the American Mathematical Society , 77: 366–367.
• Feferman, Solomon, 1960/1961, “Arithmetization of Metamathematics in a General Setting”, Fundamenta Mathematicae , 49: 35–92.
• –––, 1993, “Gödel’s Dialectica Interpretation and Its Two-way Stretch”, in Computational Logic and Proof Theory (Lecture Notes in Computer Science, Volume 713), G. Gottlob, A. Leitsch, and D. Mundici (eds.), Berlin: Springer, pp. 23–40.
• –––, 1986, “Gödel’s Life and Work”, in Gödel 1986, pp. 1–34.
• –––, 1988, “Hilbert’s Program Relativized: Proof-Theoretical and Foundational Reductions”, Journal of Symbolic Logic , 53: 364–384.
• –––, 1996, “Proof Theory”, in The Encyclopedia of Philosophy Supplement , D. Borchrt (ed.), New York: MacMillan, pp. 466–469.
• Feferman, S., and H. Friedman, P. Maddy, and J. Steel, 2000, “Does Mathematics Need New Axioms?”, Bulletin of Symbolic Logic , 6(4): 401–446.
• Feferman, S., C. Parsons, and S. Simpson (eds.), 2010, Kurt Gödel: Essays for his Centennial (Lecture Notes in Logic, 33), Cambridge: Cambridge University Press.
• Feigl, H. and A. Blumberg, 1931, “Logical Positivism. A New Movement in European Philosophy”, Journal of Philosophy , 28: 281–296.
• Floyd, J. and A. Kanamori, 2006, “How Gödel Transformed Set Theory”, Notices of the American Mathematical Society , 53(4): 419–427.
• Folina, Janet, 2014, “Gödel on How to Have your Mathematics and Know it Too”, in Interpreting Gödel , Kennedy, J. (ed.) Cambridge: Cambridge University Press, 2014.
• Føllesdal, Dagfinn, 1995, “Gödel and Husserl”, in From Dedekind to Gödel (Synthese Library, Volume 251), J. Hintikka (ed.), Dordrecht, Boston: Kluwer, pp. 427–446.
• Foreman, Matthew, 1998, “Generic Large Cardinals: New Axioms for Mathematics?”, in Documenta Mathematica , Extra Volume, Proceedings of the International Congress of Mathematicians, II, pp. 11–21 [ available online (in compressed Postscript)].
• Franks, Curtis, 2009, “The Autonomy of Mathematical Knowledge: Hilbert’s Program Revisited”, Cambridge: Cambridge University Press.
• –––, 2011, “Stanley Tennenbaum’s Socrates”, in Set Theory, Arithmetic and Foundations of Mathematics: Theorems, Philosophies , Kennedy, J. and Kossak, R., (eds.), Lecture Notes in Logic, 36, Cambridge: Cambridge University Press, 2011.
• –––, 2014, “Logical Completeness, Form and Content: An Archaeology”, in Interpreting Gödel , Kennedy, J. (ed.) Cambridge: Cambridge University Press, 2014.
• Gaifman, H., 2000, “What Godel’s Incompleteness Result Does and Does Not Show”, Journal of Philosophy , 97 (8): 462–471.
• Garson, James, 2003, “Modal Logic”, in The Stanford Encyclopedia of Philosophy , Fall 2003 Edition, Edward N. Zalta (ed.), URL = < https://plato.stanford.edu/archives/fall2003/entries/logic-modal/ >.
• Glivenko, V., 1929, “Sur quelques points de la logique de m. Brouwer.”, Académie Royale de Belgique, Bulletin de la Classe des Sciences , 15: 183–188.
• Gottwald, Siegfried, 2004, “Many-valued Logic”, in The Stanford Encyclopedia of Philosophy , Winter 2004 Edition, Edward N. Zalta (ed.), URL = < https://plato.stanford.edu/archives/win2004/entries/logic-manyvalued/ >.
• Gödel, Rudolf, 1983, “History of the Gödel Family”, Susan Simonsin (trans.), in Weingartner and Schmetterer 1987, pp. 11–27.
• Hauser, Kai, 2006, “Gödel’s Program Revisited, Part 1: the Turn to Phenomenology”, Bulletin of Symbolic Logic , 12 (4): 529–590.
• Heyting, Arendt, 1930, “Die formalen Regeln der intuitionistischen Logik”, Sitzungsberichte der Preussischen Akademie der Wissenschaften, physikalisch-mathematische Klasse , II, pp. 42–56.
• Hilbert, David, 1926, “Über das Unendliche”, Mathematische Annalen , 95: 161–190.
• Hilbert, D. and W. Ackermann, 1928, Grundzüge der theoretischen Logik , Berlin: Springer-Verlag.
• Hilbert, D. and P. Bernays, 1934, Grundlagen der Mathematik , Volume 1, Berlin: Springer-Verlag.
• –––, 1939, Grundlagen der Mathematik , Volume II, Berlin: Springer-Verlag.
• Hodges, Wilfrid, 2005, “Model Theory”, in The Stanford Encyclopedia of Philosophy , Fall 2005 Edition, Edward N. Zalta (ed.), URL = < https://plato.stanford.edu/archives/fall2005/entries/model-theory/ >.
• Husserl, Edmund, 1911, “Philosophie als strenge Wissenschaft”, Logos , 1: 289–341.
• Jaśkowski, Stanisław, 1936, “Investigations into the System of Intuitionist Logic”, Studia Logica , 34(2) (1975): 117–120. (Translated by S. McCall from the French “Rechereches sur le système de la logique intuitioniste” in Actes du Congrés International de Philosophie Scientifique , Volume VI, Hermann, Paris, 1936, pp. 58–61.)
• Jech, Thomas, 2003, Set theory , (Springer Monographs in Mathematics), Berlin: Springer-Verlag. 3rd millennium edition, revised and expanded.
• Jensen, R. Björn, 1972, “The Fine Structure of the Constructible Hierarchy” (with a section by Jack Silver), Annals of Mathematical Logic , 4: 229–308; Erratum, 4 (1972): 443.
• Kanamori, Aki, 1996, “The Mathematical Development of Set theory from Cantor to Cohen.” Bulletin of Symbolic Logic , 2(1): 1–71.
• –––, 2006, “Levy and Set Theory”, Annals of Pure and Applied Logic , 140(3): 233–252.
• Kennedy, Juliette, 2006, “Incompleteness — A Book Review,” Notices of the American Mathematical Societ , 53(4): 448–455.
• –––, 2011, “Gödel’s Thesis: An Appreciation” in Kurt Gödel and the Foundations of Mathematics: Horizons of Truth , M. Baaz, C. Papadimitriou, D. Scott, H. Putnam, and C. Harper (eds.), Cambridge: Cambridge University Press 95–110.
• –––, 2013, “On Formalism Freeness: Implementing Gödel’s 1946 Princeton Bicentennial Lecture”, Bulletin of Symbolic Logic , 19(3): 351–393.
• –––, 2014, “Gödel’s 1946 Princeton Bicentennial Lecture: An Appreciation”, in Interpreting Gödel: Critical Essays , Cambridge: Cambridge University Press.
• Kennedy, Juliette (ed.), 2014, Interpreting Gödel: Critical Essays , Cambridge: Cambridge University Press.
• Kennedy, J. and van Atten, M., 2003, “On the Philosophical Development of Kurt Gödel”, Bulletin of Symbolic Logic , 9(4): 425–476. Reprinted in Kurt Gödel: Essays for his Centennial , Solomon Feferman, Charles Parsons and Stephen G. Simpson (eds.), Cambridge: Cambridge University Press.
• –––, 2004, “Gödel’s Modernism: On Set-theoretic Incompleteness”, Graduate Faculty Philosophy Journal , 25(2): 289–349. (See the Erratum in Graduate Faculty Philosophy Journal , 26(1) (2005), page facing contents.)
• –––, 2009, “Gödel’s Modernism: On Set-theoretic Incompleteness, Revisited”, in Logicism, Intuitionism and Formalism: What has become of them? , S. Linström, E. Palmgren, K. Segerberg, and V. Stoltenberg-Hansen (eds.), Berlin: Springer: 303–356.
• –––, 2009, “Gödel’s Logic”, in D. Gabbay and J. Woods (eds.), The Handbook of the History of Logic: Logic from Russell to Gödel , Volume 5, Amsterdam: Elsevier: 449–509.
• Kleene, S. C., 1987, “Gödel’s Impression on Students of Logic in the 1930s”, in Weingartner and Schmetterer 1987, pp. 49–64.
• Koellner, Peter, 2014, “Large Cardinals and Determinacy”, The Stanford Encyclopedia of Philosophy (Spring Edition), Edward N. Zalta (ed.), URL = < https://plato.stanford.edu/archives/spr2014/entries/large-cardinals-determinacy/ >.
• Kreisel, Georg, 1980, “Kurt Gödel, 28 April 1906 – 14 January 1978”, Biographical Memoirs of Fellows of the Royal Society , 26: 148–224. Corrigenda, 27 (1981): 697; further corrigenda, 28 (1982): 697.
• –––, 1988, “Review of Kurt Gödel: Collected works , Volume I”, Notre Dame Journal of Formal Logic , 29(1): 160–181.
• –––, 1990, “Review of Kurt Gödel: Collected Works , Volume II”, Notre Dame Journal of Formal Logic , 31(4): 602–641.
• –––, 1998, “Second Thoughts Around Some of Gödel’s Writings: A Non-academic Option”, Synthese , 114(1): 99–160.
• Kripke, Saul, 2009, “The collapse of the Hilbert program: why a system cannot prove its own 1-consistency”, Bulletin of Symbolic Logic , 15 (2): 229–231.
• Kunen, Kenneth, 1983, Set Theory: An Introduction to Independence Proofs , (Studies in Logic and the Foundations of Mathematics, Volume 102), Amsterdam: North-Holland Publishing Co. Reprint of the 1980 original.
• Löb, M. H., 1956, “Formal Systems of Constructive Mathematics”, Journal of Symbolic Logic , 21: 63–75.
• Löwenheim, L., 1915, “Über Möglichkeiten im Relativkalkül”, Mathematische Annalen , 76(4): 447–470.
• Łukasiewicz, Jan, 1970, Selected works , (Studies in Logic and the Foundations of Mathematics), L. Borkowski (ed.), Amsterdam: North-Holland Publishing Co.
• Maddy, Penelope, 1990, Realism in Mathematics , New York: Clarendon Press.
• Maddy, Penelope, 2011, Defending the Axioms , Oxford: Oxford University Press.
• Mal’cev, Anatoli Ivanovic, 1971, The Metamathematics of Algebraic Systems. Collected Papers: 1936–1967 (Studies in Logic and the Foundations of Mathematics, Volume 66), translated, edited, and provided with supplementary notes by Benjamin Franklin Wells, III, Amsterdam: North-Holland Publishing Co.
• Mancosu, Paolo, 1998, From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s , Oxford: Oxford University Press.
• –––, 2004, “Review of Kurt Gödel, Collected Works , Volumes IV and V”, Notre Dame Journal of Formal Logic , 45: 109–125.
• Martin, D.A., 2005, “Gödel’s Conceptual Realism”, Bulletin of Symbolic Logic , 11: 207–224.
• McKinsey, J. C. C. and A. Tarski, 1948, “Some Theorems About the Sentential Calculi of Lewis and Heyting”, Journal of Symbolic Logic , 13: 1–15.
• Mostowski, Andrzej, 1949, “An Undecidable Arithmetical Statement”, Fundamenta Mathematicae , 36: 143–164.
• –––, 1982, Sentences Undecidable in Formalized Arithmetic: An Exposition of the Theory of Kurt Gödel , Westport, CT: Greenwood Press. Reprint of the 1952 original.
• Oliva, Paulo, 2006, “Unifying Functional Interpretations”, Notre Dame Journal of Formal Logic , 47(2): 263–290.
• Parikh, Rohit, 1971, “Existence and Feasibility in Arithmetic”, Journal of Symbolic Logic , 36: 494–508.
• Parsons, Charles, 1995a, “Platonism and Mathematical Intuition in Kurt Gödel’s Thought”, Bulletin of Symbolic Logic , 1(1): 44–74.
• –––, 1995b, “Quine and Gödel on Analyticity”, in On Quine: New Essays , Cambridge: Cambridge University Press, pp. 297–313.
• –––, 2000, “Reason and Intuition”, Synthese , 125(3): 299–315.
• –––, 2002, “Realism and the Debate on Impredicativity, 1917–1944”, in Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman , (Lecture Notes in Logic, Volume 15), W. Sieg, R. Sommer, and C. Talcott (eds.), Urbana, IL: Association of Symbolic Logic, pp. 372–389.
• –––, 2010, “Gödel and Philosophical Idealism” Philosophia Mathematica , 18 (2): 166–192.
• –––, 2014, “Analyticity for Realists”, in Interpreting Gödel , Kennedy, J. (ed.) Cambridge: Cambridge University Press, 2014.
• Poonen, Bjorn, 2014, “Undecidable Problems: A Sampler”, in Interpreting Gödel: Critical Essays , Cambridge: Cambridge University Press.
• Post, Emil L., 1921, “Introduction to a General Theory of Elementary Propositions”, American Journal of Mathematics , 43(3): 163–185.
• Pudlák, Pavel, 1996, “On the lengths of proofs of consistency: a survey of results”, Annals of the Kurt Gödel Society , 2: 65-86.
• Raatikainen, P., 2005, “On the Philosophical Relevance of Gödel’s Incompleteness Theorems”, Revue Internationale de Philosophie , 59 (4): 513–534.
• Rogers, Jr., Hartley, 1967, Theory of Recursive Functions and Effective Computability , New York: McGraw-Hill Book Co.
• Rosser, J.B., 1936, “Extensions of Some Theorems of Gödel and Church”, Journal of Symbolic Logic , 1(3): 87–91.
• Scott, Dana, 1961, “Measurable Cardinals and Constructible Sets”, Bulleint de l’Academie Polonaise des Sciences (Série des Science, Mathématiques, Astronomiques et Physiques), 9: 521–524.
• Shelah, Saharon, 2014, “Reflecting on Logical Dreams”, in Interpreting Gödel: Critical Essays , Cambridge: Cambridge University Press.
• Sieg, Wilfried, 1988, “Hilbert’s Program Sixty Years Later”, Journal of Symbolic Logic , 53(2): 338–348.
• –––, 1990, “Relative Consistency and Accessible Domains”, Synthese , 84(2): 259–297.
• –––, 1999, “Hilbert’s Programs: 1917–1922”, Bulletin of Symbolic Logic , 5(1): 1–44.
• –––, 2006, “Gödel on Computability”, Philosophia Mathematica , 14: 189–207.
• Sierpinski, Wacław, 1947, “L’hypothèse généralisée du continu et l’axiome du choix”, Fundamenta Mathematicae , 34: 1–5.
• Sigmund, Karl, 2006, “Pictures at an Exhibition”, Notices of the American Mathematical Society , 53(4): 428–432.
• Skolem, Thoralf, 1920, “Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen”, Skrifter utgit av Videnskappsselskapet i Kristiania , I. Matematisk-naturvidenskabelig klasse , Number 4, pp. 1–36. Reprinted in Skolem 1970, pp. 103–136.
• –––, 1923, “Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre”, Matematikerkongressen i Helsingfors den 4–7 Juli 1922, Den femte skandinaviska matematikerkongressen, Redogörelse , Helsinki, pp. 217–232. Reprinted in Skolem 1970, pp. 137–152.
• –––, 1933, “Über die Unmöglichkeit einer vollständigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems”, Norsk Matematisk forenings skrifter , 10: 73–82.
• –––, 1970, Selected Works in Logic , Jens Erik Fenstad (ed.), Oslo: Universitetsforlaget.
• Smith, David Woodruff, 2005, “Phenomenology”, in The Stanford Encyclopedia of Philosophy (Winter Edition), Edward N. Zalta (ed.), URL = < https://plato.stanford.edu/archives/win2005/entries/phenomenology/ >.
• Solovay, Robert, 1990, “Introductory Note to 1938, 1939, 1939a, 1940”, in Gödel 1990, pp. 1–25.
• Steel, John, 2000, “Mathematics Needs New Axioms”, Bulletin of Symbolic Logic , 6(4): 422–433.
• Steel, John, 2014, “Gödel’s Program”, in Interpreting Gödel , Kennedy, J. (ed.) Cambridge: Cambridge University Press, 2014.
• Tait, William, 1967, “Intensional Interpretations of Functionals of Finite Type I,” Journal of Symbolic Logic , 32(2): 198–212.
• –––, 1981, “Finitism”, Journal of Philosophy , 78: 524–556. Reprinted in Tait 2005, pp. 21–42.
• –––, 1986, “Truth and Proof: The Platonism of Mathematics”, Synthese , 69(3): 341–370. Reprinted in Tait 2005, pp. 61–88.
• –––, 2001, “Gödel’s Unpublished Papers on Foundations of Mathematics”, Philosophia Mathematica , 9(1): 87–126. Reprinted in Tait 2005, pp. 276–313.
• –––, 2002, “Remarks on Finitism”, in Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman (Lecture Notes in Logic, Volume 15), W. Sieg, R. Sommer, and C. Talcott (eds.), Urbana, IL: Association of Symbolic Logic, pp. 410–419. Reprinted in Tait 2005, pp. 43–53.
• –––, 2005, The Provenance of Pure Reason: Essays in the Philosophy of Mathematics and its History (Logic and Computation in Philosophy), New York: Oxford University Press.
• –––, 2006, “Gödel’s correspondence on proof theory and constructive mathematics” Philosophia Mathematica , 14 (1): 76–111.
• –––, 2006, “Gödel’s interpretation of intuitionism”, Philosophia Mathematica , 14 (2): 208–228.
• Taussky-Todd, Olga, 1983, “Remembrances of Kurt Gödel”, in Weingartner and Schmetterer 1987, pp. 29–41.
• Tieszen, Richard, 1992, “Kurt Gödel and Phenomenology”, Philosophy of Science , 59(2): 176–194.
• –––, 2002, “Gödel and the Intuition of Concepts”, Synthese , 133 (3): 363–391.
• –––, 2005, Phenomenology, Logic and the Philosophy of Mathematics , Cambridge: Cambridge University Press.
• –––, 2011, After Gödel: Platonism and Rationalism in Mathematics and Logic , Oxford: Oxford University Press.
• Toledo, Sue, 2011, “Sue Toledo’s Notes of her Conversations with Kurt Gödel in 1972-5”, in Set Theory, Arithmetic and Foundations of Mathematics: Theorems, Philosophies (Lecture Notes in Logic, 36), Kennedy, J. and Kossak, R., (eds.), Cambridge: Cambridge University Press, forthcoming.
• Tragesser, Robert, 1977, Phenomenology and Logic , Ithaca: Cornell University Press.
• –––, 1984, Husserl and Realism in Logic and Mathematics , (Series: Modern European Philosophy), Cambridge: Cambridge University Press.
• –––, 1989, “Sense Perceptual Intuition, Mathematical Existence, and Logical Imagination”, Philosphia Mathematica , 4(2): 154–194.
• Troelstra, A. S., 1986, “Note to 1958 and 1972 ”, in Gödel 1990, pp. 217–241.
• Troelstra, A. S. (ed.), 1973, Metamathematical Investigation of Intuitionistic Arithmetic and Analysis , (Lecture Notes in Mathematics, Volume 344), Berlin: Springer-Verlag.
• Turing, A. M., 1937, “On Computable Numbers, with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society (Series 2), 42: 230–265.
• van Atten, Mark, 2005, “On Gödel’s Awareness of Skolem’s Helsinki Lecture”, History and Philosophy of Logic , 26(4): 321–326.
• –––, 2006, “Two Draft Letters from Gödel on Self-knowledge of Reason”, Philosophia Mathematica , 14(2): 255–261.
• –––, 2015, “Essays on Gödel’s Reception of Leibniz, Husserl and Brouwer”, Springer.
• van Heijenoort, J. (ed.), 1967, From Frege to Gödel: A sourcebook in mathematical logic, 1879–1931 , Cambridge, MA: Harvard University Press.
• van Oosten, Jaap, 2008, Realizability: An Introduction to its Categorical Side (Studies in Logic and Foundations of Mathematics: Volume 152), Amsterdam: Elsevier.
• von Neumann, John, 2005, John von Neumann: Selected Letters (History of Mathematics, Volume 27), foreword by P. Lax, introduction by Marina von Neumann Whitman, preface and introductory comments by Miklós Rédei (ed.), Providence, RI: American Mathematical Society.
• Väänänen, Jouko, 2014, “Multiverse Set Theory and Absolutely Undecidable Propositions”, in Interpreting Gödel , J. Kennedy (ed.), Cambridge: Cambridge University Press, 2014.
• Wang, Hao, 1957, “The Axiomatization of Arithmetic”, Journal of Symbolic Logic , 22: 145–158.
• –––, 1973, From Mathematics to Philosophy , London: Routledge.
• –––, 1981, “Some Facts about Kurt Gödel”, Journal of Symbolic Logic , 46(3): 653–659.
• –––, 1987, Reflections on Kurt Gödel , Cambridge, MA: MIT Press.
• –––, 1993, Popular Lectures on Mathematical Logic , New York: Dover Publications Inc., 2nd edition.
• –––, 1996, A Logical Lourney: From Gödel to Philosophy (Representation and Mind), Cambridge, MA: MIT Press.
• Weingartner, P., and L. Schmetterer (eds.), 1987, Gödel Remembered: Salzburg 10–12 July 1983 , (History of Logic, Number 4), Naples: Bibliopolis.
• Wilkie, Alex, and J.B. Paris, 1987, “On the scheme of induction for bounded arithmetic formulas”, 35: 261–302.
• Woodin, W. Hugh, 1988, “Supercompact Cardinals, Sets of Reals, and Weakly Homogeneous Trees”, Proceedings of the National Academy of Sciences of the U.S.A. , 85(18): 6587–6591.
• –––, 2001a, “The Continuum Hypothesis. I”, Notices of the American Mathematical Society , 48(6): 567–576.
• –––, 2001b, “The Continuum Hypothesis. II”, Notices of the American Mathematical Society , 48(7): 681–690.
• –––, 2002, “Correction: ‘The Continuum Hypothesis. II’”, Notices of the American Mathematical Society , 49(1): 46.
• Yourgrau, Palle, 2005, A World Without Time. The Forgotten Legacy of Gödel and Einstein , New York: Basic Books.
• Zach, Richard, 1999, “Completeness Before Post: Bernays, Hilbert, and the Development of Propositional Logic”, Bulletin of Symbolic Logic , 5(3): 331–366.
• –––, 2003, “Hilbert’s Program”, in The Stanford Encyclopedia of Philosophy (Fall Edition), Edward N. Zalta (ed.), URL = < https://plato.stanford.edu/archives/fall2003/entries/hilbert-program/ >.

How to cite this entry . Preview the PDF version of this entry at the Friends of the SEP Society . Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO). Enhanced bibliography for this entry at PhilPapers , with links to its database.

• Avigad, Jeremy, “ Gödel and the metamathematical tradition ”, manuscript in PDF available online.
• Koellner, Peter, “ Truth in Mathematics:The question of Pluralism ”, manuscript in PDF available online.
• The Bernays Project .

Gödel, Kurt: incompleteness theorems | Hilbert, David: program in the foundations of mathematics | Husserl, Edmund | Leibniz, Gottfried Wilhelm | mathematics, philosophy of: intuitionism | mathematics, philosophy of: Platonism | model theory | model theory: first-order | phenomenology | realism | set theory | set theory: continuum hypothesis | set theory: large cardinals and determinacy

Acknowledgments

This entry was very much improved by discussion and correspondence with the following: Aki Kanamori, who made helpful corrections and comments to section 2.4; Jouko Väänänen, whose expertise in all areas of mathematical logic the author benefited from in a great many invaluable discussions regarding the material in section 2; my sub-editor Richard Zach, whose many important and helpful suggestions led to a vast improvement of this entry, and an anonymous referee for helpful comments and corrections. The author is grateful to the NWO for their support during the last period of the writing of this entry, to the Institute for Advanced Study for their hospitality during the writing of this entry, and to Marcia Tucker of the IAS and the Rare Books and Special Collections department of Firestone Library for all of their assistance over the years .

Copyright © 2015 by Juliette Kennedy < juliette . kennedy @ helsinki . fi >

• Accessibility

Support SEP

Mirror sites.

View this site from another server:

• Info about mirror sites

The Stanford Encyclopedia of Philosophy is copyright © 2023 by The Metaphysics Research Lab , Department of Philosophy, Stanford University

Library of Congress Catalog Data: ISSN 1095-5054

• Architecture and Design
• Asian and Pacific Studies
• Business and Economics
• Classical and Ancient Near Eastern Studies
• Computer Sciences
• Cultural Studies
• Engineering
• General Interest
• Geosciences
• Industrial Chemistry
• Islamic and Middle Eastern Studies
• Jewish Studies
• Library and Information Science, Book Studies
• Life Sciences
• Linguistics and Semiotics
• Literary Studies
• Materials Sciences
• Mathematics
• Social Sciences
• Sports and Recreation
• Theology and Religion
• Publish your article
• The role of authors
• Promoting your article
• Abstracting & indexing
• Publishing Ethics
• Why publish with De Gruyter
• How to publish with De Gruyter
• Our book series
• Our subject areas
• Your digital product at De Gruyter
• Contribute to our reference works
• Product information
• Tools & resources
• Product Information
• Promotional Materials
• Orders and Inquiries
• FAQ for Library Suppliers and Book Sellers
• Repository Policy
• Free access policy
• Open Access agreements
• Database portals
• For Authors
• Customer service
• People + Culture
• Journal Management
• How to join us
• Working at De Gruyter
• Mission & Vision
• De Gruyter Foundation
• De Gruyter Ebound
• Our Responsibility
• Partner publishers

Your purchase has been completed. Your documents are now available to view.

Consistency of the Continuum Hypothesis. (AM-3), Volume 3

• X / Twitter

Please login or register with De Gruyter to order this product.

• Language: English
• Publisher: Princeton University Press
• Copyright year: 1941
• Audience: Professional and scholarly;College/higher education;
• Main content: 69
• Keywords: Axiom ; Theorem ; Propositional function ; Axiom of choice ; Existence theorem ; Axiom of infinity ; Ordinal number ; Set theory ; Continuum hypothesis ; Quantifier (logic) ; Axiom of extensionality ; Constructible set (topology) ; Boolean algebra (structure) ; Axiomatic system ; Mathematical induction ; Well-order ; Variable (mathematics) ; Absoluteness ; Transfinite induction ; Existential quantification ; Order by ; Transfinite ; Metatheorem ; Reductio ad absurdum ; Mathematical logic ; Requirement ; Addition ; Integer ; Mathematics
• Published: March 2, 2016
• ISBN: 9781400881635

The River Continuum Concept

At the end of the Rockefeller study , Stroud™ Water Research Center invited water researchers from across the country to a two-day conference. It was here that Stroud Center scientist Robin Vannote first presented his river continuum hypothesis that was to have a deep impact on aquatic studies.

“In those days,” he recalled years later, “most people studied a square meter of water to death.”

But, he told the assembled scientists, it is time to move beyond the notion that you can understand how a river works by studying a tiny piece of it.

A stream is fundamentally different from a lake, and you must consider how the entire system is functionally linked. Because a river changes constantly as it moves downstream, it can only truly be understood as a continuum.

As a young graduate student named Bern Sweeney remembered it, when Vannote outlined his seemingly simple notion, “the scientists gathered in that room were just in awe. It was a major, major event.”

From those early insights, Vannote, other Stroud Center staff and a few university colleagues developed the River Continuum Concept, which would revolutionize stream research.

The concept did not materialize out of thin air. Vannote had a voracious intellectual appetite, and his ideas were built on earlier work, both within and outside his field. There was a direct line to the 1948 Conestoga studies, in which Ruth Patrick had broken new ground with her insistence that the diverse biological communities inhabiting a stretch of stream make up a single mosaic. In their Rockefeller work two decades later, Stroud Center scientists established the importance of studying the entire watershed.

During the same period, noted geologist Luna Leopold was developing a formula for understanding a stream’s physical behavior. He saw that a river’s width, depth, velocity and temperature change constantly as the water flows downstream. More importantly, he recognized that those changes are interrelated — and because a change in one factor affects all the others, a river’s pattern is predictable.

Drawing on these earlier biological, chemical and physical studies, Vannote and his colleagues added a critical element to the puzzle of how streams work. They argued that a river’s biological and chemical processes correspond to its physical attributes, and that the nature of biological communities changes in a downstream direction just as the river itself does. This means that the structure of the biological communities is also predictable and that the communities adapt, as we saw in the last chapter, to the particular conditions of a stretch of stream.

A river is more than the sum of its parts, Vannote asserted. It is not a static body of water. It is a single continuum that flows ceaselessly from its source to the sea. To understand what is happening at any point along the way, you must understand both what is happening upstream and what is entering from the watershed.

The River Continuum Concept was the first unified hypothesis about how streams and their watersheds work. It dominated river studies for the next decade, and it established the Stroud Center as a pioneer in innovative research .

Subscribe to Freshwater E-News