This volume is a collection of written versions of the talks given at the Workshop on Computational Prospects of Infinity, held at the Institute for Mathematical Sciences from 18 June to 15 August 2005. It consists of contributions from many of the leading experts in recursion theory (computability theory) and set theory. Topics covered include the structure theory of various notions of degrees of unsolvability, algorithmic randomness, reverse mathematics, forcing, large cardinals and inner model theory, and many others. Contents: Prompt Simplicity, Array Computability and Cupping (R Downey et al.); A Simpler Short Extenders Forcing Gap 3 (M Gitik); The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs (D R Hirschfeldt et al.); Absoluteness for Universally Baire Sets and the Uncountable II (I Farah et al.); Modaic Definability of Ordinals (I Neeman); Eliminating Concepts (A Nies); Rigidity and Biinterpretability in the Hyperdegrees (R A Shore); Some Fundamentals Issues Concerning Degrees or Unsolvability (S G Simpson); A tt Version of the Posner Robinson Theorem (W H Woodin); and other papers.
Author(s): Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin, Yue Yang
Year: 2008
Language: English
Pages: 432
CONTENTS......Page 6
Foreword......Page 8
Preface......Page 10
1. Introduction......Page 12
2. The technical theorem and some intuition for its proof......Page 14
2.2.2. Measuring whether the equations hold: σ1(X, Y,Λa,x,Λa,y,Λxy,a)......Page 15
2.2.4. Making C the infimum of CD and CE: s3(X, Y,.a,x,.a,y,.xy,a,.cd,.ce)......Page 17
2.2.6. If Θby(BY ) = A then y,a(Y ) = A: σ6(X, Y,Λa,x,Λa,y,Λxy,a,Θby)......Page 19
2.2.7. One sequence (X, Y,Λa,x,Λa,y,Λxy,a)......Page 23
3.2. The tree of strategies......Page 24
3.2.1. η-con.gurations......Page 27
3.3.2. Adding a σ1(X, Y,Λa,x,Λa,y,Λxy,a)......Page 28
3.3.3. Adding a σ2(X, Y,Λa,x,Λa,y,Λxy,a)......Page 29
3.3.6. Adding a σ6(X, Y,Λa,x,Λa,y,Λxy,a,Θby)......Page 30
3.4. Analyzing the construction......Page 31
References......Page 32
1. Main starting questions and some pieces of notation......Page 34
2. Results not mentioning forcing axioms......Page 36
3. Results mentioning strong forcing axioms......Page 49
4. Open questions and some consequences of large cardinal axioms......Page 52
References......Page 57
1. Introduction......Page 58
2. BE 02 models......Page 60
References......Page 67
Prompt Simplicity, Array Computability and Cupping Rod Downey, Noam Greenberg, Joseph S. Miller and Rebecca Weber......Page 70
1. Introduction......Page 71
2. PS AC cuppable......Page 74
2.1. Construction......Page 75
2.2. Veri cations......Page 76
3.1. The strategy......Page 79
3.2. Construction......Page 81
3.3. Veri cation......Page 83
References......Page 87
Lowness for Computable Machines Rod Downey, Noam Greenberg, Nenad Mihailovi c and Andr e Nies......Page 90
1. Introduction......Page 91
2. The Proof......Page 94
References......Page 96
1. The Preparation Forcing......Page 98
2. Types of Models......Page 106
3. The Main Forcing......Page 108
Acknowledgment......Page 139
References......Page 140
1. Introduction......Page 142
2. 0 -dimension......Page 146
3. The measure of the low sets......Page 149
Acknowledgments......Page 150
References......Page 151
The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Bj rn Kjos-Hanssen, Ste en Lempp and Theodore A. Slaman......Page 154
1. Introduction......Page 155
2.1. The argument for w-models......Page 158
2.2. The proof-theoretic argument......Page 159
3. COH does not imply DNR......Page 161
4. Degrees of homogeneous sets for stable colorings......Page 163
References......Page 171
Absoluteness for Universally Baire Sets and the Uncountable II Ilijas Farah, Richard Ketchersid, Paul Larson and Menachem Magidor......Page 174
1. Magidor-Malitz logic......Page 176
1.1. Proofs......Page 178
1.2. First proof of Theorem 1.7......Page 179
1.3. Second proof of Theorem 1.7......Page 183
1.4. Proof of Theorem 1.3......Page 187
2.1. Partitions of [k] < for k > 1......Page 188
2.2. [ 1]n vs. [ 1] <......Page 189
3. Extensions of the -absoluteness argument......Page 191
3.1. The setup......Page 192
3.2. Trees of models......Page 198
4. Special trees on reals......Page 199
References......Page 201
Monadic Definability of Ordinals Itay Neeman......Page 204
1. Preliminaries......Page 205
2. Definability, forward......Page 210
3. Definability, backward......Page 212
4. Parameters......Page 214
References......Page 216
1. Introduction......Page 218
2. Overview of the construction......Page 222
3. Strategy of a single requirement......Page 223
4. Interaction of strategies......Page 224
5. Priority tree layout......Page 225
6. The construction......Page 227
7. Verification......Page 230
References......Page 233
1. Outline of the results......Page 236
2.1. Three classes......Page 237
2.2. The existence and equivalence theorems......Page 239
2.3. Lowness for other randomness notions......Page 242
3.1. Brief introduction to K-triviality......Page 245
3.2. Constructions......Page 246
3.3. A is K-trivial iff A is low for K......Page 248
3.4. Further applications of the golden run method......Page 252
5.1. ML-coverable and ML-noncuppable sets......Page 253
5.2. A common subclass......Page 254
References......Page 257
1. Introduction......Page 260
2. Effective Dimension......Page 262
2.1. Effective Dimension of cones and degrees......Page 264
3. The Main Result......Page 265
4. Concluding Remarks......Page 269
References......Page 270
1. Introduction......Page 272
2. The main result......Page 274
3. Three notes......Page 277
References......Page 280
1. Introduction......Page 282
2. Preliminaries......Page 284
3. Diamonds on sets of countable cofinality......Page 288
4. The principle of Stationary -Reection......Page 290
5. Diamonds on sets of cofinality......Page 299
6. Appendix......Page 305
References......Page 308
1. Introduction......Page 310
2. Rigidity......Page 312
3. Coding......Page 313
4. Embedding lattices......Page 314
5. Biinterpretability......Page 318
References......Page 322
1. Preface......Page 324
2. Motivation......Page 325
4. Mass problems and weak degrees (rigorous definition)......Page 326
6. The lattice Pw (rigorous definition)......Page 327
7. Embedding RT into Pw......Page 329
8. Structural properties of Pw......Page 330
10. Some specific, natural degrees in Pw......Page 331
12. Proof of the Embedding Lemma......Page 333
13. Some additional, specific degrees in Pw......Page 334
14. Positive-measure domination......Page 336
15. Some further specific, natural degrees in Pw......Page 337
16. Response to Issue 2......Page 338
References......Page 340
1. Introduction......Page 344
2. Preliminaries......Page 0
2. 2-Det and 11-ID......Page 345
3. Finite levels......Page 349
4. Trans nite levels......Page 356
References......Page 363
1. Introduction......Page 366
2. Preliminaries......Page 368
3. The main theorem......Page 379
4. Further results......Page 384
References......Page 403
1. Introduction......Page 404
2. Cuppable degrees and plus-cupping......Page 406
3. Noncuppable degrees and anti-cupping property......Page 409
4. Slaman triples, cappable degrees and minimal pairs......Page 413
5. Ideals M and NCup and quotient structures......Page 417
6. Arslanov's cupping theorem and diamond embeddings......Page 418
7. Isolation and intervals of d.c.e. degrees......Page 421
8. Maximal degrees and almost universal cupping......Page 422
9. Cupping in the -c.e. degrees......Page 425
References......Page 427
