Essays on Science and SocietyPORTRAITS OF SCIENCE

Kurt Gödel--Separating Truth from Proof in Mathematics

Science  06 Dec 2002:
Vol. 298, Issue 5600, pp. 1899-1900
DOI: 10.1126/science.1079622

In 1931, a young Austrian mathematician published a paper that sent shock waves through the mathematical community and forced mathematicians to take a fresh look at their discipline. The mathematician was Kurt Gödel, and the result proved in his paper became known as the Gödel Incompleteness Theorem, or more simply Gödel's Theorem—although it was by no means the only major theorem he proved during his highly successful career. He is also known as one of the inventors of the theory of recursive functions (which formed part of the foundation for computers).

Gödel was born on 28 April 1906, in what was then Brünn in Austria, now Brno in the Czech Republic. By all accounts he was an outstanding pupil in high school and a star student at the University of Vienna, where he continued after graduation to obtain a doctoral degree in 1929. He went straight to a faculty position in Vienna, and it was there that he proved his Incompleteness Theorem. Gödel remained in Vienna until 1940, when he fled the worsening Nazi atrocities to take up a position at the Institute for Advanced Study in Princeton, which he had already visited in 1934. He remained at Princeton until his death on 14 January 1978. It was an unlikely death for the man who was arguably the world's foremost expert in logic. A hypochondriac for much of his adult life, as he grew older, Gödel became convinced that he was being poisoned. He eventually stopped eating altogether, and starved to death.

Gödel's decidedly illogical end did nothing to diminish his reputation. When Time magazine conducted a poll 2 years ago to determine the most influential thinkers of the 20th century, Gödel was one of just two mathematicians who made the top 20, along with Alan Turing.

The Incompleteness Theorem forced mathematicians to question what it means to say something is true in mathematics. The resulting change in our understanding of mathematics was every bit as dramatic as the change in our conception of geometry that followed the discovery of non-Euclidean geometries in the 19th century.

Both of these major discoveries involved axiomatic systems, and neither can be properly understood without an appreciation of what mathematicians means by the word “axiom” and the role axioms play in mathematics. A misunderstanding of the nature of axioms is what lies behind a significant amount of nonsense that has been written about Gödel's Theorem over the years.

In brief, Gödel's Theorem says that in any axiomatic mathematical system that is sufficiently rich to do elementary arithmetic, there will be some statements that are true but cannot be proved (from the axioms). In technical terminology, the axiom system must be incomplete.

Kurt Gödel (1906–1978)CREDIT: INSTITUTE FOR ADVANCED STUDY, PRINCETON, NJ

At the time Gödel proved this theorem, it was widely believed that, with sufficient effort, mathematicians would eventually be able to formulate axioms to support all of mathematics. The Incompleteness Theorem flew in the face of this expectation, and many took it to imply that there is a limit to the mathematical knowledge we may acquire. Few mathematicians think that way now, however. The change in our conception of mathematical truth that Godel's theorem brought about was so complete, that today most of us view the result itself as merely a technical observation about the limitations of axiom systems.

To appreciate the initial impact of Gödel's Theorem, you have to adopt the mind-set of the time. During the 19th century, mathematicians learned that many seemingly intuitive concepts were problematic, among them, the structure of the real continuum and the nature of continuous functions. To avoid what could be a misleading dependency on unreliable assumptions and intuitions, they began to put greater emphasis on a mode of doing mathematics introduced by the ancient Greeks, but which had been left largely on the sidelines ever since then: the axiomatic method. Here, the idea is to begin by writing down, precisely, an initial set of assumptions—or axioms (from the Greek word axioma)—that you believe to capture the concept or system you are interested in. You then proceed to establish truths about that concept or system by means of logical deduction from those axioms.

The most familiar examples of this approach are Euclid's axioms for geometry. In his mammoth work Elements, Euclid began by listing five principles from which all truths about plane geometry were supposed to be deduced. Because axioms are intended to be the starting point of a quest for truth, their own validity should not be in any doubt, of course. The axioms should be simple assertions that are self-evident.

The fifth of Euclid's five axioms states that “For every line l and for every point P that does not lie on l, there exists a unique line m through P that is parallel to l.” Questions about this Parallel Postulate dogged Euclidean geometry for hundreds of years. The axiom was in doubt because it was far more difficult to state than the other four. Attempts to resolve the issue by deducing it from simpler assumptions continued in vain, until the shocking discovery that its inclusion—while arguably in line with a natural human intuition about parallel lines—was entirely arbitrary. The familiar geometry of Euclid, in which the Parallel Postulate was taken as an axiom, was just one of a number of possible geometries. Deciding between them was purely a matter of taste or of intended application.

In fact, there was a far greater problem with Euclid's axioms than his inclusion of the Parallel Postulate. His axiom system omitted many basic assumptions that he, and generations of subsequent scholars, unconsciously used in deriving the theorems that supposedly followed from the axioms. It was left to the German mathematician David Hilbert to set the record straight in the late 19th century, by writing down those crucial missing axioms.

To give some idea of the kind of problem that Hilbert noticed, consider one of Euclid's most elementary ruler-and-compass constructions, that of an equilateral triangle. You begin with a straight line, and then draw arcs from the ends of the line, with radius set equal to the line. The point where the arcs intersect marks the third vertex of your equilateral triangle. It all seems fairly sound. You can, after all, carry out these steps and draw an equilateral triangle.

But as Hilbert observed, how can you be sure that the two arcs really do intersect? That is, how do you know they have a point in common? Just because the arcs you draw on a sheet of paper look as though they meet, that does not guarantee that there really is a point of intersection. After all, unlike the pencil lines you actually draw, the idealized lines and arcs of geometry have no thickness. How can you be sure that two arcs having no thickness have a point in common? The answer is that you cannot. If you want the two arcs to intersect, you need to have an axiom that implies that they do. It is a reasonable axiom, completely in line with our intuitions about drawing arcs. But its status is that of an assumption, not something that can be proved.

CREDIT: JOE SUTLIFF

The lesson to be learned from Hilbert's work is that it can be extremely difficult to identify all the assumptions that are used in any branch of mathematics. Following his work on the axioms for geometry, Hilbert put forward a view of mathematics that was to gain considerable acceptance. According to this view, which became known as formalism, mathematics should be regarded as being, at heart, nothing other than a collection of formal games, each one played according to completely specified rules.

To do Euclidean geometry, for instance, was to play the Euclidean geometry game. In that game, you start with the axioms for Euclidean geometry and then deduce all the truths of Euclidean geometry by means of mechanistic manipulations of symbols according to totally specified rules. Nothing could be used that was not specified by the axioms or the manipulation rules. In particular, no intuition about the nature of points or lines could or should be used. As Hilbert himself remarked, you could replace all talk about points and lines by reference to beer mugs and bar tables, provided you formulated the axioms in terms of those objects, and the resulting theory would be identical in all respects except for the actual words being used.

By removing all intuitions so that points and lines are no different from beer mugs and bar tables, the reasoning went, mathematics would be forever free from the dangers of unrecognized and possibly misleading assumptions. It would, in principle, be possible to design mechanical devices—which, of course, have no intuitions—to follow the rules and deduce all the truths for you. (This, remember, was before computers were invented.)

This approach to mathematics, to formulate all the axioms you need to deduce all the truths in a particular branch of mathematics mechanistically, became known as the Hilbert Program. For many, the search for axioms became something of a Holy Grail, although Hilbert, who had great respect for the role played by human intuition in the practice of mathematics, was not one of them, and never himself proposed that the program to which others attached his name should be carried out.

One of the most sustained efforts to carry out the Hilbert Program was made by the English philosophers Bertrand Russell and Alfred North Whitehead. Their mammoth, three-volume work, Principia Mathematica, published from 1910 to 1913, was an attempt to develop basic arithmetic and logical reasoning itself from axioms.

It was the axiom system in Principia Mathematica that Gödel took, by way of an exemplar, to demonstrate beyond any doubt that the goal of the Hilbert Program was unattainable. He called his dramatic paper “On formal undecidable statements of Principia Mathematica and related systems.” At the time that Gödel proved it, the Incompleteness Theorem gained a reputation of being difficult to follow. But that has long ago given way to a realization that it is really a rather simple result. The complexities of Gödel's original proof are largely irrelevant, a consequence of the particular way he presented the argument. In essence, Gödel took the familiar Liar Paradox and showed how to reproduce it within any axiom system that supported arithmetic.

The Liar Paradox, which goes back to ancient Greece, arises when a person stands up and says “I am lying.” If the person is lying, then the statement is true, so they are not lying; and if they are not lying, the statement is false, so they are lying. This is a seemingly inescapable paradox. Gödel took a similar statement, “This statement is not provable,” and showed how it could be formulated as a mathematical formula within arithmetic.

This required, first of all, coding statements as numbers—a process known as Gödel numbering. At the time, this was regarded as a deep and difficult step, but today any number of spy movies have depicted the way in which English words and sentences can be encoded as sequences of numbers, often as part of the process of encrypting messages. Gödel's next step was to show how the concept of provability could be captured within arithmetic. This was a somewhat deeper move, but to today's mathematicians it too seems fairly routine.

Once the coding had been completed, the noose was tight. If one assumed that the axiom systems were consistent (that is, they did not lead to any internal contradictions), the statement clearly could not be provable (since it declared its own unprovability). Hence it was true—but unprovable.

To those mathematicians (the formalists) who believed that mathematical truth was the same as provability—that the true statements of mathematics are precisely the ones you can prove from the axioms once you have formulated them all properly—Gödel's theorem was devastating. Today, however, as I remarked earlier, mathematicians regard it simply as confirming the limitations of what can be achieved with axiom systems.

But they are able to do so only because contemporary mathematics has learned the lesson that Gödel's Theorem taught us. Gödel's result may not have changed mathematics very much. But it changed the way we view it. His selection as one of the most influential thinkers of the 20th century is undoubtedly well deserved.

Subjects

Navigate This Article