The 10th Asian Logic Conference is part of the series of logic conferences inaugurated in Singapore in 1981. This meeting is held every three years and rotates among countries in the Asia-Pacific region, with interests in the broad area of logic, including theoretical computer science. It is now considered a major conference in this field and is regularly sponsored by the Association of Symbolic Logic. This volume contains papers from the 10th meeting held in Kobe, Japan.
Author(s): T. Arai, J. Brendle, H. Kikyo, C. T. Chong, R. Downey, Q. Feng, H. Ono
Publisher: World Scientific
Year: 2010
Language: English
Pages: 405
Contents......Page 8
1. Introduction......Page 12
2.1. Generic structures......Page 13
2.2. Stability......Page 15
3. Nonstandard Arguments......Page 16
4. The Strength of the Stability of Generic Structures......Page 21
5. Characterization of Independence in Generic Structures......Page 24
References......Page 28
1. Introduction......Page 30
2. Euclid's Constructions as Algorithms......Page 33
3. The Algebraic Approach to Constructions......Page 34
4. Models of the Elementary Constructions......Page 37
5. Euclid's Book I, Proposition 2......Page 41
6. Circles of Zero Radius and Circle3......Page 44
7. Continuous Coordinatization and Arithmetic......Page 46
8. Euclidean Constructive Geometry ECG......Page 52
9. Euclid's Reasoning......Page 71
10. Euclid's Parallel Postulate Proved in ECG......Page 74
11. Constructive Geometry and Euclidean Fields......Page 76
12. Classical Logic Not Needed for Negative Theorems......Page 82
13. From Proofs to Geometric Algorithms......Page 85
14. Conclusions......Page 89
15. Appendix: List of Axioms of ECG......Page 90
References......Page 94
A Separation Result for Varieties of Brouwer's Fan Theorem J. Berger......Page 96
Acknowledgments......Page 102
References......Page 103
Introduction......Page 104
1. A function class N with safe nested recursion......Page 105
2. Term rewriting system for PSPACE......Page 110
3. PSPACE-computable functions belong to N......Page 118
Acknowledgments......Page 122
References......Page 123
1. Introduction......Page 124
2. The existence of Ig-ultrafilters......Page 127
3. Rapid ultrafilters need not be Ig-ultrafilters......Page 129
4. Ig-ultrafilters need not be Q-points......Page 132
References......Page 134
1. Introduction......Page 135
1.1. Definitions and notation......Page 136
2. Lowness for Martin-Lof randomness......Page 139
3. Lowness for recursive randomness......Page 143
4. Lowness for Schnorr randomness......Page 145
5. Lowness for Kurtz randomness......Page 148
6. Lowness for weak 2-randomness......Page 152
7. Highness for randomness notions......Page 154
8. Conclusions......Page 159
References......Page 161
Countable Borel Equivalence Relations, Borel Reducibility, and Orbit Equivalence G. Hjorth......Page 163
1.1. Borel equivalence relations......Page 165
1.2. Countable Borel equivalence relations......Page 166
1.3. Amenability and hyperfiniteness......Page 169
2.1. Orbit equivalence......Page 177
2.2. The spectral theorem and direct integrals of representations......Page 178
2.3. Relative property (T)......Page 184
2.4. Gaboriau-Popa......Page 189
2.5. But are we really using the spectral theorem?......Page 196
2.6. Countable Borel equivalence relations up to Borel reducibility......Page 198
2.7. Further results on orbit equivalence for non-amenable groups......Page 201
3.1. Introduction to the theory of cost......Page 202
3.2. Gaboriau's breakthrough result......Page 205
4.1. More ramifications of cost......Page 213
4.2. Open problems in the theory of cost and treeable equivalence relations......Page 216
4.3. Epstein's theorem......Page 218
References......Page 223
1. Introduction......Page 225
2. Preliminaries......Page 226
3. Proposition......Page 229
4. Theorem......Page 233
References......Page 236
Geometric Simplicity Theory B. Kim......Page 238
1. Forking and Simplicity......Page 239
2. Type Amalgamation and Canonical Bases......Page 245
3. Modularity......Page 249
4. Geometries......Page 251
4.1. w-categorical case......Page 254
4.2. l-based case......Page 255
4.3. w-categorical supersimple case......Page 256
5. Group Configuration......Page 257
6. Generalized Amalgamation......Page 260
6.1. Group configuration for simple theories......Page 263
6.2. Generalized imaginaries......Page 264
6.3. n-simplicity......Page 265
7. 1-based Groups......Page 266
8. Fields Having Simple Theories......Page 269
References......Page 271
1. Introduction......Page 274
2. A proof of (2) ---+ (1)......Page 275
3. A proof of (1) -+ (2)......Page 279
References......Page 281
1. Introduction......Page 282
2. Preliminaries......Page 286
3.1. s.z.a. and i.a. sets......Page 288
3.2. i.a, preservation and reflection......Page 293
4.1. T~>.......Page 298
4.2. T~>.......Page 299
References......Page 309
1. Introduction......Page 311
2.1. The basic definitions......Page 312
2.2. Elementary equivalence problems......Page 314
2.3. Elementary substructure problems......Page 317
3.1. Kleene's 0......Page 318
3.2. Constructive and recursive ordinals......Page 319
3.3. 0 is II~ -complete......Page 321
4.1. a-r.e. Sets and Degrees......Page 323
4.2. Ershov's Theorems......Page 324
5. Applications to Inductive Inference......Page 327
References......Page 330
1. Introduction......Page 333
2.2. Martin-Lo! randomness......Page 336
2.3. Probability and density......Page 338
2.4. Dowd-type generic oracle......Page 339
3. ML randomness and Dowd-type genericity......Page 341
4. Conservation of Dowd-type genericity......Page 346
5.1. Density of a Dowd-type generic oracle......Page 351
5.2. An algorithm that changes density of an oracle......Page 352
Acknowledgments......Page 353
References......Page 354
2. Multiple Inductive Definitions......Page 356
3. Main Results......Page 358
References......Page 362
1. Introduction......Page 364
2. Isolated vs. nonisolated degrees......Page 365
3. Intervals of isolating degrees vs. nonisolating degrees......Page 369
4. Isolation and lattice embeddings......Page 375
5. Isolation and infima of d.c.e. degrees......Page 377
6. Isolation and Lachlan sets......Page 380
References......Page 383
1. Introduction......Page 386
2. Answers to the main questions......Page 387
3. Generalization......Page 390
References......Page 396
1. Weak Canonical Bases and GEl in Rosy Theories......Page 398
2. eM-triviality in Rosy Theories......Page 399
3. The Geometry of O-minimal Theories Having E.I.......Page 401
References......Page 403
