Read Gödel, Escher, Bach: An Eternal Golden Braid Online

Authors: Douglas R. Hofstadter

Tags: #Computers, #Art, #Classical, #Symmetry, #Bach; Johann Sebastian, #Individual Artists, #Science, #Science & Technology, #Philosophy, #General, #Metamathematics, #Intelligence (AI) & Semantics, #G'odel; Kurt, #Music, #Logic, #Biography & Autobiography, #Mathematics, #Genres & Styles, #Artificial Intelligence, #Escher; M. C

Gödel, Escher, Bach: An Eternal Golden Braid (21 page)

BOOK: Gödel, Escher, Bach: An Eternal Golden Braid
6.16Mb size Format: txt, pdf, ePub
ads

We have stressed the fact, above, that
internal
consistency of a form; system (together with an interpretation) requires that there be some
imaginable
world-that is, a world whose only restriction is that in it, mathematics and logic should be the same as in our world-in which all the interpreted theorems come out true.
External
consistency, however consistency with the external world-requires that all theorems come of true in the real world. Now in the special case where one wishes to create consistent formal system whose theorems are to be interpreted as statements of mathematics, it would seem that the difference between the two types of consistency should fade away, since, according to what we sat above,
all imaginable worlds have the same mathematics as the real world
.

Thus, i every conceivable world, 1 plus 1 would have to be 2; likewise, there would have to be infinitely many prime numbers; furthermore, in every conceivable world, all right angles would have to be congruent; and of cours4 through any point not on a given line there would have to be exactly on parallel line ...

But wait a minute! That's the parallel postulate-and to assert i universality would be a mistake, in light of what's just been said. If in all conceivable worlds the parallel postulate-is obeyed, then we are asserting that non-Euclidean geometry is inconceivable, which puts us back in the same mental state as Saccheri and Lambert-surely an unwise move.
But what, then, if not all of mathematics, must all conceivable worlds share
?

Could it I as little as logic itself? Or is even logic suspect? Could there be worlds where contradictions are normal parts of existence-worlds where contradictious are not contradictions?

Well, in some sense, by merely inventing the concept, we have shoe that such worlds are indeed conceivable; but in a deeper sense, they are al: quite inconceivable.

(This in itself is a little contradiction.) Quite serious] however, it seems that if we want to be able to communicate at all, we ha, to adopt some common base, and it pretty well has to include logic. (The are belief systems which reject this point of view-it is too logical.

particular, Zen embraces contradictions and non-contradictions with equ eagerness. This may seem inconsistent, but then being inconsistent is pa of Zen, and so ... what can one say?)

Is Number Theory the Same In All Conceivable Worlds?

If we assume that
logic
is part of every conceivable world (and note that we have not defined logic, but we will in Chapters to come), is that all? Is it really conceivable that, in some worlds, there are not infinitely many primes? Would it not seem necessary that numbers should obey the same laws in all conceivable worlds? Or ... is the concept

"natural number" better thought of as an undefined term, like "POINT" or "LINE"? In that case, number theory would be a bifurcated theory, like geometry: there would be standard and nonstandard number theories. But there would have to be some counterpart to absolute geometry: a "core" theory, an invariant ingredient of all number theories which identified them as number theories rather than, say, theories about cocoa or rubber or bananas. It seems to be the consensus of most modern mathematicians and philosophers that there is such a core number theory, which ought to be included, along with logic, in what we consider to be "conceivable worlds". This core of number theory, the counterpart to absolute geometry-is called
Peano arithmetic
, and we shall formalize it in Chapter VIII. Also, it is now well established-as a matter of fact as a direct consequence of Gödel’s Theorem-that number theory is a bifurcated theory, with standard and nonstandard versions. Unlike the situation in geometry, however, the number of "brands" of number theory is infinite, which makes the situation of number theory considerably more complex.

For practical purposes, all number theories are the same. In other words, if bridge building depended on number theory (which in a sense it does), the fact that there are different number theories would not matter, since in the aspects relevant to the real world, all number theories overlap. The same cannot be said of different geometries; for example, the sum of the angles in a triangle is 180 degrees only in Euclidean geometry; it is greater in elliptic geometry, less in hyperbolic. There is a story that Gauss once attempted to measure the sum of the angles in a large triangle defined by three mountain peaks, in order to determine, once and for all, which kind of geometry really rules our universe. It was a hundred years later that Einstein gave a theory (general relativity) which said that the geometry of the universe is determined by its content of matter, so that no one geometry is intrinsic to space itself. Thus to the question, "Which geometry is true?" nature gives an ambiguous answer not only in mathematics, but also in physics. As for the corresponding question, "Which number theory is true?", we shall have more to say on it after going through Gödel’s Theorem in detail.

Completenes

If consistency is the minimal condition under which symbols acquire passive meanings, then its complementary notion, completeness, is the maximal confirmation of those passive meanings. Where consistency is the property

way round: "Every true statement is produced by the system". Now I refine the notion slightly. We can't mean every true statement in th world-we mean only those which belong to the domain which we at attempting to represent in the system. Therefore, completeness mean! "Every true statement which can be expressed in the notation of the system is a theorem."

Consistency: when every theorem, upon interpretation, comes out true (in some imaginable world).

Completeness: when all statements which are true (in some imaginable world), and which can be expressed as well-formed strings of the system, are theorems.

An example of a formal system which is complete on its own mode level is the original pq-system, with the original interpretation. All true additions of two positive integers are represented by theorems of th system. We might say this another way: "All true additions of two positive integers are provable within the system." (Warning: When we start using th term "provable statements" instead of "theorems", it shows that we at beginning to blur the distinction between formal systems and their interpretations. This is all right, provided we are very conscious of th blurring that is taking place, and provided that we remember that multiple interpretations are sometimes possible.) The pq-system with the origin interpretation is
complete
; it is also
consistent
, since no false statement is-, use our new phrase-provable within the system.

Someone might argue that the system is incomplete, on the grounds that additions of
three
positive integers (such as 2 + 3 + 4 =9) are not represented by theorems of the pq-system, despite being translatable into the notation of the system (e.g.,
--p---p----q----

--------).
However, this string is not well-formed, and hence should be considered to I just as devoid of meaning as is
p q p---q p q
. Triple additions are simply
not expressible
in the notation of the system-so the completeness of the system is preserved.

Despite the completeness of the pq-system under this interpretation, certainly falls far short of capturing the full notion of truth in numb theory. For example, there is no way that the pq-system tells us how mat prime numbers there are. Gödel’s Incompleteness Theorem says that any system which is "sufficiently powerful" is, by virtue of its power, incomplete, in the sense that there are well-formed strings which express tr statements of number theory, but which are not theorems. (There a truths belonging to number theory which are not provable within the system.) Systems like the pq-system, which are complete but not very powerful, are more like low-fidelity phonographs; they are so poor to beg with that it is obvious that they cannot do what we would wish them do-namely tell us everything about number theory.

How an Interpretation May Make or Break Completeness

What does it mean to say, as I did above, that "completeness is the maximal confirmation of passive meanings"? It means that if a system is consistent but incomplete, there is a mismatch between the symbols and their interpretations. The system does not have the power to justify being interpreted that way. Sometimes, if the interpretations are

"trimmed" a little, the system can become complete. To illustrate this idea, let's look at the modified pq-system (including Axiom Schema II) and the interpretation we used for it.

After modifying the pq-system, we modified the interpretation for q from "equals"

to "is greater than or equal to". We saw that the modified pq-system was consistent under this interpretation; yet something about the new interpretation is not very satisfying. The problem is simple: there are now many expressible truths which are not theorems. For instance, "2 plus 3 is greater than or equal to 1" is expressed by the nontheorem
--p---q-.

The interpretation is just too sloppy! It doesn't accurately reflect what the theorems in the system do. Under this sloppy interpretation, the pq-system is not complete. We could repair the situation either by (1)
adding new rules
to the system, making it more powerful, or by (2)
tightening up the interpretation
. In this case, the sensible alternative seems to be to tighten the interpretation. Instead of interpreting
q
as "is greater than or equal to", we should say "equals or exceeds by 1". Now the modified pq-system becomes both consistent and complete. And the completeness confirms the appropriateness of the interpretation.

Incompleteness of Formalized Number Theory

In number theory, we will encounter incompleteness again; but there, to remedy the situation, we will be pulled in the other direction-towards adding new rules, to make the system more powerful. The irony is that we think, each time we add a new rule, that we surely have made the system complete
now
! The nature of the dilemma can be illustrated'

by the following allegory ...

We have a record player, and we also have a record tentatively labeled "Canon on
B-A-C-H
". However, when we play the record on the record player, the feedback-induced vibrations (as caused by the Tortoise's records) interfere so much that we do not even recognize the tune. We conclude that
something
is defective-either our record, or our record player. In order to test our
record
, we would have to play it on friends' record players, and listen to its quality. In order to test our
phonograph
, we would have to play friends' records on it, and see if the music we hear agrees with the labels. If our record player passes its test, then we will say the record was defective; contrariwise, if the record passes
its
test, then we will say our record player was defective. What, however, can we conclude when we find out that
both
pass their respective tests? That is the moment to remember the chain of two isomorphisms (Fig. 20), and think carefully!

Little Harmonic Labyrinth

The Tortoise and Achilles are spending a day at Coney Island After buying a
couple of cotton candies, they decide to take a ride on the Ferris wheel.

Tortoise: This is my favorite ride. One seems to move so far, and reality one gets nowhere.

Achilles: I can see why it would appeal to you. Are you all strapped in?

Tortoise: Yes, I think I've got this buckle done. Well, here we go.

Achilles: You certainly are exuberant today.

Tortoise: I have good reason to be. My aunt, who is a fortune-teller me that a stroke of Good Fortune would befall me today. So I am tingling with anticipation.

Achilles: Don't tell me you believe in fortune-telling!

Tortoise: No ... but they say it works even if you don't believe ii Achilles: Well, that's fortunate indeed.

Tortoise: Ah, what a view of the beach, the crowd, the ocean, the city. . .

Achilles: Yes, it certainly is splendid. Say, look at that helicopter there. It seems to be flying our way. In fact it's almost directly above us now.

Tortoise: Strange-there's a cable dangling down from it, which is very close to us. It's coming so close we could practically grab it

Achilles: Look! At the end of the line there's a giant hook, with a note
(He reaches out and snatches the note. They pass by and are on their z down.)
Tortoise: Can you make out what the note says?

Achilles: Yes-it reads, "Howdy, friends. Grab a hold of the hook time around, for an Unexpected Surprise."

Tortoise: The note's a little corny but who knows where it might lead, Perhaps it's got something to do with that bit of Good Fortune due me. By all means, let's try it!

Achilles: Let's!

(On the trip up they unbuckle their buckles, and at the crest of the ride, grab for the
giant hook. All of a sudden they are whooshed up by the ca which quickly reels
them skyward into the hovering helicopter. A It strong hand helps them in.)
Voice: Welcome aboard-Suckers.

Achilles: Wh-who are you?

Voce: Allow me to introduce myself. I am Hexachlorophene J. Goodforttune, Kidnapper At-Large, and Devourer of Tortoises par Excellence, at your service.

BOOK: Gödel, Escher, Bach: An Eternal Golden Braid
6.16Mb size Format: txt, pdf, ePub
ads

Other books

B00ARI2G5C EBOK by Goethe, J. W. von, David Luke
Off the Chart by James W. Hall
The Golden Age by Gore Vidal
Shadowborn by Adams, Jocelyn
Firemoon by Elí Freysson


readsbookonline.com Copyright 2016 - 2024