ScienceWeek

GOEDEL'S THEOREM

The bedrock upon which the edifice of mathematics rests is the notion of proof. Unlike areas such as the law, where arguments can be won by force of personality alone, in mathematics an argument succeeds only by producing a logically consistent set of steps leading from a primitive axiom to the statement whose proof is desired. Such a set of deductive steps is called a _proof sequence_, with the final statement in the sequence termed a _theorem_. We're all familiar with such a setup from the elementary geometry of Euclid, which we grappled with in secondary school. In Euclid's view of the world, the axioms are 'self-evident' truths, such as 'Two points determine a straight line' and the infamous parallel postulate, 'Through a given point one and only one line may be drawn that is parallel to a given line.' From a handful of such statements whose truth is accepted without proof, one can use the tools of deductive logic to derive a plenitude of theorems about the properties of triangles, circles, and other geometric objects.

In the early part of this century, the famed German mathematician David Hilbert [1862-1943] believed that all of mathematics --arithmetic, geometry, analysis -- could be framed within a logical system that would enable us to prove or disprove _any_ statement you cared to make about mathematical objects. In other words, any assertion was either true or false, and which of these was the case could be determined in a finite number of deductive steps. Hilbert's dream of a unified framework within which to encompass all of mathematics was shattered in 1931, when the Austrian logician Kurt Goedel [1906-1978] published a paper in which he showed that this could not possibly be the case. Goedel proved that for any consistent logical system strong enough to talk about the relationships between whole numbers (arithmetic), there must necessarily exist statements about numbers that could be neither proved nor disproved using the tools of that logical framework. Here by 'consistency' we mean a system in which a statement and its negation cannot both be proved true., which is the minimal requirement for the system to be useful in separating fact from fiction.

Goedel actually proved even more. He showed that there must exist a statement about numbers that is unprovable within the rules of the logical system -- but that can be seen to be actually true by looking at the statement from _outside_ the system. Goedel accomplished this logical sleight-of-hand by inventing a clever way to code any statement about numbers using numbers themselves. He then coded the self-referential statement 'This statement is unprovable' using his numerical scheme, thereby creating an assertion about numbers that is logically true -- but cannot be seen to be true using the proof machinery of the logical system itself. One way to describe this 'incompleteness' result is to say that Goedel proved that truth is bigger than proof.

Adapted from: John L. Casti: Paradigms Regained: A Further Exploration of the Mysteries of Modern Science. Perennial 2001, p.126. More information: http://www.amazon.com/exec/obidos/ASIN/0380731711/scienceweek