The degree structure of Weihrauch-reducibility

Abstract

We answer a question by Vasco Brattka and Guido Gherardi by proving that the Weihrauch-lattice is not a Brouwer algebra. The computable Weihrauch-lattice is also not a Heyting algebra, but the continuous Weihrauch-lattice is. We further investigate the existence of infinite infima and suprema, as well as embeddings of the Medvedev-degrees into the Weihrauch-degrees.

References in corpus (3)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Weihrauch goes Brouwerian

Cited by in corpus (19)

• Probabilistic Computability and Choice
• On the algebraic structure of Weihrauch degrees
• Non-deterministic computation and the Jayne-Rogers Theorem
• Finite choice, convex choice and finding roots
• On the Uniform Computational Content of Computability Theory
• Weihrauch goes Brouwerian
• Weihrauch-completeness for layerwise computability
• Many-one reductions and the category of multivalued functions
• The descriptive theory of represented spaces
• Game characterizations and lower cones in the Weihrauch degrees
• How constructive is constructing measures?
• Searching for an analogue of ATR in the Weihrauch lattice
• A topological view on algebraic computation models
• The open and clopen Ramsey theorems in the Weihrauch lattice
• Minimal covers in the Weihrauch degrees
• Computability on the space of countable ordinals
• Efficient Decomposition of Bimatrix Games (Extended Abstract)
• Ramsey's theorem and products in the Weihrauch degrees
• Function spaces for second-order polynomial time