GEB: An EGB overview (Part I)

I’d started some time ago, and just recently finished reading the first part of Gödel, Escher, Bach: An Eternal Golden Braid. Here, I will present my quick overview of each chapter.

This quick overview/summary only serves as a reminder to myself. I encourage you to read the book, it is a very good book. It is written in a way that makes you think about how the author formed some of the chapters (an analysis of his analysis, in a way). It is also filled with puzzles and riddles, some of which you can go on reading without even noticing. 🙂

I will talk a little bit about how I come up with this overview (in this overview itself). Before reading the book, I’ve watched the MIT lectures on the book (did they or did they not help in grasping the book more easily? I don’t know). Anyway, once I started reading the book, first I read all of the chapters one by one. Then, to construct this overview, I skimmed through the chapters quickly to see what “stuck” to my mind, and post it here.

Preface

In the 20th anniversary preface (1999), the author talks about how the point of the book was missed – it is not (only) about the relationship between mathematics, arts, and music, but how “animate beings can come out of inanimate matter”. He also talks about how the book came to be.

Chapter I: The MU-puzzle

Introducing formal systems: strings, well-formedness, rules, axioms, theorems. Thinking/jumping outside of systems. For the MIU system we (intelligent humans) oscillate between Mechanical and Intelligent mode, whereas machines are only capable of M. More on Un-mode (Zen) later.

One possible way for a decision procedure is to generate all possible theorems applying each rule, in a tree structure. Some time ago I’ve implemented something like this in Racket (and then also in Haskell), Simple Theorem Prover.

Chapter II: Meaning and Form in Mathematics

The pq-system is introduced. It represents addition, for example, $-p--q---$ is the “same” as $1 + 2 = 3$ . What’s a better word than “same”? Isomorphism – mapping two complex structures onto one another. So the pq-system is isomorphic to addition – $p$ can be mapped to $+$ , $q$ to $=$ , one to $-$ , two to $--$ , etc. Isomorphisms create meaning. If we did not interpret/map the addition isomorphism to the pq-system it would look “meaningless”. Another valid interpretation is $p \iff \text{equals}$ , $q \iff \text{taken from}$ .

pq-system is limited as we can’t reason about numbers within itself at the object language, only at the meta language. More on this in later chapters.

symbols of a formal system, though initially without meaning, cannot avoid taking on “meaning” of sorts, at least if an isomorphism is found

Can reality be mapped into a formal system? At a first glance it seems so. It’s shown how complex counting can get (1+1 water drops vs 1+1 abstract). So let’s limit ourselves to abstract for now.

A brief proof (in English) is given that there are infinite primes. We’ll see later how complex proofs like this can be, if we want to be super precise by representing them in the object language. The example shows the need of a “forall” predicate.

Chapter III: Figure and Ground

The tq-system is introduced – it captures multiplication on numbers. A rule for composite numbers is created and then the “holes” in the produced theorems by this rule will be prime numbers. Composite numbers are to prime numbers what figure is to ground. However, there are formal systems where this figure/ground isomorphism does not hold (more technically: there exist recursively enumerable sets which are not recursive).

Chapter IV: Consistency, Completeness, and Geometry

There’s a dialogue before the chapter which has self-referential usages. The chapter starts by discussing (different levels of) it. There are explicit (what’s written, the actual story) and implicit (analyzing the story at the meta-level) meanings. Per Gödel, self-reference causes some systems to resist being incorporated into any formal system.

A formal system is consistent if every theorem comes out “true” when interpreted. A rule is introduced to the pq-system which makes it inconsistent with the external world, however, consistency is regained by changing the interpretation.

A formal system is complete when every “true” statement is produced by it. A rule is introduced to the system which makes it incomplete. To fix this we can add new rules (make it more powerful) or tighten the interpretation.

We can embed formal systems into formal systems in a hierarchical way.

Related to the “Relativity” figure: We reinterpret the picture over and over until it’s free of contradictions – but it is impossible, whenever we backtrack another issue occurs. The ultimate “escape route” is the Un-mode – Zen.

Is mathematics the same in every world? At least in terms of logic, yes, for if we want to communicate, we have to adopt a common base. However, there are other systems such as Zen that embrace contradictions, so what can one say more about it?

Chapter V: Recursive Structures and Processes

Recursion, even though it looks circular (because it refers to itself), when properly defined it never leads to infinite regress or paradox. This is so because it refers to a simpler version of itself.

Stacks and Push/Pop operations are introduced. Recursive Transition Networks are introduced which represent a “computer program”. An analogy is made RTN to music notes. The figure “Fish and Scales” is presented to demonstrate copies and sameness.

Recursive enumeration is a process in which new things emerge from old things by fixed rules. Think “snowballing” from the axioms using the rules to infinite sets.

Chapter VI: The Location of Meaning

Information bearers: theorems in pq-system, information-revealer: interpretation. How do we identify a frame to see if there’s any message at all? Three layers of a message: inner message (meaning), frame message (recognize the need for a decoding mechanism), outer message (decoding of the inner message).

For example, consider a bottle washed up on a beach. The frame is when one picks up the bottle (recognizes the bottle is an information bearer). Open and examine the bottle – text is in Japanese. The outer message is “I am in Japanese”. The inner message can be anything.

Even though different people’s “jukeboxes” have different “songs”, human brains are constructed so that one brain responds similarly as another one. This is why we can mostly understand each other.

Chapter VII: The Propositional Calculus

This chapter captures logic (Gentzen, 1934) in a formal system. It introduces atoms, formation rules, and the “fantasy rule” – implication. It also shows how subproofs can be embedded within proofs, and also makes an analogy with recursion.

You can’t go on defending your patterns of reasoning forever, there comes a point where faith takes over.

I found the most powerful sentence so far to be contained in this chapter. It is due to the fantasy rule and recursion: If we have $a \land b \to z$ and $a \land b$ then we have $z$ but Tortoise squashes the argument saying “oh, you mean $((((a \land b) \to z) \land (a \land b)) \to z)$ “, etc. “infinite regress”

Propositional calculus steps neatly from truth to truth, just as a person who is concerned with staying dry that steps carefully from one stepping-stone to the next. What is impressive is that the whole thing is done purely typographically.

However, typographically (Mechanical) is limited. To see why here’s one meta theorem: $(\lnot x \lor \lnot y)$ and $\lnot (x \land y)$ are interchangeable. It is a meta theorem because it is not part of the system. Why not formalize the metatheory too? Because there are infinite levels to formalize.

What about contradictions? We step outside the system to handle them.

If you found a contradiction in your own thoughts, it’s very unlikely that your whole mentality would break down. Instead, you would probably begin to question the beliefs or modes of reasoning.

Chapter VIII: Typographical Number Theory

TNT will allow us to represent natural numbers and we will embed Propositional Calculus in it. Numerals, variables (unspecified numerals), atoms, quantifiers, rules for well-formedness, and axioms are presented for TNT.

Even though more powerful than pq- and tq- systems, something still seems to be missing: We can prove $(0 + 0) = 0$ , $(0 + S0) = S0$ , $(0 + SS0) = SS0$ , but we can’t show that this goes infinitely. Thus the system is $\omega$ -incomplete – all strings in a pyramidal family are theorems but the universally quantified summary isn’t. So we can’t show either $\lnot \forall a:(0 + a) = a$ or $\forall a:(0 + a) = a$ – thus this string is undecidable in the system. Induction as an axiom fixes the issue.

Chapter IX: Mumon and Gödel

In Zen Buddhism, there is no way to characterize what Zen is. Even so, Zen koans are “triggers” that (even though partial, incomplete stories, they) may lead to “enlightenment”. A few koans are shown such that they break logical rules. One of the koans uses “MU” (Un-mode) to “unask” a question that cannot be Mechanically or Intelectually solved.

We are limited in what we can express using words. Logic is also limited. Thus, the major part of Zen is to fight against words – to suppress perception, logic, words, thinking (similar to rocks/trees).

In questioning perception and posing absurd answerless riddles, Zen has company, in the person of M.C.Escher. (think Relativity)

Before explaining Gödel numbering, I enjoyed this statement:

From the ethereal heights of Jōshū’s MU, we now descend to the prosaic lowlinesses of Hofstadter’s MU.

The MU puzzle is encoded into number theory, and a solution is possible right away. We used another formal system to reason of a formal system.

With Gödel numbering any formal system can be embedded into number theory. Number theory within number theory is encodable: 0 is 1, S is 2, = is 3, so $0 = S0 \iff (1, 3, 2, 1)$ . The theory this way can reason about itself at the object-level instead of relying on the meta-level. This self-reference, although powerful, causes the issue of incompleteness.