A Characterization of the Strongly η-Representable Many-One Degrees

Abstract: η-representations are a way of coding sets in computable linear orders that were first introduced by Fellner in his thesis. Limitwise monotonic functions have been used to characterize the sets with η-representations and give characterizations for several variations of η-representations. The one exception is the class of sets with strong η-representations, the only class where the order type of the representation is unique. We introduce the notion of a connected approximation of a set, a variation on Σ02 approximations. We use connected approximations to give a characterization of the many-one degrees of sets with strong η-representations as well as new characterizations of the variations of η-representations with known characterizations.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.