Incompleteness and Undecidability
PHIL 470, University of Maryland
This course is focused on two fundamental theorems of Kurt Godel: The incompleteness theorems. The first theorem states, roughly, that every formal mathematical theory, provided it is sufficiently expressive and free from contradictions, is incomplete in the sense that there are always statements (in fact, true statements) in the language of the theory which the theory cannot prove. The second incompleteness theorem states that sufficiently expressive arithmetic theories cannot prove their own consistency. We will prove the 1st and 2nd Incompleteness Theorems and survey their technical and philosophical repercussions. Topics to be covered include: formal models of computation (especially elementary recursion theory); Church-Turing Thesis; Godel’s 1st and 2nd incompleteness theorems and their repercussions; Tarski’s proof of the undefinability of truth; Undecidability of the Halting Problem; Decidable subsystems of arithmetic; provability logic (Kripke soundness and completeness, arithmetical soundness and completeness, fixed-point theorems); absolute provability; and The Knower Paradox (and epistemic arithmetic).
Pervious Versions: Spring 2022Spring 2019Spring 2017Spring 2015Spring 2013