Computability and Logic

This course is devoted to understanding the limits of (formalized, or at least formalizable) mathematical proof. As we will see, the subject is closely tied to the foundations of computation and computability. We will therefore spend the first half of the quarter establishing a solid framework for theorizing about the scope and limits of what can, in principle, be computed. We then turn to arithmetic as a canonical case study, working up to the famous incompleteness theorems of K. Gödel. Finally, at the end we will discuss the philosophical repercussions of these results, centering the discussion around a dilemma known as Gödel's disjunction: roughly, either the human mind is somehow non-algorithmic, or there must be mathematical truths that are, in a very strong sense, essentially beyond our ability to ascertain or prove.Prerequisite: 151/251.