DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2017.34

Another Characterization of the Higher K-Trivials

Authors: Paul-Elliot Anglès d'Auriac and Benoit Monin

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract

In algorithmic randomness, the class of K-trivial sets has proved itself to be remarkable, due to its numerous different characterizations. We pursue in this paper some work already initiated on K-trivials in the context of higher randomness. In particular we give here another characterization of the non hyperarithmetic higher K-trivial sets.

Cite as

Paul-Elliot Anglès d'Auriac and Benoit Monin. Another Characterization of the Higher K-Trivials. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{anglesdauriac_et_al:LIPIcs.MFCS.2017.34,
  author =	{Angl\`{e}s d'Auriac, Paul-Elliot and Monin, Benoit},
  title =	{{Another Characterization of the Higher K-Trivials}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.34},
  URN =		{urn:nbn:de:0030-drops-80837},
  doi =		{10.4230/LIPIcs.MFCS.2017.34},
  annote =	{Keywords: Algorithmic randomness, higher computability, K-triviality, effective descriptive set theory, Kolmogorov complexity}
}

Document

DOI: 10.4230/LIPIcs.STACS.2014.566

Higher randomness and forcing with closed sets

Authors: Benoit Monin

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

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.

Cite as

Benoit Monin. Higher randomness and forcing with closed sets. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 566-577, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{monin:LIPIcs.STACS.2014.566,
  author =	{Monin, Benoit},
  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 =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.566},
  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}
}

Search Results

Documents authored by Monin, Benoit

Another Characterization of the Higher K-Trivials

Abstract

Cite as

Higher randomness and forcing with closed sets

Abstract

Cite as

Thanks for your feedback!

Could not send message