Instructor: Dr. Miklós ERDÉLYI SZABÓ
Text: Herbert Enderton: A Mathematical Introduction to Logic
The unexpected hanging. Truth functions.
Ù, Ú, Ø, ®, «, ½, Å
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.