Mathematical Research Letters

Volume 26 (2019)

Number 3

Joins in the strong Weihrauch degrees

Pages: 749 – 767

DOI: https://dx.doi.org/10.4310/MRL.2019.v26.n3.a5

Author

Damir D. Dzhafarov (Department of Mathematics, University of Connecticut, Storrs, Ct., U.S.A.)

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.

Received 5 April 2017

Accepted 8 October 2018

Published 25 October 2019