001448500 000__ 06781cam\a2200577\a\4500
001448500 001__ 1448500
001448500 003__ OCoLC
001448500 005__ 20230310004242.0
001448500 006__ m\\\\\o\\d\\\\\\\\
001448500 007__ cr\un\nnnunnun
001448500 008__ 220806s2022\\\\sz\\\\\\ob\\\\001\0\eng\d
001448500 019__ $$a1337523666
001448500 020__ $$a9783031113673$$q(electronic bk.)
001448500 020__ $$a3031113675$$q(electronic bk.)
001448500 020__ $$z9783031113666
001448500 020__ $$z3031113667
001448500 0247_ $$a10.1007/978-3-031-11367-3$$2doi
001448500 035__ $$aSP(OCoLC)1337946026
001448500 040__ $$aEBLCP$$beng$$epn$$cEBLCP$$dGW5XE$$dYDX$$dEBLCP$$dOCLCQ$$dOCLCF$$dUKAHL$$dOCLCQ
001448500 049__ $$aISEA
001448500 050_4 $$aQA9.25
001448500 08204 $$a511.3$$223/eng/20220808
001448500 1001_ $$aDzhafarov, Damir D.
001448500 24510 $$aReverse mathematics :$$bproblems, reductions, and proofs /$$cDamir D. Dzhafarov, Carl Mummert.
001448500 260__ $$aCham :$$bSpringer,$$c2022.
001448500 300__ $$a1 online resource (498 pages)
001448500 336__ $$atext$$btxt$$2rdacontent
001448500 337__ $$acomputer$$bc$$2rdamedia
001448500 338__ $$aonline resource$$bcr$$2rdacarrier
001448500 4901_ $$aTheory and applications of computability
001448500 500__ $$aRamsey's theorem for singletons
001448500 504__ $$aIncludes bibliographical references and index.
001448500 5050_ $$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
001448500 5058_ $$aThe 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
001448500 5058_ $$aPart 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
001448500 5058_ $$aFirst order parts of theories -- Comparing reducibility notions -- Full second order semantics -- Exercises -- Induction and bounding -- Induction, 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
001448500 5058_ $$aUpper 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
001448500 506__ $$aAccess limited to authorized users.
001448500 520__ $$aReverse mathematics studies the complexity of proving mathematical theorems and solving mathematical problems. Typical questions include: Can we prove this result without first proving that one? Can a computer solve this problem? A highly active part of mathematical logic and computability theory, the subject offers beautiful results as well as significant foundational insights. This text provides a modern treatment of reverse mathematics that combines computability theoretic reductions and proofs in formal arithmetic to measure the complexity of theorems and problems from all areas of mathematics. It includes detailed introductions to techniques from computable mathematics, Weihrauch style analysis, and other parts of computability that have become integral to research in the field. Topics and features: Provides a complete introduction to reverse mathematics, including necessary background from computability theory, second order arithmetic, forcing, induction, and model construction Offers a comprehensive treatment of the reverse mathematics of combinatorics, including Ramsey's theorem, Hindman's theorem, and many other results Provides central results and methods from the past two decades, appearing in book form for the first time and including preservation techniques and applications of probabilistic arguments Includes a large number of exercises of varying levels of difficulty, supplementing each chapter The text will be accessible to students with a standard first year course in mathematical logic. It will also be a useful reference for researchers in reverse mathematics, computability theory, proof theory, and related areas. Damir D. Dzhafarov is an Associate Professor of Mathematics at the University of Connecticut, CT, USA. Carl Mummert is a Professor of Computer and Information Technology at Marshall University, WV, USA.
001448500 588__ $$aOnline resource; title from PDF title page (SpringerLink, viewed August 8, 2022).
001448500 650_0 $$aReverse mathematics.
001448500 655_0 $$aElectronic books.
001448500 7001_ $$aMummert, Carl,$$d1978-
001448500 77608 $$iPrint version:$$aDzhafarov, Damir D.$$tReverse Mathematics.$$dCham : Springer International Publishing AG, ©2022$$z9783031113666
001448500 830_0 $$aTheory and applications of computability.
001448500 852__ $$bebk
001448500 85640 $$3Springer Nature$$uhttps://univsouthin.idm.oclc.org/login?url=https://link.springer.com/10.1007/978-3-031-11367-3$$zOnline Access$$91397441.1
001448500 909CO $$ooai:library.usi.edu:1448500$$pGLOBAL_SET
001448500 980__ $$aBIB
001448500 980__ $$aEBOOK
001448500 982__ $$aEbook
001448500 983__ $$aOnline
001448500 994__ $$a92$$bISE