2 citations · 2 across the 2 of their papers we have counts for
13 papers · 1 filter
Computing sets from all infinite subsets
Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey +1
A set is introreducible if it can be computed by every infinite subset of itself. Such a set can be thought of as coding information very robustly. We investigate introreducible se…
Milliken's tree theorem and its applications: a computability-theoretic perspective
Paul-Elliot Anglès d'Auriac, Peter A. Cholak, Damir D. Dzhafarov +2
Milliken's tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey's theorem and its many variants and co…
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…