A computably enumerable equivalence relation (ceer) $X$ is called self-full if whenever $f$ is a reduction of $X$ to $X$ then the range of $f$ intersects all $X$-equivalence classes. It is known that the infinite self-full ceers properly contain the dark ceers, i.e. the infinite ceers which do not admit an infinite computably enumerable transversal. Unlike the collection of dark ceers, which are closed under the operation of uniform join, we answer a question raised by Andrews and Sorbi by showing that there are self-full ceers $X$ and $Y$ so that their uniform join $Xoplus Y$ is non-self-full. We then define and examine the hereditarily self-full ceers, which are the self-full ceers $X$ so that for any self-full $Y$, $Xoplus Y$ is also self-full: we show that they are closed under uniform join, and that every non-universal degree in $Ceers_{/I}$ have infinitely many incomparable hereditarily self-full strong minimal covers. In particular, every non-universal ceer is bounded by a hereditarily self-full ceer. Thus the hereditarily self-full ceers form a properly intermediate class in between the dark ceers and the infinite self-full ceers which is closed under $oplus$.
Andrews, U., Schweber, N., Sorbi, A. (2020). Self-full ceers and the uniform join operator. JOURNAL OF LOGIC AND COMPUTATION, 30(3), 765-783 [10.1093/logcom/exaa023].
Self-full ceers and the uniform join operator
Sorbi Andrea
2020-01-01
Abstract
A computably enumerable equivalence relation (ceer) $X$ is called self-full if whenever $f$ is a reduction of $X$ to $X$ then the range of $f$ intersects all $X$-equivalence classes. It is known that the infinite self-full ceers properly contain the dark ceers, i.e. the infinite ceers which do not admit an infinite computably enumerable transversal. Unlike the collection of dark ceers, which are closed under the operation of uniform join, we answer a question raised by Andrews and Sorbi by showing that there are self-full ceers $X$ and $Y$ so that their uniform join $Xoplus Y$ is non-self-full. We then define and examine the hereditarily self-full ceers, which are the self-full ceers $X$ so that for any self-full $Y$, $Xoplus Y$ is also self-full: we show that they are closed under uniform join, and that every non-universal degree in $Ceers_{/I}$ have infinitely many incomparable hereditarily self-full strong minimal covers. In particular, every non-universal ceer is bounded by a hereditarily self-full ceer. Thus the hereditarily self-full ceers form a properly intermediate class in between the dark ceers and the infinite self-full ceers which is closed under $oplus$.File | Dimensione | Formato | |
---|---|---|---|
uniform-join.pdf
non disponibili
Descrizione: Articolo
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
244.2 kB
Formato
Adobe PDF
|
244.2 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/1110350