Thoughts on Gödel, Escher, Bach

I checked out Douglas Hofstadter’s Gödel, Escher, Bach at the beginning of the (fall 2021) semester, reading a bit most nights before bed. Coming in at a hefty 777 pages (nice), I only managed to finish it this winter break. It was the most unique book I’ve ever read in many ways, so I’ve tried to collect my thoughts as documentation for anybody interested in reading it as well and my future self.

It is hard to say what the book is actually about. The title implies drawing connections between math, art, and music, but the author insists his goal was to show how meaning can emerge from “meaningless” components, like how simple neurons give rise to consciousness. I personally felt like it was mainly a treatise oriented around Gödel’s Incompleteness Theorem and its philosophical implications. The gist of Gödel’s Theorem says that any consistent (that is, free from contradictions) method of reasoning about number theory is incomplete (that is, there are true statements of number theory that cannot be proved). In doing so, Hofstadter touches on literally everything, including, but not limited to, formal systems, recursion and self-reference, linguistics, paradoxes in art and logic, classical music, number theory, Zen Buddhism, neuroscience, microbiology, computability theory, and artificial intelligence.

The book consists of an introduction, an extensively annotated bibliography that is by itself excellent research material, and twenty chapters that are each preceded by a fairy tale-esque story that gives a taste of the topics to come in a more informal and playful setting. I will only attempt to summarize Gödel’s Theorem because I think it forms the core of the book and the common thread through all of its subject matter runs through, but I should note that the book isn’t interesting because of its treatment of Gödel’s Theorem. There are probably a million papers, YouTube videos, and Medium articles that do a great job of explaining Gödel’s Theorem to a non-mathematician. The beauty is in how it manages to tie a seemingly obscure result in number theory to a huge range of disciplines.

The Fascinating History of Metamathematics

When I first heard of the Incompleteness Theorem, I found the idea that math can be used to prove its own incompleteness amazing. How would one even start to go about that? I will start by providing some historical context. It is not necessary to understand the proof and this paragraph can be skipped, but I think it is interesting and worth going over. The story starts with the discovery of Bertrand Russell’s paradox at the turn of the twentieth century, which concerns itself with the theory of sets, or collections of items. Consider a set R defined as the set containing all sets which are not members of themselves. That is, an element x belongs to R if and only if x does not belong to x. Does R contain itself? If so, then its predicate is false, implying that the answer is no. But if R doesn’t contain itself, then it fulfills the predicate, implying that the answer is yes. To resolve this foundational crisis, Russell and Alfred North Whitehead wrote Principia Mathematica, where they aimed to show how all of known math can be derived from some basic axioms (a fancy word for a statement so obvious it is assumed to be true, like “zero is not the successor of any natural number”) and well-defined rules of inference that let you prove new theorems from simpler ones (like “if either a or b is true and a is false, then b must be true”). To give you an idea of its rigor, it took over 300 pages for them to get to the point where they could prove 1+1=2! Now, can it be proven that a formal system such as Principia Mathematica is consistent and complete? Gödel’s Theorem shows that this is in fact impossible.

Gödel’s Proof

A statement of number theory can be represented by a set of symbols. For example, the famous Goldbach conjecture can be expressed as follows:

\[\forall a:\exists b:\exists c:\neg(\exists d:\exists e:SSd \cdot SSe=b \lor SSd \cdot SSe=c) \land a+a=b+c\]

This roughly translates as “for all a, there exist b and c such that there are no d and e where b or c is equal to the product of d plus two and e plus two and b plus c equals a plus a.” More succinctly, “for all a, there exist b and c such that their only factors are one and themselves and a doubled equals b plus c”. Or, finally: “for all even numbers a, there exist two primes b and c that sum up to a.” The spark of genius is the idea of assigning each symbol to a number, known as Gödel numbering. Using the coding in the book, the above would be mapped by an absolutely massive integer that starts with 626 (code for the “for all” symbol) and ends with 262,163,163 (code for the variable “c”).

With that out of the way, we need two more concepts. The first is the notion of proof pairs. We say PROOF-PAIR(s, e) if s is the Gödel number of a valid and sound proof consisting of a sequence of strings that ends in the string whose Gödel number is e. The second idea is arithmoquining. We say ARITHMOQUINE(u, w) if u is a formula with at least one free variable and substituting the Gödel number of u into all of its free variables produces w. The book asserts that any procedure that is guaranteed to finish in a finite amount of time is embeddable by a formula of number theory. This is by far the biggest leap of faith in the proof in my opinion, and I would have loved to see Hofstadter elaborate on this step despite the book being already as long as it is. But accepting this claim, testing a proof pair and arithmoquining a string are both predictably terminating functions and thus can be represented by a string made of the same symbols that we used to express the Goldbach conjecture above, though it will be monstrously long.

Now all the pieces are assembled. Consider the following string:

\[\neg \exists a:\exists b:\text{PROOF-PAIR}(a, b) \land \text{ARITHMOQUINE}(c, b)\]

This has a Gödel number which we can call u. Now what happens if arithmoquine this very sentence? Substituting u into c, its only free variable, results in the below. (Assume there are u S’s.)

\[\neg \exists a:\exists b:\text{PROOF-PAIR}(a, b) \land \text{ARITHMOQUINE}(SSS..SSS0, b)\]

We have finally obtained Gödel’s sentence. Literally, it says “there are no numbers a and b such that a is the derivation of b and b is the arithmoquinification of u.” In other words, “there is no proof for the arithmoquinification of u.” But this very sentence was obtained by arithmoquining u! So in essence, Gödel’s sentence translates into “this sentence has no proof.”

What are the implications of this? If we say that Gödel’s sentence is a lie, then we imply that it there is a proof for it. But that means our formal system has a contradiction because it can prove a false statement. So we are forced to conclude it is telling the truth. Therefore, we have found a true sentence that does not have a proof, rendering math incomplete.

Personal Review

If I had to review the book in one sentence, I would say “incredible concepts, lengthy presentation.” At times, I felt like the book was written just for me. It’s literally a collection of everything I’m interested in. I loved the first ten chapters on formal systems, meaning in math, figure and ground, recursion and self-reference, and computer organization. Some people thought the dialogues were unnecessary and pretentious, but I thought they added a funny and often amazingly clever element to the formal-ness of the rest of the book. (I never thought I would laugh at a story about a tortoise repeatedly destroying a crab’s record player as a metaphor for Gödel’s theorem.) I also enjoyed chapters thirteen through seventeen which introduce Gödel’s proof, its philosophical implications, and related ideas in computer science like primitive/general/partial recursive functions, the Church-Turing thesis, the halting problem, and the Entscheidungsproblem (took me several tries just to Google how to spell that).

On the other hand, I found the four chapters where the author speculates on brain processes and AI relatively boring and I would not miss them at all if they were cut out. I’d say the book’s biggest flaw is that I’m still not sure what its trying to say, which would be a lot less of a problem if it weren’t over 700 pages long. A minor detail is that the section on AI is quite dated. For instance, the author asserts that chess programs will never surpass humans until general intelligence is achieved, but this is a reasonable viewpoint given the book was published in 1979. The rest of the book is timeless and absolutely worth reading if you like the feeling of your brain physically expanding.