MATH63042 - 2012/2013

 

Specification

Aims

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.

Learning Outcomes

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

None.

Syllabus

1. The completeness theorem for the predicate calculus: a review. First order theories. [2 lectures]
2. Recursive functions and relations. Basic properties. Primitive recursion. Closure under bounded quantification. [4]
3. Gödel's β-function. Coding of finite sequences. Recursively enumerable sets and the arithmetic hierarchy. Church's Thesis. [5]
4. 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.  [6]
5. Applications of the incompleteness theorem to show the undecidability of the predicate calculus and other axiom systems.  More about PA. [8]
6. Kleene’s Enumeration Theorem. Hilbert’s 10th problem. The MRDP theorem and its corollaries. [3]
7. Gödel’s second incompleteness theorem.  The philosophical impact of Gödel’s work.  The limitations of the axiomatic method.   [2]

Textbooks

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.

Assessment

Mid-semester coursework: two take home tests weighting 20%

End of semester examination: two and a half hours weighting 80%

to the top