Switch to: References

Add citations

You must login to add citations.
  1. Subsets coded in elementary end extensions.James H. Schmerl - 2014 - Archive for Mathematical Logic 53 (5-6):571-581.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Separating principles below Ramsey's theorem for pairs.Manuel Lerman, Reed Solomon & Henry Towsner - 2013 - Journal of Mathematical Logic 13 (2):1350007.
    In recent years, there has been a substantial amount of work in reverse mathematics concerning natural mathematical principles that are provable from RT, Ramsey's Theorem for Pairs. These principles tend to fall outside of the "big five" systems of reverse mathematics and a complicated picture of subsystems below RT has emerged. In this paper, we answer two open questions concerning these subsystems, specifically that ADS is not equivalent to CAC and that EM is not equivalent to RT.
    Download  
     
    Export citation  
     
    Bookmark   16 citations  
  • The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
    We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for ${\Sigma^0_2}$ formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs.
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
    The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ but not (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • The weakness of the pigeonhole principle under hyperarithmetical reductions.Benoit Monin & Ludovic Patey - 2020 - Journal of Mathematical Logic 21 (3):2150013.
    The infinite pigeonhole principle for 2-partitions asserts the existence, for every set A, of an infinite subset of A or of its complement. In this paper, we study the infinite pigeonhole pr...
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Review of Denis R. Hirschfeldt, Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles. [REVIEW]Benedict Eastaugh - 2017 - Studia Logica 105 (4):873-879.
    The present volume is an introduction to the use of tools from computability theory and reverse mathematics to study combinatorial principles, in particular Ramsey's theorem and special cases such as Ramsey's theorem for pairs. It would serve as an excellent textbook for graduate students who have completed a course on computability theory.
    Download  
     
    Export citation  
     
    Bookmark  
  • (1 other version)Nonstandard models in recursion theory and reverse mathematics.C. T. Chong, Wei Li & Yue Yang - 2014 - Bulletin of Symbolic Logic 20 (2):170-200.
    We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models, and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey’s Theorem for Pairs.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Cohesive sets and rainbows.Wei Wang - 2014 - Annals of Pure and Applied Logic 165 (2):389-408.
    We study the strength of RRT32, Rainbow Ramsey Theorem for colorings of triples, and prove that RCA0 + RRT32 implies neither WKL0 nor RRT42 source. To this end, we establish some recursion theoretic properties of cohesive sets and rainbows for colorings of pairs. We show that every sequence admits a cohesive set of non-PA Turing degree; and that every ∅′-recursive sequence admits a low3 cohesive set.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Linear extensions of partial orders and reverse mathematics.Emanuele Frittaion & Alberto Marcone - 2012 - Mathematical Logic Quarterly 58 (6):417-423.
    We introduce the notion of τ-like partial order, where τ is one of the linear order types ω, ω*, ω + ω*, and ζ. For example, being ω-like means that every element has finitely many predecessors, while being ζ-like means that every interval is finite. We consider statements of the form “any τ-like partial order has a τ-like linear extension” and “any τ-like partial order is embeddable into τ” . Working in the framework of reverse mathematics, we show that these (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • On the equimorphism types of linear orderings.Antonio Montalbán - 2007 - Bulletin of Symbolic Logic 13 (1):71-99.
    §1. Introduction. A linear ordering embedsinto another linear ordering if it is isomorphic to a subset of it. Two linear orderings are said to beequimorphicif they can be embedded in each other. This is an equivalence relation, and we call the equivalence classesequimorphism types. We analyze the structure of equimorphism types of linear orderings, which is partially ordered by the embeddability relation. Our analysis is mainly fromthe viewpoints of Computability Theory and Reverse Mathematics. But we also obtain results, as the (...)
    Download  
     
    Export citation  
     
    Bookmark   10 citations  
  • Forcing in proof theory.Jeremy Avigad - 2004 - Bulletin of Symbolic Logic 10 (3):305-333.
    Paul Cohen’s method of forcing, together with Saul Kripke’s related semantics for modal and intuitionistic logic, has had profound effects on a number of branches of mathematical logic, from set theory and model theory to constructive and categorical logic. Here, I argue that forcing also has a place in traditional Hilbert-style proof theory, where the goal is to formalize portions of ordinary mathematics in restricted axiomatic theories, and study those theories in constructive or syntactic terms. I will discuss the aspects (...)
    Download  
     
    Export citation  
     
    Bookmark   15 citations  
  • (Extra)Ordinary Equivalences with the Ascending/Descending Sequence Principle.Marta Fiori-Carones, Alberto Marcone, Paul Shafer & Giovanni Soldà - 2024 - Journal of Symbolic Logic 89 (1):262-307.
    We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Indecomposable linear orderings and hyperarithmetic analysis.Antonio Montalbán - 2006 - Journal of Mathematical Logic 6 (1):89-120.
    A statement of hyperarithmetic analysis is a sentence of second order arithmetic S such that for every Y⊆ω, the minimum ω-model containing Y of RCA0 + S is HYP, the ω-model consisting of the sets hyperarithmetic in Y. We provide an example of a mathematical theorem which is a statement of hyperarithmetic analysis. This statement, that we call INDEC, is due to Jullien [13]. To the author's knowledge, no other already published, purely mathematical statement has been found with this property (...)
    Download  
     
    Export citation  
     
    Bookmark   11 citations  
  • A variant of Mathias forcing that preserves \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{ACA}_0}$$\end{document}. [REVIEW]François G. Dorais - 2012 - Archive for Mathematical Logic 51 (7-8):751-780.
    We present and analyze \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${F_\sigma}$$\end{document}-Mathias forcing, which is similar but tamer than Mathias forcing. In particular, we show that this forcing preserves certain weak subsystems of second-order arithmetic such as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{ACA}_0}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WKL}_0 + \mathsf{I}\Sigma^0_2}$$\end{document}, whereas Mathias forcing does not. We also show that the needed reals for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Reduction games, provability and compactness.Damir D. Dzhafarov, Denis R. Hirschfeldt & Sarah Reitzes - 2022 - Journal of Mathematical Logic 22 (3).
    Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [math] principles over [math]-models of [math]. They also introduced a version of this game that similarly captures provability over [math]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [math] between two (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • The modal logic of Reverse Mathematics.Carl Mummert, Alaeddine Saadaoui & Sean Sovine - 2015 - Archive for Mathematical Logic 54 (3-4):425-437.
    The implication relationship between subsystems in Reverse Mathematics has an underlying logic, which can be used to deduce certain new Reverse Mathematics results from existing ones in a routine way. We use techniques of modal logic to formalize the logic of Reverse Mathematics into a system that we name s-logic. We argue that s-logic captures precisely the “logical” content of the implication and nonimplication relations between subsystems in Reverse Mathematics. We present a sound, complete, decidable, and compact tableau-style deductive system (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • On Mathias generic sets.Peter A. Cholak, Damir D. Dzhafarov & Jeffry L. Hirst - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 129--138.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • The cohesive principle and the Bolzano‐Weierstraß principle.Alexander P. Kreuzer - 2011 - Mathematical Logic Quarterly 57 (3):292-298.
    The aim of this paper is to determine the logical and computational strength of instances of the Bolzano-Weierstraß principle and a weak variant of it.We show that BW is instance-wise equivalent to the weak König’s lemma for Σ01-trees . This means that from every bounded sequence of reals one can compute an infinite Σ01-0/1-tree, such that each infinite branch of it yields an accumulation point and vice versa. Especially, this shows that the degrees d ≫ 0′ are exactly those containing (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Reverse mathematics: the playground of logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
    This paper is essentially the author's Gödel Lecture at the ASL Logic Colloquium '09 in Sofia extended and supplemented by material from some other papers. After a brief description of traditional reverse mathematics, a computational approach to is presented. There are then discussions of some interactions between reverse mathematics and the major branches of mathematical logic in terms of the techniques they supply as well as theorems for analysis. The emphasis here is on ones that lie outside the usual main (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Almost Theorems of Hyperarithmetic Analysis.Richard A. Shore - forthcoming - Journal of Symbolic Logic:1-33.
    Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing Jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof theoretic principles which are THAs. Until Barnes, Goh, and Shore [ta] revealed an array of theorems in graph theory living in this neighborhood, there was only one mathematical denizen. In (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Open questions about Ramsey-type statements in reverse mathematics.Ludovic Patey - 2016 - Bulletin of Symbolic Logic 22 (2):151-169.
    Ramsey’s theorem states that for any coloring of then-element subsets of ℕ with finitely many colors, there is an infinite setHsuch that alln-element subsets ofHhave the same color. The strength of consequences of Ramsey’s theorem has been extensively studied in reverse mathematics and under various reducibilities, namely, computable reducibility and uniform reducibility. Our understanding of the combinatorics of Ramsey’s theorem and its consequences has been greatly improved over the past decades. In this paper, we state some questions which naturally arose (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • The strength of the Grätzer-Schmidt theorem.Katie Brodhead, Mushfeq Khan, Bjørn Kjos-Hanssen, William A. Lampe, Paul Kim Long V. Nguyen & Richard A. Shore - 2016 - Archive for Mathematical Logic 55 (5-6):687-704.
    The Grätzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this theorem. We also show thatthe set of indices of computable lattices that are complete is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^1_1$$\end{document}-complete;the set of indices of computable lattices that are algebraic is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^1_1$$\end{document}-complete;the set of compact elements of a computable (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • The reverse mathematics of non-decreasing subsequences.Ludovic Patey - 2017 - Archive for Mathematical Logic 56 (5-6):491-506.
    Every function over the natural numbers has an infinite subdomain on which the function is non-decreasing. Motivated by a question of Dzhafarov and Schweber, we study the reverse mathematics of variants of this statement. It turns out that this statement restricted to computably bounded functions is computationally weak and does not imply the existence of the halting set. On the other hand, we prove that it is not a consequence of Ramsey’s theorem for pairs. This statement can therefore be seen (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Unifying the model theory of first-order and second-order arithmetic via WKL 0 ⁎.Ali Enayat & Tin Lok Wong - 2017 - Annals of Pure and Applied Logic 168 (6):1247-1283.
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • How Strong is Ramsey’s Theorem If Infinity Can Be Weak?Leszek Aleksander Kołodziejczyk, Katarzyna W. Kowalik & Keita Yokoyama - 2023 - Journal of Symbolic Logic 88 (2):620-639.
    We study the first-order consequences of Ramsey’s Theorem fork-colourings ofn-tuples, for fixed$n, k \ge 2$, over the relatively weak second-order arithmetic theory$\mathrm {RCA}^*_0$. Using the Chong–Mourad coding lemma, we show that in a model of$\mathrm {RCA}^*_0$that does not satisfy$\Sigma ^0_1$induction,$\mathrm {RT}^n_k$is equivalent to its relativization to any proper$\Sigma ^0_1$-definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe.We give a complete axiomatization of the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^n_k$for$n \ge (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • The uniform content of partial and linear orders.Eric P. Astor, Damir D. Dzhafarov, Reed Solomon & Jacob Suggs - 2017 - Annals of Pure and Applied Logic 168 (6):1153-1171.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • On principles between ∑1- and ∑2-induction, and monotone enumerations.Alexander P. Kreuzer & Keita Yokoyama - 2016 - Journal of Mathematical Logic 16 (1):1650004.
    We show that many principles of first-order arithmetic, previously only known to lie strictly between [Formula: see text]-induction and [Formula: see text]-induction, are equivalent to the well-foundedness of [Formula: see text]. Among these principles are the iteration of partial functions of Hájek and Paris, the bounded monotone enumerations principle by Chong, Slaman, and Yang, the relativized Paris–Harrington principle for pairs, and the totality of the relativized Ackermann–Péter function. With this we show that the well-foundedness of [Formula: see text] is a (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • The Thin Set Theorem for Pairs Implies DNR.Brian Rice - 2015 - Notre Dame Journal of Formal Logic 56 (4):595-601.
    Answering a question in the reverse mathematics of combinatorial principles, we prove that the thin set theorem for pairs ) implies the diagonally noncomputable set principle over the base axiom system $\mathrm{RCA}_{0}$.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Generics for computable Mathias forcing.Peter A. Cholak, Damir D. Dzhafarov, Jeffry L. Hirst & Theodore A. Slaman - 2014 - Annals of Pure and Applied Logic 165 (9):1418-1428.
    We study the complexity of generic reals for computable Mathias forcing in the context of computability theory. The n -generics and weak n -generics form a strict hierarchy under Turing reducibility, as in the case of Cohen forcing. We analyze the complexity of the Mathias forcing relation, and show that if G is any n -generic with n≥2n≥2 then it satisfies the jump property G≡TG′⊕∅G≡TG′⊕∅. We prove that every such G has generalized high Turing degree, and so cannot have even (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • On the strength of Ramsey's theorem without Σ1 -induction.Keita Yokoyama - 2013 - Mathematical Logic Quarterly 59 (1-2):108-111.
    In this paper, we show that equation image is a equation image-conservative extension of BΣ1 + exp, thus it does not imply IΣ1.
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • On the Indecomposability of $\omega^{n}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.
    We study the reverse mathematics of pigeonhole principles for finite powers of the ordinal $\omega$ . Four natural formulations are presented, and their relative strengths are compared. In the analysis of the pigeonhole principle for $\omega^{2}$ , we uncover two weak variants of Ramsey’s theorem for pairs.
    Download  
     
    Export citation  
     
    Bookmark  
  • Dominating the Erdős–Moser theorem in reverse mathematics.Ludovic Patey - 2017 - Annals of Pure and Applied Logic 168 (6):1172-1209.
    Download  
     
    Export citation  
     
    Bookmark  
  • On a question of Andreas Weiermann.Henryk Kotlarski & Konrad Zdanowski - 2009 - Mathematical Logic Quarterly 55 (2):201-211.
    We prove that for each β, γ < ε0 there existsα < ε0 such that whenever A ⊆ ω is α ‐large and G: A → β is such that (∀a ∈ A)(psn(G (a)) ≤ a), then there exists a γ ‐large C ⊆ A on which G is nondecreasing. Moreover, we give upper bounds for α for small ordinals β ≤ ω (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim).
    Download  
     
    Export citation  
     
    Bookmark  
  • Primitive Recursion and the Chain Antichain Principle.Alexander P. Kreuzer - 2012 - Notre Dame Journal of Formal Logic 53 (2):245-265.
    Let the chain antichain principle (CAC) be the statement that each partial order on $\mathbb{N}$ possesses an infinite chain or an infinite antichain. Chong, Slaman, and Yang recently proved using forcing over nonstandard models of arithmetic that CAC is $\Pi^1_1$-conservative over $\text{RCA}_0+\Pi^0_1\text{-CP}$ and so in particular that CAC does not imply $\Sigma^0_2$-induction. We provide here a different purely syntactical and constructive proof of the statement that CAC (even together with WKL) does not imply $\Sigma^0_2$-induction. In detail we show using a (...)
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • Primitive recursive reverse mathematics.Nikolay Bazhenov, Marta Fiori-Carones, Lu Liu & Alexander Melnikov - 2024 - Annals of Pure and Applied Logic 175 (1):103354.
    Download  
     
    Export citation  
     
    Bookmark  
  • Ramsey’s theorem for trees: the polarized tree theorem and notions of stability. [REVIEW]Damir D. Dzhafarov, Jeffry L. Hirst & Tamara J. Lakins - 2010 - Archive for Mathematical Logic 49 (3):399-415.
    We formulate a polarized version of Ramsey’s theorem for trees. For those exponents greater than 2, both the reverse mathematics and the computability theory associated with this theorem parallel that of its linear analog. For pairs, the situation is more complex. In particular, there are many reasonable notions of stability in the tree setting, complicating the analysis of the related results.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Partition theorems and computability theory.Joseph R. Mileti - 2005 - Bulletin of Symbolic Logic 11 (3):411-427.
    The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Weaker cousins of Ramsey's theorem over a weak base theory.Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk & Katarzyna W. Kowalik - 2021 - Annals of Pure and Applied Logic 172 (10):103028.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Degrees bounding principles and universal instances in reverse mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • THE REVERSE MATHEMATICS OF ${\mathsf {CAC\ FOR\ TREES}}$.Julien Cervelle, William Gaudelier & Ludovic Patey - 2024 - Journal of Symbolic Logic 89 (3):1189-1211.
    ${\mathsf {CAC\ for\ trees}}$ is the statement asserting that any infinite subtree of $\mathbb {N}^{<\mathbb {N}}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a reverse mathematical viewpoint. We prove that ${\mathsf {CAC\ for\ trees}}$ is robust, that is, there exist several characterizations, some of which already appear in the literature, namely, the statement $\mathsf {SHER}$ introduced by Dorais et al. [8], and the statement $\mathsf {TAC}+\mathsf {B}\Sigma ^0_2$ (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Reverse mathematical bounds for the Termination Theorem.Silvia Steila & Keita Yokoyama - 2016 - Annals of Pure and Applied Logic 167 (12):1213-1241.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • The strength of infinitary Ramseyan principles can be accessed by their densities.Andrey Bovykin & Andreas Weiermann - 2017 - Annals of Pure and Applied Logic 168 (9):1700-1709.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • The maximal linear extension theorem in second order arithmetic.Alberto Marcone & Richard A. Shore - 2011 - Archive for Mathematical Logic 50 (5-6):543-564.
    We show that the maximal linear extension theorem for well partial orders is equivalent over RCA0 to ATR0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR0 over RCA0.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Ramsey's Theorem for Pairs and Provably Recursive Functions.Alexander Kreuzer & Ulrich Kohlenbach - 2009 - Notre Dame Journal of Formal Logic 50 (4):427-444.
    This paper addresses the strength of Ramsey's theorem for pairs ($RT^2_2$) over a weak base theory from the perspective of 'proof mining'. Let $RT^{2-}_2$ denote Ramsey's theorem for pairs where the coloring is given by an explicit term involving only numeric variables. We add this principle to a weak base theory that includes weak König's Lemma and a substantial amount of $\Sigma^0_1$-induction (enough to prove the totality of all primitive recursive functions but not of all primitive recursive functionals). In the (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • (15 other versions)2008 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '08.Alex J. Wilkie - 2009 - Bulletin of Symbolic Logic 15 (1):95-139.
    Download  
     
    Export citation  
     
    Bookmark  
  • Reverse Mathematics and Ramsey Properties of Partial Orderings.Jared Corduan & Marcia Groszek - 2016 - Notre Dame Journal of Formal Logic 57 (1):1-25.
    A partial ordering $\mathbb{P}$ is $n$-Ramsey if, for every coloring of $n$-element chains from $\mathbb{P}$ in finitely many colors, $\mathbb{P}$ has a homogeneous subordering isomorphic to $\mathbb{P}$. In their paper on Ramsey properties of the complete binary tree, Chubb, Hirst, and McNicholl ask about Ramsey properties of other partial orderings. They also ask whether there is some Ramsey property for pairs equivalent to $\mathit{ACA}_{0}$ over $\mathit{RCA}_{0}$. A characterization theorem for finite-level partial orderings with Ramsey properties has been proven by the (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • On notions of computability-theoretic reduction between Π21 principles.Denis R. Hirschfeldt & Carl G. Jockusch - 2016 - Journal of Mathematical Logic 16 (1):1650002.
    Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...)
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
    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 mathematics that are starting to be developed and where interesting open question may be found.
    Download  
     
    Export citation  
     
    Bookmark   32 citations  
  • A weak variant of Hindman’s Theorem stronger than Hilbert’s Theorem.Lorenzo Carlucci - 2018 - Archive for Mathematical Logic 57 (3-4):381-389.
    Hirst investigated a natural restriction of Hindman’s Finite Sums Theorem—called Hilbert’s Theorem—and proved it equivalent over \ to the Infinite Pigeonhole Principle for all colors. This gave the first example of a natural restriction of Hindman’s Theorem provably much weaker than Hindman’s Theorem itself. We here introduce another natural restriction of Hindman’s Theorem—which we name the Adjacent Hindman’s Theorem with apartness—and prove it to be provable from Ramsey’s Theorem for pairs and strictly stronger than Hirst’s Hilbert’s Theorem. The lower bound (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • From Bolzano‐Weierstraß to Arzelà‐Ascoli.Alexander P. Kreuzer - 2014 - Mathematical Logic Quarterly 60 (3):177-183.
    We show how one can obtain solutions to the Arzelà‐Ascoli theorem using suitable applications of the Bolzano‐Weierstraß principle. With this, we can apply the results from and obtain a classification of the strength of instances of the Arzelà‐Ascoli theorem and a variant of it. Let be the statement that each equicontinuous sequence of functions contains a subsequence that converges uniformly with the rate and let be the statement that each such sequence contains a subsequence which converges uniformly but possibly without (...)
    Download  
     
    Export citation  
     
    Bookmark