Instructor: Dr. Miklós ERDÉLYI SZABÓ
Text: Herbert Enderton: A Mathematical Introduction to Logic
First order languages and structures.
Substructures, homomorphisms, products.
Terms, formulas, free variables, closed formulas.
Examples: The Peano axiom system, groups, rings, fields, graphs.
Deduction in first order theories.
Gödel's completeness theorem.
Sizes of models, Löwenheim-Skolem theorem.
Non-standard models of PA.
Classes with no finite axiom system.
Enumerability, decidability, complete theories.
Cantor's theorem on countable dense ordered sets.
Primitive recursive and recursive functions.
Gödel sentences, Tarski's theorem on the undefinability of truth.
Gödel's incompleteness theorems.
Partial and total functions.
Partial recursive functions and recursively enumerable relations.
Universal recursive/partial recursive functions, Kleene's normal form theorem.
The halting problem.
Kleene's parameter theorem.
The weak recursion theorem.