Computability and Logic

Catalog description

Kurt Goedel's ground-breaking Incompleteness Theorems demonstrate fundamental limits on formal mathematical reasoning. In particular, the First Incompleteness Theorem says, roughly, that for any reasonable theory of the natural numbers there are statements in the language that are neither provable nor refutable in that theory. In this course, we will explore the expressive power of different axiomatizations of number theory, on our path to proving the Incompleteness Theorems. This study entails an exploration of models of computation, and the power and limitations of what is computable, leading to an introduction to elementary recursion theory. At the conclusion of the course, we will discuss technical and philosophical repercussions of these results. Prerequisite: 151/251.