University of St Andrews

Key information

SCOTCAT credits : 20

ECTS credits : 10

Level : SCQF level 11

Semester: 2

Planned timetable: 9.00 am - 11.00 am Wed

This module begins with elementary aspects of the theory of cardinality, concentrating on equinumerosity and denumerability. The next topic is computability, focusing on two apparently quite different characterisations of this notion: computability by Turing machines and recursive functions. Fairly complete proofs of their equivalence are given. (Ultimately, we need this notion to give exact sense to the notion of a formal system.) This material serves as background to the remainder of the module which establishes the famous limitative results of Gödel (incompleteness of arithmetic), Tarski (non-definability of arithmetic truth), and Church (undecidability of first-order logic). To obtain these results we must show that the recursive functions are representable in a formal theory of the arithmetic of the natural numbers.

Learning and teaching methods and delivery

Weekly contact: 2 hours.

Scheduled learning hours: 0

Guided independent study hours: 0

Assessment pattern

As used by St Andrews: Coursework = 100%

As defined by QAA
Written examinations : 0%
Practical examinations : 0%
Coursework: 0%

Re-assessment: Coursework = 100%

Personnel