Monday Notes 8–20–18

What I’m Reading

Gödel, Escher, Bach by Douglas Hofstadter, pages 51–68

The Dialogue of this chapter is a paraphrase of a story written by Lewis Carroll. In this section, the Tortoise and Achilles demonstrate what it means to convince someone by the process of argumentation. At each step, Achilles proposes a logical argument which is then immediately refuted by the Tortoise. The story attempts to demonstrate that language and thought do not necessarily follow formal rules. There are no arguments which are guaranteed to make an audience accept a conclusion — particularly if that audience is a mildly ornery tortoise.

The chapter then begins with the introduction of another formal system: the pq system. Hafstadter demonstrates several properties of this syntactic system to show that certain strings are clearly possible while others aren’t. In contrast to the MU system of the previous chapter, the pq system can only create strings of increasing length. This means that it is possible to produce all strings of given length in a finite number of operations. It is therefore possible to create a process by which to determine whether or not an arbitrary string is a theorem — i.e. it is valid — of the pq system.

The author then moves to the big reveal: the pq system can be interpreted as statements about the addition of the natural numbers. There is an isomorphism between theorems of the pq system and facts about addition within the natural numbers. This isomorphism is called an interpretation of the formal system. We can then show that the formal system is consistent; it does not produce theorems whose interpretations are not valid statements about natural numbers.

Escher’s work Liberation is introduced and used as a metaphor for the differentiation of the formal properties of theories with the true nature of the systems they attempt to describe. We are then brought to Euclid’s proof of the infinity of the primes. The theorem itself is of the form, “For any number N, there is a prime larger than N.” What this gives is an unending list of statements about there being some prime larger than a given number. We have somehow gotten an infinite number of rules from a single proof.


Gödel, Escher, Bach by Douglas Hofstadter, pages 69–81

With that the chapter ends and thus a new Dialogue is brought in. In it, we hear Achilles’ side of a telephone conversation between himself and the Tortoise. While we do not see the transcription, Achilles’ lines indicate that the Tortoise has proposed a puzzle to find a word in which a certain series of letters appear consecutively. While the analogy may not yet be clear, the two characters make reference to Escher’s Mosaic II, in which a multitude of creatures tessellate the view, leaving no space to be interpreted as “background.”

The chapter’s focus is on that of figure and ground in art. That is, the object being depicted by the work in contrast to the setting in which the object is presented. The author seeks to raise the questions, “Can the figure completely define the ground? Can the ground completely define the figure?” The mathematical example he uses is that of the primes. Can the primes be defined as all those numbers which are not composite? Can the composites be defined as all those numbers which are not prime?

To indicate that the above questions are not so easily answered, Hofstadter gives some examples of artwork in which what appears to be ground should actually be interpreted as figure. There is an example below.

At this point, I’m not sure if the background on this page makes the “answer” obvious, or if my own knowledge of it precludes any other interpretations

After the graphic art examples, a musical example is presented. Bach would often introduce a theme as melody only to have it reappear later as harmony, thus blurring the lines between figure and ground.

Bringing us back to mathematics, the distinction between figure and ground might be phrased: Given a formal system A, is there a formal system B for which all non-theorems of A are theorems of B? Can we define the “ground” of A is the “figure” of some B? The answer is, quite remarkably, no. There are in fact formal systems for which the non-theorems are not theorems of any formal system. From this fact we can begin to see some hints of Gödel’s incompleteness.


Mathematical Logic by Chiswell & Hodges, pages 1–54

CH Logic is the first textbook recommended in Teach Yourself Logic by Peter Smith at the University of Cambridge. The text starts from the very basics of formal logic and builds all the way up to First Order Logic. So far the authors have been very methodical, providing examples and suggested problems for each new concept that is introduced. That being said, it was definitely written for an audience with a foundational knowledge of mathematics.

The first several chapters have been focused on natural deduction. In natural deduction, valid strings are called sequents. One can derive new sequents by applying various deduction rules. The text demonstrates how various sequents and deduction rules can be used to write formal statements which correlate directly with our intuition about logic.

Learning how to produce proofs using natural deduction has been a very interesting exercise. The syntax is quite different from the algebraic manipulations of equations that I’m accustomed to. My hope is to learn more about the general forms of formal languages, and thus far CH Logic has been an excellent resource for learning one of the simplest forms of expressing formal logic.