Affiliations: [a] School of Mathematics and Statistics, Victoria University of Wellington, New Zealand | [b] Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago, IL, USA | [c] Department of Mathematics, University of Wisconsin Madison, WI, USA | [d] Department of Mathematics, University of Wisconsin Madison, WI, USA
Abstract: Slaman and Wehner independently built a family of sets with the property that every non-computable degree can compute an enumeration of the family, but there is no computable enumeration of the family. We call such a family a Slaman–Wehner family. The original Slaman–Wehner argument relies on all sets in the family constructed being finite, and in particular, it diagonalizes against computably enumerated families using only finite differences. In this paper we ask whether this is a necessary feature, that is, whether there is a Slaman–Wehner family closed under finite differences. This question remains open but we obtain a number of interesting partial results which can be interpreted as saying that the question is quite hard. First of all, no Slaman–Wehner family closed under finite differences can contain a finite set, and the enumeration of the family from a non-computable degree cannot be uniform (whereas, in the Slaman–Wehner construction, it is uniform). On the other hand, we build the following examples of families closed under finite differences which show the impossibility of several natural attempts to show that no Slaman–Wehner family exists: (1) a family that can be enumerated by every non-low degree, but not by any low degree; (2) a family that can be enumerated by any set in a given uniform list of c.e. sets, but which cannot be enumerated computably; and (3) a family that can be enumerated by a given Δ20 set, but which cannot be computably enumerated.
Keywords: Slaman–Wehner family, enumerations
DOI: 10.3233/COM-210349
Journal: Computability, vol. 13, no. 1, pp. 89-104, 2024
