On the first-order parts of problems in the Weihrauch degrees
Preprint
Abstract
We introduce the notion of the \emph{first-order part} of a problem in the Weihrauch degrees. Informally, the first-order part of a problem $\mathsf{P}$ is the strongest problem with codomaixn $ω$ that is Weihrauch reducible to $\mathsf{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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Algebraic properties of the first-order part of a problemAnnals of Pure and Applied Logic, 2023
- Weihrauch Complexity in Computable Analysis2021
- THE STRENGTH OF RAMSEY’S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORSThe Journal of Symbolic Logic, 2018
- On the algebraic structure of Weihrauch degreesLogical Methods in Computer Science, 2018
- ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREMThe Journal of Symbolic Logic, 2017
- On the Uniform Computational Content of Computability TheoryTheory of Computing Systems, 2017
- On notions of computability-theoretic reduction between Π21 principlesJournal of Mathematical Logic, 2016
- The atomic model theorem and type omittingTransactions of the American Mathematical Society, 2009
- On the strength of Ramsey's theorem for pairsThe Journal of Symbolic Logic, 2001
- Ramsey's theorem and recursion theoryThe Journal of Symbolic Logic, 1972