Computational prospects of infinity [Workshop on Computational Prospects of Infinity held at the Institute for Mathematical Sciences, National University of Singapore, from 20 June to 15 August 2005] 2 Presented talks : [Workshop on Computational Prospect

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 Title 4 Copyright 5 Contents 6 Foreword 8 Preface 10 Generating Sets for the Recursively Enumerable Turing Degrees / Klaus Ambos-Spies, Steffen Lempp and Theodore A. Slaman 12 1. Introduction 12 2. The technical theorem and some intuition for its proof 14 2.1. Requirements and simple strategies 15 2.2. Strategies 15 2.2.1. Making Θ = A: σ0(Θ) 15 2.2.2. Measuring whether the equations hold: σ1(X, Y,Λa,x,Λa,y,Λxy,a) 15 2.2.3. Computations between B, C, and X: σ2(X, Y,Λa,x,Λa,y,Λxy,a) 17 2.2.4. Making C the infimum of CD and CE: s3(X, Y,.a,x,.a,y,.xy,a,.cd,.ce) 17 2.2.5. Making Θa(A) = D and Θa(A) = E: σ4(X, Y,Λa,x,Λa,y,Λxy,a,Θa) and σ5(X, Y,Λa,x,Λa,y,Λxy,a,Θa) 19 2.2.6. If Θby(BY ) = A then y,a(Y ) = A: σ6(X, Y,Λa,x,Λa,y,Λxy,a,Θby) 19 2.2.7. One sequence (X, Y,Λa,x,Λa,y,Λxy,a) 23 3. The global construction 24 3.1. Interactions between σ-strategies 24 3.2. The tree of strategies 24 3.2.1. η-con.gurations 27 3.3. The construction 28 3.3.1. Adding an A-diagonalization strategy σ0 28 3.3.2. Adding a σ1(X, Y,Λa,x,Λa,y,Λxy,a) 28 3.3.3. Adding a σ2(X, Y,Λa,x,Λa,y,Λxy,a) 29 3.3.4. Adding a σ3(X, Y,Λa,x,Λa,y,Λxy,a,Ψcd,Ψce) 30 3.3.5. Adding a σ4(X, Y,Λa,x,Λa,y,Λxy,a,Θa) or a σ5(X, Y,Λa,x,Λa,y,Λxy,a,Θa) 30 3.3.6. Adding a σ6(X, Y,Λa,x,Λa,y,Λxy,a,Θby) 30 3.4. Analyzing the construction 31 References 32 Coding into H(w2), Together (or Not) with Forcing Axioms. A Survey / David Aspero 34 1. Main starting questions and some pieces of notation 34 2. Results not mentioning forcing axioms 36 3. Results mentioning strong forcing axioms 49 4. Open questions and some consequences of large cardinal axioms 52 References 57 Nonstandard Methods in Ramsey's Theorem for Pairs / Chi Tat Chong 58 1. Introduction 58 2. BE 02 models 60 References 67 Prompt Simplicity, Array Computability and Cupping / Rod Downey, Noam Greenberg, Joseph S. Miller and Rebecca Weber 70 1. Introduction 71 1.1. Notation 74 2. PS AC cuppable 74 2.1. Construction 75 2.2. Veri cations 76 3. AC cuppable 6= PS 79 3.1. The strategy 79 3.2. Construction 81 3.3. Veri cation 83 References 87 Lowness for Computable Machines / Rod Downey, Noam Greenberg, Nenad Mihailovic and Andre Nies 90 1. Introduction 91 2. The Proof 94 References 96 A Simpler Short Extenders Forcing - Gap 3 / Moti Gitik 98 1. The Preparation Forcing 98 2. Types of Models 106 3. The Main Forcing 108 Acknowledgment 139 References 140 Limit Computability and Constructive Measure / Denis R. Hirschfeldt and Sebastiaan A. Terwijn 142 1. Introduction 142 2. 0 -dimension 146 3. The measure of the low sets 149 Acknowledgments 150 References 151 The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs / Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Bjorn Kjos-Hanssen, Steffen Lempp and Theodore A. Slaman 154 1. Introduction 155 2. SRT2 implies DNR 158 2.1. The argument for w-models 158 2.2. The proof-theoretic argument 159 3. COH does not imply DNR 161 4. Degrees of homogeneous sets for stable colorings 163 Acknowledgments 171 References 171 Absoluteness for Universally Baire Sets and the Uncountable II / Ilijas Farah, Richard Ketchersid, Paul Larson and Menachem Magidor 174 1. Magidor-Malitz logic 176 1.1. Proofs 178 1.2. First proof of Theorem 1.7 179 1.3. Second proof of Theorem 1.7 183 1.4. Proof of Theorem 1.3 187 2. More on correctness for partitions of nite sets 188 2.1. Partitions of [k] 1 188 2.2. [ 1]n vs. [ 1] < 189 3. Extensions of the -absoluteness argument 191 3.1. The setup 192 3.2. Trees of models 198 4. Special trees on reals 199 References 201 Monadic Definability of Ordinals / Itay Neeman 204 1. Preliminaries 205 2. Definability, forward 210 3. Definability, backward 212 4. Parameters 214 References 216 A Cuppable Non-Bounding Degree / Keng Meng Ng 218 1. Introduction 218 2. Overview of the construction 222 3. Strategy of a single requirement 223 4. Interaction of strategies 224 5. Priority tree layout 225 6. The construction 227 7. Verification 230 References 233 Eliminating Concepts / Andre Nies 236 1. Outline of the results 236 2. Computational weakness 237 2.1. Three classes 237 2.2. The existence and equivalence theorems 239 2.3. Lowness for other randomness notions 242 3. Far from random 245 3.1. Brief introduction to K-triviality 245 3.2. Constructions 246 3.3. A is K-trivial iff A is low for K 248 3.4. Further applications of the golden run method 252 4. Effective descriptive set theory 253 5. Subclasses of the K-trivials 253 5.1. ML-coverable and ML-noncuppable sets 253 5.2. A common subclass 254 5.3. Is there a characterization of K-triviality independent of randomness and K? 257 References 257 A Lower Cone in the wtt Degrees of Non-Integral Effective Dimension / Andre Nies and Jan Reimann 260 1. Introduction 260 2. Effective Dimension 262 2.1. Effective Dimension of cones and degrees 264 3. The Main Result 265 4. Concluding Remarks 269 References 270 A Minimal rK-Degree / Alexander Raichev and Frank Stephan 272 1. Introduction 272 2. The main result 274 3. Three notes 277 Acknowledgements 280 References 280 Diamonds on P_kλ / Masahiro Shioya 282 1. Introduction 282 2. Preliminaries 284 3. Diamonds on sets of countable cofinality 288 4. The principle of Stationary -Reection 290 5. Diamonds on sets of cofinality 299 6. Appendix 305 References 308 Rigidity and Biinterpretability in the Hyperdegrees / Richard A. Shore 310 1. Introduction 310 2. Rigidity 312 3. Coding 313 4. Embedding lattices 314 5. Biinterpretability 318 Acknowledgments 322 References 322 Some Fundamental Issues Concerning Degrees of Unsolvability / Stephen G. Simpson 324 1. Preface 324 2. Motivation 325 3. Mass problems (informal discussion) 326 4. Mass problems and weak degrees (rigorous definition) 326 5. Digression: Weak vs. strong reducibility 327 6. The lattice Pw (rigorous definition) 327 7. Embedding RT into Pw 329 8. Structural properties of Pw 330 9. Response to Issue 1 331 10. Some specific, natural degrees in Pw 331 11. The Embedding Lemma and some of its consequences 333 12. Proof of the Embedding Lemma 333 13. Some additional, specific degrees in Pw 334 14. Positive-measure domination 336 15. Some further specific, natural degrees in Pw 337 16. Response to Issue 2 338 17. Summary 340 References 340 Weak Determinacy and Iterations of Inductive Definitions / MedYahya Ould MedSalem and Kazuyuki Tanaka 344 1. Introduction 344 2. Preliminaries -1 2. 2-Det and 11-ID 345 3. Finite levels 349 4. Trans nite levels 356 References 363 A tt Version of the Posner-Robinson Theorem / W. Hugh Woodin 366 1. Introduction 366 2. Preliminaries 368 3. The main theorem 379 4. Further results 384 References 403 Cupping Computably Enumerable Degrees in the Ershov Hierarchy / Guohua Wu 404 1. Introduction 404 2. Cuppable degrees and plus-cupping 406 3. Noncuppable degrees and anti-cupping property 409 4. Slaman triples, cappable degrees and minimal pairs 413 5. Ideals M and NCup and quotient structures 417 6. Arslanov's cupping theorem and diamond embeddings 418 7. Isolation and intervals of d.c.e. degrees 421 8. Maximal degrees and almost universal cupping 422 9. Cupping in the -c.e. degrees 425 References 427 Generating sets for the recursively enumerable turing degrees / Klaus Ambos-Spies, Steffen Lempp and Theodore A. Slaman -- Coding into H([symbol]), together (or not) with forcing axioms. A survey / David Asperó -- Nonstandard methods in Ramsey's theorem for pairs / Chi Tat Chong -- Prompt simplicity, array computability and cupping / Rod Downey [und weitere] -- Lowness for computable machines / Rod Downey [und weitere] -- A simpler short extenders forcing - Gap 3 / Moti Gitik -- Limit computability and constructive measure / Denis R. Hirschfeldt and Sebastiaan A. Terwijn -- The strength of some combinatorial principles related to Ramsey's theorem for pairs / Denis R. Hirschfeldt [und weitere] -- Absoluteness for universally Baire sets and the Uncountable II / Ilijas Farah [und weitere] -- Monadic definability of ordinals / Itay Neeman -- A cuppable non-bounding degree / Keng Meng Ng -- Eliminating concepts / André Nies -- A lower cone in the wtt degrees of non-integral effective dimension / André Nies and Jan Reimann -- A minimal rK-degree / Alexander Raichev and Frank Stephan -- Diamonds on [symbol] / Masahiro Shioya -- Rigidity and biinterpretability in the hyperdegrees / Richard A. Shore -- Some fundamental issues concerning degrees of unsolvability / Stephen G. Simpson -- Weak determinacy and iterations of inductive definitions / MedYahya Ould MedSalem and Kazuyuki Tanaka -- A tt version of the Posner-Robinson theorem / W. Hugh Woodin -- Cupping computably enumerable degrees in the Ershov hierarchy / Guohua Wu