HISTORICAL BACKGROUND:
Cantor, Frege and the paradoxes. Solutions to the problem of paradoxes. Hilbert and formalism,
Brouwer and intuitionism. Hilbert's Programme. Completeness, incompleteness,
and Godel's Theorem.
REVISION OF FIRST-ORDER LOGIC:
The rst-order language L; formulas and sentences; the axiomatisation K for predicate
calculus; proofs, deductions, theorems; the Deduction Theorem; Godel's Completeness
Theorem for K; Lowenheim-Skolem Theorem and the Compactness Theorem.
FIRST-ORDER PEANO ARITHMETIC:
The language and special axioms of PA; proofs in PA; models of PA; non-standard
models.
REPRESENTABILITY IN PA:
Examples of number-theoretic functions and relations; representability and functionally
represents.
THE RECURSIVE FUNCTIONS:
Primitive recursive functions; the -operator; partial recursive functions. Church's Thesis.
Recursive relations.
REPRESENTABILITY OF RECURSIVE FUNCTIONS:
An outline proof that all recursive functions and relations are representable in PA. The
representability of all computable functions, relations and sets.
ARITHMETISING ARITHMETIC:
Godel numbers. Important number theoretic relations expressing aspects of PA, and their
recursiveness. Recursive/computable axiomatisability.
COMPUTABLY ENUMERABLE SETS AND MANY-ONE REDUCIBILITY:
Computably enumerable (c.e.) and many-one reducibility; a computably axiomatisable
theory has a c.e. set of theorems. Consistency and !-consistency. Semi-representability.
A set is c.e. i
semi-representable in PA, i
many-one reducible to the set of theorems of
PA. Enumeration theorem for c.e. sets. A c.e. set K which is not computable.
GODEL'S INCOMPLETENESS THEOREM:
Completeness of a theory; using representability of K to prove incompleteness of a theory;
incompleteness of PA. Extensions of a theory. Godel's First and Second Incompleteness
Theorems.
UNDECIDABILITY AND CREATIVE SETS:
Decidability of a theory. Creative sets. The creativeness of PA.
CHURCH'S THEOREM:
Raphael Robinson's nite axiomatisation of rst-order arithmetic. Church's Theorem and
the undecidability of logical validity. The creativeness of K.
MORE ON LOGIC AND COMPUTABILITY:
We will look further at logic as a branch of computability theory, dealing with Turing machines
and Turing's notion of oracle machine. Further topics from: Relative computability
and degree structures; Computably enumerable sets; Arithmetical hierarchy and forcing
in computability theory.