Abstract: The Weihrauch degrees and strong Weihrauch degrees are partially ordered structures representing degrees of unsolvability of various mathematical problems. Their study has been widely applied in computable analysis, complexity theory, and more recently, also in computable combinatorics. We answer an open question about the algebraic structure of the strong Weihrauch degrees, by exhibiting a join operation that turns these degrees into a lattice. Previously, the strong Weihrauch degrees were only known to form a lower semi-lattice. We then show that unlike the Weihrauch degrees, which are known to form a distributive lattice, the lattice of strong Weihrauch degrees is not distributive. Therefore, the two structures are not isomorphic.
Recommendations
- The degree structure of Weihrauch-reducibility
- On the algebraic structure of Weihrauch degrees
- Weihrauch degrees, omniscience principles and weak computability
- Weihrauch degrees, omniscience principles and weak computability
- Joins and meets in the partial orders of the computably enumerable ibT- and cl-degrees
Cited in
(8)- Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
- Continuous and monotone machines
- Completion of choice
- Weihrauch goes Brouwerian
- scientific article; zbMATH DE number 7471680 (Why is no real title available?)
- The degree structure of Weihrauch-reducibility
- Weihrauch Complexity in Computable Analysis
- On the algebraic structure of Weihrauch degrees
This page was built for publication: Joins in the strong Weihrauch degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2331769)
