10 citations · 68 across the 40 of their papers we have counts for
6 papers · 1 filter
SRT22 does not imply RT22 in omega-models
Benoit Monin, Ludovic Patey
We complete a 40-year old program on the computability-theoretic analysis of Ramsey's theorem, starting with Jockusch in 1972, and improving a result of Chong, Slaman and Yang in 2…
The weakness of the pigeonhole principle under hyperarithmetical reductions
Benoit Monin, Ludovic Patey
The infinite pigeonhole principle for 2-partitions () asserts the existence, for every set , of an infinite subset of or of its complement. In this paper, w…
COH, SRT22, and multiple functionals
Damir Dzhafarov, Ludovic Patey
We prove the following result: there is a family of subsets of such that for every stable coloring hyperarithmetical in $…
Relationships between computability-theoretic properties of problems
Rod Downey, Noam Greenberg, Matthew Harrison-Trainor +2
A problem is a multivalued function from a set of \emph{instances} to a set of \emph{solutions}. We consider only instances and solutions coded by sets of integers. A problem admit…
Ramsey-like theorems and moduli of computation
Ludovic Patey
Ramsey's theorem asserts that every -coloring of admits an infinite monochromatic set. Whenever , there exists a computable -coloring of whose solut…
Some results concerning the vs. problem
Peter A. Cholak, Damir D. Dzhafarov, Denis R. Hirschfeldt +1
The vs.\ problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the pr…