Last week I explained how a then 25-year-old logician, Kurt Gödel, overturned a basic assumption of many mathematicians in the early 20th century. Even as experts were building a seemingly firm foundation for all mathematics, Gödel demonstrated that this effort would never answer every question.
Gödel’s incompleteness theorems are among the most fascinating results in mathematics. They have revolutionized the subject—and disillusioned scientists. But in addition to their far-reaching consequences, his ideas fascinated his colleagues by being able to say something about the capabilities of a mathematical system while operating within that system.
That is, Gödel used the computational rules and logical inferences that follow from the foundational axioms of mathematics (the Zermelo-Fraenkel set theory with the axiom of choice, or ZFC) to make statements about that system itself. This was a brilliant feat that no one had ever accomplished before.
To do this, he developed an approach that involved assigning a unique number to each mathematical statement. Instead of writing, for example, “for every number m, there is another number n greater than m,” he defined a corresponding natural number (which is very large) from which the statement could be derived. The coding is not even that complicated: Gödel assigned the so-called Gödel numbers 1 to 12 to the 12 basic logical operations such as “plus” or the logical operator “OR.” Variables such as m or n corresponded to prime numbers larger than 12.
If you now form a statement from the 12 operations and some variables, the corresponding code number can be calculated quickly. For example: For the statement 0 + 0 = 0, you need the Gödel numbers 0, + and =. These are 6, 11 and 5. Now this must succeed in transforming the series 6, 11, 6, 5, 6 (which stands for 0 + 0 = 0) into a number, from which one can unambiguously decode the original statement. Simply lining up the digits and forming “611656” does not work because the coding could fit also to the Gödel numbers 6, 1, 1, 6, 5, 6, which correspond to the statement 0 NOT NOT 0 = 0.
Gödel’s idea, therefore, was to choose prime factors as a guide because any number can be uniquely broken down into its prime factors, say 12 = 22 × 3. Thus, to encode a statement from n Gödel numbers, one can multiply the first n prime numbers together, raising each prime number to the power of the corresponding Gödel number. For the example 6, 11, 6, 5, 6, the corresponding coding would be: 26 × 311 × 56 × 75 × 116. Thus, for each statement, one can find a number that uniquely corresponds to it.
A Statement about the Statement Itself
By expressing logical statements, formulas and even proofs as numbers, Gödel could use the ordinary tools of mathematics to reveal mathematical truths. For example, if one encodes the axioms and a statement, then one can use ordinary arithmetic operations to check whether the statement can be proved using the axioms.
Thus, Gödel achieved a stroke of genius: he managed to formulate a statement G, which was about itself. G read, “The statement G cannot be proved.” Now all Gödel had to do was to find out whether this was true or false. Suppose that G is false. Then the negation of the statement holds—namely, “The statement G can be proved.” But if this is the case, G must be true. Accordingly, there is a contradiction: by assuming that G is false, one obtains the statement that G is true.
Therefore, G must be true. In this case, however, G cannot be proved. Thus, if one assumes that an axiom system is free of contradictions, then there are necessarily true but unprovable statements. Thus, the foundation of mathematics is necessarily incomplete. But this does not mean that there are problems which are neither false nor true—only that they are not always provable. And as Gödel could also show in his seminal work, this is the case for all axiom systems (not just for ZFC).
