Structure And Randomness In Computability And Set Theory

Contents
Preface
About the Editors
Part I: Infinitary Combinatorics and Ultrafilters
	1. Topological Ramsey Spaces Dense in Forcings
		1. Overview
		2. A Few Basic Definitions
		3. The Prototype Example: Ramsey Ultrafilters and the Ellentuck Space
			3.1. Complete combinatorics of Ramsey ultrafilters
			3.2. Rudin–Keisler order
			3.3. Tukey order on ultrafilters
			3.4. Continuous cofinal maps from P-points
			3.5. TheEllentuckspace
			3.6. Fronts, barriers, and the Nash-Williams theorem
			3.7. Canonical equivalence relations on barriers
			3.8. Fubini iterates of ultrafilters and the correspondence with uniform fronts
			3.9. Ramsey ultrafilters are Tukey minimal, and the RK structure inside its Tukey type is exactly the Fubini powers of the Ramsey ultrafilter
		4. Forcing with Topological Ramsey Spaces
			4.1. Basics of general topological Ramsey spaces
			4.2. Almost reduction, forced ultrafilters, and complete combinatorics
			4.3. Continuous cofinal maps
			4.4. Barriers and canonical equivalence relations
			4.5. Initial Tukey and Rudin–Keisler structures, and Rudin–Keisler structures inside Tukey types
		5. Topological Ramsey Space Theory Applied to Ultrafilters Satisfying Weak Partition Relations: An Overview of the Following Sections
		6. Weakly Ramsey Ultrafilters
		7. Ultrafilters of Blass Constructed by n-square Forcing and Extensions to Hypercube Forcings
		8. More Initial Rudin–Keisler and Tukey Structures Obtained from Topological Ramsey Spaces
			8.1. k-arrow, not (k + 1)-arrow ultrafilters
			8.2. Ultrafilters of Laflamme with increasingly weak partition relations
			8.3. Ultrafilters forced by P(ω × ω)/(Fin ⊗ Fin)
		9. Further Directions
		Acknowledgments
		References
	2. Infinitary Partition Properties of Sums of Selective Ultrafilters
		1. Introduction
		2. Notation and Preliminaries
			2.1. Special ultrafilters
			2.2. Sums and tensor products
			2.3. The square of the Frechet filter
			2.4. Types
			2.5. TheLevy–Mahlo model
			2.6. Tukey reduction
		3. All Types Are Realized
		4. Almost a Contradiction
		5. Generic Ultrafilters Become Sums
		Acknowledgments
		References
Part II: Algorithmic Randomness and Information
	3. Limits of the Kucera–Gacs Coding Method
		1. Introduction
			1.1. Finite information
			1.2. Bennett’s analogy for infinite information
			1.3. A quantitative version of the Kucera–Gacs theorem?
			1.4. Coding into random reals, since Kuceraand Gacs
		2. Coding into an Effectively Closed Set Subject to Density Requirements
			2.1. Overview of the Kucera–Gacs argument
			2.2. The general Kucera–Gacs argument
			2.3. The oracle-use in the general Kucera–Gacscoding argument
			2.4. Some limits of the Kucera–Gacs method
		3. Coding into Randoms Without Density Assumptions
			3.1. Coding as a labeling task
			3.2. Fully labelable trees
		Acknowledgment
		References
	4. Information vs. Dimension: An Algorithmic Perspective
		1. Introduction and Preliminaries
		2. Information Measures and Entropy
			2.1. Optimal prefix codes
			2.2. Effective coding
		3. Hausdorff Dimension
		4. Hausdorff Dimension and Information
			4.1. Hausdorff dimension and Kolmogorov complexity
			4.2. Effective nullsets
			4.3. Effective dimension and Kolmogorov complexity
			4.4. Effective dimension vs. randomness
			4.5. The Shannon–McMillan–Breiman theorem
			4.6. The effective SMB-theorem and dimension
			4.7. Subshifts
			4.8. Application: Eggleston’s theorem
		5. Multifractal Measures
			5.1. The dimension of a measure
			5.2. Pointwise dimensions
			5.3. Multifractal spectra
		References
Part III: Computable Structure Theory
	5. Computable Reducibility for Cantor Space
		1. Introduction to Reducibility
		2. Analyzing the Basic Borel Theory
		3. Completeness Results
		4. Equivalence Relations Respecting Enumerations
		5. Noncomputable Reductions
		6. The Glimm–Effros Dichotomy
		Acknowledgments
		References
	6. Logic Programming and Effectively Closed Sets
		1. Introduction
		2. Background on Normal Logic Programs
		3. Computability Theory and Effectively Closed Sets
		4. The Main Theorems
			4.1. Proof of Theorem 4.1
			4.2. Proof of Theorem 4.2
		5. Complexity of Index Sets for Normal Finite Predicate Logic Programs
		Acknowledgments
		References
	7. Computability and Definability
		1. Introduction and Preliminaries: Theories, Diagrams, and Models
		2. Computable Infinitary Formulas: Scott Rank
		3. Index Sets of Structures and Classes of Structures
		4. Relatively Δ0α-categorical Structures
		5. Definability and Complexity of Relations on Structures
		Acknowledgments
		References
Author Index
Subject Index