Logic

1. Introduction and historical background: the Hilbert-Witehead program, paradoxes in set theory, independence theorems.
2. First order logic: formulas, structures truth value of a formula in a model, calculus with and without equality.
3. Goedel’s Completeness theorem: deduction systems for propositional logic, the completeness theorem for propositional logic and for first order logic. The model existence theorem and the compactness theorem.Applications and corollaries (Upward Lowenheim-Skolem).
4. Goedel’s incompleteness theorem: codes, Goedel’s fixed point theorem, Tarski’s theorem on the non-definability of truth.
5. Corollaries of incompleteness.
6. Introduction to model theory.

• An axiom system for predicate calculus and the completeness theorem.
• Introduction to model theory: The compactness Theorem, Skolem–Löwenheim Theorems, elementary substructures.
• Decidability and undecidability of theories, Gödel first Incompleteness Theorem.

85% final exam 10% HW assignements. 5% HW grading.