Instructor: Dr. Miklós ERDÉLYI SZABÓ
Text: Herbert Enderton: A Mathematical Introduction to Logic
Prerequisite: ---
Topics covered
The unexpected hanging. Truth functions.
Truth tables.
De Morgan laws and other identities. Complete
systems.
Post-Yablonskii theorem (without proof). Derivations.
Modus Ponens. Logical axioms.
First order languages. Terms, formulas.
The Peano axiom system. Free variables.
Closed formulas. Examples: groups, rings,
fields, graphs.
Prenex norm form. Deduction in
first order theories.
The completeness theorem (without proof).
Compactness theorem.
Categoricity, l-categoricity.
Tarski-Vaught-criterion.
Cantor's theorem on countable dense ordered sets.
Löwenheim-Skolem theorem. Non-standard
models of PA.
Classes with no finite axiom system.
Primitive recursive functions.
The Ackermann function. Partial and total functions.
m-operation.
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 theorem.
An example of an unprovable theorem in PA: the hydra theorem.