Algebraic properties of the first-order part of a problem

Abstract

In this paper we study the notion of first-order part of a computational problem, first introduced by Dzhafarov, Solomon, and Yokoyama, which captures the "strongest computational problem with codomain $\mathbb{N}$ that is Weihrauch reducible to $f$". This operator is very useful to prove separation results, especially at the higher levels of the Weihrauch lattice. We explore the first-order part in relation with several other operators already known in the literature. We also introduce a new operator, called unbounded finite parallelization, which plays an important role in characterizing the first-order part of parallelizable problems. We show how the obtained results can be used to explicitly characterize the first-order part of several known problems.

arXiv comment41 pages. Updated after reviewer comments

References in corpus (11)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Effective Choice and Boundedness Principles in Computable Analysis
• Weihrauch Degrees, Omniscience Principles and Weak Computability
• Probabilistic Computability and Choice
• On the Uniform Computational Content of Ramsey's Theorem
• Completion of Choice
• On the Uniform Computational Content of Computability Theory
• Finding descending sequences through ill-founded linear orders
• The open and clopen Ramsey theorems in the Weihrauch lattice
• Searching for an analogue of ATR in the Weihrauch lattice

Cited by in corpus (2)

• The tree pigeonhole principle in the Weihrauch degrees
• The Weihrauch lattice at the level of ${\mathbf{\Pi }}_1^1{-\mathsf{CA}}_0$: the Cantor-Bendixson theorem