Switch to: References

Add citations

You must login to add citations.
  1. $\Pi ^{0}_{1}$ -Encodability and Omniscient Reductions.Benoit Monin & Ludovic Patey - 2019 - Notre Dame Journal of Formal Logic 60 (1):1-12.
    A set of integers A is computably encodable if every infinite set of integers has an infinite subset computing A. By a result of Solovay, the computably encodable sets are exactly the hyperarithmetic ones. In this article, we extend this notion of computable encodability to subsets of the Baire space, and we characterize the Π10-encodable compact sets as those which admit a nonempty Σ11-subset. Thanks to this equivalence, we prove that weak weak König’s lemma is not strongly computably reducible to (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • 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  
  • Dominating the Erdős–Moser Theorem in Reverse Mathematics.Ludovic Patey - 2017 - Annals of Pure and Applied Logic 168 (6):1172-1209.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  • 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.
  • On the Uniform Computational Content of Ramsey’s Theorem.Vasco Brattka & Tahina Rakotoniaina - 2017 - Journal of Symbolic Logic 82 (4):1278-1316.
    We study the uniform computational content of Ramsey’s theorem in the Weihrauch lattice. Our central results provide information on how Ramsey’s theorem behaves under product, parallelization, and jumps. From these results we can derive a number of important properties of Ramsey’s theorem. For one, the parallelization of Ramsey’s theorem for cardinalityn≥ 1 and an arbitrary finite number of colorsk≥ 2 is equivalent to then-th jump of weak Kőnig’s lemma. In particular, Ramsey’s theorem for cardinalityn≥ 1 is${\bf{\Sigma }}_{n + 2}^0$-measurable in (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations