Course:

M69, Introduction to Mathematical Logic

Instructor:

Jindrich Zapletal

Schedule:

MWF 1:45-2:50

Objective:

As the title of the class suggests, I will go through the bare essentials of mathematical logic and foundations of mathematics. The people leaving the class will understand

  • from set theory: what cardinalities are, that there are different infinite cardinalities and in particular the set of all natural numbers and the set of all real numbers have different cardinality

  • from proof theory: what formal languages, formal theories and formal proofs are, and that arithmetic and set theory can be formalized. I will prove Godel's First Incompleteness Theorem: there are arithmetic statements that cannot be proved or disproved in Peano Arithmetic.

  • from model theory: what models of theories are, and that one theory can have many different models. I will prove Godel's Completeness Theorem: every theory containing no contradictions has a model.

  • from recursion theory: what recursive functions and Turing machines are, and what Church's Thesis means.

Prerequisites:

Everyone familiar with basic notions of abstract mathematics is welcome.

Text:

Herbert Enderton: A Mathematical Introduction to Logic, Academic Press 1972. I will not necessarily follow the book to the letter.

Exams, etc:

Homework assignments every week, one midterm and final. I will emphasize independent work and the final exam.