1.2. Some History 5

three-volume work was an effort to develop all mathematics from a

small common set of axioms, with full rigor at every step. Russell

and Whitehead wanted to remove vagueness and paradox from math-

ematics; every step in their system could be checked mechanically.

It seems this might take all creativity out of mathematics, as all

possible theorems would eventually be produced by the mechanical

application of logical deduction rules to axioms and previously gen-

erated theorems. However, in 1931 G¨ odel showed it was impossible

for such a system to produce all true mathematical statements [30].

He used the mechanical nature of the system, intended for rigor, and

showed it allowed a system of formula encoding that gave access to

self-reference: he produced a formula P that says “P has no proof.”

If P is true, it is unprovable. If the negation of P is true, P has a

proof, since that is the assertion made by P ’s negation. Therefore,

unless Russell and Whitehead’s system is internally inconsistent, P

must be true, and hence unprovable. We will see a proof of G¨odel’s

Incompleteness Theorem via undecidable problems in §5.3.

Principia Mathematica was a grand undertaking and one might

expect it to fail to fulfill all its authors’ hopes. However, Hilbert’s

quest was doomed as well. The proof that there can be no procedure

to determine whether an arbitrary Diophantine equation has integer

roots was not completed until 1973 [61], but in 1936 Church made

the first response suggesting that might be the case [14]. He wrote:

There is a class of problems of elementary number

theory which can be stated in the form that it is

required to find an effectively calculable function f

of n positive integers, such that f(x1,...,xn) = 2

is a necessary and suﬃcient condition for the truth

of a certain proposition of elementary number the-

ory involving x1,...,xn as free variables. [footnote:

The selection of the particular positive integer 2 in-

stead of some other is, of course, accidental and non-

essential.]

... The purpose of the present paper is to propose

a definition of effective calculability which is thought

to correspond satisfactorily to the somewhat vague