Advertisement
Published in:
11-06-2016
Higher Randomness and Forcing with Closed Sets
Published in: Theory of Computing Systems | Issue 3/2017
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Kechris showed in Kechris (Trans. Am. Math. Soc. 202, 259–297, 1975) that there exists a largest \({\Pi ^{1}_{1}}\) set of measure 0. An explicit construction of this largest \({\Pi ^{1}_{1}}\) nullset has later been given in Hjorth and Nies (J. Lond. Math. Soc. 75(2), 495–508, 2007). Due to its universal nature, it was conjectured by many that this nullset has a high Borel rank (the question is explicitely mentioned in Chong and Yu (J. Symb. Log. 80(04), 1131–1148, 2015) and Yu (Fundam. Math. 215, 219–231, 2011)). In this paper, we refute this conjecture and show that this nullset is merely \({\Sigma }^{0}_{3}\). Together with a result of Liang Yu, our result also implies that the exact Borel complexity of this set is \({\Sigma }^{0}_{3}\). To do this proof, we develop the machinery of effective randomness and effective Solovay genericity, investigating the connections between those notions and effective domination properties.