Was Gödel's second incompleteness theorem really von Neumann's? Part I

Gödel never produced a proof but told von Neumann he had one to prevent the Hungarian from publishing his

This is the first of two posts on the hidden history of Gödel's second incompleteness theorem. Part II is available here.

Kurt Gödel’s first and second incompleteness theorems are legendary accomplishments, “among the most important results in modern logic” and two of the human mind’s most towering intellectual achievements. As logician Juliette Kennedy writes, “whether mathematicians will ever have to face the consequences of Gödel’s theorems … the fact is that mathematics had changed forever after 1931 – for those who cared to ponder the matter.”

Like many who have encountered and grasped something of Gödel’s reasoning, I was left in a state of slack-jawed amazement at the audacity of his insights. It was as if he had leapt off this mortal plane for a moment and, hovering above us all, had grasped in an instant the limits of mathematics.

But as is so often the case with discoveries in maths and science, the truth is more interesting and complicated than the myths handed down to us. And recent analysis of Gödel’s unpublished notebooks, which were mostly written in the long-obsolete Gabelsberger shorthand, have revealed that another brilliant logician may be due some credit for proving the second incompleteness theorem — and that Gödel’s behaviour towards this mathematician was less than honourable. The mathematician in question was, of course, John von Neumann.

Gödel would later claim that he had hit upon the theorems while thinking of self-referential statements like the liar’s paradox (‘this statement is a lie’). As I explain in The Man from the Future:

Gödel recast this in terms of unprovability rather than falsity, devising an analogous statement— call it ‘G’ — that says: ‘the proposition g is not provable in the system’… then Gödel turned the statement back on itself by making the subject, g, of the proposition be G itself. Now, if the proposition G cannot be proved, then it is true. If, on the other hand, G can be proved, then it is false. But that would mean the truth of the original statement — that G is not provable — had been formally demonstrated. Thus, G is also true. A mathematical system in which the same statements can be both true and false would be useless. So better to plump for the first option: there are true but unprovable statements in mathematics.

This, in essence, was Gödel’s first incompleteness theorem. The second incompleteness theorem builds on the first to show that no system complex enough to contain arithmetic could be proven to be consistent — at least, not using the tools of the system itself. That is, it is impossible to prove that statements that contradict our common-sense notions of the counting numbers (like 2+2 = 5) can themselves never be proved.

Gödel first stated both theorems in a two-page note to the Austrian Academy of Sciences, communicated to the academy by his doctoral advisor, Hans Hahn. The note, published in October 1930, promised that proofs for the theorems would appear in the Monatshefte für Mathematik und Physik. But Gödel would never publish a formal proof of the second incompleteness theorem. Instead, in the famous paper (PDF) of 1931, in which he proves the first theorem, there is a final passage (section 4) which begins, “From the results of Section 2 follows a remarkable result, regarding a consistency proof of the system P…” and goes on to sketch an argument for the second. A formal proof of the second theorem was supposed to follow in a second paper but no Part II was ever submitted and, the following year, Gödel would admit, in a letter to philosopher Rudolf Carnap, that “part II of my work exists only in a realm of ideas.” In fact, a rigorous proof of the second theorem turned out to be rather difficult to produce and only appeared in 1939, in a book by David Hilbert and Paul Bernays.

So what happened?

Encounter in Königsberg

The drama begins at the three-day International Conference on the Epistemology of the Exact Sciences, held in Königsberg from 5-7 September 1930. Here’s the widely-accepted version of events from The Man from the Future:

Only on the last day of the conference, towards the end of a round-table discussion that would bring the meeting to a close, did Gödel play [the ace he was hiding up his sleeve]. In a single sentence, he quietly reduced the earlier proceedings of the conference to an irrelevance and the foundations of mathematics to a flaming ruin. ‘One can,’ he ventured modestly, ‘even give examples of propositions (and in fact of those of the type of Goldbach or Fermat) that, while contentually true, are unprovable in the formal system of classical mathematics.’

In other words, there are truths in mathematics that cannot be proven by mathematics. Mathematics is not complete. His off-hand references to Goldbach and Fermat were portentous. Golbach’s conjecture (that all even numbers greater than 2 are the sum of two primes) and Fermat’s last theorem (that no positive integers a, b, and c satisfy the equation a^n + b^n = c^n for values of n greater than 2) were two of the great unsolved problems in arithmetic. Gödel was implying that even in the sort of maths taught to schoolchildren there might lurk verities that can never be substantiated.

Gödel had announced one of the foremost intellectual feats of the twentieth century. He must have been rather piqued when the response to this revelation was even more muted than the perfunctory praise that had greeted his thesis. The assemblage politely ignored his carefully prepared one-sentence bombshell as if he had cracked a bad joke at a dinner party.

Gödel’s proclamation ought at least to have prompted a question or two. How could, for instance, a mathematical proposition be true yet unprovable? Yet it appears that only one person grasped the import of Gödel’s achievement well enough to want to know more. After the round table was over, von Neumann, there as a trusted evangelist for Hilbert’s programme, grabbed Gödel by the sleeve and steered him to a quiet corner to grill him about his methods.

The following day Hilbert gave his retirement address, a passionate speech in which he declared again there were no unsolvable problems in mathematics and uttered the words that would become the epitaph on his gravestone: We must know – we will know. But Gödel had already proved him wrong.

…

Von Neumann kept thinking about Gödel’s proof after the Königsberg conference. On 20 November, he wrote excitedly to Gödel. ‘Using the methods you employed so successfully . . . I achieved a result that seems to me to be remarkable, namely,’ von Neumann continued with a flourish, ‘I was able to show that the consistency of mathematics is unprovable.’

Von Neumann promised to send him his proof, which he said would soon be ready for publication. But it was too late. Gödel, probably sensing that von Neumann was hot on his heels after their conversation in Königsberg, had already sent his paper to a journal. He now sent a copy to von Neumann. Crestfallen, von Neumann wrote back [on 29 November], thanking him. ‘As you have established the theorem on the unprovability of consistency as a natural continuation and deepening of your earlier results,’ he added, ‘I clearly won’t publish on this subject.’ So saying, von Neumann quietly passed up the opportunity to stake a claim on the most remarkable result in mathematical history.

The problem is that Gödel’s response to von Neumann’s letter of 20 November has been lost. We do know, however, that Gödel could not have sent him a proof of the second incompleteness theorem because there is no evidence he ever had one. So what did Gödel send to von Neumann that suggested he had “established the theorem on the unprovability of consistency”?

First, a bit more on the discussion that took place between the two mathematicians at Königsberg in Gödel’s own words, as reported by the Chinese-American logician Hao Wang:

“I had a private talk with von Neumann, who called it a most interesting result and was enthusiastic. To von Neumann’s question whether the proposition could be expressed in number theory I replied: of course they can be mapped into integers but there would be new relations [different from the familiar ones in number theory]. He believed that it could be transformed into a proposition about integers. This suggested a simplification, but he contributed nothing to the proof because the idea that it can be transformed into integers is trivial. I should, however, have mentioned the suggestion; otherwise too much credit would have gone to it.”

Logician Jan von Plato, who has worked on decoding Gödel notebooks since 2017, notes that, “ The wording of Wang’s notes seems somewhat awkward here, as if Gödel needed to protect himself against a priority claim by von Neumann, deceased two decades earlier.” No wonder. Though Gödel calls the idea ‘trivial’, expressing the proposition G in arithmetic terms leads to a more profound result:

Gödel produced an arithmetic statement — a complicated sum if you like — that mirrored the phrase ‘the proposition g is not provable in the system’. He then demonstrated that the Gödel number of this phrase could itself be g. That is, Gödel had added another layer of self- reference to the original statement by making arithmetic talk about the very nature of arithmetic. His breathtaking discovery was that the language of mathematics could be used to make metastatements about mathematics.

…and…

One remarkable consequence of his arcane paper is not widely appreciated. In 1930, Gödel had written a computer program long before any machine capable of running it would exist. He had dissolved in one fell swoop the rigid distinction between syntax and data. He had shown that it was possible to devise a rigorous system in which logical statements (that were very much like computer commands) could be rendered as numbers. Or as von Neumann would put it in 1945 while describing the computer he was planning to build at the IAS, ‘ “Words” coding the orders are handled in the memory just like numbers.’ That is the essence of modern-day coding, the concept at the heart of software.

—The Man from the Future

“It seems to have been von Neumann’s desire to go deeper into the comprehension of what, at least to him, sounded like an unexpected result,” says philosopher Giambattista Formica, and, so, he says, “to have suggested to Gödel the way to obtain, via the arithmetization of the syntax, an even more significant result, which would have also touched the simpler parts of mathematics, e.g. arithmetic.”

That does all rather suggest that von Neumann’s contribution was an important one and, as a matter of courtesy, Gödel should indeed have credited him for his insights.

So much for the first incompleteness theorem. What about the second?

The crucial letter from Gödel to von Neumann remains lost. But thanks to sleuthing by von Plato, we now have a fair idea of exactly how far Gödel was prepared to go to mislead von Neumann. And though von Neumann’s proof of the second incompleteness theorem is also considered lost (for now), Formica has assembled from various clues a plausible outline of what von Neumann’s proof might have looked like. I’ll look at both pieces of work in Part II, which, unlike the second part of Gödel’s paper, I promise will appear shortly.

For now, I’ll leave you with the words of Gödel scholar John W. Dawson Jr., who has written a biography of the logician and catalogued his papers:

“In his correspondence with von Neumann concerning the proof of the second theorem Gödel was certainly disingenuous about how much he had actually accomplished.”

Now read Part II, on what Gödel’s private journals reveal about his interactions with von Neumann.

With many thanks to reader Jonathan Who for making me aware of this work.

I love getting comments or you can talk to me via email ananyo@substack.com or on Twitter at @ananyo

And now a word from our sponsors…

Many thanks to Kenneth T for becoming my second paid subscriber. Good science writing is expensive. If you loved The Man from the Future and enjoy what I’m doing here, please support my writing by paying something to subscribe. Whether you buy me a coffee for $5 or a couple of printer cartridges for $50, it all helps.