Diagonalization and Self-Reference

Preface......Page 4
Contents......Page 8
1 Introduction to self-reference......Page 20
§1 Use and mention......Page 21
§2 Self-reference using diagonalization......Page 22
§3 Normalization......Page 23
§4 One-sided quotation......Page 26
§5 Cross-reference using one-sided quotation......Page 28
§6 Some general principles concerning designational systems......Page 31
§7 A pseudo-quotational system......Page 33
§8 Some other methods of self-reference......Page 34
§9 A more general setting......Page 35
§10 Applications to quotational systems......Page 36
§11 Near Diagonalization......Page 37
§12 Cross-reference......Page 38
§13 Application to one-sided quotational systems......Page 39
§1 An argument from combinatory logic......Page 44
§2 Godel sentences......Page 45
§3 An argument from recursion theory......Page 46
§4 Another argument from recursion theory......Page 47
§5 Self-reproducing machines......Page 48
§6 A relational fixed point theorem......Page 50
§7 Some stronger results......Page 53
§1 A universal machine......Page 58
Part II Some related problems......Page 62
Part III Solutions to problems......Page 63
4 Some general incompletenesstheorems......Page 67
§1 Diagonalization......Page 69
§2 An incompleteness argument using a truth set......Page 71
§3 Godel\'s argument and some variations......Page 75
§4 Rosser\'s argument......Page 78
§5 Complete representability and definability......Page 82
§6 Admissible functions......Page 86
§7 Kleene\'s symmetric incompleteness theorem generalized......Page 87
§8 Provability by stages......Page 88
§1 Normalization in arithmetic......Page 94
§2 Tarski\'s method of achieving self-reference......Page 100
§3 The more general situation......Page 103
§4 Near normalization......Page 104
§5 Situation in Polish notation......Page 106
§6 More on quotational systems......Page 107
§7 Some variants......Page 109
§8 Godelizing operations......Page 110
§9 Generalized diagonalization......Page 112
§1 Elementary formal systems......Page 116
§2 Some basic closure properties......Page 124
§3 Solvability over K......Page 129
§4 Recursively enumerable relations......Page 132
§5 Recursive functions......Page 137
§6 Finite quantifications and constructive definability......Page 141
§7 Recursive pairing functions......Page 145
§8 Dyadic Godel numbering......Page 148
§9 Lexicographical Godel numbering and n-adic notation......Page 151
§1 The universal system (U)......Page 154
§2 The recursive unsolvability of (U)......Page 158
§3 The enumeration theorem......Page 160
§4 Iteration theorem......Page 163
Part I Arithmetization of elementaryformal systems......Page 168
§1 Some facts about Eo-relations......Page 169
§2 Arithmetization of elementary formal systems......Page 173
§3 Some applications......Page 175
§4 All r.e. relations are E,......Page 178
*§5 More on arithmetization (optional)......Page 180
9 Elementary formal systems andincompleteness proofs......Page 184
§1 The non-formalizability of arithmetic truth......Page 185
§2 Peano arithmetic......Page 188
§3 Peano arithmetic is a formal system......Page 189
§4 The Godel and Rosser proofs......Page 193
§0 Definitions......Page 195
§1 Universal sets......Page 197
§2 Generative sets......Page 198
§3 Double enumeration and double universality......Page 201
§4 Doubly generative pairs......Page 206
§5 Semi-D.G. pairs......Page 209
§6 Closing the circle......Page 214
§7 Summary of main results......Page 217
Part I Effective representation......Page 219
§1 Undecidability......Page 220
§2 Generative systems......Page 223
§3 Doubly generative systems......Page 224
§4 Rosser systems......Page 226
§5 Extensions......Page 229
§6 Exact Rosser systems......Page 231
§7 Variations on a theme by Shepherdson......Page 233
§8 Effective Rosser systems......Page 238
§10 Unconquerable systems and omniscient functions......Page 242
Part I Definitions and purpose......Page 247
§1 Types 0,1,2......Page 252
§2 The weak fixed point property......Page 255
§3 Universal systems and the weak Kleene property......Page 258
§4 Integrated systems......Page 260
Part IV Summary and applications......Page 261
§1 The recursion property......Page 264
§2 A type 2 approach......Page 268
§3 The extended recursion property......Page 270
Part II The Myhill property and relatedproperties......Page 271
§4 Strongly connected systems......Page 272
§5 The Myhill and recursion properties compared......Page 274
§6 Very strong connectivity......Page 275
§7 Universal integrated systems......Page 276
§8 The strong Kleene property......Page 277
Part III Summary and applications......Page 278
I Indexed relational systems......Page 279
II Sentential systems......Page 280
III Applicative systems......Page 281
§1. The weak double fixed point property......Page 282
§2 Double recursion......Page 286
§3 A type 2 approach......Page 288
§4 The double Myhill property......Page 292
§5 The properties DMk......Page 296
§7 Integrated systems of type 1......Page 297
§8 Symmetric functions......Page 298
§10 Universal systems of type 2......Page 302
§11 Multiple fixed point properties......Page 303
§0 Synchronized sequences of functions......Page 305
§1 Synchronized fixed point theorems......Page 307
§2 Relation to multiple fixed point properties......Page 309
Part II Pairing functions......Page 311
§3 Exact and quasi-exact functions......Page 312
§4 Some consequences......Page 315
§5 Strongly connected systems of type 1*......Page 316
§6 The property DR*......Page 318
§7 The property DM*......Page 320
§8 Integrated systems of type I*......Page 321
§1 Recursion and double fixed points......Page 323
§2 Recursion and double recursion......Page 325
§3 Systems of type 1*......Page 326
§4 Myhill and double Myhill properties......Page 327
§5 Bar fixed points......Page 328
§6 Further topics......Page 330
Part I Interdefinability of somecombinators......Page 334
§1 The combinator B......Page 335
§2 We add T......Page 336
§3 We add M......Page 339
§4 Two special combinators......Page 343
§5 The combinator I......Page 344
§7 Some curiosities......Page 345
§8 We now consider K......Page 346
§10 Some sufficient conditions......Page 348
§12 A fixed point principle......Page 349
§13 Some fixed point combinatorsProblem 13......Page 350
§15 Some special properties of 0......Page 352
§16 Sages from B and W......Page 353
§17 n-sages......Page 354
§19 The cross-point property......Page 355
§20 The weak double fixed point property......Page 356
§21 The property DM......Page 357
§22 Nice combinators and symmetric combinators......Page 358
§1 Formal combinatory logic......Page 376
§2 Consistency and models......Page 379
Appendix on CL1......Page 380
§1 Admissible name functions......Page 385
Pre-admissible mappings......Page 386
More on admissibility......Page 387
Full admissibility......Page 388
More on pre-admissibility......Page 389
*§2 Admissible maps via numeral systems......Page 390
§3 The second fixed point theorem......Page 392
§4 Applications......Page 393
§5 Other fixed point theorems of the second variety......Page 397
20 Extended sequential systems......Page 399
§0 M-diagonalizers......Page 400
§1 M-fixed points......Page 401
§2 The double M-fixed point theorem......Page 402
§3 Strong M-fixed point properties......Page 403
§4 Uniform double M-fixed point properties......Page 406
§5 M-nice and M-symmetric functions......Page 407
References......Page 408
Index......Page 411