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/
Go to the corresponding LIPIcs Volume Portal

Monin, Benoit

Higher randomness and forcing with closed sets

pdf-format:
46.pdf (0.6 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI