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.