43
$\begingroup$

As is known, Hilbert attempted a proof sketch of the Continuum Hypothesis in the latter part of his paper, "On the Infinite". It is also known that it is false.

Has there ever been a published analysis of this alleged proof showing where the error(s) lie(s)? In particular, does his 'proof' implicitly assume a form of $V=L$?

Thanks in advance for any help given.

$\endgroup$
43
$\begingroup$

The article "Hilbert and Set Theory" by Dreben and Kanamori devotes Section 7 to this argument and an analysis of its flaws. Dreben and Kanamori use the translation provided by van Heijenoort, so that helps things significantly if you have access to that book. I unfortunately don't at the moment; I might add to this answer once I find my copy, if I find anything else to say.

I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the modern sense (= computable); they considered a truly huge range of recursions, to the point that plausibly every function of natural numbers could be recursive in this sense.

According to Dreben and Kanamori, Hilbert's goal was to use proof theory to show that from any (formal) disproof of the continuum hypothesis, he could produce a proof of the continuum hypothesis. As Dreben and Kanamori observe, even if he could accomplish this he wouldn't have proved CH, merely the consistency of CH, but even this didn't work.

They isolate two crucial lemmas in Hilbert's claimed proof. The second lemma was a technical one, comparing forms of definition-by-recursion, and Dreben and Kanamori state that "there is a sense in which Hilbert's Lemma II is correct." The first lemma, however, is the crucial one, where Hilbert claims to be able to transform any disproof of CH into one which only invokes "$\epsilon$-free" definitions of functions - in more detail,

"functions defined, without the use of the symbol $\epsilon$, by means merely of ordinary and transfinite recursion, so that the transfinite appears only in the guise of the universal quantifier."

From Lemma I Hilbert concludes that

"in order to prove the continuum theorem, it is essential to correlate those definitions of number-theoretic functions that are free from the symbol $\epsilon$ one-to-one with [the countable ordinals]."

This represented a huge step forwards in recursion theory, at least in spirit: as Dreben and Kanamori write, "Hilbert was the first to consider number-theoretic functions defined through recursions more general than primitive recursion."

However, even assuming he could carry out the substitution claimed by Lemma I, his use of the lemma is flawed: why is it enough to consider only those functions which appear in claimed disproofs of CH? This wouldn't even establish consistency! But this was something Hilbert missed; according to Dreben and Kanamori,

Hilbert seems to have believed that there can be no number-theoretic functions unless definable in some formal proof.

Of course they go on to say more, but I think the above gives a good introduction to their discussion, which you should read for a full answer to the first part of your question.

In answer to the second - whether the argument could be salvaged and applied in, say, $L$ - I think the answer is that the proof that CH holds in $L$ could be viewed as a spiritual cousin of Hilbert's attempt, but Hilbert's ideas probably wouldn't get you all the way; and far more fundamentally, the need for an argument that $L$ satisfies ZFC is something that never occurred to Hilbert in any guise. Hilbert's assumption that "there can be no number-theoretic functions unless definable in some formal proof" can be weakened to "there is a model of ZFC in which there can be no number-theoretic functions unless definable in some formal proof," but of course even that would have to be proved.


EDIT: Let me elaborate on my last paragraph, specifically the sub-question:

To what extent can Hilbert's sketch be viewed as a precursor of Godel's proof of the consistency of ZFC+CH via $L$?

A closely related question is: what did Godel think about the two?

At least early on, Godel interpreted Hilbert's program quite generously, explicitly connecting it with his own proof(s) in two lectures (see below). Others did, too: for instance, Bernays, in his 1940 review of Godel's paper, wrote "The whole Godel reasoning may also be considered as a way of modifying the Hilbert project."

At the same time, though, this analogy - and its implicit interpretation of Hilbert's program - can be seriously criticized. Indeed, Godel's own opinion seems to have changed over time, as can be seen in his 1965 response to a letter from van Heijenoort quoting Bernays (to be found in the Collected Works); I'll quote from this below. In his introduction to the lectures in the Collected Works, Solovay is harsher: he argues that in fact Godel’s generous interpretation was "not only excessively generous but downright misleading." (Personally I find Solovay’s criticisms very on-point, but I might not go that far.)

So this is clearly a bit of a subtle question. In what follows I'll try to dig into Godel's original sympathetic interpretation a bit. Keep in mind that I am wildly unqualified to give an historical interpretation of Hilbert and Godel, but hey, this is the internet, that’s what it’s for.

(The relevant parts of the Collected Works are pages 114-155 and 175-189 of vol. 3. The lectures in question are a 1939 lecture in Gottingen and a 1940 lecture at Brown University; note that this was right after his proof, and at the same time as Bernays' comparison quoted above.)

Godel opened his 1940 lecture at Brown University by explicitly drawing the analogy between his arguments and Hilbert's: "If I want to sketch a proof for the consistency of Cantor's continuum hypothesis, I have a choice between many possibilities. Just recently I have succeeded in giving the proof a new shape which makes it somewhat similar to Hilbert's program presented in his lecture." During the lecture, he then repeatedly compares his approach to Hilbert's program, e.g. "The difference between this notion of recursiveness and the one that Hilbert seems to have had in mind is chiefly that I allow quantifiers to occur in the definiens."

The relevant passages in the 1940 lecture are brief. To get a better sense for Godel’s interpretation (at least stated) of Hilbert's sketch at the time, I think it’s valuable to quote a large section of Godel’s introduction to his 1939 lecture, mostly verbatim (pp. 129-130). And, to get at the criticisms of that interpretation, I’ll bold sections of the quote below that I take particular issue with, and say a bit about these at the end:

“As you know, the first to outline a program for a consistency proof of the continuum hypothesis was Hilbert … Let me remind you that, in a very broad outline, Hilbert’s program for proving this proposition consisted in the following: first, a certain class of functions of integers was singled out, namely, those that are defined recursively [recall my comment at the top of my answer re: this word in this context]. About these recursive functions, two lemmas were then to be proved; namely:

  • These recursively defined functions can be put in correspondence with the numbers of the second number class.

  • The other definitions that occur in mathematics, namely, those involving quantification, …, do not lead outside the domain of the recursively definable functions, or at any rate, one can consistently assume that they do not lead outside the domain of the recursively definable functions.

[At this point, compare with Dreben/Kanamori's summary of Hilbert's two lemmas.]

Thereby the proof of the first lemma, about the number of recursive functions, was to rest on the fact that in the recursive definitions of functions of natural numbers one can avoid variables of types higher than those of the second number class.

The proof on which I would like to report here is analogous to this program insofar as there is likewise singled out a certain class of functions, or, what comes to the same thing, of sets, which I call constructible sets. … Now likewise two things are shown about these constructible sets, namely:

  • The cardinality of the constructible sets of natural numbers is at most $\aleph_1$ [(and etc.)] …

  • The methods of definition otherwise applied in mathematics (in particular, the impredicative as well) do not lead outside the domain of the constructible sets.

The proof of the first lemma, about the number of constructible sets, here too rests on the avoidability in the definition of constructible sets of variables of types that are too high. As to the second lemma, closer examination reveals that this statement means nothing other than that the constructible sets form a model for set theory … As to Lemma 2 therefore it is a matter of proving that the constructible sets form a model for set theory, and on the basis of Lemma 1, one can show that the generalized continuum hypothesis holds in that model, and thus its consistency is proved by the method of models.”

(It's worth going back to the 1940 lecture at this point, to note that - having used the analogy with Hilbert's program to situate his proof in his first lecture - he still felt it worthwhile to present a second proof, even closer in spirit (and it is meaningfully closer - it replaces the model-theoretic approach of 1939 with a more proof-theoretic one). To me this indicates that he was serious in his interpretation of Hilbert (as opposed to, say, simply presenting the analogy to quicken acceptance of his proof, which would in my opinion be a reasonable action given the multiple mathematical and philosophical novelties in the argument).)

The analogy Godel draws here is clear, but in my opinion faulty, because of the points bolded: Hilbert, unlike Godel, does not seem to understand the subtleties of using a model to provide a consistency proof. First, Hilbert doesn’t recognize (at least, not explicitly) the importance of checking that the class of functions specified actually satisfies the given set of axioms. He avoids this by implicitly claiming something stronger: that all functions have this property. Godel recognizes the problem here, and the first bolded passage above introduces a crucial phrase (“one can consistently assume that”) which was not in Hilbert’s argument. This is important, because it adds a layer of subtlety to the task - namely, the appropriate construction and verification of a model - which was definitely not in Hilbert. Another side of this coin crops up in Godel’s description of his own proof, in the second and third bolded passages (“the constructible sets form a model for set theory” and “its consistency is proved by the method of models”) which are not present in his description of Hilbert’s.

Solovay also points out the huge gulf between Godel’s notion of constructible and Hilbert’s (admittedly somewhat vague) notion of recursive, and argues (and I agree) that this gulf isn’t just a technical point but really fundamental; in particular, although Solovay doesn’t explicitly say this, I think that Hilbert’s notion is too restrictive to convincingly cover all “the other definitions that occur in mathematics.” Certainly to the extent that we care about set theory, it isn’t enough: after all, $L$ forms the smallest inner model of ZFC! So the difference in power between Godel’s constructible and Hilbert’s recursive is really reflective of the fact that Godel was aware of the complexities of actually building a model, in a way which Hilbert wasn’t (or at least, wasn’t explicitly in “uber das unendliche.” And according to Solovay, in his later letter to van Heijenoort (which I don’t have) Godel was himself far less generous.

Godel, later on (in his 1965 correspondence with van Heijenoort referred to above - pp. 324-325 of Collected Works vol. 5), seems to agree - he writes:

"There is a remote analogy ... There is, however, this great difference that Hilbert considers only strictly constructive definitions and, moreover, transfinite iterations of the defining operations only up to constructive ordinals, while I admit, not only quantifiers in the definitions, but also iterations of the defining operations up to any ordinal number, no matter whether or how it can be defined. ... It was exactly by viewing the situation from this highly transfinite, set-theoretical point of view that in my approach the difficulties were overcome and a relative finitary consistency proof was obtained. Of course there is no place in this approach for anything like Hilbert's Lemma 1."

(Recall that this lemma was the one singled out by Dreben and Kanamori as the most problematic.)

So on the balance, I think that there is an analogy between Hilbert’s ideas and Godel’s proof, but it is fundamentally shaky and arguably even misleading.

(Again, though, I have absolutely no expertise as an historian, so I’m not really qualified to do this kind of analysis.)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I wonder if Hilbert would have taken Feferman's position that CH is not a definite problem sometime after 1963 (or, you know, later as more axioms and more CH related consequences were unearthed). $\endgroup$ – Asaf Karagila Jun 12 '17 at 18:03
  • 1
    $\begingroup$ I think that Hilbert and Godel were different people throughout history... $\endgroup$ – Asaf Karagila Jun 12 '17 at 19:19
  • $\begingroup$ @AsafKaragila Wow. Derp. Reading, I'm good at it. Still, it's interesting to note that Godel maintained the definiteness of CH even post-forcing. $\endgroup$ – Noah Schweber Jun 12 '17 at 19:26
  • $\begingroup$ Sure, and there are people who maintain that CH has a concrete answer even after all this. But it seems that Hilbert was somewhat of a semi-constructivist in his philosophy (although not really with his mathematics, as we know, being the main proponent behind proof by contradiction and launching the modern era of mathematics into "theology" as some might [have] call[ed] it). Which is why I wondered out loud, if Hilbert would have agreed with Feferman. $\endgroup$ – Asaf Karagila Jun 12 '17 at 19:29
  • 1
    $\begingroup$ @GerryMyerson Derp, thanks! I don't have the collected works on hand now, so I've written a bit of a placeholder; tomorrow I'll put in some actual quotes. $\endgroup$ – Noah Schweber Jun 13 '17 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.