V.15 Gödel’s Theorem
Peter J. Cameron
In response to problems in the foundations of mathematics such as Russell’s paradox (“consider the set of all sets which are not members of themselves; is it a member of itself?”), HILBERT [VI.63] proposed that the consistency of any given part of mathematics should be established by finitary methods that could not lead to a contradiction. Any part for which this had been done could then be used as a secure foundation for all of mathematics.
An example of a “part of mathematics” is the arithmetic of the natural numbers, which can be described in terms of FIRST-ORDER LOGIC [IV.23 §1]. We begin with symbols, both logical (connectives such as “not” and “implies,” quantifiers such as “for all,” the equality symbol, symbols for variables, and punctuation) and nonlogical (symbols for constants, relations, and functions suitable for the branch of mathematics under consideration). Formulas are finite strings of symbols built according to certain precise rules (which allow them to be mechanically recognized). We fix a certain set of formulas as our axioms, and we also choose a few rules of inference that allow us to infer some formulas from others. An example of a rule of inference is modus ponens: if we have inferred φ and (φ → ψ), then we can infer ψ. A theorem is a formula that is at the end of a chain (or tree) of inferences that starts with axioms.
Axioms for the natural numbers were given by PEANO [VI.62] (see THE PEANO AXIOMS [III.67]). The nonlogical symbols are zero, the “successor function” s, addition, and multiplication. (The last two can be defined in terms of the others by inductive axioms: for example, the rules x + 0 = x and x + s(y) = s(x + y) define addition.) The crucial axiom is the principle of induction, which asserts that if P(n) is a formula such that P(0) is true and P(n) implies P(s(n)) for all n, then P(n)is true for all n. Hilbert’s specific challenge was to give a formal proof of the consistency of this theory: that is, a proof that no contradiction can be deduced from the axioms by the rules of first-order logic.
Hilbert’s program was undone by two remarkable incompleteness theorems proved by GÖDEL [VI.92]. The first theorem states the following.
There are (first-order) statements about the natural numbers that can be neither proved nor disproved from Peano’s axioms.
(This is sometimes qualified by being prefixed with, “If Peano’s axioms are consistent, then . . . .” However, since we accept the existence of the natural numbers, we do know that Peano’s axioms are consistent, as the natural numbers model them. So the qualification is unnecessary here, although it would need to be included if we were discussing some axioms whose consistency was not clear.)
Gödel’s proof is long, but it is based on two simple ideas. The first is Gödel numbering, which is a means of encoding each formula or sequence of formulas as a natural number in a systematic and mechanical way.
It can be shown that there is a two-variable formula π (x,y) such that π (m,n) holds if and only if “n is a proof of m,” which is a shorthand way of saying that m is the Gödel number of a formula φ and n is the Gödel number of a string of formulas that constitutes a proof of φ. Slightly more elaborately, there is a formula ω(x,y) such that ω(m,n) holds if and only if m is the Gödel number of a formula φ that has one free variable and n is the Gödel number of a proof of φ(m). (A free variable is one that is not quantified over. For example, φ(x) might be the formula (∃y) y2 = x, in which case x is the free variable. For this choice of φ, the number n would be the Gödel number of a proof that the Gödel number of φ was a perfect square.)
Now let ψ(x) be the formula (∀y)(¬π(x,y)). If φ is a formula (with one free variable) with Gödel number m, then ψ(m) tells us that there is no proof of φ(m). (It tells us this indirectly: what it actually says is that there is no y that is the Gödel number of such a proof.) Let p be the Gödel number of ψ itself, and let ζ be the formula ψ(ρ).
This brings us to the second idea in the proof: self-reference. The formula ζ is carefully devised so that it asserts its own unprovability, since ψ (p) tells us that there is no proof of the formula φ(p), where φ is the formula with Gödel number p. In other words, it tells us that there is no proof of ψ(p). Since ζ asserts its own unprovability, it must be unprovable (since a proof of ζ would be a proof that ζ had no proof, which is absurd). Since ζ asserts its unprovability and is unprovable, it is true, and since it is true it cannot be disprovable. (One might wonder why this argument that ζ is true does not constitute a proof of ζ. The answer is that although it is a rigorous demonstration of the truth of ζ, it is not a proof in Peano arithmetic. That is, it is not an argument that starts from the Peano axioms and uses the rules of inference of the kind we discussed earlier.)
Gödel numbering also allowed Gödel to consider the consistency of the axioms as a first-order formula: namely (∀y)(¬(π(m,y))), where m is the Gödel number of the formula 0 = s(0) (or any other contradiction). Here is Gödel’s second theorem.
It is impossible to prove from Peano’s axioms that they are consistent.
The proofs of these theorems are not specific to the Peano axioms, but apply to any (consistent) system of mechanically recognizable axioms that is powerful enough to describe the natural numbers. Thus, completeness cannot be restored simply by adding a true but unprovable statement as a new axiom, for the resulting system is still strong enough for Gödel’s theorem to apply to it.
It might seem that we could obtain a complete axiomatization of the natural numbers by simply taking all true statements as axioms. However, one requirement for Gödel’s theorems is that the axioms should be recognizable by some mechanical method. (This is needed to construct the formula π(x,y) at the start of the proof.) Indeed, we can deduce from this that (as subsequently pointed out by TURING [VI.94]) the true statements about the natural numbers cannot be mechanically recognized (that is, their Gödel numbers do not form a recursive set).
Gödel’s true but unprovable statement is important for the foundations of mathematics, but it has no intrinsic interest in its own right. Later, Paris and Harrington gave the first example of a mathematically significant statement that is unprovable from Peano’s axioms. Their statement is a variant of RAMSEY’S THEOREM [IV.19§2.2]. Subsequently, many other “natural incompletenesses” have been found.
Of course, the consistency of Peano’s axioms can be proved in a stronger system, since we could just add the (unprovable) consistency statement. Less trivially, since a model of the natural numbers can be constructed within set theory, the consistency of Peano arithmetic can be proved from THE ZERMELO-FRAENKEL AXIOMS [IV.22§3.1] (known as ZFC) for set theory. Of course, ZFC cannot prove its own consistency, but the consistency of ZFC can be deduced from a yet stronger system (for example, adding an axiom that asserts the existence of a suitably “large” cardinal number such as an INACCESSIBLE CARDINAL [IV.22 §6]).
For small enough parts of mathematics, it is sometimes possible to find complete axiom systems (that is, systems that allow one to prove every true statement). For instance, this can be done for the theory of the natural numbers with zero, the successor function, and addition alone. Thus, multiplication is essential to Gödel’s argument.
It is more elementary to see that Peano’s axioms are not categorical: there are models for the axioms that are not isomorphic to the natural numbers. Such nonstandard models of arithmetic contain infinitely large numbers (that is, numbers that are larger than all natural numbers).
Gödel’s theorem has been a battleground for philosophers arguing about whether the human brain is a deterministic machine (in which case, presumably, we would not be able to prove any formally unprovable statement). Fortunately, there is not enough space in this article for more details!