Part II of the GLL exclusive

 By permission of Vi Hart, mathemusiciartist: source

Kurt Gödel has assented to our publishing the second part of the interview we conducted with him a year ago.

We had his assent to begin with, but issues of time are unclear in this type of situation, and with this kind of super-luminary one can never be too careful. We also needed his help in transcribing this second part. What happened is that as the collective human consciousness realized that the discovery of naturally-occurring faster-than-light neutrinos had failed owing to a loose cable, the effect our setup relied on faded and disappeared. Gödel compensated by spinning up enough artificial neutrinos to transmit what was recorded on his end. However, he could not do this until All Hallows Day came around again, which was Thursday.

The first part had glossed over his achievements in logic and set theory. We were delighted that he talked about them in much detail—indeed enough that this post is in two installments. We hope you will be interested. Whether we can get him back for a further interview may depend on your interest, to satisfy the anonymous donor we mentioned in August.

We did not call him Kurt. German speakers of his generation tended not to use first names even with their close friends. As we said, with that kind of person one can never be too careful. Dick conducted the interview while I monitored the transmitter.

## Interview, Part II

The second part followed a few hours after the first, when we realized we hadn’t heard much on what “incompleteness” really means. Hence we got right to it when we resumed.

## Completeness and Incompleteness

GLL: Good day again Professor Gödel—good afternoon I guess—and danke viel mals for being willing to continue.

Gödel: It is fine—Adele, my wife, lets me sleep late in bed, or even read in bed.

GLL: So it is still morning for you?

Gödel: Morning, afternoon…wie Sie es wünschen.

GLL: Thank you. Professor, our readers would like to know, what is the difference between “completeness” and “incompleteness”—in your famous theorems.

Gödel: Zwischen den Vollständigkeitssatz und den Unvollständigkeitssatz?

GLL: Ja—yes. You prove that all systems of first-order logic that include the predicate calculus are complete, but first-order arithmetic and all stronger systems—which include the predicate calculus—are incomplete.

Gödel: Yes—ja.

GLL: How can the same system be complete and incomplete? How can making something stronger make it incomplete?

Gödel: Ach—your words in English are too short. We have longer words so we think more before finishing them. Less confusion.

Gödel: Sure. The difference is that with arithmetic you build from a single model, the integers, while with general first-order systems you can have any model.

GLL: What is a model?

Gödel: I can explain it without models. Completeness says that if a statement in the system is valid—which means always true—then it has a proof. Incompleteness says that there are some true statements—about integers—that are not provable in the system.

GLL: So isn’t that a contradiction? Surely a true statement–call it ${s}$—is always true?

Gödel: No, in some situation ${s}$ might not be true.

GLL: But ${s}$ involves only numbers—integers—that was the brilliant point of your using Gödel Numbers. So how can it be true about integers and not be true?

Gödel: It can be true but not valid.

GLL: What’s the difference?

Gödel: Let me try an example. Consider the statement ${2 + 2 \neq 1}$.

GLL: Certainly true.

Gödel: But what if the integers are modulo 3?

GLL: Ah, then ${2 + 2 = 1}$. So inequality is not valid. But the integers aren’t modulo 3.

Gödel: Right, but how do you tell your formal system that?

GLL: You add axioms: ${x + 1 > x}$. And ${y > x \longrightarrow y \neq x}$. That does it, now your mod-3 case doesn’t hold.

Gödel: But what happened is you made ${2 + 2 \neq 1}$ a theorem. You can deduce it from your axioms. And anything you can deduce is valid—that’s clear—but the opposite is the point of completeness: Anything valid can be deduced.

GLL: I still don’t see why this doesn’t contradict incompleteness.

At this point Gödel sighed. Unfortunately it wasn’t a usual sigh—it was an Al Gore type of sigh, and it overloaded the transmitter. Dick and I decided while we waited that perhaps we should move on to incompleteness. We were afraid Gödel would be impatient with us, but actually he was apologetic.

## Incompleteness

Gödel: Verzeih mir—I’m sorry—maybe I should define models. I gave such a bad proof in my Ph.D thesis because I didn’t use models.

GLL: A bad proof?

Gödel: Yes it was a good theorem, but a bad proof, and I didn’t learn much until after the war, from Henkin.

GLL: You mean Leon Henkin—another student of Alonzo Church.

Gödel: Yes, and Gisbert Hasenjaeger—who was the German anti-Turing.

GLL: Anti-Turing?

Gödel: He found and patched the weaknesses in the Enigma code, not realizing Turing and fellows had broken more of it long before.

GLL: How do you know that? It’s 1971 where you are, and Turing’s WW II role wasn’t declassified until later in the 1970′s.

Gödel: Why should that surprise you? You know how I guard against spies. With that kind of person, one can never be too careful.

GLL: OK, let’s move on to incompleteness.

Gödel: Ach, another bad proof.

GLL: Bad proof? It is considered one of the greatest intellectual achievements of the century.

Gödel: But I did not even get the theorem statement right. Of course consistency is enough, but I was lazy and published what I had and Rosser trumped me.

GLL: But—

Gödel: My paper was 100 manuscript pages, and I ended the title with “Part I” because I had another 100 pages in sketches. If a person today claims a big proof in 100 pages and then expands it to 200 pages, what do you think of that?

GLL: You know, John Barkley Rosser’s son—same name—commented in our blog when we had the episode with Vinay Deolalikar’s 100-page proof.

Gödel: His father was a true giant, and the Church-Rosser theorem is the only ultimately practical fact about computation. Without it there is chaos.

GLL: OK, but there was nothing wrong with your 100 pages, let alone 200.

Gödel: How do you know? Like Principia Mathematica itself, almost nobody read it! They decided it was true based on simpler thinking.

GLL: What makes you think that?

Gödel: The only person I believed really read it was Ernst Zermelo, who thought he found an error, which I replied in 10 pages was not. But he didn’t like it and attacked me instead, so I deduced he didn’t read it. Besides, nobody asked me for the Part II.

GLL: Well yes, people teach your theorem in courses without covering 100 pages.

Gödel: Happily now I can prove everything in half a page.

Dick and I gasped, and this time we upset the apparatus. The image of Gödel flickered but held.

## Gödel’s Half-Page Proof

GLL: Sorry. Please proceed, Professor.

Gödel: We build logic with numbers, but the goal is to understand computation. For a formal system ${F}$ to be strong, it must at least be able to recognize whether a string ${c}$ is a full trace of a halting computation. Can be by Turing machine or debugger in your favorite programming language, like Algol or COBOL or the new one, Pascal.

GLL: Many more languages now.

Gödel: No matter, whatever language, if ${F}$ is useful at all then whenever ${c}$ is a halting computation of a program ${e}$, can be on empty input, ${F}$ proves it. Call the sentence ${F}$ proves ${T(e,c)}$. And when ${c}$ is not a full trace, ${F}$ proves ${\neg T(e,c)}$.

GLL: OK—like the Kleene ${T}$-predicate ${T(e,x,c)}$ with ${x =}$ the empty string.

Gödel: Genau. Of course we assume ${F}$ is consistent, and also effective: we can decide whether a given string is a proof of a theorem. Now define the predicate

$\displaystyle S(e) \equiv (\forall c)\neg T(e,c).$

So ${L_S}$—the set of ${e}$ making ${S(e)}$ true—is the set of non-halting programs.

GLL: Which is undecidable—indeed not even computably enumerable.

Gödel: Finally let

$\displaystyle L' = \{e: S(e)\text{ is a theorem of }F\}.$

What do you have?

We were being schooled by him—did he ever teach a course at Princeton? At least we knew what to say.

GLL: Since ${F}$ is effective, ${L'}$ is computably enumerable. So it can’t be equal to ${L_S}$ which is not c.e.

Gödel: Can we have an ${e}$ in ${L' \setminus L_S}$?

GLL: If we have, then ${F}$ proves ${S(e) = (\forall c)\neg T(e,c)}$, but ${e \notin L_S}$ so the program ${e}$ really does have a finite halting computation ${c}$. Thus ${F}$ proves ${T(e,c)}$, but also by the rule for ${\forall}$, ${F}$ proves ${\neg T(e,c)}$. Thus ${F}$ would be inconsistent.

Gödel: Richtig. So ${L'}$ is a subset of ${L_S}$.

GLL: And by above, a proper subset. So there is a ${d}$ in ${L_S \setminus L'}$.

Gödel: And this means?

GLL: The statement ${S(d)}$ is true but not a theorem of ${F}$.

Gödel: Now this is not quite all of the First Incompleteness Theorem—you also need to make sure ${\neg S(d)}$ is not a theorem of ${F}$, to make ${S(d)}$ fully independent. For this I stated “omega-consistency,” but for intuition let’s just assume ${F}$ is sound—everything it proves is true. Then that’s it.

GLL: What more do we need for the Second Incompleteness Theorem?

Gödel: Nothing! Well we skip technicality about proof predicates. It’s simply: If ${F}$ could prove its own consistency, then it would prove ${S(d)}$ after all, so it cannot prove its own consistency. Der zweite Unvollständigkeitssatz.

GLL: Does this work with any predicate ${S(\cdot)}$ that defines a non-c.e. set? Such as ${S(e) \equiv}$ program ${e}$ halts for all inputs. It always has instances that are true but not provable.

Gödel: But when ${L_S}$ is not co-c.e., is assuming consistency enough? Your readers may also enjoy trying to find ${S(\cdots)}$ that makes Rosser’s version work, both sides needing only consistency. Anyway, finally this explains the Completeness Theorem.

GLL: You mean Incompleteness Theorem.

Gödel: No—!

At this point I came in front of his monitoring station to say something, but this disturbed the transmitter and we lost the rest of what Gödel said. Happily he came back before we did anything. He was excited and pressed forward so that his head filled the screen—it felt like the movie “The Wizard of Oz.”

## Completeness and the Infinite Halting Machine

Gödel: Now consider the statement ${S(d)}$ again, which ${F}$ cannot prove. Is it valid?

GLL: It is true…

Gödel: But by Completeness, if it were valid it would be a theorem!

GLL: So it isn’t true?

Gödel: Yes it is true. It just isn’t valid.

GLL: The program ${d}$—say it’s a Turing machine ${M_d}$ on empty input—never halts, right?

Gödel: Yes and there is a simple arithmetical formula that codes ${S(d)}$ saying this. Doesn’t matter Turing machines or Algol or Pascal or even APL. This is what people decide is true without reading boring details—except those who write interpreters or compilers that hopefully have no bugs. Always just a sentence about integers. A true sentence.

GLL: How can that not be valid? You mean if the integers were mod 3 again?

Gödel: No, we built in your previous axioms already. ${F}$ is a strong system, remember? One you use to prove real theorems, and verify programs, like that.

GLL: What if I add more axioms?

Gödel: Can’t—you fixed ${F}$ to begin with. It’s like saying oops you forgot to put Cantor’s diagonal number in your list of reals. No oops.

GLL: So what happens if ${S(d)}$ is not valid?

Gödel: Well, I said that then the statement ${\neg S(d)}$ is consistent with the system ${F}$. That is, ${F \cup \neg S(d)}$ is consistent, though no longer sound. But Henkin said something better.

GLL: What did he say?

Gödel: He showed that ${F \cup \neg S(d)}$ has a model—a structure ${\cal N}$ in which every axiom of ${F}$ is true, every theorem of ${F}$ is true, and also ${\neg S(d)}$ is true.

GLL: But ${\cal N}$ is the same as numbers, right?

Gödel: It has all the numbers: ${0}$, and ${0 + 1 > 0}$, and ${1 + 1 = 2 > 1}$, ${3,4,5,\dots}$, and all the negative integers with their usual properties like ${(-n) + n = 0}$.

GLL: So what’s the trouble?

Gödel: It has extra numbers. Positive numbers that are above all the ones in ${\mathbb{N}}$, and their negatives.

GLL: But anyway if ${\neg S(d)}$ is true it means the machine ${M_d}$ halts, which it must do in some number of steps…

Gödel: Indeed, but not necessarily in some finite number of steps. It can be one of those other, non-standard numbers of steps.

GLL: So ${M_d}$ can halt after infinitely many steps?

Gödel: It’s like counting up to ${\omega+1}$, or any non-limit ordinal.

GLL: But a Turing machine is not an ordinal. If I run ${M_d}$, it will never halt.

Gödel: It will non-standardly halt. It will have a halting part that majorizes the non-halting parts.

GLL: Turing machines don’t run like that. You have to run them from the beginning.

Gödel: It follows from Completeness and Incompleteness that they must run like that. Because we have defined computation in terms of numbers. Abraham Robinson made non-standard analysis out of these numbers—you can have non-standard computation. Perhaps it will help you understand why it is hard to find a proof of ${\mathsf{P \neq NP}}$—or the reverse.

Dick and I exchanged quizzical glances—we had not expected our intuition about computation to be upset like that. I was also surprised by Gödel’s objective approach to truth—he didn’t say it was relative to axioms or mention relative consistency, and he shied away from models. He didn’t sound much different from David Hilbert.

Viewing the time, we moved on to Set Theory. We will post the rest of the interview shortly—Gödel added some things in his Thursday re-send about large cardinals, the meaning of completeness, and Alexander Grothendieck that we don’t understand, and we are trying to learn them before we post.

To Be Continued…

## Open Problems

Did Kurt’s explanation of major results in logic help you understand them? Or did it leave you unsettled?

[simplified ${L_{S'}}$ to read ${L'}$, changed pic of Gödel]

8 Comments leave one →
1. November 3, 2012 12:00 pm

These Gödel posts are fantastic. I feel smarter, as I said last time. Thanks!

2. November 3, 2012 1:39 pm

The expressions of KG’s attitudes are guided partly by reading in to the Stanford Encyclopedia of Philosophy article on Gödel. The bit in the intro about fading neutrino effects is not meant to take KG’s own venture into Husserlian phenomenology as far as the quantum-consciousness people do; it’s influenced more by my daughter’s acting in a high-school production of “Peter Pan” this weekend :-).

November 3, 2012 6:47 pm

very nice presentation! this kind of short presentation of the incompleteness theorem is buried in books that are not so popular nowadays. e.g., par. 43 of Kleene’s “Mathematical Logic” (John Wiley & Sons 1967, reprinted by Dover 2002), or (a bit more technical but equally succinct) par. 7.8 of “Roger’s Theory of recursive functions and effective computability” (1967 McGraw-Hill, reprinted 1987 MIT). soooo good they are re-vived and re-circulated! :)

4. Javaid Aslam permalink
November 4, 2012 3:52 pm

Thank you GLL for providing an easier account of Godel’s Incompleteness theorem.
But I remain blurry and confused!

5. Jim Blair permalink
November 7, 2012 6:25 am

“Did Kurt’s explanation of major results in logic help you understand them? Or did it leave you unsettled?”

Both. The more I understand his logic, the more unsettling it becomes.

I suspect I do not understand his model of the integers.