Reverse mathematics : problems, reductions, and proofs / Damir D. Dzhafarov, Carl Mummert.
Dzhafarov, Damir D.; Mummert, Carl, 1978-
2022
QA9.25
Available Online

Linked e-resources

Linked Resource Online Access
Concurrent users Unlimited
Authorized users Authorized users
Document Delivery Supplied Can lend chapters, not whole ebooks

Details

Title Reverse mathematics : problems, reductions, and proofs / Damir D. Dzhafarov, Carl Mummert.
Author Dzhafarov, Damir D.
ISBN 9783031113673 (electronic bk.)
3031113675 (electronic bk.)
9783031113666
3031113667
DOI https://doi.org/10.1007/978-3-031-11367-3
Publication Details Cham : Springer, 2022.
Language English
Description 1 online resource (498 pages)
Item Number 10.1007/978-3-031-11367-3 doi
Call Number QA9.25
Dewey Decimal Classification 511.3
Summary Reverse 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.
Note Ramsey's theorem for singletons
Bibliography, etc. Note Includes bibliographical references and index.
Access Note Access limited to authorized users.
Source of Description Online resource; title from PDF title page (SpringerLink, viewed August 8, 2022).
Added Author Mummert, Carl, 1978-
Series Theory and applications of computability.
Available in Other Form Reverse Mathematics.
Linked Resources Online Access
Record Appears in Online Resources > Ebooks
All Resources
Intro
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
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

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

Browse Subjects

Show more subjects...

Statistics

from
to
Export