MATH43042 - 2010/2011
- Title: Gödel's Incompleteness Theorems
- Unit code: MATH43042
- Credits: 15
- Prerequisites: MATH43001 Predicate Logic or a familiarity with the predicate calculus up to and including the completeness theorem (such as can be gained e.g. from Enderton's book below).
- Co-requisite units: None
- School responsible: Mathematics
- Members of staff responsible:
To introduce the student to Gödel's two incompleteness theorems and to their most important corollaries.
Brief Description of the unit
Can a computer be programmed to generate all true statements of mathematics and no false ones? An extraordinary result, proved by Kurt Gödel in 1931, shows that even if we restrict ourselves to the most fundamental part of mathematics, namely statements about the natural numbers, the answer to the above question is no. Moreover Gödel’s method is such that given any “mechanical procedure” for generating true statements about the natural numbers we are actually able to construct a true statement about the natural numbers which will not be generated by that procedure. Later results have shown that such statements can always be chosen to have the simple logical form of an assertion that a particular polynomial equation has no solution over the integers.
Gödel’s work stands as one of the great landmarks of 20th century thought and has a significance which reaches well beyond mathematics. The course unit will be centred on proofs of Gödel’s two incompleteness theorems and will examine some of their principal applications.
On successful completion of this course unit students will
- be familiar with the notion of recursive function;
- have developed a facility in the manipulation and application of these functions, with particular emphasis on applications to logic and decision problems.
Future topics requiring this course unit
- The completeness theorem for the predicate calculus: a review. First order theories. [2 lectures]
- Recursive functions and relations. Basic properties. Primitive recursion. Closure under bounded quantification. 
- Gödel's β-function. Coding of finite sequences. Recursively enumerable sets and the arithmetic hierarchy. Church's Thesis. 
- Formal arithmetic. The systems S and PA. Representability. Gödel numbering and the arithmetization of logic. The recursiveness of the proof predicate. Gödel’s first incompleteness theorem. Tarski’s undefinability theorem. 
- Applications of the incompleteness theorem to show the undecidability of the predicate calculus and other axiom systems. More about PA. 
- Kleene’s Enumeration Theorem. Hilbert’s 10th problem. The MRDP theorem and its corollaries. 
- Gödel’s second incompleteness theorem. The philosophical impact of Gödel’s work. The limitations of the axiomatic method. 
There is no set textbook covering all the material in the module, although the first two books listed below cover much of it, albeit using different notation. Full lecture notes are provided online on the lecturer’s website.
- H.B. Enderton, A Mathematical Introduction to Logic, (especially chapter 3), Academic Press,
- J.R. Shoenfield, Mathematical Logic, (chapters 4 and 6). Addison-Wesley 1967,
- Peter Smith, An Introduction to Gödel's Theorems, Cambridge University Press, 2007,
- Hao Wang, A Logical Journey, MIT Press, 1997,
- Hao Wang, From Mathematics to Philosophy. RKP 1974,
- G.T. Kneebone, Mathematical Logic and the Foundations of Mathematics. Van Nostrand 1963.
Teaching and learning methods
24 lectures, 8 examples classes and assigned reading. In addition students should expect to do at least seven hours private study each week for this course unit.
- Mid-semester coursework: two take home tests weighting 20%
- End of semester examination: two and a half hours weighting 80%
Timing of the course
The classes will take place in the eight weeks prior to the Easter vacation. The examination will take place soon after the Easter vacation and before the normal examination period.