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

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. Pre-press, no. Pre-press, pp. 1-13, 2024