"The Tortoise and Achilles have just completed a tour of a porridge factory."
Achilles: You don't mind if I change the subject, do you?
Tortoise: Be my guest.
Achilles: Very well, then. It concerns an obscene phone call I received a few days ago.
According to our Greek athlete hero, here's what the caller said:
Caller (shouting wildly): Yields falsehood when preceded by its quotation! Yields falsehood when preceded by its quotation!
The two friends enter a strange tower:
Achilles: We can just step inside right here. Follow me.
(Achilles opens the door. They enter, and begin climbing the steep helical staircase inside the tower.)
Tortoise (puffing slightly): I'm a little out of shape for this sort of exercise, Achilles. How much further do we have to go/?
It turns out that the tower resembles the Escher picture, Above and Below. It is a two-story building such that the ceiling of one level becomes the floor of the other level. The two friends go here to discuss the obscene phone call:
Tortoise: A most imaginative example. But suppose we restrict the word "preceded" to the idea of precedence on a printed sheet, rather than elaborate entries into a banquet room.
Achilles: All right. But what exactly do you mean by "quotation" here?
The reptile explains that when we discuss a word or phrase, we put it in quotes. Thus here are some examples of phrases preceded by their own quotations:
"HUBBA" HUBBA
"'PLOP' IS NOT THE TITLE OF ANY BOOK, SO FAR AS I KNOW" 'PLOP' IS NOT THE TITLE OF ANY BOOK, SO FAR AS I KNOW.
"IS NOT THE TITLE OF ANY BOOK, SO FAR AS I KNOW" IS NOT THE TITLE OF ANY BOOK, SO FAR AS I KNOW.
Actually, on Amazon I found a comic book called "Plop," dated 1973 -- about a decade before Hofstadter wrote his book. On the other hand. "Is not the title of any book, so far as I know" still is not the title of any book, so far as Amazon knows. Achilles thinks this whole thing is silly.
Tortoise: Why silly?
Achilles: Because it's so pointless. Here's another one for you:
"WILL BE BOYS" WILL BE BOYS.
The Tortoise decides to give a name to the operation of preceding a phrase by its own quotation -- "to quine a phrase." He tells his friend that this name refers to its inventor, philosopher William Van Orman Quine.
Achilles: That should be easy ... I'd say the quining gives this:
"WHEN QUINED, YIELDS A TORTOISE'S LOVE SONG" WHEN QUINED, YIELDS A TORTOISE'S LOVE SONG.
Hmm ... There's something just a little peculiar here. Oh, I see what it is! The sentence is talking about itself! Do you see that?
Tortoise: What do you mean? Sentences can't talk.
Achilles explains that he can consider Sentence P to be "_____ WHEN QUINED, YIELDS A TORTOISE'S LOVE SONG" and Sentence Q to be the sentence formed by quining the blank. Thus Sentence P claims that Sentence Q is a reptile's love song. But if the phrase that we place in the blank is "WHEN QUINED, YIELDS A TORTOISE'S LOVE SONG," then Sentence Q -- the quine of that phrase -- becomes Sentence P itself:
Achilles: And since Sentence Q is always the topic of Sentence P, there is a loop, so now P points back to itself. But you see, the self-reference is a sort of accident. Usually Sentences Q and P are entirely unlike each other, but with the right choice for the blank in Sentence P, quining will do this magic trick for you.
And so the pair eventually figure out that the "obscene phone call" is a similarly quined phrase:
"YIELDS FALSEHOOD WHEN PRECEDED BY ITS QUOTATION" YIELDS FALSEHOOD WHEN PRECEDED BY ITS QUOTATION."
Achilles: Thank you, Mr. T., for your lucid clarification of that obscene telephone call.
Tortoise: And that you, Achilles, for the pleasant promenade. I hope we meet again soon.
Chapter 14 of Douglas Hofstadter's Godel, Escher, Bach is called "On Formally Undecidable Propositions of TNT and Related Systems." It begins as follows:
"This Chapter's title is an adaptation of the title of Godel's 1931 paper -- 'TNT' having been substituted for 'Principia Mathematica.' Godel's paper was a technical one, concentrating on making his paper watertight and rigorous; this Chapter will be more intuitive, and in it I will stress the two key ideas which are at the core of the proof."
The author begins with the first idea -- that of proof-pairs:
"A proof-pair is a pair of natural numbers related in a particular way. Here is the idea:"
Two natural numbers, m and n respectively, form a TNT-proof-pair if and only if m is the Godel number of a TNT-derivation whose bottom line is the string with Godel number n.
He gives us a simpler example, using MIU instead of TNT. Recall that MIU is the system mentioned all the way back in Chapter 1, where we started with MI and were supposed to derive MU (which turned out to be impossible). He tells us that m = 3131131111301 and n = 301 form a MIU-proof-pair, because m is the Godel number of the MIU-derivation:
MI
MII
MIIII
MUI
(Recall that in Godel-numbering MIU-proofs, M=3, I=1, and U=0.) On the other hand, we see that the values m = 31311311130 and n = 30 do not form a MIU-proof pair, because:
MI
MII
MIII
MU
is not a valid derivation -- from MII we can't derive MIII. Now Hofstadter returns to TNT:
"Here are two parallel examples, one being merely an alleged TNT-proof-pair, the other being a valid TNT-proof-pair. Can you spot which is which?"
(1) m = 626,262,636,223,123,262,111,666,611,223,123,666,111,666
n = 123,666,111,666
(2) m = 626,262,636,223,123,262,111,666,611,223,333,262,636,123,262,111,666
n = 223,333,262,636,123,262,111,666
I briefly listed the Godel-numbering for some of the TNT symbols previously with Chapter 9, but not all of them. In particular, we now need the symbol 611, which is a line separator. With that plus a few others, we can now translate the above Godel numbers into proofs:
(1) Aa: ~Sa=0
~S0=0
is a proof of S0=0?
(2) Aa: ~Sa=0
~Ea: Sa=0
is a proof of ~Ea: Sa=0?
The author asks us to check:
(1) whether the alleged derivation coded for by m is actually a legitimate derivation;
(2) if so, whether the last line of the derivation coincides with the string which n codes for.
Both of the proposed derivations satisfy the first criterion. Derivation (1) is using the specification rule (from "for all a, 0 is not the successor of a," derive "0 is not the successor of 0") and Derivation (2) is using the interchange rule (from "for all a, 0 is not the successor of a," derive "there does not exist a such that 0 is the successor of a").
But derivation (1) is a proof of ~S0=0, instead of S0=0 as claimed. (We proved that "0 is not the successor of 0," instead of "0 is the successor of 0.") Thus (1) fails the second criterion. Therefore only (m, n) for (2) is a valid TNT-proof-pair.
The author asserts the following facts:
Fundamental Fact 1: The property of being a proof-pair is a primitive recursive number-theoretical property, and can therefore be tested for by a BlooP program.
Here BlooP is the coding language mentioned in my last post. But Hofstadter warns:
"There is a notable contrast to be made here with that other closely related number-theoretical property: that of being a theorem-number. To assert that n is a theorem number is to assert that some value of m exists which forms a proof-pair with n."
In other words, it's easier to check a proof than it is to find one. The author continues:
Fundamental Fact 2: The property of forming a proof-pair is testable in BlooP, and consequently, it is represented in TNT by some formula having two free variables.
This formula is very, very complex -- but all that matters is that it exists. The same is true of MIU:
"Let us abbreviate that formula, whose exists we are assured of by Fundamental Fact 2, this way:"
MIU-PROOF-PAIR{a,a'}
"Since it is a property of two numbers, it is represented by a formula with two free variables."
Then the statement that there exists a derivation of MU becomes:
Ea: MIU-PROOF-PAIR{a,SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS0/a'}
where "/a'" means that a' has been replaced by a numeral -- the thirtieth successor of 0 (since 30 is the Godel number of MU).
The author does the same for TNT:
TNT-PROOF-PAIR{a,a'}
Then "0=0 is a theorem of TNT" becomes:
Ea: TNT-PROOF-PAIR{a,SSSSS ......... SSSS0/a'}
where a' has been replaced with the 666,111,666th successor of 0. For reasons that will soon be apparent, the author abbreviates this as "JOSHU." Hofstadter then asserts that all of the following statements can be written in TNT:
(1) 0=0 is not a theorem of TNT.
(2) ~0=0 is a theorem of TNT.
(3) ~0=0 is not a theorem of TNT.
"How do the solutions differ from the example done above, and from each other? Here are a few more translation exercises:"
(4) JOSHU is a theorem of TNT. (Call the TNT-string which expresses this "META-JOSHU.")
(5) META-JOSHU is a theorem of TNT. (Call the TNT-string which expresses this "META-META-JOSHU.")
(6) META-META-JOSHU is a theorem of TNT.
(7) META-META-META-JOSHU is a theorem of TNT.
(etc., etc.)
The author warns us that we can't write the formula:
Ea: TNT-PROOF-PAIR{a,a'}
to mean "a' is a TNT-theorem-number," because this property is not primitive-recursive, and so no such formula can be written in TNT.
Hofstadter now wants to consider substitution as:
replacement of all free variables by a specific numeral.
"Below are shown a couple of examples of this operation, which are followed by the parallel changes in Godel numbers."
Formula: a=a
Godel Number: 262,111,262
We now replaces all free variables by the numeral for 2:
Formula: SS0=SS0
Godel Number: 123,123,666,111,123,123,666
Formula: ~Ea: Ea': a"=(SSa*SSa')
Godel Number: 223,333,262,636,333,262,163,636,262,163,163,111,362,123,123,262,236,123,123,262,163,323
We now replaces all free variables by the numeral for 4:
Formula: ~Ea: Ea': SSSS0=(SSa*SSa') (We don't substitute a or a' because these aren't free variables.)
Godel number: 223,333,262,636,333,262,163,636,123,123,123,123,666,111,362,123,123,262,236,123,123,262,163,323
The author gives us some more exercises -- check to see that if we start with the formula represented by the first Godel number and substitute in the second numeral for all free variables, then we obtain the formula represented by the last Godel number:
(1) 362,262,112,262,163,323,111,123,123,123,123,666;
2;
362,123,123,666,112,123,123,666,323,111,123,123,123,123,666.
(2) 223,362,262,236,262,323,111,262,163;
1;
223,362,123,666,236,123,666,323,111,262,163.
OK, let's do the exercises:
(1) (a+a')=SSSS0;
2;
(SS0+SS0)=SSSS0.
(2) ~(a*a)=a'
1;
~(S0*S0)=a'
Only (1) is a valid substitution. In both examples both a and a' are free (since neither one is bound by an A or E quantifier), but in (2) only a is substituted for. It's easy for us to check which substitution is correct because substitution is primitive-recursive. Thus TNT can check for us as well:
"Let us abbreviate that TNT-formula by the following notation:"
SUB{a,a',a"}
(Here a and a" are Godel numbers, while a' is the numeral to be substituted into a to obtain a".)
"Because this formula represents the substitution relationship, the formula shown below must be a TNT-theorem":
SUB{262,111,262S0/a, SS0/a', 123,123,666,111,123,123,666S0/a"}
where the number before S tells how many S's there are.
At this point the author introduces arithmoquining -- that's "quine" is just like the quines we see earlier in the Dialogue. We take a formula:
a=S0 (Godel number 262,111,123,666)
and arithmoquine it by substituting in its own Godel number for a:
262,111,123,666S0 = S0.
This is clearly false since 262,111,123,666 does not equal 1. Hofstadter tells us that if we were to take ~a=S0 and arithmoquine it, the resulting statement would be true:
"When you arithmoquine, you are of course performing a special case of the substitution operation we defined earlier. If we wanted to speak about arithmoquining inside TNT, we would use the formula:"
SUB{a",a",a'}
which he abbreviates as:
ARITHMOQUINE{a",a'}
He also writes it as:
a' is the arithmoquinification of a"
and states that the arithmoquinification of 262,111,123,666 is:
123,123,123, ....., 123,123,123,666,111,123,666
where there are 262,111,123,666 copies of '123.'
Hofstadter now uses arithmoquining to define a new formula, which he calls G's uncle:
~Ea: Ea': <TNT-PROOF-PAIR{a,a'} ^ ARITHMOQUINE{a",a'}>
"You can see explicitly how arithmoquinification is thickly involved in the plot. Now this "uncle" has a Godel number, of course, which we'll call 'u.' The head and tail of u's decimal expansion, and even a teeny bit of its midsection, can be read off directly:"
u = 223,333,262,636,333,262,163,636,212, ..., 161, ..., 213
And now the authors takes G's uncle and arithmoquines it:
~Ea: Ea': <TNT-PROOF-PAIR{a,a'} ^ ARITHMOQUINE{uS0/a", a'}>
He tells us that this is Godel's famous string, or 'G.' Then he asks:
(1) What is G's Godel number?
(2) What is the interpretation of G?
He answers (1) by saying that it's "the arithmoquinification of u." He answers (2) in stages:
"There do not exist numbers a and a' such that both (1) they form a TNT-proof-pair, and (2) a' is the arithmoquinification of u."
"There is no number a that forms a TNT-proof-pair with the arithmoquinification of u."
"The formula whose Godel number is the arithmoquinifcation of u is not a theorem of TNT."
"G is not a theorem of TNT."
-- or, if you prefer:
"I am not a theorem of TNT."
And as Hofstadter reminds us, this is why TNT is incomplete -- there exists a statement G, which is true yet unprovable.
The above steps are confusing, so he gives a similar example:
~Ea: Ea': <TORTOISE-PAIR{a,a'} ^ TENTH-POWER{SS0,a",a'}>
where "Tortoise-pair" is as defined in my last post and "TENTH-POWER{a",a'}" is the statement that a' is the tenth power of a. So we translate:
"There do not exist numbers a and a' such that both (1) they form a Tortoise-pair, and (2) a' is the tenth power of 2."
"There is no number a that forms a Tortoise-pair with 1024"
"1024 does not have the Tortoise property":
As he explains:
"Here it was the number 1024 that was described as 'the tenth power of 2'; above, it was the number described as 'the arithmoquinification of u."
Hofstadter now takes time to remind us what Godel was trying to accomplish:
"Recall that this was a great philosophical dilemma of the day: how to prove a system consistent. Godel found a simple way to express the statement 'TNT is consistent' in a TNT-formula: and then he showed that this formula (and all others which express the same idea) are only theorems of TNT under one condition: that TNT is inconsistent."
And since we don't want TNT to be inconsistent, the only alternative is for it to be incomplete -- that there are true yet unprovable statements in TNT.
Hofstadter explains that TNT is omega-incomplete, as follows. He considers the statement:
Aa: ~Ea': <TNT-PROOF-PAIR{a,a'} ^ ARITHMOQUINE{uS0/a", a'}>
He tells us that from this statement we could derive G in one step (interchange) -- and since G is not a theorem, neither can this statement. Yet all the following are provable:
~Ea': <TNT-PROOF-PAIR{0/a, a'} ^ ARITHMOQUINE{uS0/a", a'}>
~Ea': <TNT-PROOF-PAIR{S0/a, a'} ^ ARITHMOQUINE{uS0/a", a'}>
~Ea': <TNT-PROOF-PAIR{SS0/a, a'} ^ ARITHMOQUINE{uS0/a", a'}>
~Ea': <TNT-PROOF-PAIR{SSS0/a, a'} ^ ARITHMOQUINE{uS0/a", a'}>
which translate as:
"0 and the arithmoquinification of u do not form a TNT-proof pair."
"1 and the arithmoquinification of u do not form a TNT-proof pair."
"2 and the arithmoquinification of u do not form a TNT-proof pair."
"3 and the arithmoquinification of u do not form a TNT-proof pair."
Not only are all of these true -- since G isn't a theorem, no integer forms a proof-pair with G -- but they are provable, since the proof-pair property is primitive recursive. But since:
"For all n, n and the arithmoquinification of u do not form a TNT-proof pair."
is not provable, this makes TNT omega-incomplete.
Hofstadter explains that there are two different ways to plug the hole:
"Now the standard type of extension would involve:"
adding G as a new axiom.
And the other way would be:
adding the negation of G as a new axiom.
The author compares this to the situation of non-Euclidean geometry. He explains:
"To put it bluntly, ~G says:"
"There exists some number which forms a TNT-proof-pair with the arithmoquinification of u"
"...but the various members of the pyramidal family successively assert:"
"0 is not that number"
"1 is not that number"
"2 is not that number"
...
Thus the Godel number of a proof of G is a new type of natural number -- a supernatural number. He explains that supernaturals look a lot like ordinary natural numbers:
"In fact, supernatural numbers share all of the properties of natural numbers, as long as those properties are given to us in theorems of TNT."
Thus supernatural numbers are not fractions or negative numbers, and so on. Instead, they are more like infinitely large natural numbers. Indeed, the proof of a supernatural theorem must be infinitely long in order to avoid contradictions:
"The supernatural number I won't cause any disaster. However, we will have to get used to the idea that ~G is now the one which asserts a truth ("G has a proof"), while G asserts a falsity ("G has no proof").
Hofstadter tells us that supernaturals are useful, but he asks, are they real? Again, he compares the situation to non-Euclidean geometry:
"In both instance, one is powerfully driven to ask, 'But which one of these rival theories is correct? Which is the truth?"
It's not necessarily correct to appeal to the physical would to answer the question about geometry:
"Therefore, one should be extremely cautious in saying that the brand of geometry which physicists might wish to use would represent 'the true geometry,' for in fact, physicists will always use a variety of different geometries, choosing in any given situation the one that seems simplest and most convenient."
Hofstadter considers how supernatural numbers might affect banks -- what would happen if someone has a supernatural amount of money? He also wonders about clouds -- sometimes one cloud plus one cloud equals one cloud (because the two clouds come together):
"This doesn't prove that 1 plus 1 equals 1; it just proves that our number-theoretical concept of 'one' is not applicable in its full power to cloud-counting. So bankers, cloud-counters, and most of the rest of us need not worry about the advent of supernatural numbers: they won't affect our everyday perception of the world in the slightest."
The only people who need to consider supernaturals are mathematicians and mathematical logicians:
"It is that intuition about reality which determines which 'fork' of number theory mathematicians will put their faith in, when the chips are down. But this faith may be wrong."
Hofstadter gives one final application of Godel's Theorem. He describes Diophantine equations, which I've mentioned on the blog before (most recently in December) -- polynomial equations whose solutions are integers:
a = 0
5x + 13y - 1 = 0
5p^5 + 17q^17 - 177 = 0
a^123,666,111,666 + b^123,666,111,666 - c^123,666,111,666 = 0
He tells us that Hilbert wants to find a general solution to all Diophantine equations:
"Little did he suspect that no such algorithm exists! Now for the simplification of G. It has been shown that whenever you have a sufficiently powerful formal number theory, and a Godel-numbering for it, there is a Diophantine equation which is equivalent to G."
And since G is unprovable, the equivalent Diophantine equation would both have a solution and have no solution -- thus making Hilbert's general solution impossible. Hofstadter concludes the chapter:
"This is what the Tortoise did in the Prelude, using Fermat's equation as his Diophantine equation. It is nice to know that when you do this, you can retrieve the sound of Old Bach from the molecules in the air!"
Of course, since Hofstadter wrote his book, FLT has been proved. All that means, of course, is that a different Diophantine equation must be used to reproduce Bach music!
For once, I've posted most of what I wanted to write about the Hofstadter Chapter. I'm glad it was this one, since this Chapter discusses Godel's proof in more detail.
This is what I wrote last year about today's lesson:
Lesson 15-5 of the U of Chicago text is on "Angles Formed by Chords or Secants." There is one vocabulary term as well as two theorems to learn.
The vocabulary word to learn is secant. The U of Chicago defines a secant as a line that intersects a circle in two points. This is in contrast with a tangent, a line that intersects the circle in one point.
At this point, I often wonder why we have tangent and secant lines as well as tangent and secant functions in trig. Well, here's an old (nearly 20 years!) Dr. Math post with the explanation:
http://mathforum.org/library/drmath/view/54053.html
Now, the tangent and the secant trigonometric functions are related to the tangent and secant of a circle in the following way. Consider a UNIT circle centered at point O, and a point Q outside the unit circle. Construct a line tangent to the circle from point Q and call the intersection of the tangent line and the circle point P. Also construct a secant line that goes through the center O of the circle from point Q. The line segment OQ will intersect the circle at some point A. Next draw a line segment from the center O to point P. You should now have a right triangle OPQ. A little thought will reveal that the length of line segment QP on the tangent line is nothing more but the tangent (trig function) of angle POQ (or POA, same thing). Also, the length of the line segment QO on the secant line is, not surprisingly, the secant (trig function) of angle POA.
And now let's look at the theorems:
Angle-Chord Theorem:
The measure of an angle formed by two intersecting chords is one-half the sum of the measures of the arcs intercepted by it and its vertical angle.
Given: Chords
Prove: Angle CEB = (Arc AD + Arc BC)/2
Proof:
Statements Reasons
1. Draw
2. Angle C = Arc AD/2, 2. Inscribed Angle Theorem
Angle A = Arc BC/2
3. Angle CEB = Angle C + Angle A 3. Exterior Angle Theorem
4. Angle CEB = Arc AD/2 + Arc BC/2 4. Substitution
Angle-Secant Theorem:
The measure of an angle formed by two secants intersecting outside the circle is half the difference of the arcs intercepted by it.
Given: Secants
Prove: Angle E = (Arc AC - Arc BD)/2
Proof:
Statements Reasons
1. Draw
2. Angle ADC = Arc AC/2, 2. Inscribed Angle Theorem
Angle A = Arc BD/2
3. Angle A + Angle E = Angle ADC 3, Exterior Angle Theorem
4. Angle E = Angle ADC - Angle A 4. Subtraction Property of Equality
5. Angle E = Arc AC/2 - Arc BD/2 5. Substitution
In the end, I must admit that of all the theorems in the text, I have trouble recalling circle theorems the most.
I decided to include another Exploration Question as a bonus:
The sides of an inscribed pentagon ABCDE are extended to form a pentagram, or five-pointed star.
a. What is the sum of the measures of angles, F, G, H, I, and J, if the pentagon is regular?
Notice that each angle satisfies the Angle-Secant Theorem. So Angle F is half the difference between CE (which is two-fifths of the circle, Arc CD + Arc DE = Arc CE = 144) and AB (which is one-fifth of the circle, Arc AB = 72). So Angle F = (144 - 72)/2 = 36 degrees. All five angles are measured the same way, so their sum is 36(5) = 180 degrees.
b. What is the largest and smallest this sum can be if the inscribed polygon is not regular.
Well, let's write out the Angle-Secant Theorem in full:
Angle F + G + H + I + J
= Arc (CD + DE - AB + DE + EA - BC + EA + AB - BC + AB + BC - DE + BC + CD - EA)/2
= Arc (CD + DE + EA + AB + BC)/2
= (360)/2 (since the five arcs comprise the entire circle)
= 180
So the largest and smallest this sum can be is 180. The sum of the five angles is a constant.
No comments:
Post a Comment