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