Diagonalization and Self-Reference - Raymond M. Smullyan
<p class=default>
<b>Diagonalization and Self-Reference</b>
</p><p>
<b>Raymond M. Smullyan</b>
</p><p>
<b>CONTENTS</b>
<br/>
<b>PART I: Introduction to Self-Reference and Recursion</b>
<br/>
1. Introduction to Self-Reference
<br/>
1.1. Quotation and Self-Reference
<br/>
1.2. Self-Reference in a More General Setting
<br/>
2. Some Classical Fixed Point Arguments Compared
<br/>
2.1. Five fixed Point Arguments
<br/>
2.2. A Unification
<br/>
2.3. Quasi-Diagonalization
<br/>
3. How to Silence a Universal Machine
<br/>
3.1. Silencing a Universal Machine
<br/>
3.2. Some Related Problems
<br/>
3.3. Solutions to Problems
<br/>
4. Some General Incompleteness Theorems
<br/>
4.1. Incompleteness
<br/>
4.2. Provability by Stages
<br/>
5. Self-Reference in Arithmetic
<br/>
5.1. Normalization and Tarskification
<br/>
5.2. Some Special Devices
<br/>
5.3. Generalizations
<br/>
6. Introduction to Formal Systems and Recursion
<br/>
6.1. Formal Representability
<br/>
6.2. Recursive Enumerability
<br/>
7. A Universal System and Its Applications
<br/>
7.1. A Universal System
<br/>
7.2. Enumeration and Iteration Theorems
<br/>
<b>PART II: Systems with Effective Properties</b>
<br/>
8. Arithmetization of Formal Systems
<br/>
8.1. Arithmetization of Elementary Formal Systems
<br/>
8.2. Double Enumeration
<br/>
8.3. More on Arithmetization
<br/>
9. Elementary Formal Systems and Incompleteness Proofs
<br/>
9.1. Truth in Lo Cannot be Formalized
<br/>
9.2. A Concrete Incompleteness Proof
<br/>
10. Double Indexed Relational Systems
<br/>
10.1. Indexed Relational Systems
<br/>
10.2. Double Indexing
<br/>
11. Effective Representation Systems
<br/>
11.1. Effective Representation
<br/>
11.2. Exact and Effective Rosser Systems
<br/>
<b>PART III: Fixed Point Theorems in General Setting</b>
<br/>
12. Sequential Systems
<br/>
12.1. Definitions and Purpose
<br/>
12.2. Preliminary Definitions
<br/>
12.3. Some Fixed Point Properties
<br/>
12.4. Summary and Applications
<br/>
13. Strong Fixed Point Properties
<br/>
13.1. The Recursion and Extended Recursion Properties
<br/>
13.2. The Myhill Property and Related Properties
<br/>
13.3. Summary and Applications
<br/>
14. Multiple and Fixed Point Properties
<br/>
14.1. Double Fixed Points
<br/>
14.2. Double Recursion Properties
<br/>
14.3. Double Myhill Properties and Related Results
<br/>
14.4. Symmetric Functions and Nice Functions
<br/>
15. Synchronization and Pairing Functions
<br/>
15.1. Synchronized Fixed Point Properties
<br/>
15.2. Pairing Functions
<br/>
15.3. Synchronized Recursion Resumed
<br/>
16. Some Further Relations Between Fixed Point Properties
<br/>
16.1. Single and Double Fixed Point Properties Compared
<br/>
16.2. More on Systems of Type 1*
<br/>
<b>PART IV: Combinators and Sequential Systems</b>
<br/>
17. Fixed Point Properties of Combinatory Logic
<br/>
17.1. Interdefinability of Some Combinators
<br/>
17.2. Fixed Points
<br/>
17.3. Multiple Fixed Points
<br/>
18. Formal Combinatory Logic
<br/>
18.1 The Axiom Systems CL and CLo.
<br/>
19. A Second Variety of Fixed Point Theorems
<br/>
19.1. Self-Reference in CLo
<br/>
19.2. Fixed Point Theorems of the Second Type
<br/>
20. Extended Sequential Systems
<br/>
</p>