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