Joins in the strong Weihrauch degrees

DOI10.4310/MRL.2019.V26.N3.A5zbMATH Open1486.03072arXiv1704.01494WikidataQ126985695 ScholiaQ126985695MaRDI QIDQ2331769FDOQ2331769

Authors: Damir D. Dzhafarov 

Publication date: 30 October 2019

Published in: Mathematical Research Letters (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1704.01494

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

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Other degrees and reducibilities in computability and recursion theory (03D30)

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
• Title not available (Why is that?)
• 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)