EUVIMEDEUVIMED entdecken
Crossref

On the transversals of a ceer

Irakli Chitaia, Valentino Delle Rose, Andrea Sorbi

Computability · 2025

DOI: 10.1177/22113568241296546 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computability, 2025. Verfasst von Irakli Chitaia und 2 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Gefördert von: SRNSFG, ANID Fondecyt Postdoctorado, MIUR.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study immunity properties of the transversals of computably enumerable equivalence relations (or, briefly, ceers ), where a transversal is a set which picks at most one element from every equivalence class of the given equivalence relation. Among transversals, a particular role is played by the principal transversal , whose members are the least elements of the various equivalence classes. While hyperimmunity of the principal transversal implies hyperimmunity of every infinite transversal, we show that this fails both for immunity and hyperhyperimmunity. In both cases, counterexamples are taken from the class of interval ceers , that is, ceers whose equivalence classes are either singletons or intervals of maximal length consisting of consecutive elements of some given c.e. set. We also look into the class of hyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperimmune, analyzing how this property relates to other computability theoretic properties of the infinite transversals. We make some preliminary observations on the hyperhyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperhyperimmune.

Förderung

  • SRNSFG
  • ANID Fondecyt Postdoctorado
  • MIUR

Zitieren

APA

Chitaia, I., Rose, V. D., & Sorbi, A. (2025). On the transversals of a ceer. Computability. https://doi.org/10.1177/22113568241296546

Vancouver

Chitaia I, Rose VD, Sorbi A. On the transversals of a ceer. Computability. 2025. doi:10.1177/22113568241296546

BibTeX
@article{Chitaia2025,
  author = {Chitaia, Irakli and Rose, Valentino Delle and Sorbi, Andrea},
  title = {On the transversals of a ceer},
  journal = {Computability},
  year = {2025},
  doi = {10.1177/22113568241296546}
}
Kostenlos starten →