Computational Prospects of Infinity Part II Presented Talks 1st Edition by Chitat Chong, Qi Feng, Theodore A Slaman, W Hugh Woodin, Yue Yang – Ebook PDF Instant Download/Delivery. 981279655X, 9789812796554
Full download Computational Prospects of Infinity Part II Presented Talks 1st Edition after payment
Product details:
ISBN 10: 981279655X
ISBN 13: 9789812796554
Author: Chitat Chong, Qi Feng, Theodore A Slaman, W Hugh Woodin, Yue Yang
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.
Computational Prospects of Infinity Part II Presented Talks 1st Table of contents:
1. Introduction
2. The technical theorem and some intuition for its proof
2.1. Requirements and simple strategies
2.2. Strategies
2.2.1. Making Θ = A: σ0(Θ)
2.2.2. Measuring whether the equations hold: σ1(X, Y,Λa,x,Λa,y,Λxy,a)
2.2.3. Computations between B, C, and X: σ2(X, Y,Λa,x,Λa,y,Λxy,a)
2.2.4. Making C the infimum of CD and CE: s3(X, Y,.a,x,.a,y,.xy,a,.cd,.ce)
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,
2.2.6. If Θby(BY ) = A then y,a(Y ) = A: σ6(X, Y,Λa,x,Λa,y,Λxy,a,Θby)
2.2.7. One sequence (X, Y,Λa,x,Λa,y,Λxy,a)
3. The global construction
3.1. Interactions between σ-strategies
3.2. The tree of strategies
3.2.1. η-con.gurations
3.3. The construction
3.3.1. Adding an A-diagonalization strategy σ0
3.3.2. Adding a σ1(X, Y,Λa,x,Λa,y,Λxy,a)
3.3.3. Adding a σ2(X, Y,Λa,x,Λa,y,Λxy,a)
3.3.4. Adding a σ3(X, Y,Λa,x,Λa,y,Λxy,a,Ψcd,Ψce)
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)
3.3.6. Adding a σ6(X, Y,Λa,x,Λa,y,Λxy,a,Θby)
3.4. Analyzing the construction
References
Coding into H(w2), Together (or Not) with Forcing Axioms. A Survey David Asper o
1. Main starting questions and some pieces of notation
2. Results not mentioning forcing axioms
3. Results mentioning strong forcing axioms
4. Open questions and some consequences of large cardinal axioms
References
Nonstandard Methods in Ramsey’s Theorem for Pairs Chi Tat Chong
1. Introduction
2. BE 02 models
References
Prompt Simplicity, Array Computability and Cupping Rod Downey, Noam Greenberg, Joseph S. Miller and
1. Introduction
1.1. Notation
2. PS AC cuppable
2.1. Construction
2.2. Veri cations
3. AC cuppable 6= PS
3.1. The strategy
3.2. Construction
3.3. Veri cation
References
Lowness for Computable Machines Rod Downey, Noam Greenberg, Nenad Mihailovi c and Andr e Nies
1. Introduction
2. The Proof
References
A Simpler Short Extenders Forcing | Gap 3 Moti Gitik
1. The Preparation Forcing
2. Types of Models
3. The Main Forcing
Acknowledgment
References
Limit Computability and Constructive Measure Denis R. Hirschfeldt and Sebastiaan A. Terwijn
1. Introduction
2. 0 -dimension
3. The measure of the low sets
Acknowledgments
References
The Strength of Some Combinatorial Principles Related to Ramsey’s Theorem for Pairs Denis R. Hirschf
1. Introduction
2. SRT2 implies DNR
2.1. The argument for w-models
2.2. The proof-theoretic argument
3. COH does not imply DNR
4. Degrees of homogeneous sets for stable colorings
Acknowledgments
References
Absoluteness for Universally Baire Sets and the Uncountable II Ilijas Farah, Richard Ketchersid, Pau
1. Magidor-Malitz logic
1.1. Proofs
1.2. First proof of Theorem 1.7
1.3. Second proof of Theorem 1.7
1.4. Proof of Theorem 1.3
2. More on correctness for partitions of nite sets
2.1. Partitions of [k] 1
2.2. [ 1]n vs. [ 1] <
3. Extensions of the -absoluteness argument
3.1. The setup
3.2. Trees of models
4. Special trees on reals
References
Monadic Definability of Ordinals Itay Neeman
1. Preliminaries
2. Definability, forward
3. Definability, backward
4. Parameters
References
A Cuppable Non-Bounding Degree Keng Meng Ng
1. Introduction
2. Overview of the construction
3. Strategy of a single requirement
4. Interaction of strategies
5. Priority tree layout
6. The construction
7. Verification
References
Eliminating Concepts Andr e Nies
1. Outline of the results
2. Computational weakness
2.1. Three classes
2.2. The existence and equivalence theorems
2.3. Lowness for other randomness notions
3. Far from random
3.1. Brief introduction to K-triviality
3.2. Constructions
3.3. A is K-trivial iff A is low for K
3.4. Further applications of the golden run method
4. Effective descriptive set theory
5. Subclasses of the K-trivials
5.1. ML-coverable and ML-noncuppable sets
5.2. A common subclass
5.3. Is there a characterization of K-triviality independent of randomness and K?
References
A Lower Cone in the wtt Degrees of Non-Integral Effective Dimension Andr e Nies and Jan Reimann
1. Introduction
2. Effective Dimension
2.1. Effective Dimension of cones and degrees
3. The Main Result
4. Concluding Remarks
References
A Minimal rK-Degree Alexander Raichev and Frank Stephan
1. Introduction
2. The main result
3. Three notes
Acknowledgements
References
Diamonds on P Masahiro Shioya
1. Introduction
2. Preliminaries
3. Diamonds on sets of countable cofinality
4. The principle of Stationary -Reection
5. Diamonds on sets of cofinality
6. Appendix
References
Rigidity and Biinterpretability in the Hyperdegrees Richard A. Shore
1. Introduction
2. Rigidity
3. Coding
4. Embedding lattices
5. Biinterpretability
Acknowledgments
References
Some Fundamental Issues Concerning Degrees of Unsolvability Stephen G. Simpson
1. Preface
2. Motivation
3. Mass problems (informal discussion)
4. Mass problems and weak degrees (rigorous definition)
5. Digression: Weak vs. strong reducibility
6. The lattice Pw (rigorous definition)
7. Embedding RT into Pw
8. Structural properties of Pw
9. Response to Issue 1
10. Some specific, natural degrees in Pw
11. The Embedding Lemma and some of its consequences
12. Proof of the Embedding Lemma
13. Some additional, specific degrees in Pw
14. Positive-measure domination
15. Some further specific, natural degrees in Pw
16. Response to Issue 2
17. Summary
References
Weak Determinacy and Iterations of Inductive Definitions MedYahya Ould MedSalem and Kazuyuki Tanaka
1. Introduction
2. Preliminaries
2. 2-Det and 11-ID
3. Finite levels
4. Trans nite levels
References
A tt Version of the Posner-Robinson Theorem W. Hugh Woodin
1. Introduction
2. Preliminaries
3. The main theorem
4. Further results
References
Cupping Computably Enumerable Degrees in the Ershov Hierarchy Guohua Wu
1. Introduction
2. Cuppable degrees and plus-cupping
3. Noncuppable degrees and anti-cupping property
4. Slaman triples, cappable degrees and minimal pairs
5. Ideals M and NCup and quotient structures
6. Arslanov’s cupping theorem and diamond embeddings
7. Isolation and intervals of d.c.e. degrees
8. Maximal degrees and almost universal cupping
9. Cupping in the -c.e. degrees
People also search for Computational Prospects of Infinity Part II Presented Talks 1st:
computational prospects of infinity
computational integrity
computational inference
computational probability and inference
computational inverse problems