Thursday, August 25, 2016

Kurt Godel: Mathematician/Philosopher Extraordinaire

If you have heard the name Kurt Godel at all, you probably heard it in connection with Douglas Hofstadter's masterful (and massive) Gödel, Escher, Bach: An Eternal Golden Braid. Unless you read and remember the contents of that more than 30 year old book, you probably have no idea who Godel was and why his work is so significant.

John W. Dawson's article Godel and the Limits of Logic provides a sensitive and perceptive glimpse at the accomplishments and inner life of one of the most eminent mathematicians of all time. Dawson explains that Godel was a Platonist: "he believed that in addition to objects, there exists a world of concepts to which humans have access by intuition. For Plato, who lived around 400 BC, concepts such as truth were not products of the human mind which can change according to the thinker's point of view, as some philosophers believe, but existed independently of the human observer. Thus, a statement could have a definite 'truth value'--be true or not--whether or not it had been proved or could be empirically confirmed or refuted by humans. Gödel subscribed to this philosophy, and, in his own view, this was an aid to his remarkable mathematical insights."

Mental illness plagued Godel for much of his life and ultimately led to his untimely demise but Godel nevertheless made an indelible impact on mathematics, logic and philosophy. Dawson declares:

Gödel proved that the mathematical methods in place since the time of Euclid (around 300 BC) were inadequate for discovering all that is true about the natural numbers. His discovery undercut the foundations on which mathematics had been built up to the 20th century, stimulated thinkers to seek alternatives and generated a lively philosophical debate about the nature of truth. Gödel's innovative techniques, which could readily be applied to algorithms for computations, also laid the foundation for modern computer science...

Although Gödel's work irrefutably proves that "undecidable" statements do exist within number theory, not many examples of such statements have been found. One example comes from the sentence:

This statement is unprovable

You can see why this is a prime candidate: if you could prove this statement to be true, then it would be false! It is true only if it is unprovable, and unprovable only if it is true. As it stands, this is not a statement about the natural numbers. But Gödel had devised an ingenious way to assign numbers to English-language phrases like this one, so that finding whether the statement is true or not translates to solving numerical equations. He proved that, within the axioms of number theory, it is impossible to prove whether or not the equation corresponding to the sentence above holds true, thus confirming our "common-sense" analysis.


In a similar way, Gödel translated the statement

The axioms of this theory do not contradict each other

into numerical code, and again proved that the translation is unprovable. Any proof that the axioms do not contradict each other--that they are consistent-- must therefore appeal to stronger principles than the axioms themselves. 


The latter result greatly dismayed David Hilbert, who had envisioned a program for securing the foundations of mathematics through a "bootstrapping" process, by which the consistency of complex mathematical theories could be derived from that of simpler, more evident theories. Gödel, on the other hand, saw his incompleteness theorems not as demonstrating the inadequacy of the axiomatic method but as showing that the derivation of theorems cannot be completely mechanized. He believed they justified the role of intuition in mathematical research.

The concepts and methods Gödel introduced in his incompleteness paper are central to all of modern computer science. This is not surprising, since computers are forced to use logical rules mechanically without recourse to intuition or a "birds-eye view" that allows them to see the systems they are using from the outside. Extensions of Gödel's ideas have allowed the derivation of several results about the limits of computational procedures. One is the unsolvability of the halting problem. If you have ever written a computer program, you will know that a programming mistake can cause it to enter an infinite loop: it will run forever and never end. The question is if there can be an algorithm that can examine any computer program and decide whether it will eventually halt or whether it will keep running forever. This is the halting problem and the answer is "no."

Another result that derives from Gödel's ideas is the demonstration that no program that does not alter a computer's operating system can detect all programs that do. In other words, no program can find all the viruses on your computer, unless it interferes with and alters the operating system.

Godel's concepts have wide-ranging implications not only for mathematics, physics and computer science but also for philosophy and metaphysics. David Goodman, writing in First Things, describes Godel's impact as both a mathematician and someone who thought seriously about theological matters:

Kurt Gödel was a believer--or, at least, a knower--whose engagement with God included a reworking of the ontological proof of God’s existence. Born in 1906, Gödel was arguably the great mathematician of his time. Certainly no twentieth-century thinker did more to show that the human mind cannot be reduced to a machine. At twenty-five he ruined the positivist hope of making mathematics into a self-contained formal system with his incompleteness theorems, implying, as he noted, that machines never will be able to think, and computer algorithms never will replace intuition. To Gödel this implies that we cannot give a credible account of reality without God. But Gödel’s God is not the well-behaved deity of the old natural theology, or the happy harmonizer of the intelligent-design subculture. Gödel’s God hides his countenance and can be glimpsed only in paradox and intuition. God is not an abstraction but “can act as a person,” as Gödel once wrote, confronting those who seek him with paradox, uplifting man through glorious insights while guarding his infinitude from human grasp. Gödel’s investigations in number theory and general relativity suggest a similar theological result: that God cannot be reduced to a mere principle of the natural world. Gödel may have seen himself as a successor to Leibniz, whose critique of Spinoza’s atheism set a precedent for much of Gödel’s work.

Rebecca Goldstein's book-length biography Incompleteness: The Proof and Paradox of Kurt Godel further explains Godel's significance: "This man's theorem is the third leg, together with Heisenberg's uncertainty principle and Einstein's relativity, of that tripod of theoretical cataclysms that have been felt to force disturbances deep down in the foundations of the 'exact sciences.' The three discoveries appear to deliver us into an unfamiliar world, one so at odds with our previous assumptions and intuitions that, nearly a century on, we are still struggling to make out where, exactly, we have landed" (p. 22).

Positivists and postmodernists cite Albert Einstein, Kurt Godel and Werner Heisenberg as three figures who destroyed the concept of objective reality but Einstein and Godel rejected this interpretation of their work. In Goldstein's words, "Einstein interpreted his theory as representing the objective nature of space-time, so very different from our human, subjective point of view of space and time" (p. 42). Similarly, Godel's "commitment to the objective existence of mathematical reality is the view known as conceptual, or mathematical, realism. It is also known as mathematical Platonism, in honor of the ancient Greek philosopher whose own metaphysics was a vehement rejection of the Sophist Protagoras' 'man is the measure of all things'" (p. 44). In layman's terms, "For Godel mathematics is a means of unveiling the features of objective mathematical reality, just as for Einstein physics is a means of unveiling aspects of objective physical reality" (p. 45). Einstein and Godel did not believe that they had thrown the world into chaos but rather that they had used their intellect to decipher the true nature of, respectively, space-time and mathematical reality.

Godel was a member of the famous Vienna Circle of intellectuals who regularly met in the 1920s and 1930s but most of the Vienna Circle's members believed in logical positivism while Godel was a Platonist. However, Godel rarely spoke during these meetings and he was one of the younger members of the group, so it appears that the other members did not even realize that Godel opposed their views. Godel first presented his revolutionary Incompleteness Theorem during a 20 minute talk on "Epistemology of the Exact Sciences" during the second day of a scientific conference in Konigsberg. Godel's work was later described as an "amazing intellectual symphony" but because of his mild-mannered presentation and because of the complexity of his ideas it was not immediately apparent even to the esteemed attendees of this conference that Godel had accomplished something monumental.

On the third day of the conference, Godel summarized the meaning of his Incompleteness Theorem: "One can (assuming the [formal] consistency of classical mathematics) even give examples of propositions (and indeed of such a type as Goldbach and Fermat) which are really contextually [materially] true but unprovable in the formal system of classical mathematics." Goldstein describes this sentence as "meticulously crafted, a miniature masterpiece" (p. 157) but adds, "Godel was always disappointed by the abilities of others to draw the implications he had scrupulously prepared for them, and his experience at Konigsberg must have been a magnificent disappointment, for the response was a resounding silence."

The only person present who grasped the implications of what Godel had said was another towering genius, John von Neumann. Von Neumann spoke with Godel afterwards and Von Neumann later informed Godel--who was then still finishing his doctoral studies--that the implication of what Godel had said was that it is impossible to formally prove the consistency of a system of arithmetic within that system of arithmetic. Godel drily replied that not only did he realize this but he had already drafted the mathematical proof of it (this is known as Godel's second Incompleteness Theorem).

After Godel emigrated to the United States, he shared a close friendship with Einstein, despite being separated in age by nearly 30 years. Einstein so enjoyed their daily walks together on the grounds of the Institute of Advanced Study that toward the end of Einstein's life he told the economist Oskar Morgenstern that his own work did not matter much anymore but he came to the Institute primarily for the privilege of walking alongside Godel each day. Einstein was an outgoing, mentally stable (though highly unconventional) person, while Godel was introverted and battled mental illness throughout his life but they shared in common immense genius and insatiable curiosity: Einstein once said, "The most important thing is to not stop questioning," while Godel was known as "Mr. Why" when he was a child because he constantly asked questions.

In A World Without Time: The Forgotten Legacy of Godel and Einstein, Palle Yourgrau notes that Godel provided a mathematical solution for Einstein's General Theory of Relativity that demonstrated that in a relativistic universe time travel is theoretically possible. If Godel is correct, then this means that time does not exist, at least not in the linear way that we humans subjectively perceive it, because what is past is not actually past.

Yourgrau laments that mathematicians and physicists have essentially ignored or dismissed Godel's solution even though no one has found any flaw with Godel's math; Einstein disliked the idea that time travel might be possible but he could find no mistakes in Godel's calculations and Einstein admitted that "the problem here involved disturbed me at the time of the building up of the general theory of relativity."

Einstein further stated, "Kurt Godel's essay constitutes, in my opinion, an important contribution to the general theory of relativity, especially to the analysis of the concept of time." However, Einstein questioned whether Godel's model was physically plausible even though it was mathematically and conceptually sound; Godel's theoretical universe rotates and for the remainder of his life after he proposed this solution Godel had a keen interest in whether or not our universe rotates (to this day, astrophysical observations have neither confirmed nor refuted the possibility that our universe may in fact conform to Godel's hypothetical model).

In his younger days, Einstein had questioned other interpretations of general relativity--including the possibility that black holes exist and the possibility that the universe is expanding--on the grounds of being physically implausible only to later be proven wrong. Godel's relentless logic led Godel inexorably to the conclusion that if time does not exist in a theoretically possible universe (such as the rotating universe postulated in his solution to Einstein's General Relativity equations) then it stands to reason that time does not exist in any universe to which General Relativity applies. Physicists and philosophers have mocked Godel's concept for decades but have yet to actually disprove it. We humans subjectively perceive the passage of time but that does not mean that our subjective perception is accurate; Einstein's theory accurately predicted that time passes more slowly as an object is accelerated and thus there is not one universal "now" but rather only various frames of reference, so Godel's suggestion that the passage of time is an illusion is perhaps not so radical a notion as it seems (though, if correct, it does raise an interesting philosophical or perhaps theological question of why our brains are designed/have evolved to believe in the passage of time if the passage of time is actually illusory).

The Einstein-Godel friendship survived any disagreements about theoretical or practical matters and it endured despite differences in age and temperament. While Einstein enjoyed his celebrity status and used his fame as a platform to publicly speak out about a variety of issues, Godel shunned the spotlight and at times seemed stunningly oblivious to anything that did not directly relate to mathematics; during the late 1930s, he innocently asked a refugee scientist who had recently fled the Nazis what had brought him to America. Not surprisingly, many people were not charmed by Godel's singular focus on mathematics to the exclusion of just about anything else. Godel avoided conflict and in time avoided human contact in general (other than with his wife, Einstein and very few others) by utilizing his full-proof escape method: agree to meet a person at a particular place and time and then not show up, thus ensuring that he avoided contact/conflict.

Godel was burdened from an early age with serious psychological problems. He suffered rheumatic fever as a child and when he was a child his research about rheumatic fever revealed that it often causes permanent heart damage. Therefore, Godel concluded that logic dictates that he suffered permanent heart damage, so he spent most of his adult life taking pills for a non-existent heart ailment. Godel also convinced himself that poisonous fumes were emanating from his air conditioner's ducts.

A deep pessimism clouded Godel's thoughts and moods. "We live in a world in which ninety-nine percent of all beautiful things are destroyed in the bud," he lamented. Godel did not believe in the concept of historical progress but instead felt that humanity was regressing: "The world tends to deteriorate. Good things appear from time to time in single persons and events...but the general development tends to be negative."

Taking this concept to what seemed to him to be a logical conclusion, Godel was convinced that there was a conspiracy to rid the world of logical-thinking people and that--as perhaps the foremost logician in the world--he was one of the targets of this conspiracy. Thus, Godel was constantly afraid that his food would be poisoned. Godel's wife Adele allayed those fears by sampling his food first; not long after Adele became too ill to perform this task for him, Godel died of starvation because he refused to eat.

Godel's paranoia is similar to the paranoia exhibited by the great chess champion Bobby Fischer in the sense that both men excelled in disciplines that require the rigorous application of logic and yet, paradoxically, logic failed them in areas outside of their expertise. However, Goldstein does not find Godel's paranoia paradoxical: "Paranoia isn't the abandonment of rationality. Rather, it is rationality run amuck, the inventive search for explanations turned relentless. A psychologist friend of mine put it this way: 'A paranoid person is irrationally rational...Paranoid thinking is characterized not by illogic, but by a misguided logic, by logic run wild" (p. 205).

Goldstein asks a haunting question about Godel that applies equally to Fischer and to other supergeniuses whose strict dedication to misguided logic led them to very dark places: "How can a person, operating within a system of beliefs, including beliefs about beliefs, get outside that system to determine whether it is rational? If your entire system becomes infected with madness, including the very rules by which you reason, then how can you ever reason your way out of your madness?" (p. 204). This is clearly a formidable task even for some of the most brilliant people who ever lived; neither Fischer nor Godel ever figured out how to reason their way out of their particular versions of madness: Fischer's logic extrapolated from the truth that the Soviet Union cheated at chess to create in his mind a vast conspiracy centered on anti-Jewish thought that reached bizarre (but to Fischer completely logical) conclusions such as every single move in every single Kasparov-Karpov game was prearranged; Godel's logic extrapolated from some truths about his early childhood illnesses to some unfounded beliefs about his health and about supposed conspiracies to poison him.

Fischer was only officially the World Chess Champion from 1972-75 but more than 40 years later many people still consider him to be the greatest chess player of all-time. Similarly, Godel published relatively little during his lifetime but because of the depth, quality and influence of what he did publish he has been called the greatest mathematician of the 20th century and perhaps the greatest logician since Aristotle. Godel postulated that the passage of time may be illusory but as long as we humans perceive the passage of time he should and will be remembered as someone who shed some light on the mysteries of the universe.

Further Reading:

1) Douglas Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid has been described as "simply the best and most beautiful book ever written by the human species."

In the 20th anniversary edition of his Pulitzer Prize winning book, Hofstadter explains his original goals and intentions:

GEB is a very personal attempt to say how it is that animate beings can come out of inanimate matter...GEB approaches [this question] by slowly building up an analogy that likens inanimate molecules to meaningless symbols, and further likens selves... to certain special swirly, twisty, vortex-like, and meaningful patterns that arise only in particular types of systems of meaningless symbols. It is these strange, twisty patterns that the book spends so much time on, because they are little known, little appreciated, counterintuitive, and quite filled with mystery [that] I call..."strange loops"...

...the Godelian strange loop that arises in formal systems in mathematics... is a loop that allows such systems to "perceive itself," to talk about itself, to become "self-aware," and in a sense it would not be going too far to say that by virtue of having such a loop, a formal system acquires a self.

2) A World Without Time: The Forgotten Legacy of Godel and Einstein by Palle Yourgrau focuses on Godel's mathematical solution to Einstein's General Theory of Relativity and the implication of that solution, namely that in a universe governed by the General Theory of Relativity time travel is possible. As Godel realized, if the past is accessible then this means that the past is not really past and therefore time cannot exist as anything other than an ideal concept in such a universe (i.e., in such a universe there is no real distinction between past, present and future).

3) Incompleteness: The Proof and Paradox of Kurt Godel by Rebecca Goldstein is a very readable yet informative account of Godel's life, though it apparently contains some errors in its descriptions of Godel's work (see below; as I do not have formal, higher level mathematical training I must defer to the experts on this issue).

4) The Incomplete Godel is a review of Yourgrau's book and Goldstein's book by Gregory Moore, a professor of mathematics at McMaster University in Canada. Moore prefers Yourgrau's book to Goldstein's because of several errors he notes in Goldstein's attempts to explain Godel's mathematical work but he states that the definitive Godel biography is Logical Dilemmas: The Life and Work of Kurt Gödel (A K Peters, 1997), by John W. Dawson, Jr.

5) Time and Causation in Godel's Universe describes some of the practical implications of Godel's concept of a universe in which time travel is possible.

6) The theoretical possibility of time travel presents us with the confounding Grandfather Paradox, which Robert Heinlein memorably explored in his classic short story "'--All You Zombies--.'"
All contents Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024 David Friedman. All rights reserved.