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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.