David R. Bélanger

most citedWhere Pigeonhole Principles meet König Lemmas

1 citations · 1 across the 1 of their papers we have counts for

collaborators

3 papers

math.LO2022

Conservation theorems for the Cohesiveness Principle

David R. Belanger

We prove that the Cohesiveness Principle (COH) is $Π_{1}^{1}$ conservative over $R C A_{0} + I Σ_{n}^{0}$ and over $R C A_{0} + B Σ_{n}^{0}$ for all $n \geq 2$ by recursion-theoretic means. We first cha…

cs.LO2020

Learnability and Positive Equivalence Relations

David Belanger, Ziyuan Gao, Sanjay Jain +2

Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence…

math.LO2019★ 1 cited

Where Pigeonhole Principles meet König Lemmas

David Belanger, Chitat Chong, Wei Wang +2

We study the pigeonhole principle for $Σ_{2}$ -definable injections with domain twice as large as the codomain, and the weak König lemma for $Δ_{2}^{0}$ -definable trees in which every lev…