On the first-order parts of problems in the Weihrauch degrees

Issue title: CiE 2022

Guest editors: Ulrich Berger, Johanna Franklin and Elvira Mayordomo

Article type: Research Article

Authors: Dzhafarov, Damir D.^{a; *} | Solomon, Reed^b | Yokoyama, Keita^c

Affiliations: [a] Department of Mathematics, University of Connecticut, Storrs, Connecticut, USA | [b] Department of Mathematics, University of Connecticut, Storrs, Connecticut, USA | [c] Mathematical Institute, Tohoku University, Sendai, Japan

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

Abstract: We introduce the notion of the first-order part of a problem in the Weihrauch degrees. Informally, the first-order part of a problem P is the strongest problem with codomaixn ω that is Weihrauch reducible to P. We show that the first-order part is always well-defined, examine some of the basic properties of this notion, and characterize the first-order parts of several well-known problems from the literature.

DOI: 10.3233/COM-230446

Journal: Computability, vol. 13, no. 3-4, pp. 363-375, 2024