Skip to main content

This is a series on the book Gödel, Escher, Bach: An eternal golden braid by Douglas Hofstadter.  

Earlier diaries are here

Today, we will examine  On formally undecidable propositions of TNT and related systems p. 439 - 460.

This chapter isn't very long,  but it's very dense, and will take some very slow reading (at least, I had to read it slowly!)  But it repays slow, careful reading, as it gets at the key idea of Godel's proof.

From the overview

This Chapter's title is an adaptation of the title of Godel's 1931 article, in which the Incompleteness Theorem was first published.  The two major parts of Godel's proof are gone through carefully.  It is shown how the consistency of TNT forces one to conclude that TNT (or any similar system) is incomplete.  Relations to Euclidean and non-Euclidean geometry are discussed.  Implications for the philosophy of mathematics are gone into with some care

On page 438, DH says that this chapter is "more intuitive" than Godel's paper; undoubtedly true.  But maybe not quite intuitive enough?

My view of the central idea is as follows:
You can make statements IN number theory that are ABOUT number theory, and one statement you can make is "This string is not a theorem". This brings the paradox of "this statement is false" into any formal system that is sophisticated enough to express it.  BOOM.

Then we have to show that each of the parts of this idea are correct:
a) you can make statements about number theory IN number theory
b) you can make a statement "this string is not a theorem".

The first thing DH introduces is proof-pairs. Here's the idea:

  1.  In any formal system, change the rules to rules of arithmetic.  (DH did this in Chapter 9).  
  1. Express a derivation of a theorem in arithmetic (this will be a VERY LONG number, but it doesn't matter).
  1. A proof pair two numbers: The first is that huge number, the second is what we set out to prove.

The next key idea is to distinguish between a proof pair and a proof.  Proof pairs can be analyzed in a finite number of steps .... maybe a huge number, but a finite number.  Therefore, they can be represented by TNT, and there is a TNT number for PROOFPAIRNESS.  But the general concept of proving a theorem can NOT be analyzed in a finite number of steps, there is NO TNT number for this.  It's the difference between:

This is a proof of X
X can be proven

On p. 442, one might wonder why 666,111,666 zeroes .... well, by the coding scheme:
666 is 0
111 is =
666 is 0

so, the text

there exists a such thatt TNTPROOFPAIR(a, SSSS....0/a')

is saying what DH has right above "There exists a number a which forms a proof pair with 666,111,666 as its second element" which means that there is a proof of 0 = 0.

On p. 444, near the bottom, here's what I made of the two strings.

  1. means (a + a) = SSSS0

        SS0 + SS0 = SSSS0

that is, the following derivation:
  a + a = 4
  a = 2
  2 + 2 = 4

  1. means  ~(a*a)=a'

         ~(S0*S0) = a'
that is
  a*a does not equal a'
  a = 1
  1*1 not equal a'

the latter is incorrect - it does not simply substitute 1 for all free variables.

On p. 449, Godel's second theorem - either G or ~G must be correct, but neither is a theorem, so the system is incomplete.

The supernatural numbers are really cool.  

Originally posted to plf515 on Sun May 31, 2009 at 02:57 AM PDT.

Your Email has been sent.
You must add at least one tag to this diary before publishing it.

Add keywords that describe this diary. Separate multiple keywords with commas.
Tagging tips - Search For Tags - Browse For Tags


More Tagging tips:

A tag is a way to search for this diary. If someone is searching for "Barack Obama," is this a diary they'd be trying to find?

Use a person's full name, without any title. Senator Obama may become President Obama, and Michelle Obama might run for office.

If your diary covers an election or elected official, use election tags, which are generally the state abbreviation followed by the office. CA-01 is the first district House seat. CA-Sen covers both senate races. NY-GOV covers the New York governor's race.

Tags do not compound: that is, "education reform" is a completely different tag from "education". A tag like "reform" alone is probably not meaningful.

Consider if one or more of these tags fits your diary: Civil Rights, Community, Congress, Culture, Economy, Education, Elections, Energy, Environment, Health Care, International, Labor, Law, Media, Meta, National Security, Science, Transportation, or White House. If your diary is specific to a state, consider adding the state (California, Texas, etc). Keep in mind, though, that there are many wonderful and important diaries that don't fit in any of these tags. Don't worry if yours doesn't.

You can add a private note to this diary when hotlisting it:
Are you sure you want to remove this diary from your hotlist?
Are you sure you want to remove your recommendation? You can only recommend a diary once, so you will not be able to re-recommend it afterwards.
Rescue this diary, and add a note:
Are you sure you want to remove this diary from Rescue?
Choose where to republish this diary. The diary will be added to the queue for that group. Publish it from the queue to make it appear.

You must be a member of a group to use this feature.

Add a quick update to your diary without changing the diary itself:
Are you sure you want to remove this diary?
(The diary will be removed from the site and returned to your drafts for further editing.)
(The diary will be removed.)
Are you sure you want to save these changes to the published diary?

Comment Preferences

Subscribe or Donate to support Daily Kos.

Click here for the mobile view of the site