Mathematical Logic — LOG

Instructor: Dr. Miklós ERDÉLYI SZABÓ

Text: Herbert Enderton: A Mathematical Introduction to Logic

Prerequisite:  ---

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.

Topics covered:

• 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.