10 found
Order:
  1.  7
    Relationships Between Computability-Theoretic Properties of Problems.Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey & Dan Turetsky - 2022 - Journal of Symbolic Logic 87 (1):47-71.
    A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  4
    Ramsey-Like Theorems and Moduli of Computation.Ludovic Patey - 2022 - Journal of Symbolic Logic 87 (1):72-108.
    Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$, there exists a computable k-coloring of $[\omega ]^n$ whose solutions compute the halting set. On the other hand, for every computable k-coloring of $[\omega ]^2$ and every noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _T H$. The latter property is known as cone avoidance.In this article, we design a natural class of Ramsey-like theorems encompassing (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  11
    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   3 citations  
  4.  17
    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  
  5.  3
    Partition Genericity and Pigeonhole Basis Theorems.Benoit Monin & Ludovic Patey - forthcoming - Journal of Symbolic Logic:1-36.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  7
    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...
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  7.  13
    $\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  
  8.  2
    The Reverse Mathematics of the Thin Set and Erdős–Moser Theorems.Lu Liu & Ludovic Patey - 2022 - Journal of Symbolic Logic 87 (1):313-346.
    The thin set theorem for n-tuples and k colors states that every k-coloring of $[\mathbb {N}]^n$ admits an infinite set of integers H such that $[H]^n$ avoids at least one color. In this paper, we study the combinatorial weakness of the thin set theorem in reverse mathematics by proving neither $\operatorname {\mathrm {\sf {TS}}}^n_k$, nor the free set theorem imply the Erdős–Moser theorem whenever k is sufficiently large. Given a problem $\mathsf {P}$, a computable instance of $\mathsf {P}$ is universal (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  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  
  10.  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