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, as time allows.

• 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% Take home exam. 10% HW assignments. 5% HW grading (if no grader is found, In case a grader is found these 5% will be added to the take home exam).