Logic Seminar

Of the principles just slightly weaker than ATR, the most well-known are the theories of hyperarithmetic analysis (THA). By definition, such principles hold in HYP. Motivated by the question of whether the Borel dual Ramsey theorem is a THA, we consider several theorems involving Borel sets and ask whether they hold in HYP. To make sense of Borel sets without ATR, we formalize the theorems using completely determined Borel sets. We characterize the completely determined Borel subsets of HYP as precisely the sets of reals which are Δ11 in Lωck1. Using this, we show that in HYP, Borel sets behave quite differently than in reality. For example, in HYP, the Borel dual Ramsey theorem fails, every n-regular Borel acyclic graph has a Borel 2-coloring, and the prisoners have a Borel winning strategy in the infinite prisoner hat game. Thus the negations of these statements are not THA. Joint work with Henry Towsner and Rose Weisshaar.