Slicing the Truth : On the Computable and Reverse Mathematics of Combinatorial Principles

1. Setting off: An introduction. 1.1. A measure of motivation. 1.2. Computable mathematics. 1.3. Reverse mathematics. 1.4. An overview. 1.5. Further reading -- 2. Gathering our tools: Basic concepts and notation. 2.1. Computability theory. 2.2. Computability theoretic reductions. 2.3. Forcing -- 3. Finding our path: Konig's lemma and computability. 3.1. II[symbol] classes, basis theorems, and PA degrees. 3.2. Versions of Konig's lemma -- 4. Gauging our strength: Reverse mathematics. 4.1. RCA[symbol]. 4.2. Working in RCA[symbol]. 4.3. ACA[symbol]. 4.4. WKL[symbol]. 4.5. [symbol]-models. 4.6. First order axioms. 4.7. Further remarks -- 5. In defense of disarray -- 6. Achieving consensus: Ramsey's theorem. 6.1. Three proofs of Ramsey's theorem. 6.2. Ramsey's theorem and the arithmetic hierarchy. 6.3. RT, ACA[symbol], and the Paris-Harrington theorem. 6.4. Stability and cohesiveness. 6.5. Mathias forcing and cohesive sets. 6.6. Mathias forcing and stable colorings. 6.7. Seetapun's theorem and its extensions. 6.8. Ramsey's theorem and first order axioms. 6.9. Uniformity -- 7. Preserving our power: Conservativity. 7.1. Conservativity over first order systems. 7.2. WKL[symbol] and II[symbol]-conservativity. 7.3. COH and r-II[symbol]-conservativity -- 8. Drawing a map: Five diagrams -- 9. Exploring our surroundings: The world below RT[symbol]. 9.1. Ascending and descending sequences. 9.2. Other combinatorial principles provable from RT[symbol]. 9.3. Atomic models and omitting types -- 10. Charging ahead: Further topics. 10.1. The Dushnik-Miller theorem. 10.2. Linearizing well-founded partial orders. 10.3. The world above ACA[symbol]. 10.4. Still further topics, and a final exercise

Author: Denis Roman Hirschfeldt

Publisher: World Scientific Publishing Company Incorporated

Publication Date: Sep 15, 2014

Number of Pages: 214 pages

Language: English

Binding: Hardcover

ISBN-10: 9814612618

ISBN-13: 9789814612616