Skip to content

The Graph of Math

November 15, 2013


The last part of our interview with Gödel two years ago

GodelBlackboard
src

Kurt Gödel is said to have been a latecomer to appreciating the power of Model Theory. He was of course the greatest architect of Proof Theory, which stands in contrast to Model Theory. Model Theory concerns itself with what could be true, while Proof Theory deals with what can be proved. The latter sounds more definite, but they are supplementary: a statement is capable of being true somewhere precisely when its negation cannot be proved. The question is, where is that somewhere? And when?

Two years ago by our reckoning, Dick and I put that question to Gödel, at the close of our interview whose first and second parts we posted at this time the past two years.

As before, we took advantage of time-reversed communication that was made possible by Gödel’s own solution to Albert Einstein’s equations of general relativity. We needed zillions of rapidly spinning objects to implement a dual form of it. Time-traveling neutrinos fit the bill nicely, until the proof of this technology was found to be flawed. Still, it worked for a time, and the transmitter I managed while Dick led the talking duly sent its streams to mines in Soudan, Minnesota and Gran Sasso, Italy for recovery and transcription.

We must confess we are unable to recover the beginning of this part of the interview. Gödel said something we thought was crazy, just false, a self-contradiction really, and our reaction upset him. What he said was he thought the axioms of set theory were “obviously true” and he was trying to prove them using “large cardinals,” which we took to be part of set theory. We reacted with what we thought was a careful, innocent, reader-friendly question:

Doesn’t using set theory to prove set theory true imply proving it’s consistent, which you proved set theory cannot do?

Well Gödel didn’t like this question. He flew into German so loudly and rapidly that I missed a lot of words. He either said our trifling question was not serious then something about Zermelo’s axioms, or he said it was a niggling question like Ernst Zermelo would ask—since “ernst” means “serious” in German. Then he said that set theory was “not closed in on itself” so “my theorem doesn’t stop it.” Then I made out only a few words: sechszehn (sixteen) … jungfern (virgin) … Körper (bodies) … vermeiden Russell (avoid Russell), amid several references to “classes” and “Johnny.” Bertrand Russell’s escapades were well known, but that couldn’t be what Gödel was talking about, and my total perplexity was read well enough by Dick.

What saved us again was Gödel’s tendency to be contrite on regaining his composure. He said he thought he had convinced everyone that set theory was true (!—he did not say “consistent”) when he proved that the Axiom of Choice could not cause its inconsistency, but now he himself was beginning to doubt the truth (!) of the Continuum Hypothesis even though he had proved it was “equally consistent.” He admitted how people could be concerned that set theory was inconsistent “since it happened before,” and said he would apologize by demonstrating his understanding of their point of view.

Then he launched into something we didn’t know from his writings, and this is what we want to share with you, our readers. As before, Dick asked the questions unless I chimed in.

Interview, Part III

Gödel: Of course mathematics is about truth, not possibility. But possibility in mathematics—which is when falseness is not necessary—can also be about truth, the truth of being able to build…

GLL: To build?

Gödel: Nicht nur bauen, sondern ständig zu bauen… Better in English: when you have building as a standing condition.

GLL: Building what?

Gödel: I should say “building a model,” but in the 1950’s I thought about this again after hearing some of Johnny’s last ideas.

GLL: Johnny of course is John von Neumann.

Gödel: Ja—and he said his work on cellular automata made him study networks, I think now you say “graphs.”

GLL: Yes of course, directed or undirected, finite or infinite graphs. A big area of study.

Gödel: Gut dann—well these questions about the foundations of mathematics are about whether you can build infinite directed graphs according to certain rules.

GLL: What kind of rules?

Gödel: Simple for the most part. Let me try one example. Every node has one arrow in and one arrow out, except one source node has only one arrow out.

GLL: You are tricky—since you said there is one source node I can’t just use the empty graph.

Gödel: Right, but can you use a finite graph?

Dick realized that the source node rule prevents a finite cycle, while the other rule prevents any arrow from going to any old node. So the graph must be infinite.

GLL: We have to build the infinite path.

Gödel: Yes, the rule admits no finite model, as they say today.

GLL: But obviously the path obeys the rule. So I can build the graph.

Gödel: Indeed you can build it observing the condition that whenever you place a node, you determine all arrows that go in to it.

GLL: Yes, no problem. But I place a node infinitely many times—I guess that’s what you meant by “standing condition.”

Gödel: Genau—exactly—now one more point will convey the whole task. Can you place a node that has arrows coming in from every node in your path?

GLL: Yes of course—it just sits at the top above the path…oh I see, I see…, there’s no finite time when you place it, if you need to determine all incoming arrows when you do.

Gödel: But you can imagine it being placed.

GLL: Of course, no problem. We just imagine it’s like the numbers {0, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \;...} and then there’s {1}.

PathGraph

I squirmed in the background and thought of asking whether we’d have to place nodes at uncountably many infinite delays, but feared another fuss. Gödel seemed to sense my thought anyway, because he said:

Gödel: The rules that matter will be simple, and maybe we care about only one more infinite building step.

GLL: What are some other rules?

Gödel: I will give you the hardest rule—in a sense the only hard one—right away.

Hard is Easy, But What’s Impossible?

Gödel pulled up a green chalkboard on wheels. I’ve often wondered whether they use those or PowerPoint where he is, now I know. He drew one dot at bottom center and one at upper center but not near the top, and I wondered why he left room there.

Gödel: Here is the rule:

{\infty}: There is a node {t} which has an arrow from the source node {s}, such that whenever {x} has an arrow into {t}, there is another node {y} that has arrows into it from {x} and every node that has an arrow into {x}, and {t} has an arrow from {y}.

Gödel wheeled the blackboard toward Dick, maybe not realizing that across the spacetime expanse Dick couldn’t come forward to use it. But Dick started telling Kurt—OK we never called him Kurt—what he wanted to draw.

GLL: Take your {x} on the path up from {s}, now we put {y} up and to the side and connect it from {x} and {s}, and we will have to connect both {x} and {y} to {t}, now move on the next node {x'} up on the path from {x} and—we’ll also have to do this to {y} too…so the graph may get pretty bushy…

Gödel leaned in with a grin and waved his hand out but toward himself, like hinting for a better answer. Dick picked up quick:

GLL: Ah—we don’t need {y} to be different from {x'}. It can be {x'}, but we connect it from {s} too—so it has two arrows coming in. It’s just like the path plus {t} before, except now each node has an in-arrow from every node before it. It’s just a fat path.

Gödel: Jawohl. Your fat path is called N.

He drew a blackboard-bold {\mathbb{N}}, and I realized what he meant: {0 = \emptyset}, {1 = \{\emptyset\}}, {2 = \{\emptyset, \{\emptyset\}\}}, and in general {x+1 = x \cup \{x\}}. He wrote the quantifiers he’d stated and then a wavy line to represent the fat path. But Dick kept on about rules.

FatPathGraph

GLL: That was the hardest rule? That was easy…

Gödel: Well, we’ll see how it interacts with the other rules. I will mention it again later.

GLL: Are any rules impossible? What would be an impossible rule?

Gödel: Each rule is possible—all the rules together is the issue. But here is an impossible rule: You must not allow infinitely many nodes having no arrows between any two, and you must not allow infinitely many nodes with an arrow between every two.

GLL: The fat path has an arrow between every pair, so that’s out, while the thin path…ah, does not have any arrows between even nodes. Or between odd-numbered nodes. So that’s out. But why can’t I build alternating…?

Again we saw the professorial grin and wide—but not smug—eyes behind Kurt’s thick glasses.

GLL: Oh of course. The infinite Ramsey theorem.

I had thought of that too. Kurt waggled his hands approvingly. I was glad he didn’t think we were stupid anymore. Indeed I thought to say the Ramsey rule was maybe unfair because it had second-order quantifiers over infinite sets, but Gödel had the floor.

Gödel: Are you ready now to try the rules—the real rules? There are eight of them, but one is a “schema” that I discovered can be expanded into just nine more rules, so that makes sixteen with no schemas. But if you are happy with the intuition with a schema about formulas, then another rule—Johnny’s rule—can be treated very nicely if you also allow choice.

We were game for anything.

Start of the Rules

Kurt erased the board so only {s} and {t} and the partially-written {\infty} rule were left. Then he moved his hand into the area I wondered about above {t} and drew an open circle, not a dot. He labeled it {V}.

Gödel: There is one extra concept. The graph has sinks as well as the one source {s}. Many sinks. But one sink is, how do you say in English—the Kitchen Sink, because it has an arrow from every non-sink. Of course like with {t} you imagine {V} and the arrows are placed at the very end, last, well after all non-sinks. Note {t} is not a sink—{V} will have an arrow from {t}.

GLL: Why {V}?

Gödel: Johnny and some others called it {V} for veritas, truth, while I thought “virtual” in English, but I now think maybe better is “virgin,” because it does not connect to anything. There are other sinks too—other virgins—and they are very useful. Virgins can be born—have arrows coming in but only from non-virgins of course—and importantly they can be “midwives” to non-virgins.

I couldn’t resist cutting in.

GLL: There are no Virgin Births?

Gödel: No.

He did not laugh at my joke; instead he got serious.

Gödel: The empty set {s} is the first, and {V} is the last, and they are connected. Paul Bernays spoke of them as two separate kinds of object—at least this was better than Johnny making everything a function—but it suits my spirit better if they are one kind but have two different states of being.

Dick took this in but moved forward.

GLL: OK, the white dots are “virgins”?

Gödel: You can call them “classes,” except for me “class” includes “set”—so you can say “proper classes” to distinguish the white ones. If you say “class” for white then I could say Körper—bodies—for both, but anyway the rules about incoming arrows will apply to both the same way, so don’t worry. It’s all one graph—that’s why I consider it the same kind.

GLL: Okay, how do we build the graph?

Gödel: The first rule is really only a “gentleman’s agreement,” since if you ever violated it with a placement, you could just skip it. The rule is:

1. No two nodes may have arrows from the same set of nodes.

GLL: Since you say “set,” and the set could be infinite, aren’t you assuming what you’re formalizing?

I caught my breath momentarily, but Kurt was actually very pleased.

Gödel: Ziemlich gut! So the rule really says:


1. For every {x} and distinct {y}, there must exist {z} such that {z} is connected to {x} and not to {y} or vice-versa.


GodelSetup


This made me brave enough to ask a really niggling question:

GLL: But Herr Professor Doktor, when you say “distinct,” is this not already referencing the condition of set-inequality which you are defining here?

Gödel: The standard answer is that the first-order concept of {=} as identity is more primitive than equality of sets, which this rule ensures never comes up. My other answer is that the rule applies in the order of placement for {x}, and {y} refers to nodes which are there at the time.

GLL: And a third answer is that if you ever had two nodes with the same in-neighbors, you could just combine them.

Gödel: Yes, and this applies to all nodes. No white node can ever have the same in-neighbors as a black node, or another white node. So {V} is unique. And {s} is the unique source.

I cut in again.

GLL: If you had other sources that were not placed but were there from the beginning, would that be OK?

Gödel: Yes that would be OK. Such nodes are called Ur-Elemente, original elements. I think of them like Adam and Eve, and Lilith and others… Having them be sources will not cause a problem and is good for discourse, but there is no need—this makes no difference in what you are able to prove.

I also wanted to ask about whether using quantifiers and variables was prematurely assuming things about set theory as a foundation, but I gathered Gödel had a long answer which could go into Principia Mathematica and/or the lambda calculus of Alonzo Church. I guessed that so long as all the rules stuck to first-order logic this would be fine. Dick had a more-pressing question anyway.

Four Rules to Avoid Russell

GLL: Can we make an arrow go back to the same node? Can we have a cycle?

Gödel: First I’ll state the second rule. I’ll use the “ordinal placement” language to state it:


2. When you place a node {x}, there must be some {y} that gives an in-arrow to {x}, such that no {z} is connected to both {x} and {y}.

GLL: I see—if {x} just has an arrow to itself then with {y = x} you would have a violation with {z = y = x}. I notice too it’s important not to limit the statement to “already-existing” {y}.

Gödel: Indeed we must write the rules without referencing the time of placement or ideas of “already” or “before” at all.

GLL: Wait—what if {y} is a different node with an in-arrow to {x}. Then {x} going to {x} could be OK.

Gödel: Well the contradiction actually comes because we will have a rule that for all non-virgin {x} you must place {x'} having an in-arrow only from {x}. Then for {x'} you must choose {y = x} and you get the violation with {z = y = x}.

GLL: Oh. What about cycles?

Gödel: Here is where the idea that all arrows into {x} come at time of placement helps.

GLL: I see—you can’t place a cycle in order, not even an infinite cycle.

Gödel: The actual way cycles are banished with two more rules is important to see, because it is a “delayed effect” of the kind that makes me wonder whether we can formalize a better intuition. Here are the next two rules:


3. When you place a node {x} you must place a node {u} such that for all {y} with in-arrows to {x}, and all {z} with in-arrows to {y}, {u} has an in-arrow from {z}.


4. When you place a non-virgin node {x}, for every non-virgin node {y}, you must place a non-virgin node {z} with in-arrows from {x} and {y} and no other node. This allows {x = y}, but of course they cannot be virgins since they have out-arrows.


GodelMidway


GLL: The former rule is fine—you must repeat it when you place {u}, but it eventually “bottoms out.” The latter, however, forces an infinite amount of work, because not only do you have to loop over all {y}, but then you repeat the whole process with {z}. Plus I’m a little bothered by the “non-virgin” condition here—when do we tell whether a node is going to be or stay a virgin?

Gödel: Maybe I am bothered too, but in mathematics {z} is simply the pair {\{x,y\}}. Or with {y = x}, {z} is the singleton set {x' = \{x\}} which I gave above. Anyway, here is how these rules forbid cycles in general. Suppose we had a 3-cycle, {p \rightarrow q \rightarrow r \rightarrow p}:

  • By rule 4 we have a node {v} with arrows from {p} and {q}.

  • By rule 4 again we have a node {w} with arrows from {v} and {r}.

  • By rule 3 we have a node {x} with three in-arrows: from {p}, {q}, and {r}.

  • But now that placement of {x} violates rule 2. Because: whatever {y} we choose, its predecessor {z} in the cycle is connected to both {y} and {x}.


GodelCycle


Gödel: For longer cycles you have to do more pairing and union steps, but even for an infinite cycle, as you build up the infinite union you would fly inexorably to a violation of rule 2 at some infinite time.

GLL: That’s rather scary.

Gödel: But it never comes up, because the rules are first-order, and you never have to fear that you will accidentally build the cycle. The placement intuition tells you this already.

GLL: OK. But what about Russell? Isn’t the idea of a “node connected from all nodes that are not connected from themselves” still a contradiction?

Gödel. No. All virgins are not connected to anything, so not to themselves. If you were going to get a paradox whose statement doesn’t already violate the condition of being virgin, it would be about a node connected from all non-virgin nodes that are not connected to themselves. Above we made sure all non-virgins are not connected to themselves. So that node exists, without paradox. It is {V}. And the node for the set of nodes that are connected to themselves exists without paradox. It is {s}.

GLL: Oh my. You don’t need a whole type hierarchy to avoid the paradox, just the concept of “virgin.”

Gödel: The larger purpose is to make the world safe for formulas as definitions. Thus there is no problem now with the formulas {X \in X} and {X \notin X}. You just allow that your answer might turn out to be a virgin—well, virtual. If you are happy with formulas, then the last three rules will not bother you. One of them already is no problem.

The Last Three Rules

Gödel had just enough room at the left to write one more rule, and started writing “5.” just as Dick broke in.

GLL: You said 8 rules, but three more makes only 7.

Gödel: Don’t forget the rule {\infty} which I mentioned first, but prefer to number last as 8. Now:


5. For every non-virtual node {x}, there is a node {p} such that for all nodes {y,} {y} has an arrow to {p} if and only if all nodes {z} with an arrow to {y} also have an arrow to {x}.

We recognized the last part as the subset relation, and Gödel wrote it that way as {Uyx} using the German word Untermenge for subset. We realized he had not otherwise written or spoken anything else like “set” or {\in} for “member” in these rules. Dick wanted to know whether this could cause a snag like with the cycle.

GLL: Ooh, I have to place {p} when I place {x}, but {p} has to come after all the {y}. So I have to place all the {y} first. But that’s OK: I only have to worry about all the possibilities for nodes {z} that I am connecting to {x}. For every two or three of them, I will have to build {y} as the pair or triple of them anyway, as you showed above when discussing the 3-cycle. And so on. So it bottoms out OK. OK, I think I can build with this rule…maybe when the {y}‘s are infinite I have to worry…ah, that will be an issue after your rule 8 or {\infty} produces {t}. I see why you call that rule hard.

Gödel: But I hope that since we are putting it eighth and last, you won’t find the other two rules hard. I am going to be informal with the next one, because it is the schema that I can expand into nine more simple rules.


6. For every first-order formula {\phi(X)} with one free variable {X}, there is a node {D_{\phi}} with arrows from exactly those nodes {x} such that {\phi(x)} is true.

Gödel: The one catch is that {D_{\phi}} can be virtual, though the bound variables in {\phi} range only over non-virgins. But {D_{\phi}} need not always be virtual—the seventh rule will tell you when it is. If you accept this rule—like I said it follows from nine simpler ones—then you can define and use any first-order property of sets.

GLL: Any first-order property?

Gödel: Yes, but it is merely what the syntax gives you. We already have pairs, and I should show you now how to make ordered pairs.

Before writing rule 6 on the board, he drew diagrams above the cycle picture, saying these were the ordered pairs {(x,x)} and {(x,y)} for {y \neq x}:


GodelThruPairs


Gödel: We can now have a relation between virtual nodes, because its members are pairs comprised of an element from each and those elements are not virtual. Then we can define when the relation is a function, when it is onto, one-to-one, and a bijection. Well Johnny started with functions, but we have arrived there, and now we can state his rule—note that rule 6 defined {V}. This literally makes Russell’s paradox into a virtue.


7. A node is virtual exactly when there is a bijection between it and {V}.

Gödel registered our shock—this wasn’t like a building rule. He added helpfully, drawing a surjection arrow to symbolize rule 7:

Gödel: Well it doesn’t have to be a bijection—it is enough to have a function that is onto {V}.

GLL: How can we tell?

Gödel: When you are finishing saying how you are building the graph, you just have to tell how all your sinks have bijections. From {V} to {V} it is immediate, of course. But I showed this is equivalent to the schema of replacement, allowng virtual nodes as functions between sets like midwives, plus the Axiom of Choice extended to all nodes. If you accept the former, then since I showed the latter cannot be the obstacle that blocks you, you can build.


GodelAllRules


Dick and I exchanged glances. We were expecting the interview to end now, but Kurt was revved up and prancing around like a madman. We realized he would oblige any further request, so Dick ventured:

GLL: Can you tell us the nine simple rules and the other schema?

He was already starting to do so.

The Two Schemas

Gödel did not write anything more on the board he had filled, but rather dictated the following rules:

  • {V} represents True and {\emptyset} represents False;

  • We build {D} for “diagonal,” which has an arrow from every {(x,x)}, and represents {x = y}.

  • We build {M} for “member.” This has an arrow from every {(x,y)} where {x \rightarrow y}, and represents {x \in y}.

  • We build {\sim\!D} with arrows from all nodes not of the form {(x,x)}. Similarly we can apply {\sim} to complement any node. This represents negation.

  • For any nodes {A,B} we ensure there is a node {C} such that {x \rightarrow C \iff x \rightarrow A \wedge x \rightarrow B}. We write {C = A \cap B}, and here {C} too need not be virtual—for instance {D \cap M = \emptyset}. This represents Boolean AND.

  • For any node {A} we build a node {B} with arrows from {(x,y)} for all {x} and all {y} such that {y \rightarrow A}, allowing {x = y}. This represents introducing a variable and forms the Cartesian product {V \times A}.

  • For any {E} with arrows only from ordered pairs not in {D}, we build the node {R} with arrows from the “{y}” part of each pair. This forms the range and represents existentially quantifying the “{x}” parts.

  • For any {A} with arrows only from ordered pairs {(x,y)}, we can build {A'} with arrows from their reversed pairs {(y,x)}, with {x = y} being OK. And for any {B} composed of triples {(x,(y,z))}, we can build {B'} with triples {((x,y),z)} and {B''} with triples {(y,(x,z))}. Finally for {C} with quartuples {(w,(x,(y,z)))}, we build {C'} with quartuples {(w,((x,y),z)} instead. These rules represent enough ways to permute the list of variables in a formula.

Dick frantically took them down on his notepad. He slowed Kurt down only on the last one, which Dick wrote as four separate rules. Upon ending the last one, Gödel went stock-still, but did not look cross, so Dick queried him.

GLL: These are eleven rules?

Gödel: The last is almost one rule, but I call it three for pairs, triples, quartuples. And the first rule is just interpretation, not building, so it isn’t a rule—we have the empty set with infinity and {V} with complements. Hence I count nine. Whatever, this is finite and allows you to build the denotation of any formula in the original schema 6, so it is not a schema.

GLL: Oh.

Gödel: Main thing to notice is that the {x} parts of pairs cannot be virtual. Hence the formulas quantify only over non-virtual nodes, though the denotation itself for the free variable can be virtual. This limitation is completely natural. If you ignore it and allow formulas to quantify over virtual nodes, you cannot make a finite set of rules anymore. You get a stronger set theory, but the only ways I see how to build it are inaccessible…

We were starting to feel stupid and were afraid to ask what “inaccessible” meant. Instead we wanted to know more about Johnny’s rule.

GLL: Can you tell us the other schema?

Gödel: The only schema? If you forget virtuals and choice it is the only schema, and has to be. But it is still good to have it in my system, even though it isn’t needed.

GLL: The schema for Johnny’s rule…

Gödel: Yes. Johnny’s rule tells you when you can say a node is virtual. This rule—it is Abraham Fraenkel’s rule—tells you when you can say it is not virtual. If you have choice for all nodes then the effect is the same.

GLL: Please continue.

Gödel: The schema has one rule for every {E} that you define that is a function. It is called “Replacement,” though you can also use it for placement.


When you have defined an {E} that is a function, you obtain the rule that for any non-virtual {z}, if {Y} is such that for all {x \rightarrow z} there is {y \rightarrow Y} such that {(x,y) \rightarrow E}, then {Y} is colored black. Or you can place such a {Y}.

This made us happier than von Neumann’s rule, because it was talking about sets rather than “virtual” whatevers, and each individual rule concerned a function {E} that was expressly defined. Dick wanted to clarify that point.

GLL: {E} itself can be virtual?

Gödel: Yes. Of course, if you make {E} the image of another function with non-virtual domain, then you can color {E} black too. A midwife doesn’t have to be a virgin. The basis is that you start with {E} that are simple like {D} and {M} and combinations of them as above.

GLL: Does {x} have to be the whole domain of {E}?

Gödel: No, but if {x} is definable, then we can define {E} restricted to {x} anyway. Also {E} needs only to be a function on {x}.

I cut in.

GLL: Since we can define what it means to be a function, why don’t we just quantify over {E} in the rule, so we have just one rule not a schema? We can also define “{x} is non-virtual” by saying {(\exists y) x \rightarrow y.}

Gödel: Letting {E} be arbitrary would lose the sense of building, and also it would be a universal quantifier over virtual objects inside a rule. This was also my first feeling about Johnny’s rule, until I saw it can be proved from replacement if you have choice.

Dick and I stiffened up. We were about to hear the Axiom of Choice from Gödel himself.

One Choice

Kurt strolled over to his greenboard and solemnly drew a white circle between {V} and {t}. He labeled it {F}. Then with a flourish he drew bang in the middle a sketch with an arcing dashed arrow he called the action of {F}.

Gödel: You need only an existential quantifier for this virtual object:


There is a virtual node {F} such that for all non-virtual nodes {x} other than {s}, there is a unique {y} such that {(x,y)} has an arrow to {F}, and that {y} has an arrow to {x}.

Dick and I totally missed what he said. We thought the axiom of choice always began with the words “for every,” as in “for every collection of nonempty sets…” We were expecting to hear the word “function” again. Dick nicely spared me the embarrassment by taking it on himself.

GLL: I’m totally sorry, I missed what you said.

Gödel repeated it calmly, and then said:

Gödel: Of course {F} is a function, and it is global, so this is called the Axiom of Global Choice. {F} is last like {V}, but always there with you from your first placement after {s}. Of course you see why its presence does not interfere with building.


GodelComplete


It took only a few seconds to hit us that Kurt was saying his famous proof of the relative consistency of the axiom of choice—in his stronger version—was something we should see immediately.

GLL: Right—I see—it’s not going to get you into trouble like when you placed {x} above the {p,q,r} cycle, because you’re not placing anything else. You either believe {F} exists, or you don’t.

Gödel: If you believe {V} exists, then you should believe {F} exists.

I was still going to play Doubting Thomas.

GLL: Can’t you get into trouble, when placing {x}, with what {y} you choose? What if you commit to a bad {y}? Could that screw up the pairs in {F}, so that you have a problem with in-neighbors to a pair?

I realized that was silly before I finished—all the pairs in {F} are already present, and rule 2 trivially holds for {F} itself. Gödel read my facial retraction, and simply put his palms out.

But then Dick swiveled around to me and whispered something about finite choice and complexity that he had posted on. I caught Dick’s drift and spoke up again in a firmer tone.

GLL: Herr Professor Doktor, what is the complexity of {F}? What if I make my choices of {y} a super-complex function, vastly uncomputable. Is {F} going to catch that? What I really mean is, what if the only {F} is super-complex, “inaccessible” like you said? Then we don’t see how to build the choices—and isn’t that what you need to say you can build {F}?

Gödel flipped the chalk in his hand, and distorted his face as if it were a rubber mask he was about to tear off, but gave a snorting chuckle and sounded recomposed.

Gödel: Woher kommt diese Frage? Aber… But I tell you, after we sorted out this trouble with Max Zorn and Kazimierz Kuratowski, we realized {F} can always be simple.

Dick reacted and led the rest of the interview.

GLL: If you believe in {F}, then it is simple?

Gödel: Ja, equivalently. For one thing {F} is equivalent to there being a well-ordering of {V}, from which you get {F} by taking {y} to be the least element among the possibilities. And the well-ordering itself can also be a simple consequence of how you build:

When you placed {x}, there is always some in-neighbor {y} such that previously when {y} was placed, none of the other in-neighbors of {x} were there yet. This is the {y} you choose.

GLL: You cannot have two such {y}, because just between any {y} and {y'}, one of them must have been placed earlier and been there for the other. Having no such {y} is similarly unthinkable. But you said you wouldn’t put the ordinal idea into the rules.

Gödel: I didn’t. Did I say that? The rule is what I said before. This is just the intuition. These last two rules, replacement and choice, are equivalent to rule 7 anyway. Rule 7 gives you a finite axiomatization, but I prefer the other two rules for my thinking. They convince me that Johnny’s rule is good.

GLL: I must admit, the intuition is clear. And we know from our recent discussion of first-order models that the graph itself can always stay countable, even while it is modeling Cantor’s Theorem.

Gödel: Any trouble you have building with choice, you have already with the other rules on the board. Rule 6 already restores the Eden we had with “naive” set theory, provided we acknowledge the original sin from Russell’s paradox. But to make it a kingdom, we should have the action of choice.

Math as a Graph

Dick and I stared at the eight rules. We wondered how they could possibly capture virtually all of mathematics as we know it, all of computer science theory. But they do. Every theorem we know can be systematically encoded in this language and proved with standard first-order logic plus these rules. Even second-order and higher logic can be simulated by quantifying over sets.

Only the “sets” we were looking at were just dots with arrows in graphs. The graphs don’t even have any cycles. Directed acyclic graphs—DAGs—are about the simplest things we work on in algorithms and theory. How can they execute everything?

GLL: So if we can build the graph, then set theory—your set theory—is consistent?

Gödel: ZFC set theory too. They are equally consistent. Any statement that does not mention a virtual node—or involve my notion of coloring a node white or black—can be proved in my system with Johnny and Bernays, if and only if it can be proved in ZFC. Ours is a “conservative extension.”

GLL: So your system has exactly the same power for expressing mathematics, the main body of mathematics…

Gödel Ja, genau. But outside the body, people complain that the virtual nodes complicate Paul Cohen’s forcing idea. I think it is better to think of the body as something you can perhaps extend by a 17th rule, one that can be like the Unified Field Theory which Albert was looking for.

GLL: But the body we have cannot tell whether the graph exists.

Gödel: Right—the 16 rules cannot prove their own consistency.

GLL: Yet all you’re talking about is the existence of a countably infinite directed acyclic graph. One graph. One with constructive rules for building. So we can’t use our whole math curriculum to determine that this graph exists?

Gödel: No. You must only believe it, or look for higher rules—like I am also doing.

GLL: It seems like the only obstacle is what you sketched with the cycle, from Rule 2.

Gödel: Pretty much. But also you must start with Rule 8…

GLL: So that is it. All of math in one graph.

Gödel: Math in a graph, yes, Johnny was one step ahead again this time.

GLL: Thank you very much, Herr Professor.

Gödel: Bitte schön.

GLL: Can we see you again sometime?

Gödel: Should be possible. But you will need new science.

And with that the professor and the chalkboard became enmeshed in a noise of dots and lines on our screen, until it all went white.

Open Problems

Do you see how to build the graph of math? Are you convinced it is entirely there?

As an exercise, can you complete the first-order infinity rule, which Gödel left “non-finito”?

[fixed two counts of the “simpler rules” from “eight” to “nine”; added link to Morse-Kelley’s “stronger set theory”; woher-to-woraus-back to-woher; spot word tweaks]

20 Comments leave one →
  1. November 15, 2013 10:28 pm

    whoa, thats some super abstract stuff there dudes.
    DUDE, WHERES MY CAR?!
    psychadelic man!
    its like a long story without a punchline.
    are you gonna reveal what the heck theory you are talking about? could someone enlighten me in the comments at least?
    the idea of reducing all math to DAGs/graph theory is quite interesting though.
    it fits in with a research program Im developing of reducing all math/CS to automated theorem proving…. hey dont laugh, gowers has expressed similar ideas….

  2. November 16, 2013 9:28 am

    As a disclaimer, the words “something we didn’t know from his writings” in the introduction indicate that this is more fictive than the other two interviews. I was not able to take time to read Gödel’s primary sources. I picked up the “graph” idea from Peter Aczel’s theory of Non-Well-Founded Sets, more generally the notion of an accessible pointed graph.

  3. November 16, 2013 2:32 pm

    Ah, but a man’s reach should exceed his graph,
    Or what’s Aufhebung for?

  4. November 16, 2013 3:30 pm

    Re: “Kurt Gödel is said to have been a latecomer to appreciating the power of Model Theory.”

    Whether this light flashed onto model theory earlier or later than any other light we might name is of course relative to one’s frame of reference — and the train of thought known as model theory has not by any reckoning been standing still at its point of departure.

  5. November 16, 2013 9:11 pm

    KWR thx for the punchline. you guys are quite a tease sometimes. was lost without it. reading the 2nd ref on “accessible pointed graph”. why do you suppose they dont refer to a DAG in that description as you do? its much simpler/more intuitive. are they talking about a DAG? if not, wondering about that difference & what it could represent.

    scanning that gives me a rough idea/reminds me of another analogy, more applied. was just reading a post on tcs.se talking about how its an open problem if some of the type constructions in modern languages such as java/.Net are well-formed, which turns out to be a nearly-undecidable problem with all their complexities. the idea of creating types that are built out of other types in OOP (objects that have inheritance vs composition etc) and seems very similar. an object that is composed of other objects represents a natural graph describing the composition relationships. although there it can be a graph and not merely a DAG….

  6. November 18, 2013 8:29 pm

    I thought this thread was going to generate a lot more comments. Did suggesting that “Johnny” got it right scare everyone off? In any case, my favorite line from the dialogue was,

    ” GLL: Yet all you’re talking about is the existence of a countably infinite directed acyclic graph. One graph. One with constructive rules for building. So we can’t use our whole math curriculum to determine that this graph exists?

    Gödel: No. You must only believe it, or look for higher rules—like I am also doing.”

    Is there always a part of the empirical presentation that is just given? A Law? Some feature that can not be either proven or derived; it just is?

    • November 18, 2013 11:46 pm

      Well …

      I know not what course (of instruction) others may take from this, but for my part most of the recent posts on this blog throw me back to the days of my earliest foundational crises in math, when I found myself asking things like, “What the heck is a (1) definition, (2) (3) axiom, (4) rule of inference, (5) theorem, (6) proof, (7) model, …, anyway?”

      A lot of water has passed under the bridge since then, and bit by bit I found my own ways of gaining a few quanta of clarity on those issues — ironically enough it was the discipline of concrete computing and practical programming that kept my feet on the ground when the totalitarian tendencies of abstract math threatened to fill my head with gas — but all those impressions flooding my mind leave me with nothing very apt to add here.

      • November 18, 2013 11:56 pm

        edit — (1) definition, (2) axiom, (3) rule of inference, (4) theorem, (5) proof, (6) model, …

    • November 18, 2013 11:55 pm

      Gödel’s incompleteness theorems express that what you can prove in any reasonably strong formal system stops short of what is true—that is, true in a distinguished model. That statements in the difference such as G&oumldel’s T—or the consistency statement it depends on—can still be considered one’s knowledge was the basis of J.R. Lucas’ defense of his argument when we had a friendly staged debate at Merton College in 1986. (My attack was that since Peano Arithmetic could prove Gödel’s theorems, what about your argument really separates people from PA? It was blunted by my not being able to knock “knowledge” down to “mere belief” or say PA could have it.) I do believe I’ve faithfully represented Gödel’s confidence in knowing the ZFC axioms and his to be true—and more concretely, that his “Constructible Universe” L is a model—but my dialogue opens in the context of attending to those who have greater doubts about consistency. (I chose to leave “L = V” and Suslin’s Hypothesis unmentioned; I also stopped short of saying replacement is needed to construct the ordinal ω+ω; I may be guilty of minimizing the effect of the powerset axiom.)

  7. John Sidles permalink
    November 19, 2013 5:50 pm

    Attributed [by GLL] to Kurt Gödel  “Possibility in mathematics — which is when falseness is not necessary — [is] about the truth of being able to build models (I thought about this again after hearing some of Johnny’s [von Neumann’s] last ideas).”

    As a further affirmation of Kurt Gödel’s guidance — as channeled by GLL — John von Neumann’s very last book (namely the still-in-print The Computer and the Brain, 1958) has as the title of its very last section (page 81) “The Language of the Brain is NOT the Language of Mathematics”

    If we take an equivalent title to be “The Language of the Brain is a MODEL of the Language of Mathematics”, then von Neumann’s final work foresees the accelerating present-day synthesis of model theory, mathematical naturality (in the sense of Eilenberg/Mac Lane/Grothendieck etc., and arguably Chomsky too) and cognitive neurobiology.

    Aye lassies and laddies, now that’s foresight!

    • November 19, 2013 10:22 pm

      What — if anything — is the common sense that connects the different senses of the word model, as it is and has been used over the years in logic, math, and the special sciences? It’s a problem I’ve been running into for several decades now and I think I can trace the roots of it going back as far as Aristotle’s treatment of analogy. Just by way of creating a bit of trans-disciple-ary interaction, here’s a link to a link of the issue’s most recent arising in my own roll of blogs.

      Objects, Models, Theories

    • John Sidles permalink
      November 20, 2013 5:00 am

      Jon Awbrey asks  “What — if anything — is the common sense that connects the different senses of the word model, as it is and has been used over the years in logic, math, and the special sciences?”

      People have been asking that question ever since unknown artisans began to craft models like the Woman of Willendorf. Ever since, we humans have been wondering “What is it that our models represent?”

      The philosopher Hilary Putnam’s essay “Models and Reality” (1980) includes a prescient section “Operational constraints and counterfactuals” that addresses various model-related issues that perplex today’s STEM community.

      For example:

      • Even in principle, does there exist a model for the languages in the complexity class P that consists of a subset TM/P of Turing Machines (TMs) that accept those languages? And if the answer is “yes”, then for a specified language L in P, can the model set TM(L)/P be constructively restricted to the subset TM(L)/P/E of TMs that are most efficient? Can the overall set TM/P/E be ordered, and can a claimed ordering be verified?

      Broadly, do complexity classes have models that can be constructively exhibited as TMs, in the familiar sense that real numbers have models that can be constructively exhibited as binary expansions, and high-level programs have models that can be constructively exhibited as compiled code?

      • Similarly (and directly inspired by Putnam’s examples), do there exist models for stochastic processes? And what does it mean to assert that a model accurately represents a stochastic process?

      Broadly, by what constructive mathematical means do we verify the consistency of a claimed stochastic model of an abstract random process?

      Ongoing advances in BosonSampling theory and experiment, and the sustained Moore’s Law acceleration of classical and quantum simulation capability, and the many still-unanswered questions relating to PvsNP, all require increasing precision and acuity in reducing these tough model-related questions to constructive practices.

      • November 20, 2013 3:44 pm

        Funny you should mention those paleolithic pulchrinudes …

        I was sitting in my usual haze in a logic course taught by Larry Moss (A^2 ~ 1986?), when I heard him punch up something he’d been saying by asking the class, “And where do these models come from?”

        My wisecrack, one of my best ever — “The Modeling Agency❢”

Trackbacks

  1. Objects, Models, Theories : 2 | Inquiry Into Inquiry
  2. Objects, Models, Theories : 3 | Inquiry Into Inquiry
  3. Objects, Models, Theories : 4 | Inquiry Into Inquiry
  4. Predictions For The New Year | Gödel's Lost Letter and P=NP
  5. Constructive Sets | Gödel's Lost Letter and P=NP
  6. Reconstructing Gödel | Gödel's Lost Letter and P=NP
  7. The World Series Of Complexity Theory | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s