Goedel and the Limits of Logic
https://plus.maths.org/content/goumldel-and-limits-logic
Goedel and the Limits of Logic
Submitted by plusadmin on June 1, 2006
Papers courtesy of Princeton University and Institute for Advanced Study.
The man in the photograph on the right looks formal, reserved and somewhat undernourished. His face and his writings are unfamiliar to most, except for a few philosophers and mathematical logicians. He was Kurt Gödel, celebrated for his incompleteness theorems, the implications of which are far-reaching for the foundations of mathematics and computer science. The story of his life and work is that of a persistent quest for rationality in all things, pursued against a background of recurrent mental instability.
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.
Mr Why
Born on April 28, 1906, in Brno, Moravia, Gödel was the second of two children of Rudolf and Marianne Gödel, expatriate Germans whose families were associated with the city’s textile industry. Gödel and his brother were both sent to private German language schools, where they did very well in their studies.
Indeed, only once during his primary and secondary school career did young Kurt ever receive less than the highest mark in any subject (mathematics!). Yet he gave no early intimation of genius. He was a highly inquisitive child, so much so that he was nicknamed der Herr Warum (“Mr. Why”). But he was also introverted, sensitive and somewhat sickly. At about the age of eight he contracted rheumatic fever, and although it seems not to have caused lasting physical damage, it kept him out of school for some time and may have fostered the exaggerated concern for his health and diet that was to become increasingly prominent over the years.
The reticent genius
In 1924 Gödel left his homeland to enrol at the University of Vienna. At the time of his enrolment Gödel intended to seek a degree in physics. But after a short while, impressed by the lectures of professors Philipp Furtwängler and Hans Hahn, he switched to mathematics. His remarkable talents soon attracted attention — so much so that just two years after his matriculation he was invited to attend sessions of a discussion group that Hahn and philosopher Moritz Schlick had founded two years earlier. The group, which was later to become famous as the Vienna Circle, was inspired by the writings of Ernst Mach, a champion of rationalism who believed that all things could be explained by logic and empirical observation, without recourse to metaphysics.
The Circle brought Gödel into contact with scholars such as philosopher of science Rudolf Carnap and mathematician Karl Menger and helped to acquaint him with the literature of mathematical logic and philosophy. In particular, the Circle was immersed in the writings of Ludwig Wittgenstein, whose concern about the extent to which language can speak about language may have prompted Gödel to probe analogous questions about mathematics.
Gödel did not, however, share the positivistic philosophical outlook of the Circle, which extended Mach’s ideas. Instead he was aPlatonist: 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.
Although Gödel was an attentive observer and clearly brilliant, he rarely contributed to the Circle’s discussions, unless they were about mathematics. Shy and reclusive, he had few close friends. (He did, however, like the company of women and was apparently quite attractive to them.) After 1928 he seldom attended the group’s meetings but became active instead in a mathematical colloquium organised by Menger.
Moment of impact
During this period, Gödel suddenly acquired international stature in mathematical logic. Two papers in particular thrust him into prominence. One was his doctoral dissertation, submitted to the University of Vienna in 1929 and published the next year. The other was his treatise On Formally Undecidable Propositions of Principia Mathematica and Related Systems, published in German in 1931 and submitted as his Habilitationsschrift (qualifying dissertation for entrance into the teaching profession) in 1932.
The dissertation, entitled The Completeness of the Axioms of the First-Order Functional Calculus, solved an open problem that David Hilbert and Wilhelm Ackermann had posed in their 1928 textbook Grundzüge der theoretischen Logik (Foundations of Theoretical Logic). The problem concerned formalised mathematical systems and the accepted rules for logical reasoning, which were stated in the book.
A formalised mathematical system is described by a set of axioms. These are pre-determined truths that define the objects in the system and are never called into question. The ancient mathematician Euclid, for example, based his theory of plane geometry on five axioms. The statements “any two points can be joined by a straight line segment” (fig 1), and “any straight line segment can be extended indefinitely” (fig 2), are two of these axioms.
— read more in the Plus article The origins of proof.
They are taken to be true from the outset, and any other statement about plane geometry has to be derived from the five axioms using only the rules of logic — no intuition or knowledge that comes from outside the system are allowed.Hilbert and Ackermann’s question was: if you have a set of axioms describing a mathematical system, do the rules for logical reasoning which they gave in their book allow you to derive every true statement about the system, and do they ensure that only true statements can be derived?
The expected answer was “yes”, and Gödel confirmed that it was. His dissertation established that the principles of logic developed up to that time were adequate for their intended purpose, which was to prove everything that was true on the basis of a given set of axioms. It did not show, however, that every true statement concerning the natural numbers, that is the numbers 0,1,2, … , could be proved on the basis of the accepted axioms of number theory.
The problem with number theory
The axioms of number theory were based on those laid out by the Italian mathematician Giuseppe Peano in 1889. The first four of his axioms are
- 0 is a natural number,
- every natural number has a successor,
- no natural number has 0 as its successor,
- distinct natural numbers have distinct successors.
The successor of 0 is what we call 1, the successor of 1 is what we call 2, etc. In this way, all the natural numbers are defined, and so is the operation of addition: 16+4, for example means “take the number 16 and move on 4 places in the sequence of successors”.The fifth and final of Peano’s axioms is known as the principle of induction, and this axiom proved to be the sticking point. It states:
Suppose that a property holds for 0, and suppose you can prove that if this property holds for another natural number, then it also holds for the successor of that number. Then the property holds for all natural numbers.
A simple proof by induction
We will prove by induction that
0 + 1 + 2 + 3 + …. + n = n(n+1)/2
for any positive whole number n.First, we verify that the statement is true for n = 0:
0 = (0 × 1)/2,
so it is.Now we assume that the statement is true for a positive whole number kand see if we can show that it is also true for k+1:
1 + 2 + … + k + k+1
= k(k+1)/2 + k+1
= (k(k+1)+2k+2)/2 = (k2+3k+2)/2
= (k+1)(k+2)/2.
Thus, whenever the statement is true for a number k, it is also true fork+1, the next number along.So, since we have verified the statement for 0, it follows that it must be true for 1, which means it must be true for 2 and in turn for 3, etc. We can reach any positive whole number n in this way, so we have proved that the statement is true for all positive whole numbers, as required. QED
This is sometimes called the domino principle: if you knock one over, the rest will topple. It might seem self-evident, but mathematicians found it problematic, because rather than talking about natural numbers themselves, it talks aboutproperties of natural numbers. Such a “second-order” statement was thought too vague and ill defined to serve as a basis for the theory of natural numbers.To circumvent that problem, the induction axiom was translated into an infinite schema of similar axioms that refer to specific formulas rather than to general properties of numbers. Unfortunately, however, those axioms no longer uniquely characterize the natural numbers. Indeed, as Norwegian logician Thoralf Skolem demonstrated a few years after Gödel’s work, even if all statements that are true of the natural numbers are taken as axioms, there will still be other structures, essentially different from the natural numbers, that also satisfy the axioms.
Now Gödel’s completeness theorem states that whatever propositions are taken as axioms, one can prove all (and only) those statements that hold in all structures satisfying the axioms. But if some statement is true of the natural numbers but is not true of another system of entities that also satisfies the axioms, then it cannot be proved. At first, that did not seem to be a serious problem, because mathematicians hoped that entities that masqueraded as numbers but were essentially different from them did not exist. So Gödel’s next theorem came as a shock.
The Incompleteness Theorem
In his 1931 paper Gödel showed that, no matter how you formulate the axioms for number theory, there will always be some statement that is true of the natural numbers, but that can’t be proved. (That is, objects that obey the axioms of number theory but fail to behave like the natural numbers in some other respects do exist.)
But why not just turn such a true but unprovable statement into an axiom? After all, axioms are precisely those statements which we accept to be true without proof. But here lies the true bite of the incompleteness theorem: Gödel showed that whenever the axioms can be characterized by a set of mechanical rules, it does not matter which statements are taken to be axioms: some other true statements about the natural numbers will remain unprovable. It’s like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you’ll always end up with some that won’t fit in the end.
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 trueonly 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 thehalting 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 examineany 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.
No program can find all the viruses on your computer,
unless it interferes with the operating system itself.
Matters of heart and mind
Gödel spent the 1933-34 academic year in Princeton, New Jersey, at the newly founded Institute for Advanced Study, where he lectured on his incompleteness results. He was invited to come there the next year as well but suffered a mental breakdown shortly after his return to Vienna. He recovered in time to return to Princeton in the fall of 1935, but a month after his arrival he experienced a relapse and did not return to lecturing until the spring of 1937 in Vienna.
His problems seem to have started with hypochondria: he was obsessive about his diet and bowel habits and kept a daily record for two decades or more of his body temperature and milk of magnesia consumption. He had a fear of accidental and, in later years, deliberate poisoning. This phobia led him to avoid eating food, so that he became malnourished. At the same time, though, he ingested a variety of pills for an imaginary heart problem.
Except in times of crisis, Gödel’s mental problems hampered his work surprisingly little. The person who kept him going was Adele Porkert, whom he had met at a Viennese nightclub during his student years. Porkert was a Catholic divorcée six years older than Gödel, who worked as a dancer and whose face was disfigured by a birthmark. His parents regarded her as a scandalous person. But the two were devoted to each other, and more than once, by serving as his food taster, she helped to allay Gödel’s growing fears that someone was trying to poison him. The two were married in September 1938, just before Gödel returned once more to America.
Back in the states, Gödel lectured at the Institute for Advanced Study and the University of Notre Dame on exciting new results in set theory, which answered another question of Hilbert’s. These results represented another major achievement, but they were still not enough to earn him a permanent academic position. During his year at the Institute for Advanced Study and Notre Dame, his authorization to teach at Austrian universities lapsed. When he returned to Vienna to be reunited with his wife in the summer of 1939, he was summoned for a military physical and declared fit for service in the Nazi armed forces.
Shelter in America
Until then, Gödel appears to have been aloof to the frightening developments in Europe. His lack of emotional engagement with people may have kept him from appreciating the significance of what was happening. He seemed oblivious to the fates befalling his colleagues and professors, many of whom were Jewish: he stayed immersed in his work while the world around him fell apart. Finally, he realized it was taking him down as well.
In that desperate situation he enlisted the support of the Institute for Advanced Study to help secure exit visas for himself and his wife. His efforts were successful, and in January 1940 the two of them began a long journey to Princeton.
Gödel never again left the U.S. He was made a permanent member of the institute faculty in 1946. Two years later he acquired American citizenship (on which occasion the judge who swore him in made the unfortunate error of asking his opinion of the U.S. Constitution, and thereby unleashed a pent-up lecture on its inconsistencies.) But Gödel was not promoted to professor until 1953 — the same year he was elected to membership in the National Academy of Sciences — in part because his expressed fear that poison gases were escaping from his refrigerator aroused continuing concern about his mental stability. During those years, his friend Albert Einstein took it on himself to look after Gödel as best he could, taking a walk with him every day. Their conversations seem to have had a calming effect on Gödel.
After his emigration Gödel turned to philosophy and relativity theory. In 1949 he demonstrated that universes in which time travel into the past is possible were compatible with Einstein’s equations.
Deepening fears
Gödel’s last published paper appeared in 1958. After that he withdrew more and more into himself, becoming increasingly emaciated, paranoid and hypochondriacal. He last appeared in public in 1972, when the Rockefeller University granted him an honorary doctorate. Three years later he was awarded the National Medal of Science but declined to attend the awards ceremony on grounds of ill health.
On July 1, 1976, having reached the mandatory retirement age of 70, Gödel became professor emeritus at the institute. His responsibilities did not lessen, though, because his wife, who for so many years had nurtured and protected him, had suffered an incapacitating stroke a few months before. It was his turn to care for her. He did so, devotedly, until July 1977, when she underwent emergency surgery and was hospitalized for nearly six months.
At about that time Oskar Morgenstern, the friend who had helped to look after Gödel in the years after Einstein’s death in 1955, died of cancer. Gödel was thus left to fend for himself against his growing paranoia. In the face of that, he declined rapidly. His fear of poisoning led to self-starvation, from which he died on January 14, 1978.
Adele Gödel survived her husband by three years. At her death, on February 4, 1981, she bequeathed rights to Gödel’s papers to the Institute for Advanced Study.
Gödel published remarkably few papers during his lifetime, but their impact has been enormous. They have affected virtually every branch of modern logic. During the past decade, other papers of his have been translated and published posthumously in the third volume of his Collected Works. Their contents, including his formalization of the so-called ontological argument for the existence of God, have now begun to attract attention as well. At last, the breadth of his work is becoming known to those outside the mathematical community.
Further reading
Read more about mathematical proof in past Plus articles, including our series on the origins of proof from Euclid to Gödel to the proof of Fermat’s Last Theorem.
About this article
This article was adapted from Gödel and the limits of logic by JW Dawson. Copyright © June 1999 by Scientific American, Inc. All rights reserved.
John W Dawson is Professor of Mathematics at the York campus of Pennsylvania State University. Trained as a logician, during the years 1982-84 he catalogued Gödel’s papers at the Institute for Advanced Study, work that provided the basis for his 1997 biographyLogical Dilemmas: The Life and Work of Kurt Gödel.
Dawson’s book Logical dilemmas: The life and work of Kurt Gödel is reviewed in this issue of Plus.