### 2023–24–A

## Prof. Assaf Hasson

## Abstract

- Introduction and historical background: the Hilbert-Witehead program, paradoxes in set theory, independence theorems.
- First order logic: formulas, structures truth value of a formula in a model, calculus with and without equality.
- 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).
- Goedel’s incompleteness theorem: codes, Goedel’s fixed point theorem, Tarski’s theorem on the non-definability of truth.
- Corollaries of incompleteness, as time allows.

## Course topics

- 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.

## Requirements and grading

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).