We study computably enumerable equivalence relations (abbreviated as ceers) under computable reducibility, and we investigate the resulting degree structure $Ceers$, which is a poset with a smallest and a greatest element. We point out a partition of the ceers into three classes: the finite ceers, the light ceers, and the dark ceers. These classes yield a partition of the degree structure as well, and in the language of posets the corresponding classes of degrees are first order definable within $Ceers$. There is no least, no maximal, no greatest dark degree, but there are infinitely many minimal dark degrees. We study joins and meets in $Ceers$, addressing the cases when two incomparable degrees of ceers $X,Y$ have or do not have a join or a meet according to where $X,Y$ are located in the classes of the aforementioned partition: in particular no pair of dark ceers has a join, and no pair in which at least one ceer is dark has a meet. We also exhibit examples of ceers $X,Y$ having as a join their uniform join $X oplus Y$, but also examples with a join which is strictly less than $X oplus Y$. We study join-irreducibility and meet-irreducibility: every dark ceer is both join-, and meet-irreducible. In particular we characterize the property of being meet-irreducible for a ceer $E$, by showing that it coincides with the property of $E$ being self-full, meaning that every reducibility from $E$ to itself is in fact surjective on its equivalence classes (this property properly extends darkness). We then study the quotient structure obtained by dividing the poset $Ceers$ by the degrees of the finite ceers, and study joins and meets in this quotient structure: interestingly, contrary to what happens in the structure of ceers, here there are pairs of incomparable equivalence classes of dark ceers having a join, and every element different from the greatest one is meet-reducible. In fact in this quotient structure, every degree different from the greatest one has infinitely many strong minimal covers, whereas in $Ceers$ every degree different from the greatest one has either infinitely many strong minimal covers, or the cone strictly above it has a least element: this latter property characterizes the self-full degrees. We look at automorphisms of $Ceers$, and show that there are continuum many automorphisms fixing the dark ceers, and continuum many automorphisms fixing the light ceers. Finally, we compute the complexity of the index sets of the classes of ceers studied in the paper.

Andrews, U., Sorbi, A. (2019). Joins and meets in the structure of ceers. COMPUTABILITY, 8(3-4), 193-241 [10.3233/COM-180098].

Joins and meets in the structure of ceers

Sorbi, Andrea
2019-01-01

Abstract

We study computably enumerable equivalence relations (abbreviated as ceers) under computable reducibility, and we investigate the resulting degree structure $Ceers$, which is a poset with a smallest and a greatest element. We point out a partition of the ceers into three classes: the finite ceers, the light ceers, and the dark ceers. These classes yield a partition of the degree structure as well, and in the language of posets the corresponding classes of degrees are first order definable within $Ceers$. There is no least, no maximal, no greatest dark degree, but there are infinitely many minimal dark degrees. We study joins and meets in $Ceers$, addressing the cases when two incomparable degrees of ceers $X,Y$ have or do not have a join or a meet according to where $X,Y$ are located in the classes of the aforementioned partition: in particular no pair of dark ceers has a join, and no pair in which at least one ceer is dark has a meet. We also exhibit examples of ceers $X,Y$ having as a join their uniform join $X oplus Y$, but also examples with a join which is strictly less than $X oplus Y$. We study join-irreducibility and meet-irreducibility: every dark ceer is both join-, and meet-irreducible. In particular we characterize the property of being meet-irreducible for a ceer $E$, by showing that it coincides with the property of $E$ being self-full, meaning that every reducibility from $E$ to itself is in fact surjective on its equivalence classes (this property properly extends darkness). We then study the quotient structure obtained by dividing the poset $Ceers$ by the degrees of the finite ceers, and study joins and meets in this quotient structure: interestingly, contrary to what happens in the structure of ceers, here there are pairs of incomparable equivalence classes of dark ceers having a join, and every element different from the greatest one is meet-reducible. In fact in this quotient structure, every degree different from the greatest one has infinitely many strong minimal covers, whereas in $Ceers$ every degree different from the greatest one has either infinitely many strong minimal covers, or the cone strictly above it has a least element: this latter property characterizes the self-full degrees. We look at automorphisms of $Ceers$, and show that there are continuum many automorphisms fixing the dark ceers, and continuum many automorphisms fixing the light ceers. Finally, we compute the complexity of the index sets of the classes of ceers studied in the paper.
2019
Andrews, U., Sorbi, A. (2019). Joins and meets in the structure of ceers. COMPUTABILITY, 8(3-4), 193-241 [10.3233/COM-180098].
File in questo prodotto:
File Dimensione Formato  
joinsandmeets.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 507.31 kB
Formato Adobe PDF
507.31 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/1066541