M69, Introduction to Mathematical Logic

Jindrich Zapletal

MWF 1:45-2:50

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.

Everyone familiar with basic notions of abstract mathematics is welcome.

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

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