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, i.e., 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, i.e., those ceers with infinitely many classes, whose infinite transversals are all hyperimmune, analysing how this property relates to other computability theoretic properties of the infinite transversals. We make some preliminary observations on the hyperhyperdark ceers, i.e., those ceers with infinitely many classes, whose infinite transversals are all hyperhyperimmune.
Chitaia, I., Delle Rose, V., Sorbi, A. (2025). On the transversals of a ceer. COMPUTABILITY, 14(2), 111-127 [10.1177/22113568241296546].
On the transversals of a ceer
Andrea Sorbi
2025-01-01
Abstract
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, i.e., 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, i.e., those ceers with infinitely many classes, whose infinite transversals are all hyperimmune, analysing how this property relates to other computability theoretic properties of the infinite transversals. We make some preliminary observations on the hyperhyperdark ceers, i.e., those ceers with infinitely many classes, whose infinite transversals are all hyperhyperimmune.| File | Dimensione | Formato | |
|---|---|---|---|
|
CDS-transversals-of-ceers.pdf
non disponibili
Descrizione: pdf-of-article
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
304.65 kB
Formato
Adobe PDF
|
304.65 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1305494
