Created by:

Profile Photo

Last updated:

December 7, 2022


Unlimited Duration


This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration


This course begins with an introduction to the theory of computability, then proceeds to a detailed study of its most illustrious result:

Kurt Gödel’s theorem that, for any system of true arithmetical statements we might propose as an axiomatic basis for proving truths of arithmetic, there will be some arithmetical statements that we can recognize as true even though they don’t follow from the system of axioms. In my opinion, which is widely shared, this is the most important single result in the entire history of logic, important not only on its own right but for the many applications of the technique by which it’s proved. We’ll discuss some of these applications, among them: Church’s theorem that there is no algorithm for deciding when a formula is valid in the predicate calculus; Tarski’s theorem that the set of true sentence of a language isn’t definable within that language; and Gödel’s second incompleteness theorem, which says that no consistent system of axioms can prove its own consistency.

Course Curriculum

  • Why Study Computability? Unlimited
  • Key Computability Concepts Unlimited
  • The Language of Arithmetic Unlimited
  • Church-Turing Thesis Unlimited
  • Nonstandard Models of Arithmetic Unlimited
  • Gödel Numbering Unlimited
  • Robinson’s Arithmetic Unlimited
  • Coding Proofs Unlimited
  • Peano Arithmetic Unlimited
  • Self-Reference Lemma Unlimited
  • First Incompleteness Theorem Unlimited
  • Interpretations Unlimited
  • Tarski’s Theory of Truth Unlimited
  • Second Incompleteness Theorem Unlimited
  • Introduction to Modal Logic Unlimited
  • Provability Logic Unlimited
  • Defining Exponentiation Unlimited

About the instructor

5 5

Instructor Rating







Profile Photo
Massachusetts Institute of Technology