6
None.
MAT/01 Mathematical Logic.
Oral exam.
The course aims to provide some of the tools of mathematical logic, in particular model-theoretic methods, for the analysis of first-order structures. It also includes an introduction to the fundamental notions of computability theory in order to illustrate Gödel’s incompleteness theorems.
Natural deduction for propositional calculus, soundness and completeness. Compactness theorem with an application to graph theory. First-order languages and structures. Satisfiability and the coincidence theorem. Formulas true in a structure, satisfiable formulas, logically valid formulas and logically equivalent formulas. Logical consequence. Homomorphisms, monomorphisms and isomorphisms between structures. Definable sets in a structure. Isomorphisms and definable sets. Comparison between structures: elementarily equivalent structures and isomorphic structures. Elementary substructure. Tarski-Vaught test and application to the ordered structures of the rationals and the reals. Natural deduction for predicate calculus: completeness theorem. Compactness theorem and some applications: the Löwenheim-Skolem theorems, non-standard models of the naturals and the reals, non-axiomatisability of certain classes of structures. k-categorical theories and examples: dense linear orders without maximum and minimum, divisible torsion-free abelian groups. Vaught’s theorem on the completeness of a k-categorical theory. Decidable theories.
Computability: primitive recursive functions, the Ackermann function and partial recursive functions. Church’s thesis. Turing machines and Turing’s thesis. Recursive sets and recursively enumerable sets. Universal Turing machine. The halting problem and other undecidable problems. Peano arithmetic and outline of Gödel’s incompleteness theorems.
By the end of the course, students must demonstrate that they
Command of the knowledge acquired, clarity of presentation, rigour in the use of language, confidence in using the notions acquired.
