Mathematical Logic — LOG

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

Text: Herbert Enderton: A Mathematical Introduction to Logic

Prerequisite:  ---

Topics covered

First order languages and structures.
Substructures, homomorphisms, products.

Terms, formulas, free variables, closed formulas.
Truth definititon.
Examples: The Peano axiom system, groups, rings, fields, graphs.
Deduction in first order theories.
Gödel's completeness theorem.
Compactness theorem.

Sizes of models, Löwenheim-Skolem theorem.
Non-standard models of PA.
Classes with no finite axiom system.
Enumerability, decidability, complete theories.
Categoricity.
Cantor's theorem on countable dense ordered sets.

Primitive recursive and recursive functions.
Church-Turing thesis.
Gödel coding.
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.
Rice's theorem.