2 citations · 2 across the 1 of their papers we have counts for
8 papers
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…
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…
Thin set theorems and cone avoidance
Peter Cholak, Ludovic Patey
The thin set theorem asserts the existence, for every -coloring of the subsets of natural numbers of size , of an infinite set of natural numbe…