Logic and Computability

Go to this course in the University Course Planner.

Description

Mathematical logic is the branch of mathematics that is concerned with the methods of mathematical reasoning, i.e., how we get from our assumptions or axioms to our results or theorems. It is therefore of fundamental importance in mathematics, and it has become even more important because of its applications to computability. Following the discovery of many paradoxes in set theory, Hilbert, in 1900, proposed a program with the aim of proving mathematics was consistent and free from error.

Objective

Content

The culmination of this course is G¿del's Incompleteness Theorem, in which he showed that this was not possible for any mathematical theory that contains arithmetic. Mathematical foundations. Propositional calculus, first order theories, interpretations and models. G¿del's completeness theorem for predicate calculus. Computability: Turing machines, recursive functions and the halting problem. Undecidability of predicate calculus. G¿del's theorem for elementary number theory

Delivery

Assessment

Ongoing assessment 30%, exam 70%.

Graduate attributes

Linkage past

No past linkages have been noted.

Linkage present

No present linkages have been noted.

Linkage future

This course is not recorded as prequisite for other courses.

Restrictions

None.

Recommended text

None.