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.
2025
Chitaia, I., Delle Rose, V., Sorbi, A. (2025). On the transversals of a ceer. COMPUTABILITY, 14(2), 111-127 [10.1177/22113568241296546].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1305494