[图书][B] Slicing the truth: On the computable and reverse mathematics of combinatorial principles
DR Hirschfeldt - 2015 - World Scientific
Ramsey's Theorem [166] captures the idea that total disorder is impossible: a sufficiently
large structure will always contain a large ordered substructure. A well-known special case …
large structure will always contain a large ordered substructure. A well-known special case …
Reverse Mathematics
DD Dzhafarov, C Mummert - … , reductions, and proofs, Theory Appl. Comput …, 2022 - Springer
When we set out to write this book in the spring of 2011, the only introduction to reverse
mathematics was Simpson's Subsystems of Second Order Arithmetic [288]. Our motivation …
mathematics was Simpson's Subsystems of Second Order Arithmetic [288]. Our motivation …
Combinatorial principles weaker than Ramsey's theorem for pairs
DR Hirschfeldt, RA Shore - The Journal of Symbolic Logic, 2007 - cambridge.org
We investigate the complexity of various combinatorial theorems about linear and partial
orders, from the points of view of computability theory and reverse mathematics. We focus in …
orders, from the points of view of computability theory and reverse mathematics. We focus in …
Computability and analysis: the legacy of Alan Turing.
§ 1. Introduction. For most of its history, mathematics was algorithmic in nature. The
geometric claims in Euclid's Elements fall into two distinct categories:“problems,” which …
geometric claims in Euclid's Elements fall into two distinct categories:“problems,” which …
On uniform relationships between combinatorial problems
F Dorais, D Dzhafarov, J Hirst, J Mileti… - Transactions of the …, 2016 - ams.org
The enterprise of comparing mathematical theorems according to their logical strength is an
active area in mathematical logic, with one of the most common frameworks for doing so …
active area in mathematical logic, with one of the most common frameworks for doing so …
Open questions in reverse mathematics
A Montalbán - Bulletin of Symbolic Logic, 2011 - cambridge.org
We present a list of open questions in reverse mathematics, including some relevant
background information for each question. We also mention some of the areas of reverse …
background information for each question. We also mention some of the areas of reverse …
On notions of computability-theoretic reduction between principles
DR Hirschfeldt, CG Jockusch Jr - Journal of Mathematical Logic, 2016 - World Scientific
Several notions of computability-theoretic reducibility between Π 2 1 principles have been
studied. This paper contributes to the program of analyzing the behavior of versions of …
studied. This paper contributes to the program of analyzing the behavior of versions of …
Mass problems and randomness
SG Simpson - Bulletin of Symbolic Logic, 2005 - cambridge.org
A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is
weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is …
weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is …
Uniform versions of some axioms of second order arithmetic
N Sakamoto, T Yamazaki - Mathematical Logic Quarterly …, 2004 - Wiley Online Library
The bulk of ordinary mathematics is naturally developed within higher order (finite type)
arithmetic, which formally treats a structure consisting of natural numbers N and function (al) …
arithmetic, which formally treats a structure consisting of natural numbers N and function (al) …
Comparing dnr and wwkl
K Ambos-Spies, B Kjos-Hanssen, S Lempp… - The Journal of …, 2004 - cambridge.org
COMPARING DNR AND WWKL §1. Introduction. Reverse mathematics is a branch of proof
theory which involves proving the equivalence Page 1 THI: JOURNAL OF SYMBOLIC LOGIC …
theory which involves proving the equivalence Page 1 THI: JOURNAL OF SYMBOLIC LOGIC …