B027820 - MATHEMATICAL LOGIC

Italian

Boolean logic. Hilbert's decision problem. Herbrand and Tarski semantics.. Valid deductions. Goedel completeness theorem. Basic notions of cardinal arithmetic. Loewenheim theorem. Compactness of predicate logic with equality. Los-Vaught test. Examples of complete theories: DLO, TFDAG (sketch)
Goedel first incompleteness theorem

D.Mundici, Logic: a Brief Course, Springer, 2012

Other suggested textbooks:

P. Halmos, "Naive set theory", 1960
Notes by prof. A. Berarducci about Goedel incompleteness theorem
Boolos et al. "Computability and logic"
P.Smith "An introduction to Gödel's theorems" (CUP 2013) and the companion notes "Gödel without too many tears" (on his website)

Knowledge acquired: The fundamental theorems of logic
Competence acquired: Formal refutations, Proof procedures in propositional and in first-order logic
Skills acquired (at the end of the course): Ability to write down formal proofs, specifically as graphical objects. Knowledge of Goedel’s completeness, compactness, and incompleteness theorems

Courses to be used as requirements (required and/or recommended)
Courses required: None
Courses recommended: basic knowledge of algebra and of programming

Total hours of the course (including the time spent in attending lectures, seminars, private study, examinations, etc...): 225
Hours reserved to private study and other indivual formative activities: 153
Hours for lectures: 72
Hours for laboratory: 0
Hours for laboratory-field/practice: 0
Seminars (hours): 0
Stages (hours): 0
Intermediate examinations (hours): 0

Attendance of lectures, practice and lab:
Not mandatory

oral examination

* * * Propositional logic

* Syntax and Semantics
Boolean connectives and truth tables
Boolean logic: syntax
Boolean formulae
Non-ambiguity of syntax
Boolean valiation: unique extension to formulae
Tautology, contradiction, satisfiability
Equivalence between formulae
Logical consequence
Propositional theory and its models
Compactness Theorem (both countable and unconuntable case)
Tukey and Zorn's lemma
Application of compactness: coloring a graph
Disjunctive and Conjunctive Normal Forms

* Boolean logic

* * * Predicate Logic

* Formuale
Syntax: terms, atomic formulae, clauses, CNF
Tarski's Semantic: language and models, terms, clauses
Substitution
Sub-formulae
Deductive closure
Equivalent formulae modulo a theory
Expansions and restrictions of a language
Herbrand Universe and resolution
Ground instantiation and its correctness
Basic results on cardinal arithmetic
Cardinality of Herbrand Universe
Axioms for equality and models with equality
Substructures
Gödel Completeness Theorem
Compactness Theorem

Löwenheim-Skolem Theorem

* Examples of theories and structures
Rings, Groups, DLO, ACF

* Complete theories
Definition
Examples of non-complete theories:
Groups, Abelian Groups

* K-categoricity
Test of Los-Vaught
Morley Theorem (statement only)

* Examples of K-categorical theories

* Elementary classes and finitely axiomatizable classes

* Corollaries of Compactness Theorems

* * * Goedel incompleteness theorem

Computability and recursion (sketch)
Arithmetic sets
Recursive sets are arithmetic
Tarski Theorem: truth is not arithmetic
Robinson's Q theory
Representability of sets and functions
Diagonalization Lemma
Goedel's first incompleteness theorem