M. Curzio, P. Longobardi, M. Maj "Lezioni di algebra" (cap. 1)
Learning Objectives
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): Exit from logic analphabetism which is so common among mathematicians. Ability to write down formal proofs, specifically as graphical objects. Knowledge of Goedel’s completeness and compactness theorem in first order logic with equality
Prerequisites
Courses to be used as requirements (required and/or recommended)
Courses required: None
Courses recommended: None
Teaching Methods
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
Further information
Attendance of lectures, practice and lab:
Not mandatory
Type of Assessment
oral examination
Course program
* * * 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
Tautologu, 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 and resolution
Clauses and and formulae as sets
Resolution
Davis-Putnam Procedure (DPP)
Robinson's completeness theorem
Refutation
* Fast classes for DPP
Krom clauses
Horn clauses
* * * Predicate Logic
* Quantifier-free formuale
Syntax: terms, atomic formulae, clauses, CNF
Tarski's Semantic: language and models, terms, clauses
Substitution
Herbrand Universe and resolution
Ground instantiation and its correctness
Refutation
Basic results on cardinal arithmetic
Cardinality of Herbrand Universe
Completeness Theorem for quantifier-free formulae
Compactness Theorem
Axioms for equality and models with equality
Substructures
* First-order Logic
Syntax and Semantics
Prenex Normal Form
Sub-formulae
Deductive closure
Equivalent formulae modulo a theory
Expansions and restrictions of a language
Skolemization
Gödel Completeness Theorem
Compactness Theorem
Cardinality of Skolemization
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
DLO+
Cantor's Theorem (omega-categoricity of DLO+)
Operations on linear orders: sum, products
DLO+ is not K-categorical for K uncountable
Pure sets
DTFAG and vector spaces over Q
Z with successor function; study of orbits
* Elementary classes and finitely axiomatizable classes
* Corollaries of Compactness Theorems
{Char 0 fields} is not finitely axiomatizable
Theories with finite models of arbitrarily large cardinality
Erdös-Bruijin Theorem
Robinson's Principle