5 found
Order:
  1.  11
    Ramsey-Type Graph Coloring and Diagonal Non-Computability.Ludovic Patey - 2015 - Archive for Mathematical Logic 54 (7-8):899-914.
    A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a not (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  9
    Degrees Bounding Principles and Universal Instances in Reverse Mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  8
    $\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 (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  7
    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  
  5.  3
    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 (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark