Gödel and the limits of logic
Gödel and the limits of logic
Submitted by plusadmin on June 1, 2006
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.
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.
Kurt Gödel (right) with his brother Rudolf around 1908. Image courtesy JW Dawson.
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. ForPlato, 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.
Euclid’s five axioms for plane geometry
— 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
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.
The incomplete puzzle of the natural numbers: no
matter what you try, some pieces will never fit.
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.