Computational Prospects of Infinity, Part I: Tutorials: Tutorials Pt. I

✍ Scribed by Chitat Chong, Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin, Yue Yang

• Publisher: World Scientific Publishing Company
• Year: 2008
• Tongue: English
• Leaves: 264
• Series: Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore
• Category: Library

✦ Synopsis

This volume presents the written versions of the tutorial lectures given at the Workshop on Computational Prospects of Infinity, held from 18 June to 15 August 2005 at the Institute for Mathematical Sciences, National University of Singapore. It consists of articles by four of the leading experts in recursion theory (computability theory) and set theory. The survey paper of Rod Downey provides a comprehensive introduction to algorithmic randomness, one of the most active areas of current research in recursion theory. Theodore A Slaman's article is the first printed account of the ground-breaking work of Slaman Woodin and Slaman Shore on the definability of the Turing jump. John Steel presents some results on the properties of derived models of mice, and on the existence of mice with large derived models. The study was motivated by some of the well-known Holy Grails in inner model theory, including the Mouse Set Conjecture. In his presentation, W Hugh Woodin gives an outline of an expanded version (unpublished) on suitable extender sequences, a subject that was developed in the attempt to understand inner model theory for large cardinals beyond the level of superstrong cardinals.

The volume serves as a useful guide for graduate students and researchers in recursion theory and set theory to some of the most important and significant developments in these subjects in recent years.

Contents: Five Lectures on Algorithmic Randomness (R Downey); Global Properties of the Turing Degrees and the Turing Jump (T A Slaman); Derived Models Associated to Mice (J R Steel); Tutorial Outline: Suitable Extender Sequences (W H Woodin).

✦ Table of Contents

CONTENTS......Page 6
Foreword......Page 8
Preface......Page 10
Recursion Theory Tutorials......Page 12
Five Lectures on Algorithmic Randomness Rod Downey......Page 14
1. Introduction......Page 15
2.1. Plain complexity......Page 17
2.2. Symmetry of Information......Page 22
2.3. Pre.x-free complexity......Page 24
2.4. The Coding Theorem......Page 28
2.5. Pre.x-free symmetry of information......Page 29
2.6. Pre.x-free randomness......Page 31
2.7. The overgraph functions......Page 33
3.1. Martin-L¨of randomness......Page 35
3.2. Schnorr’s Theorem and the computational paradigm......Page 36
3.3. Martingales and the prediction paradigm......Page 41
3.4. Supermartingales and continuous semimeasures......Page 44
3.5. Schnorr and computable randomness......Page 45
4.1. The de Leeuw, Moore, Shannon, Shapiro Theorem, and Sacks’ Theorem......Page 49
4.2. Coding into randoms......Page 51
4.3. Kuˇcera Coding......Page 52
4.4. n-randomness......Page 54
4.5. Notes on 2-randoms......Page 56
4.6. Kuˇcera strikes again......Page 59
4.7. van Lambalgen’s Theorem......Page 60
4.8. Effective 0-1 Laws......Page 61
5. Lecture 4: Calibrating randomness......Page 63
5.1. Measures of relative randomness and the Kucera-Slaman Theorem......Page 64
5.2. The Density Theorem......Page 68
5.3. Other measures of relative randomness......Page 70
5.4. <C and <K.......Page 71
5.5. Outside of the randoms......Page 75
5.6. <K and <r......Page 76
5.7. Hausdor. Dimension......Page 78
6.1. Risking measure......Page 79
6.2. 2-random degrees are hyperimmune......Page 80
6.3. Almost every degree is CEA......Page 82
References......Page 88
1. Introduction......Page 94
2. The coding lemma and the rst order theory of the Turing degrees......Page 95
2.1. The coding lemma......Page 96
3.1. Results of Nerode and Shore......Page 98
4. Slaman and Woodin analysis of Aut(D)......Page 99
4.1. Persistent automorphisms......Page 100
4.2. Persistently extending persistent automorphisms......Page 101
4.4. Generic persistence......Page 102
4.5. De nability of automorphisms of D......Page 104
5.1. Bi-interpretability......Page 107
6. The Turing jump......Page 110
References......Page 111
Set Theory Tutorials......Page 114
1. Introduction......Page 116
2.1. Homogeneously Suslin sets......Page 120
2.2. Hom1 iteration strategies......Page 121
2.3. The derived model......Page 122
2.5. Premice over a set......Page 125
3. Iteration independence for derived models of mice......Page 126
4. Mouse operators and jump operators......Page 136
5. The mouse set conjecture in D(M; )......Page 142
6. The Solovay sequence in D(M; )......Page 144
7. The -transform......Page 149
8. A long Solovay sequence......Page 152
9. The mouse set conjectures: Framework of the induction......Page 156
10. The background universe N......Page 163
11. The L[E]-model Nx......Page 166
12. Two hybrid mouse operators at 0......Page 169
13. New mice modulo (y)......Page 174
15. The consistency strength of AD+ + 0 <......Page 185
16. Global MSC implies the local MSC......Page 189
17. MSC implies capturing via R-mice......Page 198
References......Page 202
Tutorial Outline: Suitable Extender Sequences W. Hugh Woodin......Page 206
1. Introduction......Page 207
2.1. Long extenders......Page 208
2.2. Iteration trees......Page 211
2.3. Branch conjectures......Page 217
3.1. Martin-Steel extender sequences with long extenders......Page 223
3.2. The failure of comparison......Page 226
4. Suitable extender sequences......Page 228
4.1. Closure of L[E] under extenders and the -logic of L[E]......Page 234
4.3. L[E] in the context of comparison hypotheses......Page 244
5.1. Suitable Doddages and the Doddage Conjecture......Page 249
5.3. Closure properties of HOD......Page 257
6. Conclusions......Page 263
References......Page 264