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$.
2020
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].
File in questo prodotto:
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.

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