Provability, Mechanism, and the Diagonal Problem
Graham Leach-Krouse · Oxford University Press eBooks · 2016
The primary goal in this chapter is to understand and to make a start at evaluating Gödel and Post’s conceptions of absolute provability. The starting point will be Gödel’s famous assertion from the 1951 Gibbs lecture that either (a) there exist absolutely undecidable mathematical propositions or (b) the process of human mathematical reasoning cannot be fully imitated by any machine. Interestingly, in 1921 Post independently arrived at an equivalent conclusion. But while Gödel, at least in private, seems to have hoped to refute (a) and establish (b), Post, on the basis of a rejection of (b), apparently hoped to prove (a). This situation raises at least two interesting questions. First: why did Gödel take the side he did and Post the opposite? Second: given such a dramatic divergence on an apparently basic question, is it clear that we even have a disagreement here? How do we know that Post and Gödel were talking about the same sense of absolute provability? This chapter addresses these questions.