Instructor: Dr. Miklós ERDÉLYI SZABÓ
Text: Herbert Enderton: A Mathematical Introduction to Logic
Overview: A model (first order classical logic) of mathematical proofs, structures, truth and their connection. The axiomatic method and its limitations. Finally the connection between logic and computability.
- First order languages. Terms, formulas.
- The Peano axiom system. Free variables.
- Closed formulas. Structures, examples: groups, rings, fields, graphs.
- Truth in structures, logical implication, theories. Valid and satisfiable formulas. Elementary equivalence.
- Definability in a structure, definability of a class of structures. Elementary, axiomatizable and delta-elementary classes.
- Prenex norm form. Deduction in first order theories.
- The connection between truth and provability: Gödel's completeness theorem. Compactness theorem.
- Sizes of models, limitations of the axiomatic method.
- Decidability and enumerability.
- Categoricity. Tarski-Vaught-criterion.
- Cantor's theorem on countable dense ordered sets.
- Löwenheim-Skolem theorem. Non-standard models of Peano Arithmetic.
- Classes with no finite axiom system. Primitive recursive functions.
- The Ackermann function. Partial and total functions. Partial recursive and recursive functions.
- Church-Turing thesis. Universal recursive/partial recursive functions.
- The halting problem. Recursive, recursively enumerable sets.
- There is a nonrecursive, recursively enumerable set.
- Gödel coding. The representation theorem (without proof).
- Gödel's incompleteness theorems.