LEADER 06544nam 2200493 450 001 996483160303316 005 20230105023635.0 010 $a3-031-11367-5 035 $a(MiAaPQ)EBC7050334 035 $a(Au-PeEL)EBL7050334 035 $a(CKB)24281725100041 035 $a(PPN)263898709 035 $a(EXLCZ)9924281725100041 100 $a20230105d2022 uy 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aReverse mathematics $eproblems, reductions, and proofs /$fDamir D. Dzhafarov, Carl Mummert 210 1$aCham, Switzerland :$cSpringer,$d[2022] 210 4$d©2022 215 $a1 online resource (498 pages) 225 1 $aTheory and applications of computability 311 08$aPrint version: Dzhafarov, Damir D. Reverse Mathematics Cham : Springer International Publishing AG,c2022 9783031113666 320 $aIncludes bibliographical references and index. 327 $aIntro -- Preface -- Acknowledgments -- Contents -- List of Figures -- Introduction -- What is reverse mathematics? -- Historical remarks -- Considerations about coding -- Philosophical implications -- Conventions and notation -- Part I Computable mathematics -- Computability theory -- The informal idea of computability -- Primitive recursive functions -- Some primitive recursive functions -- Bounded quantification -- Coding sequences with primitive recursion -- Turing computability -- Three key theorems -- Computably enumerable sets and the halting problem -- The arithmetical hierarchy and Post's theorem -- Relativization and oracles -- Trees and PA degrees -- Pi-0-1 classes -- Basis theorems -- PA degrees -- Exercises -- Instance-solution problems -- Problems -- Forall/exists theorems -- Multiple problem forms -- Represented spaces -- Representing R -- Complexity -- Uniformity -- Further examples -- Exercises -- Problem reducibilities -- Subproblems and identity reducibility -- Computable reducibility -- Weihrauch reducibility -- Strong forms -- Multiple applications -- Omega model reducibility -- Hirschfeldt-Jockusch games -- Exercises -- Part II Formalization and syntax -- Second order arithmetic -- Syntax and semantics -- Hierarchies of formulas -- Arithmetical formulas -- Analytical formulas -- Arithmetic -- First order arithmetic -- Second order arithmetic -- Formalization -- The subsystem RCAo -- Delta-0-1 comprehension -- Coding finite sets -- Formalizing computability theory -- The subsystems ACAo and WKLo -- The subsystem ACA0 -- The subsystem WKL0 -- Equivalences between mathematical principles -- The subsystems P11-CAo and ATRo -- The subsystem Pi-1-1-CA0 -- The subsystem ATR0 -- Conservation results -- First order parts of theories -- Comparing reducibility notions -- Full second order semantics -- Exercises -- Induction and bounding. 327 $aInduction, bounding, and least number principles -- Finiteness, cuts, and all that -- The Kirby-Paris hierarchy -- Reverse recursion theory -- Hirst's theorem and B-Sigma02 -- So, why Sigma-01 induction? -- Exercises -- Forcing -- A motivating example -- Notions of forcing -- Density and genericity -- The forcing relation -- Effective forcing -- Forcing in models -- Harrington's theorem and conservation -- Exercises -- Part III Combinatorics -- Ramsey's theorem -- Upper bounds -- Lower bounds -- Seetapun's theorem -- Stability and cohesiveness -- Stability -- Cohesiveness -- The Cholak-Jockusch-Slaman decomposition -- A different proof of Seetapun's theorem -- Other applications -- Liu's theorem -- Preliminaries -- Proof of Lemma 8.6.6 -- Proof of Lemma 8.6.7 -- The first order part of RT -- Two versus arbitrarily many colors -- Proof of Proposition 8.7.4 -- Proof of Proposition 8.7.5 -- What else is known? -- The SRT22 vs. COH problem -- Summary: Ramsey's theorem and the ``big five'' -- Exercises -- Other combinatorial principles -- Finer results about RT -- Ramsey's theorem for singletons -- Ramsey's theorem for higher exponents -- Homogeneity vs. limit homogeneity -- Partial and linear orders -- Equivalences and bounds -- Stable partial and linear orders -- Separations over RCA0 -- Variants under finer reducibilities -- Polarized Ramsey's theorem -- Rainbow Ramsey's theorem -- Erd?s-Moser theorem -- The Chubb-Hirst-McNicholl tree theorem -- Milliken's tree theorem -- Thin set and free set theorems -- Hindman's theorem -- Apartness, gaps, and finite unions -- Towsner's simple proof -- Variants with bounded sums -- Applications of the Lovász local lemma -- Model theoretic and set theoretic principles -- Languages, theories, and models -- The atomic model theorem -- The finite intersection principle -- Weak weak König's lemma. 327 $aThe reverse mathematics zoo -- Exercises -- Part IV Other areas -- Analysis and topology -- Formalizations of the real line -- Sequences and convergence -- Sets and continuous functions -- Sets of points -- Continuous functions -- The intermediate value theorem -- Closed sets and compactness -- Separably closed sets -- Uniform continuity and boundedness -- Topological dynamics and ergodic theory -- Birkhoff's recurrence theorem -- The Auslander-Ellis theorem and iterated Hindman's theorem -- Measure theory and the mean ergodic theorem -- Additional results in real analysis -- Topology, MF spaces, CSC spaces -- Countable, second countable spaces -- MF spaces -- Reverse mathematics of MF spaces -- Exercises -- Algebra -- Groups, rings, and other structures -- Vector spaces and bases -- The complexity of ideals -- Orderability -- The Nielsen-Schreier theorem -- Other topics -- Exercises -- Set theory and beyond -- Well orderings and ordinals -- The Sigma-1-1 separation principle -- Comparability of well orderings -- Proof of Proposition 12.1.12 -- Descriptive set theory -- Determinacy -- Gale-Stewart games -- Clopen and open determinacy -- Gödel's constructible universe -- Friedman's theorem -- Higher order reverse mathematics -- Exercises -- References -- Index. 410 0$aTheory and applications of computability. 606 $aComputable functions 606 $aReverse mathematics 615 0$aComputable functions. 615 0$aReverse mathematics. 676 $a511.3 700 $aDzhafarov$b Damir D.$01252240 702 $aMummert$b Carl$f1978- 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996483160303316 996 $aReverse mathematics$92999664 997 $aUNISA