Gödel, Escher, Bach

[The following, except where otherwise noted, is by Douglas Hofstadter, from his book Gödel, Escher, Bach.]

*

“A strange loop occurs whenever, by moving upwards (or downwards) through the levels of some hierarchical system, we unexpectedly find ourselves right back where we started. Wandering further and further from our starting point, we’re suddenly back! Sometimes I use the term ‘tangled hierarchy’ to describe a system in which a strange loop occurs.

To my mind, the most beautiful and powerful visual realizations of this notion of strange loops exist in the work of M. C. Escher.”

*

Ascending and Descending by M. C. Escher

*

Waterfall by M. C. Escher

*

“In Escher’s drawings, one level might clearly be recognizable as representing fantasy or imagination; another level would be recognizable as reality.

These two levels might be the only ones explicitly portrayed. But their mere presence invites the viewer to look upon himself as part of yet another level; and by taking that step, he can’t help getting caught up in Escher’s implied chain, in which, for any one level, there’s always another level above it of greater ‘reality’, and likewise, there’s always a level below, ‘more imaginary’ than it is.”

“What is recursion? The concept is very general. (Stories inside stories, movies inside movies, paintings inside paintings, Russian dolls inside Russian dolls (even parenthetical comments inside parenthetical comments!) ― these are just a few of the charms of recursion.)”

*

This paradigm of levels is incredibly pervasive and important. It encompasses the notions of recursion and representation and about-ness and symbolism and derivatives/integrals and meta-ness. “‘Meta’ can be thought to mean ‘about itself’.” [3]

Language and reality are a level apart. Thought and reality are a level apart.

“The philosophers’ favorite tactic is ‘going meta’ ― thinking about thinking, talking about talking, reasoning about reasoning.” [Daniel Dennett]

Similarly, you can have a thought about a thought about a thought… Or a sentence about a sentence about a sentence… Or knowledge about knowledge about knowledge… Or a belief about a belief about a belief… And reality sits at the bottom.

Put another way, anything that has the ability to represent anything can represent itself. And similarly, anything that has the ability to be about anything can be about itself.

*

“This can be mind-boggling in itself. However, what happens if the chain of levels isn’t linear, but forms a loop?”

This image has an empty alt attribute; its file name is drawing-hands.jpg
Drawing Hands by M. C. Escher

“One of the most canonical examples is M. C. Escher’s Drawing Hands, in which (depending on where one starts) one sees a right hand drawing a picture of a left hand (nothing paradoxical yet), and yet the left hand turns out to be drawing the right hand (all at once, it’s a paradox).

Here, the shift in levels would be the leap from drawing to drawer (or equally, from image to artist), the latter level being intuitively ‘more real’ than the former, in more senses than one. To begin with, a drawer is always a sentient, mobile being, whereas a drawing is a frozen, immobile image. Secondly, whereas a drawer is three-dimensional, a drawing is two-dimensional. And thirdly, a drawer chooses what to draw, whereas a drawn has no say in the matter. In at least these three senses, then, the leap from a drawn to a drawer always has a ‘more real’ feel to it.

And yet, in Drawing Hands this rule has been sharply and cleanly violated, for each of the hands is hierarchically ‘above’ the other!”

*

***

*

“Other examples of strange loops include the ‘chicken or egg’ problem and quines, which are computer programs that take no input and produce a copy of their own source code as their only output.

What about rock, paper, scissors?

Another example is the fictional story of Baron Munchausen pulling himself out of a mire by his own ponytail.” [4]

[5]

[Pannenkoek] “Clearly, this is related to the concept of pulling yourself up by your bootstraps. Also, so does that mean he can float?”

*

“A further example of a strange loop can be found in The Fisherman and His Wife, a fairytale collected by the Brothers Grimm, summarized as follows.

There’s a poor fisherman who lives with his wife in an old cottage by the sea. One day, the fisherman catches a flounder, who claims to be an enchanted prince, and begs to be set free. The fisherman kindly releases it. When his wife hears the story, she says he ought to have had the flounder grant him a wish. She insists that he go back and ask the fish to grant her wish for a larger, nicer house.

The fisherman returns to the shore but is uneasy when he finds that the sea seems to be becoming more turbulent, as it was so clear before. He summons the flounder, and it grants the wife’s wish. The fisherman is pleased with his new wealth, but his wife still isn’t satisfied. She demands that he go back and wish to be made a king. Reluctantly, he does, and his wish is granted. But again and again, his wife sends him back to ask for more. The fisherman feels that this is wrong, and he tells his wife that they should stop annoying the flounder and be content with what they’ve been given. But he’s unable to reason with her. Each time, the flounder grants the wishes with the words: ‘Alright. Go back home. She already has it,’ or something similar. And each time, the sea grows more and more fierce.

Eventually, the wife wishes to command the sun, moon, and heavens, and so she sends her husband to the flounder with the wish, ‘I want to become equal to God.’ When that final wish is made, the flounder says: ‘Alright. Go back home. She’s already sitting in the old cottage again.’ And with that, the sea becomes calm once more.” [6]

*

***

*

“It all began with the attempt to mechanize the process of reasoning. Now it’s often claimed that our ability to reason is what distinguishes us from other species ― so it seems somewhat paradoxical, on first thought, to mechanize that which is most human. Yet even the ancient Greeks knew that reasoning is a patterned process, and is at least partially governed by statable laws. Aristotle codified syllogisms, and Euclid codified geometry. But thereafter, many centuries had to pass before progress in the study of axiomatic reasoning would take place again.”

“Before I began the study of geometry, somebody had told me that it proved things, and so I was delighted when my brother said he’d teach it to me. When we came to the axioms, he said, ‘These can’t be proved, but they have to be assumed before the rest can be proved.’ At these words my hopes crumbled. I’d thought it would be wonderful to find something that one could prove, and then it turned out that this could only be done by means of assumptions for which there was no proof. I looked at my brother and said: ‘But why should I admit these things if they can’t be proved?’ He replied: ‘Well, if you won’t, we can’t go on ― and we won’t be able to prove anything at all.’” [Bertrand Russell]

“Since a proposition can only be proved by means of other propositions, it’s obvious that not all propositions can be proved, for proofs can only begin by assuming something. And since the consequences have no more certainty than their premises, the things that are proved are no more certain than the things that are accepted merely because they’re obvious.” [Bertrand Russell]

“In all inquiries, after a preliminary analysis of complex data, we proceed to build up complex things from their simpler constituents ― starting from ideas which we understand though we can’t define them in terms of simpler ideas, and from premises which we know though we can’t prove them.” [Bertrand Russell]

“A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. A formal system is essentially an axiomatic system.” [7]

Some of the most common and important formal/axiomatic systems are:

*

***

*

“In the late 19th century, interesting developments were taking place in mathematics. A theory of different types of infinities was developed by Cantor. It was powerful and beautiful, but intuition-defying. Before long, a variety of set-theoretical paradoxes had been unearthed.

The most famous is Russell’s paradox. Most sets, it would seem, are not members of themselves ― for example, the set of walruses is not a walrus, the set containing only Bertrand Russell is not Bertrand Russell (a set is not a person) ― and so on. In this respect, most sets are rather ‘run-of-the-mill’. However, some ‘self-swallowing’ sets do contain themselves as members, such as the set of all sets, or the set of all things except Bertrand Russell, and so on. Clearly, every set is either run-of-the-mill or self-swallowing, and no set can be both.

Now nothing prevents us from inventing R: the set of all run-of-the-mill sets. At first, R might seem a rather run-of-the-mill invention ― but that opinion must be revised when you ask yourself, ‘Is R itself a run-of-the-mill set or a self-swallowing set?’ You’ll find that the answer is: ‘R is neither run-of-the-mill nor self-swallowing, for either choice leads to paradox.’”

*

***

*

“Just as Escher’s loops appeal to simple and ancient intuitions, such as a staircase, Gödel’s discovery of a strange loop in mathematics also has its origins in simple and ancient intuitions. In its absolutely barest form, Gödel’s discovery involves the translation into mathematical terms of the Epimenides paradox, or liar paradox.

Epimenides was a Cretan who made one immortal statement: ‘All Cretans are liars.’ A sharper version of the statement is simply, ‘I am lying,’ or, ‘This statement is false.’ It’s that last version which I’ll usually mean when I speak of the Epimenides paradox.

It’s a statement which rudely violates the usually assumed dichotomy of statements into true and false, because if you tentatively think it’s true, then it immediately backfires on you and makes you think it’s false. But once you’ve decided it’s false, a similar backfiring returns you to the idea that it must be true.”

I’ve come to think of the liar paradox and Russell’s paradox as the king and queen paradoxes. A surprising number of other paradoxes are just variants of these two.

*

***

*

“Gödel’s idea was to use mathematical reasoning in exploring mathematical reasoning itself. This proved to be enormously powerful, and perhaps its richest implication was Gödel’s incompleteness theorem, which states: All consistent axiomatic formulations of number theory include propositions that are neither provable nor refutable. Or put another way, there are bound to be statements in arithmetic that are neither provable nor refutable.

The proof of Gödel’s incompleteness theorem hinges upon the writing of a self-referential mathematical statement, in the same way as the Epimenides paradox is a self-referential statement of language. But whereas it’s very simple to talk about language in language, it’s not at all easy to see how a statement about numbers can talk about itself.”

“Gödel’s final translation of the Epimenides paradox didn’t say, ‘This statement of number theory is false,’ but rather, ‘This statement of number theory doesn’t have any proof.’ Whereas the Epimenides statement creates a paradox since it’s neither true nor false, the Gödel sentence is unprovable but true. The grand conclusion? There are true statements of number theory which our methods of proof are too weak to demonstrate.

Gödel revealed to us that there’s a profound gulf between truth and provability ― and showed us that, for the whole numbers (0, 1, 2, 3, …), provability is a weaker notion than truth, no matter what axiomatic system is involved.”

*

***

*

“One might conclude that a strange loop necessarily involves a self-undermining or self-negating quality. However, negation doesn’t play an essential role. It’s just that the strangeness becomes more pungent or humorous if the loop enjoys a self-undermining quality. Recall Escher’s Drawing Hands. There’s no negation in it ― both hands are drawing. Imagine if one were erasing the other!

Every bit as strange a loop, although perhaps a little less dramatic, would have been created if Gödel had concocted a self-affirming formula that cockily asserted of itself, ‘This formula is provable.’ Indeed, some years after Gödel, such self-affirming formulas were concocted and studied by logicians, and these formulas, too, had amazing and deep properties.

The strange loopiness resides not in the flip due to the word ‘not’, but in the unexpected, hierarchy-violating twisting-back due to the word ‘this’.”

*

*

*

Citations

  1. (original source unknown)
  2. Ernie Bushmiller
  3. (various sources)
  4. Wikipedia’s Strange Loop article
  5. Oskar Herrfurth
  6. Wikipedia’s The Fisherman’s and His Wife article
  7. Wikipedia’s Formal System article

%d bloggers like this: