Lecturer:
Marcus Tressl
School websites of the course:
MATH43042 /
MATH63042
Prerequisites:
This unit requires basic knowledge of Predicate Logic.
Detailed revision notes on Predicate Logic can be found
here
(we will not need Predicate Logic for the first three weeks).
A good
introduction to the topics studied in this course can be found here:
http://plato.stanford.edu/entries/goedel-incompleteness/
Timetable:
Tuesday 9.00-10.00 and Friday 13.00-15.00. Room: Alan Turing G.113
Coursework:
There are two take home tests (one in week 5 and one in week 10), each one weighting 10% in the unit.
Past exam papers can be found
here.
Textbooks:
Independent notes are provided above.
Books and articles:
- [Cutland] Nigel Cutland. Computability. Cambridge University Press, Cambridge, 1980.
An introduction to recursive function theory.
-
[DaPuRo] Martin Davis, Hilary Putnam, and Julia Robinson. The decision
problem for exponential diophantine equations. Ann. of Math. (2), 74:425-436, 1961.
-
[Goedel63] Kurt Gödel. On formally undecidable propositions of Principia Mathematica and
related systems. Translated by B. Meltzer, with an introduction by R. B. Braithwaite.
Basic Books Inc. Publishers, New York, 1963.
-
[Goedel31] Kurt Gödel. Über formal unentscheidbare Sätze der principia mathematica und
verwandter Systeme. I. Monatsh. Math., 149(1):1-30, 2006. Reprinted from Monatsh.
Math. Phys. 38 (1931), 173-198 [MR1549910], With an introduction by Sy David Friedman.
-
[Grzegorczyk] Andrzej Grzegorczyk. Undecidability of some topological theories. Fund. Math.,
38:137-152, 1951.
-
[Matija] Ju. V. Matijasevic. The Diophantineness of enumerable sets. Dokl. Akad. Nauk SSSR,
191:279-282, 1970.
-
[Rautenberg] Wolfgang Rautenberg. A concise introduction to mathematical logic. Universitext.
Springer, New York, second edition, 2006. With a foreword by Lev Beklemishev.
-
[Robinson] Julia Robinson. The undecidability of algebraic rings and fields. Proc. Amer. Math.
Soc., 10:950-957, 1959.
-
[Smullyan] Raymond M. Smullyan. Gödel's incompleteness theorems, volume 19 of Oxford Logic
Guides. The Clarendon Press Oxford University Press, New York, 1992.
-
[Tarski] Alfred Tarski. Undecidable theories. Studies in Logic and the Foundations of
Mathematics. North-Holland Publishing Company, Amsterdam, 1953. In collaboration with
Andrzej Mostowski and Raphael M. Robinson.
-
[PrLog] Marcus Tressl. Predicate Logic. Lecture Notes, 2016.
pdf
-
[Encyclopedia]
http://plato.stanford.edu/entries/goedel-incompleteness/