License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.566
URN: urn:nbn:de:0030-drops-44883
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4488/
Monin, Benoit
Higher randomness and forcing with closed sets
Abstract
[Kechris, Trans. Amer. Math. Soc. 1975] showed 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. London Math. Soc. 2007]. Due to its universal nature, it was conjectured by many that this nullset has a high Borel rank (the question is explicitely mentioned by Chong and Yu, and in [Yu, Fund. Math. 2011]). In this paper, we refute this conjecture and show that this nullset is merely Sigma_3^0. Together with a result of Liang Yu, our result also implies that the exact Borel complexity of this set is Sigma_3^0.
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.
BibTeX - Entry
@InProceedings{monin:LIPIcs:2014:4488,
author = {Benoit Monin},
title = {{Higher randomness and forcing with closed sets}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {566--577},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4488},
URN = {urn:nbn:de:0030-drops-44883},
doi = {10.4230/LIPIcs.STACS.2014.566},
annote = {Keywords: Effective descriptive set theory, Higher computability, Effective randomness, Genericity}
}
Keywords: |
|
Effective descriptive set theory, Higher computability, Effective randomness, Genericity |
Collection: |
|
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) |
Issue Date: |
|
2014 |
Date of publication: |
|
05.03.2014 |