Computable Structures and the Hyperarithmetical Hierarchy

Front Cover......Page 1
Computable Structures and the Hyperarithmetical Hierarchy......Page 4
Copyright Page......Page 5
Contents......Page 12
0.1 Introduction......Page 6
0.2 Constructivizations......Page 8
0.3 Authorship and acknowledgements......Page 9
1.1 Informal concepts......Page 18
1.2 Church's Thesis......Page 21
1.4 Some basic results......Page 22
1.5 Coding functions......Page 24
1.7 Facts about c.e. sets and relations......Page 25
1.9 The s – m – n Theorem......Page 29
1.10 The Recursion Theorem......Page 30
1.11 Relative computability......Page 31
1.13 Turing reducibility......Page 33
1.14 Other reducibilities......Page 34
2.1 Jumps......Page 38
2.2 Basic definitions......Page 39
2.3 Basic theorems......Page 41
2.4 Combining arithmetical relations......Page 43
2.5 Alternative definitions......Page 44
2.6 Approximations......Page 45
2.7 Trees......Page 47
3.1 Propositional languages and structures......Page 50
3.2 Predicate languages......Page 51
3.3 Structures for a predicate language......Page 53
3.4 Satisfaction......Page 54
3.5 Enlarging a structure......Page 55
3.6 Theories and models......Page 56
3.8 Isomorphism......Page 57
3.9 Quotient structures......Page 58
3.10 Model existence......Page 59
3.11 Compactness......Page 61
3.12 Some special kinds of structures......Page 62
3.13 Computable sets of sentences......Page 66
3.14 Complexity of structures......Page 67
3.15 Complexity of definable relations......Page 68
3.16 Copies of a given structure......Page 70
3.17 Complexity of quotient structures......Page 72
4.1 Set theoretic facts......Page 74
4.2 Inductive proofs and definitions......Page 75
4.3 Operations on ordinals......Page 76
4.5 Constructive and computable ordinals......Page 77
4.6 Kleene’s 0......Page 78
4.7 Constructive and computable ordinals......Page 79
4.8 Transfinite induction on ordinal notation......Page 83
5.1 The hyperarithmetical hierarchy......Page 88
5.2 The analytical hierarchy......Page 92
5.3 The Kleene-Brouwer ordering......Page 99
5.4 Relativizing......Page 101
5.5 Ershov’s hierarchy......Page 103
6.1 Predicate formulas......Page 106
6.2 Sample formulas......Page 107
6.3 Subformulas and free variables......Page 109
6.4 Normalform......Page 110
6.5 Model existence......Page 111
6.6 Scott’s Isomorphism Theorem......Page 113
6.7 Ranks and special Scott families......Page 115
6.8 Rigid structures and defining families......Page 117
6.9 Definability of relations......Page 118
6.10 Propositional formulas......Page 119
7.1 Informal definitions......Page 122
7.2 Formal definition......Page 124
7.3 Sample formulas......Page 125
7.4 Satisfaction and the hyperarithmetical hierarchy......Page 126
7.5 Further hierarchies of computable formulas......Page 127
7.6 Computable propositional formulas......Page 129
7.7 The simplest language......Page 132
7.8 Hyperarithmetical formulas......Page 133
7.9 X-computable formulas......Page 135
8.1 Model existence and paths through trees......Page 138
8.2 The Compactness Theorem......Page 140
8.3 Hyperarithmetical saturation......Page 144
8.4 Orderings and trees......Page 146
8.5 Boolean algebras......Page 148
8.6 Groups......Page 149
8.7 Priority constructions......Page 150
8.8 Ranks......Page 153
9.1 Equivalence structures......Page 154
9.2 Abelian p-groups......Page 156
9.3 Linear orderings......Page 159
9.4 Boolean algebras......Page 167
9.5 Results of Wehner......Page 169
9.6 Decidable homogeneous structures......Page 172
10.1 Images of a relation......Page 176
10.2 Ershov's hierarchy......Page 184
10.3 Images of a pair of relations......Page 186
10.4 Isomorphisms......Page 190
10.6 Sets computable in all copies......Page 194
10.7 Copies of an arbitrary structure......Page 196
11.1 Simple examples......Page 198
11.2 Results of Ash and Nerode......Page 199
11.3 Applications......Page 202
11.4 Expansions......Page 204
11.5 Results of Harizanov......Page 205
11.6 Ershov’s hierarchy......Page 206
11.7 Pairs of relations......Page 209
12.1 Simple examples......Page 214
12.2 Relations between notions......Page 215
12.3 Computable categoricity......Page 216
12.4 Decidable structures......Page 218
12.5 Computable stability......Page 220
12.6 Computable dimension......Page 222
12.7 One or infinitely many......Page 223
12.8 Quotient structures......Page 226
13.1 Introduction......Page 230
13.2 Statement of the metatheorem......Page 231
13.3 Some examples......Page 233
13.4 Proof of the metatheorem......Page 237
13.5 Looking ahead......Page 240
13.6 Michalski’s Theorem......Page 241
14.1 Statement of the metatheorem......Page 244
14.2 Organizing the construction......Page 245
14.3 Derived systems......Page 247
14.4 Simultaneous runs......Page 251
14.5 Special (αn)-systems......Page 253
14.6 Further metatheorems......Page 254
15.1 Standard back-and-forth relations......Page 256
15.2 α-friendly families......Page 258
15.3 Examples......Page 259
15.4 Ranks......Page 264
15.5 Stronger back-and-forth relations......Page 267
15.6 Abstract back-and-forth relations......Page 268
15.7 Open problems......Page 269
16.1 Barker’s Theorems......Page 270
16.2 Davey’s Theorems......Page 276
17.1 Relations between notions......Page 280
17.2 Δ0α stability......Page 281
17.3 Well orderings......Page 285
17.4 Δ0α categoricity......Page 286
17.5 Superatomic Boolean algebras......Page 289
18.1 Simple examples......Page 292
18.2 General results......Page 295
18.3 Results of Feiner and Thurber......Page 298
18.4 Limit structures......Page 301
18.5 Quotient orderings......Page 304
19.1 Scott sets......Page 308
19.2 Enumerations......Page 311
19.3 Structures representing a Scott set......Page 313
19.4 Harrington’s Theorem......Page 322
19.5 Solovay’s Theorems......Page 324
19.6 Sets computable in all models......Page 325
19.7 Open problems......Page 326
A .l Vector spaces......Page 328
A.2 Fields......Page 329
A.3 Orderings......Page 331
A.4 Boolean algebras......Page 332
A.6 Abelian pgroups......Page 334
A.7 Models of arithmetic......Page 335
Bibliography......Page 340
Index......Page 352