Joins and meets in the structure of ceers

Issue title: Oberwolfach Workshop on Computability Theory 2018

Guest editors: Vasco Brattka, Rod Downey, Julia F. Knight and Steffen Lempp

Article type: Research Article

Authors: Andrews, Uri^{a; *} | Sorbi, Andea^b

Affiliations: [a] Department of Mathematics,University of Wisconsin, WI, USA. [email protected] | [b] Department of Information Engineering and Mathematics,University of Siena, 53100 Siena, Italy. [email protected]

Correspondence: [*] Corresponding author. [email protected].

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⊕Y, but also examples with a join which is strictly less than X⊕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.

Keywords: Computably enumerable equivalence relation, computable reducibility on equivalence relations, dark ceers, light ceers, self-fullness

DOI: 10.3233/COM-180098

Journal: Computability, vol. 8, no. 3-4, pp. 193-241, 2019