1 citations · 1 across the 1 of their papers we have counts for
6 papers · 1 filter
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…
Bad oracles in higher computability and randomness
Laurent Bienvenu, Noam Greenberg, Benoit Monin
Many constructions in computability theory rely on "time tricks". In the higher setting, relativising to some oracles shows the necessity of these. We construct an oracle~ and a…
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…
Pigeons do not jump high
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, we develop a new noti…
Continuous higher randomness
Laurent Bienvenu, Noam Greenberg, Benoit Monin
We investigate the role of continuous reductions and continuous relativisation in the context of higher randomness. We define a higher analogue of Turing reducibility and show that…