### 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.
- Introduction to model theory.

## 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% final exam 10% HW assignements. 5% HW grading.