TY - JOUR
T1 - Borel combinatorics fail in HYP
AU - Towsner, Henry
AU - Weisshaar, Rose
AU - Westrick, Linda
N1 - Publisher Copyright:
© 2023 World Scientific Publishing Company.
PY - 2023/8/1
Y1 - 2023/8/1
N2 - We characterize the completely determined Borel subsets of HYP as exactly the δ1(Lω1ck) 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.
AB - We characterize the completely determined Borel subsets of HYP as exactly the δ1(Lω1ck) 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.
UR - http://www.scopus.com/inward/record.url?scp=85144524131&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85144524131&partnerID=8YFLogxK
U2 - 10.1142/S0219061322500234
DO - 10.1142/S0219061322500234
M3 - Article
AN - SCOPUS:85144524131
SN - 0219-0613
VL - 23
JO - Journal of Mathematical Logic
JF - Journal of Mathematical Logic
IS - 2
M1 - 2250023
ER -