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 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 sufficient 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
Previous Page Next Page