We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Borel combinatorics fail in HYP.
- Authors
Towsner, Henry; Weisshaar, Rose; Westrick, Linda
- Abstract
We characterize the completely determined Borel subsets of HYP as exactly the Δ 1 (L ω 1 c k ) subsets of HYP. As a result, HYP believes there is a Borel well-ordering of the reals, that the Borel Dual Ramsey Theorem fails, and that every Borel d-regular bipartite graph has a Borel perfect matching, among other examples. Therefore, the Borel Dual Ramsey Theorem and several theorems of descriptive combinatorics are not theories of hyperarithmetic analysis. In the case of the Borel Dual Ramsey Theorem, this answers a question of Astor, Dzhafarov, Montalbán, Solomon and the third author.
- Subjects
COMBINATORICS; BOREL subsets; BIPARTITE graphs; BOREL sets; REGULAR graphs; REVERSE mathematics
- Publication
Journal of Mathematical Logic, 2023, Vol 23, Issue 2, p1
- ISSN
0219-0613
- Publication type
Article
- DOI
10.1142/S0219061322500234