62 | 7 HIlBERT AND HIS fAmOUS PROBlEm
a vast quantity of other truths about natural numbers can be deduced: for example, that multi-
plying a natural number by 0 results in 0; and that if any natural number has a selected mathe-
matical property, then there is a least number with that property (the ‘least-number principle’).
It would be nice to be able to say that all truths about natural numbers can be deduced from
the Peano axioms, but Gödel proved that this is not so: the Peano axioms are incomplete, in
precisely the sense that not all truths about the numbers 0, 1, 2, 3, . . . can be proved from them.
This came as an unpleasant surprise to Hilbert.
To be precise, Gödel proved this incompleteness result on the assumption that the Peano
axioms are consistent with one another, as certainly seems obvious once you see all the axioms
together. Consistency, or freedom from contradiction, is traditionally regarded as fundamen-
tally important in mathematics, and Hilbert expended a lot of mathematical energy on the very
difficult problem of how to prove that arithmetic is consistent: ‘we can never be c e r t a i n’, he said,
‘of the consistency of our axioms if we do not have a special proof of it’.^20 On the other hand,
once we do have a consistency proof, ‘then we can say that mathematical statements are in fact
incontestable and ultimate truths’.^21
So Hilbert desired a consistent and complete set of axioms for arithmetic; but, in what has
become known as his first incompleteness theorem, Gödel proved that Hilbert could not pos-
sibly have what he desired. As if this were not bad enough, Gödel then dealt a second crushing
blow to Hilbert’s attempt to provide what he called ‘a secure foundation for mathematics’.^22 In
his second incompleteness theorem, Gödel proved that it is impossible to find a proof of the con-
sistency of arithmetic satisfying Hilbert’s stringent conditions. The proof that Hilbert thought
mathematicians had to find—because it would fill in the missing step in his case that math-
ematics consists of ‘incontestable truth’—turned out to be an impossibility.^23
Turing exposed yet another of the flaws in Hilbert’s thought. This concerned the process of
adding new axioms to a set of axioms that has already been laid down—whether to the Peano
axioms or to any other set of axioms (e.g. for geometry or for analysis). Suppose a mathemati-
cian wanted to add some extra axioms to the Peano axioms—what additional axioms could
legitimately be laid down? Hilbert’s answer was simple and powerful: a mathematician could
lay down any new axioms that he or she saw fit, just so long as the new axioms could be proved
consistent with the ones that had already been adopted. Turing pointed out that (for techni-
cal reasons) Gödel’s second incompleteness theorem did not rule out this form of consistency
proof, and he tackled this aspect of Hilbert’s thought himself.^24
In 1928, just a few years before Turing struck, Hilbert had put matters like this:^25
The development of mathematical science accordingly takes place in two ways that constantly
alternate: (i) the derivation of new ‘provable’ formulae from the axioms by means of formal
inference; and, (ii) the adjunction of new axioms together with a proof of their consistency.
It is this view of mathematics that explains why Hilbert regarded the decision problem as being
of such supreme importance. For, he announced, also in 1928:^26
Questions of consistency would also be able to be solved by means of the decision process.
For this reason Hilbert called the decision problem ‘the main problem of mathematical logic’.^27
No doubt these stirring words influenced the young Turing in his own decision to take on this
particular problem. He would also have read Hilbert’s 1928 statement that:^28
in the case of the engere Functionenkalkül the discovery of a general decision process forms an as
yet unsolved and difficult problem.