Diagonalization and Self-Reference

This book presents a systematic, unified treatment of fixed points as they occur in Godel's incompleteness proofs, recursion theory, combinatory logic, semantics, and metamathematics. Packed with instructive problems and solutions, the book offers an excellent introduction to the subject and highlights recent research.

The main purpose of this book is to present a unified treatment of fixed points as they occur in Gödel's incompleteness proofs, recursion theory, combinatory logic, semantics, and metamathematics. The book provides a survey of introductory material and a summary of recent research. The first chapters are of an introductory nature and consist mainly of exercises with solutions given to most of them.

1. - Introduction to self-reference
2. - Some classical fixed point argument compared
3. - How to silence a universale machine
4. - Some general incompleteness theorems
5. - Self-reference in arithmetic
6. - Introduction to formal systems and recursion
7. - A universal system and its applications
8. - Arithmetization of formal systems
9. - Elementary formal systems and incompleteness proofs
10. - Doubly indexed relational systems
11. - Effective representation systems
12. - Sequential systems
13. - Strong fixed point properties
14. - Multiple fixed point properties
15. - Synchronization and pairing functions
16. - Some further relations between fixed point properties
17 - Fixed point properties of combinatory logic
18. - Formal combinatory logic
19. - A second variety of fixed point theorems
20. - Extended sequential systems