28 found
Order:
  1. 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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  2.  28
    Weak Comparability of Well Orderings and Reverse Mathematics.Harvey M. Friedman & Jeffry L. Hirst - 1990 - Annals of Pure and Applied Logic 47 (1):11-29.
    Two countable well orderings are weakly comparable if there is an order preserving injection of one into the other. We say the well orderings are strongly comparable if the injection is an isomorphism between one ordering and an initial segment of the other. In [5], Friedman announced that the statement “any two countable well orderings are strongly comparable” is equivalent to ATR 0 . Simpson provides a detailed proof of this result in Chapter 5 of [13]. More recently, Friedman has (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  3.  45
    Reverse Mathematics, Computability, and Partitions of Trees.Jennifer Chubb, Jeffry L. Hirst & Timothy H. McNicholl - 2009 - Journal of Symbolic Logic 74 (1):201-215.
    We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  4.  8
    Reverse Mathematics and Ordinal Exponentiation.Jeffry L. Hirst - 1994 - Annals of Pure and Applied Logic 66 (1):1-18.
    Simpson has claimed that “ATR0 is the weakest set of axioms which permits the development of a decent theory of countable ordinals” [8]. This paper provides empirical support for Simpson's claim. In particular, Cantor's Normal Form Theorem and Sherman's Inequality for countable well-orderings are both equivalent to ATR0. The proofs of these results require a substantial development of ordinal exponentiation and a strengthening of the comparability result in [3].
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  5.  28
    Reverse Mathematics and Uniformity in Proofs Without Excluded Middle.Jeffry L. Hirst & Carl Mummert - 2011 - Notre Dame Journal of Formal Logic 52 (2):149-162.
    We show that when certain statements are provable in subsystems of constructive analysis using intuitionistic predicate calculus, related sequential statements are provable in weak classical subsystems. In particular, if a $\Pi^1_2$ sentence of a certain form is provable using E-HA ${}^\omega$ along with the axiom of choice and an independence of premise principle, the sequential form of the statement is provable in the classical system RCA. We obtain this and similar results using applications of modified realizability and the Dialectica interpretation. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  6.  17
    Comparing the Strength of Diagonally Nonrecursive Functions in the Absence of Induction.François G. Dorais, Jeffry L. Hirst & Paul Shafer - 2015 - Journal of Symbolic Logic 80 (4):1211-1235.
    We prove that the statement “there is aksuch that for everyfthere is ak-bounded diagonally nonrecursive function relative tof” does not imply weak König’s lemma over${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that everyk-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of${\rm{I\Sigma }}_2^0$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  63
    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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  8.  27
    Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
    We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  9.  14
    Hilbert Versus Hindman.Jeffry L. Hirst - 2012 - Archive for Mathematical Logic 51 (1-2):123-125.
    We show that a statement HIL, which is motivated by a lemma of Hilbert and close in formulation to Hindman’s theorem, is actually much weaker than Hindman’s theorem. In particular, HIL is finitistically reducible in the sense of Hilbert’s program, while Hindman’s theorem is not.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  8
    Denis R. Hirschfeldt. Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles. Lecture Note Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 28. World Scientific Publishing Co. Pte. Ltd., Singapore, 2015, Xiv+214 Pp. [REVIEW]Jeffry L. Hirst - 2015 - Bulletin of Symbolic Logic 21 (3):338-339.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  7
    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.
  12.  45
    Ordinal Inequalities, Transfinite Induction, and Reverse Mathematics.Jeffry L. Hirst - 1999 - Journal of Symbolic Logic 64 (2):769-774.
    If α and β are ordinals, α ≤ β, and $\beta \nleq \alpha$ , then α + 1 ≤ β. The first result of this paper shows that the restriction of this statement to countable well orderings is provably equivalent to ACA 0 , a subsystem of second order arithmetic introduced by Friedman. The proof of the equivalence is reminiscent of Dekker's construction of a hypersimple set. An application of the theorem yields the equivalence of the set comprehension scheme ACA (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  14
    Minima of Initial Segments of Infinite Sequences of Reals.Jeffry L. Hirst - 2004 - Mathematical Logic Quarterly 50 (1):47-50.
    Suppose that 〈xk〉k∈ℕ is a countable sequence of real numbers. Working in the usual subsystems for reverse mathematics, RCA0 suffices to prove the existence of a sequence of reals 〈uk〉k∈ℕ such that for each k, uk is the minimum of {x0, x1, …, xk}. However, if we wish to prove the existence of a sequence of integer indices of minima of initial segments of 〈xk〉k∈ℕ, the stronger subsystem WKL0 is required. Following the presentation of these reverse mathematics results, we will (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14.  20
    Connected Components of Graphs and Reverse Mathematics.Jeffry L. Hirst - 1992 - Archive for Mathematical Logic 31 (3):183-192.
  15.  14
    Reverse Mathematics and Rank Functions for Directed Graphs.Jeffry L. Hirst - 2000 - Archive for Mathematical Logic 39 (8):569-579.
    A rank function for a directed graph G assigns elements of a well ordering to the vertices of G in a fashion that preserves the order induced by the edges. While topological sortings require a one-to-one matching of vertices and elements of the ordering, rank functions frequently must assign several vertices the same value. Theorems stating basic properties of rank functions vary significantly in logical strength. Using the techniques of reverse mathematics, we present results that require the subsystems ${\ensuremath{\vec{RCA}_0}}$ , (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  11
    Reverse Mathematics and Homeomorphic Embeddings.Harvey M. Friedman & Jeffry L. Hirst - 1991 - Annals of Pure and Applied Logic 54 (3):229-253.
    Extrapolating from the work of Mahlo , one can prove that given any pair of countable closed totally bounded subsets of complete separable metric spaces, one subset can be homeomorphically embedded in the other. This sort of topological comparability is reminiscent of the statements concerning comparability of well orderings which Friedman has shown to be equivalent to ATR0 over the weak base system RCA0. The main result of this paper states that topological comparability is also equivalent to ATR0. In Section (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  16
    Infinite Versions of Some Problems From Finite Complexity Theory.Jeffry L. Hirst & Steffen Lempp - 1996 - Notre Dame Journal of Formal Logic 37 (4):545-553.
    Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  18.  26
    Partitions of Trees and $${{\Sf ACA}^\Prime_{0}}$$.Bernard A. Anderson & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (3-4):227-230.
    We show that a version of Ramsey’s theorem for trees for arbitrary exponents is equivalent to the subsystem ${{\sf ACA}^\prime_{0}}$ of reverse mathematics.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  19.  20
    Partitions of Trees And.Bernard A. Anderson & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (3-4):227-230.
    We show that a version of Ramsey’s theorem for trees for arbitrary exponents is equivalent to the subsystem \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\sf ACA}^\prime_{0}}$$\end{document} of reverse mathematics.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  7
    Combinatorics and Graph Theory.John M. Harris, Jeffry L. Hirst & Michael J. Mossinghoff - 2008 - Springer.
    This book covers a wide variety of topics in combinatorics and graph theory.
    No categories
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  21.  16
    Derived Sequences and Reverse Mathematics.Jeffry L. Hirst - 1993 - Mathematical Logic Quarterly 39 (1):447-453.
    One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR0. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR0. In actuality, the full strength of ATR0 is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR0, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  22.  11
    Embeddings of Countable Closed Sets and Reverse Mathematics.Jeffry L. Hirst - 1993 - Archive for Mathematical Logic 32 (6):443-449.
    If there is a homeomorphic embedding of one set into another, the sets are said to be topologically comparable. Friedman and Hirst have shown that the topological comparability of countable closed subsets of the reals is equivalent to the subsystem of second order arithmetic denoted byATR 0. Here, this result is extended to countable closed locally compact subsets of arbitrary complete separable metric spaces. The extension uses an analogue of the one point compactification of ℝ.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  23.  14
    J. Stillwell, Reverse Mathematics: Proofs From the Inside Out, Princeton University Press, Princeton, 2018, Xiii + 182 Pp. [REVIEW]Jeffry L. Hirst - 2018 - Bulletin of Symbolic Logic 24 (2):176-177.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  17
    Reverse Mathematics and Ordinal Multiplication.Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):459-464.
    This paper uses the framework of reverse mathematics to analyze the proof theoretic content of several statements concerning multiplication of countable well-orderings. In particular, a division algorithm for ordinal arithmetic is shown to be equivalent to the subsystem ATR0.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  25.  13
    Reverse Mathematics and Marriage Problems with Unique Solutions.Jeffry L. Hirst & Noah A. Hughes - 2015 - Archive for Mathematical Logic 54 (1-2):49-57.
    We analyze the logical strength of theorems on marriage problems with unique solutions using the techniques of reverse mathematics, restricting our attention to problems in which each boy knows only finitely many girls. In general, these marriage theorems assert that if a marriage problem has a unique solution then there is a way to enumerate the boys so that for every m, the first m boys know exactly m girls. The strength of each theorem depends on whether the underlying marriage (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  26.  19
    Reverse Mathematics of Prime Factorization of Ordinals.Jeffry L. Hirst - 1999 - Archive for Mathematical Logic 38 (3):195-201.
    One of the earliest applications of Cantor's Normal Form Theorem is Jacobstahl's proof of the existence of prime factorizations of ordinals. Applying the techniques of reverse mathematics, we show that the full strength of the Normal Form Theorem is used in this proof.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  27.  22
    Reverse Mathematics of Separably Closed Sets.Jeffry L. Hirst - 2006 - Archive for Mathematical Logic 45 (1):1-2.
    This paper contains a corrected proof that the statement “every non-empty closed subset of a compact complete separable metric space is separably closed” implies the arithmetical comprehension axiom of reverse mathematics.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  28.  15
    Using Ramsey’s theorem once.Jeffry L. Hirst & Carl Mummert - 2019 - Archive for Mathematical Logic 58 (7-8):857-866.
    We show that \\) cannot be proved with one typical application of \\) in an intuitionistic extension of \ to higher types, but that this does not remain true when the law of the excluded middle is added. The argument uses Kohlenbach’s axiomatization of higher order reverse mathematics, results related to modified reducibility, and a formalization of Weihrauch reducibility.
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark