Entry requirements

Logic MN1 and Algebra MN3 or Algebra DV2.

Aims

The course is intended to give insight into

recursion theory and Gödel's incompleteness

theorems. It

should also give an understanding of the

limitations and expressive power of first-order

theories.

Content

Gödel's incompleteness theorem. Recursion theory:

recursive functions, the second recursion theorem,

universal functions, the S-m-n theorem, Rice's

theorem. Recursively enumerable sets, the

Rice-Shapiro theorem, recursively inseparable

sets, the arithmetical hierarchy.

Relative computability.

Set theory: Well-ordering, ordinals, cardinals,

transfinite induction, the axiom of choice and its equivalents, the

continuum hypothesis.

Model theory: Isomorphism, substructure,

elementary equivalence, elementary substructure,

the compactness theorem, the

Lövenheim-Skolem theorems, categoricity.

Non-standard arithmetic and analysis.

Tennenbaum's theorem.

Instruction

Lectures and problem solving sessions.

Assessment

Written and, possibly, supplementary oral

examination at the end of the course. Moreover,

compulsory assignments may be given during the

course.