Advanced Mathematical Logic: Syllabus & Learning outcomes

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.